An Improved Error Model for Noisy Channel Spelling Correction

An Improved Error Model for Noisy Channel Spelling Correction Abstract The noisy channel model has been applied to a wide range of problems, including spelling correction. These models consist of two components: a source model and a channel model. Very little research has gone into improving the channel model for spelling correction. This paper describes a new channel model for spelling correction, based on generic string to string edits. Using this model gives significant performance improvements compared to previously proposed models. Introduction The noisy channel model (Shannon 1948) has been successfully applied to a wide range of problems, including spelling correction. These models consist of two components: a source model and a channel model. For many applications, people have devoted considerable energy to improving both components, with resulting improvements in overall system accuracy. However, relatively little research has gone into improving the channel model for spelling correction. This paper describes an improvement to noisy channel spelling correction via a more powerful model of spelling errors, be they typing mistakes or cognitive errors, than has previously been employed. Our model works by learning generic string to string edits, along with the probabilities of each of these edits. This more powerful model gives significant improvements in accuracy over previous approaches to noisy channel spelling correction. 1 Noisy Channel Spelling Correction This paper will address the problem of automatically training a system to correct generic single word spelling errors.1 We do not address the problem of correcting specific word set confusions such as {to,too,two} (see (Golding and Roth 1999)). We will define the spelling correction problem abstractly as follows: Given an alphabet Σ , a dictionary D consisting of strings in Σ * and a string s, where s ∉D and s∈Σ* , find the word w∈D that is most likely to have been erroneously input as s. The requirement that s ∉D can be dropped, but it only makes sense to do so in the context of a sufficiently powerful language model. In a probabilistic system, we want to find |) ( argmax w Pws . Applying Bayes’ Rule and dropping the constant denominator, we get the unnormalized posterior: () *) (| argmax w PswPw . We now have a noisy channel model for spelling correction, with two components, the source model P(w) and the channel model P(s | w). The model assumes that natural language text is generated as follows: First a person chooses a word to output, according to the probability distribution P(w). Then the person attempts to output the word w, but the noisy channel induces the person to output string s instead, according to the 1 Two very nice overviews of spelling correction can be found in (Kukich 1992) and (Jurafsky and Martin 2000). Eric Brill and Robert C. Moore Microsoft Research One Microsoft Way Redmond, Wa. 98052 {brill,bobmoore}@microsoft.com distribution P(s | w). For instance, under typical circumstances we would expect P(the | the) to be very high, P(teh | the) to be relatively high and P(hippopotamus | …

Content truncated to 500 words