Discriminative Reranking for Spelling Correction

Discriminative Reranking for Spelling Correction* Yang Zhang1, Pilian He1, Wei Xiang2, Mu Li3 1 School of Computer Science and Technology Tianjin University, China {yangzhang, plhe}@tju.edu.cn 2 Department of Computer Science Hong Kong University of Science and Technology, China wxiang@cse.ust.hk 3 Natural Language Computing Group Microsoft Research Asia muli@microsoft.com Abstract. This paper proposes a novel approach to spelling correction. It reranks the output of an existing spelling corrector, Aspell. A discriminative model (Ranking SVM) is employed to improve upon the initial ranking, using additional features as evidence. These features are derived from state- of-the-art techniques in spelling correction, including edit distance, letter-based n-gram, phonetic similarity and noisy channel model. This paper also presents a new method to automatically extract training samples from the query log chain. The system outperforms the baseline Aspell greatly, as well as previous models and several off-the-shelf spelling correction systems (e.g. Microsoft Word 2003). The results on query chain pairs are comparable to that based on manually-annotated pairs, with 32.2%/32.6% reduction in error rate, respectively. 1. Introduction Spelling correction is used to suggest one or several hypothetical corrections for the assumed error once a spell checker detects some misspelling, which is typically identified when it cannot been found in a pre-compiled lexicon. In this paper, we focus on the problem of interactively correcting non-word errors (e.g. teh for the). We do not deal with real word errors (such as from is written when form is intended). We propose an approach that can be applied to text processing applications, such as the spelling corrector used in Microsoft Word or Aspell [2]. In these applications several suggestions (5 or 10 in most cases) are provided in an interactive manner, letting the user choose the desired one. In most cases the suggestion ranked first is preferred. For this reason top 1 suggestion is our most concern. We also care about the top 5/10 accuracies since they are presented to the user, too. Aspell [2] is a spelling program widely used on different platforms. As shown in [1], the top 5 accuracy of Aspell is more than 85%. However, it suffers from its poor performance on top 1 accuracy, which is less than 60%. Our motivation is to improve the initial ranking of Aspell’s output to gain a higher performance. The main contributions are as follows: 1. We adapt a discriminative model (Ranking SVM) to rerank the output of Aspell’s N-best candidates, adding some global features as evidence. The model is general-purposed so that we can integrate state-of-the-art techniques in spelling correction into one model, including edit distance, n-gram, phonetic similarity and noisy channel model. Encouraging results are gained on this task. 2. A novel approach is proposed to actively solicit training pairs from query log chain. The quality of this approach is verified in the evaluation that follows. The rest of the paper is organized as follows: in Section 2, we conduct a literature research into spelling correction. The reranking problem is formulated in Section 3. Section 4 shows the …

Content truncated to 500 words