📄 An Improved Error Model for Noisy Channel Spelling Correction

Summary

The paper argues that noisy channel spelling correction has improved its source (language) model far more than its channel (error) model. Earlier error models, such as Mayes, Damerau et al. (1991) and Church and Gale (1991), only allow single-character insertions, deletions, substitutions and transpositions. Brill and Moore replace these with a model that learns probabilities for arbitrary substring-to-substring edits, such as "ph"→"f" or "ent"→"ant". Each edit is also conditioned on where it falls in the intended word: start, middle or end.

Edits are learned from pairs of misspellings and their corrections. The authors align each pair at the character level, then expand each mismatch with neighbouring edits to produce candidate rules with fractional counts. At correction time, a trie-based search over the dictionary finds the best candidates efficiently.

On a corpus of common English misspellings, the model removes about half of the 1-best errors made by a Church-and-Gale-style baseline. It also stays clearly ahead when both models are combined with a trigram language model. The work shows that a richer error model is a cheap and effective way to improve spelling correction.

Key points

• Data and setup:
  • 10,000 English misspellings paired with their corrections, split 80/20 into training and test sets.
  • A dictionary of about 200,000 entries that includes every test word.
  • Initial experiments use a uniform language model.
• Without positional conditioning, 1-best accuracy rises from 87.0% (window 0) and 89.5% (CG baseline) to 93.6% (windows 3–4).
• Adding position raises 1-best accuracy to 95.0% (95.1% at window 5). This is a 52% relative error reduction against CG.
  • Position adds more with larger windows: a 13% relative gain at window 0 versus 22% at window 4.
• With a left-context trigram language model, the authors rescore the 5-best candidates on Brown Corpus contexts.
  • The new error model cuts errors by 73.6% compared with CG plus the same language model.
  • Rescoring 20 CG candidates instead of 5 barely helps, raising 1-best accuracy from 90.9% to 91.0%.
• Iterative parameter reestimation, as used by Church and Gale, slightly hurt results on this cleaner data.
• Speed: correcting one out-of-dictionary string takes about 50 ms on a 500 MHz Pentium III.

Interesting ideas

• I1. Multi-character edits learned from simple alignments: The authors start from a plain single-character alignment and grow each mismatch into larger edit windows. Each candidate rule gets a fractional count, so useful patterns accumulate weight while noise fades. This trick could extract transliteration or OCR confusion rules from any set of paired strings.
• I2. Conditioning edits on position in the word: The same substitution can be common at a word ending but rare at the start, as with suffix confusions. Position features are cheap to add and could help morphologically rich languages, where errors cluster around endings. The authors themselves suggest morpheme boundaries as a further feature.
• I3. Testing whether a strong language model makes a good error model unnecessary: The authors pair the same trigram model with a weak and a strong error model, and also widen the weak model's candidate list. This shows that the gains are not redundant, and it is a clean ablation design for any two-component pipeline.
• I4. Dropping a poorly estimated factor: The authors found that a crudely modelled partition probability performed worse than omitting it entirely. This is a reminder to check bad estimates against simply leaving them out.
• I5. Trie-of-tries storage with reversed strings: Storing the dictionary and the edit rules in tries keeps the costlier generic-edit dynamic programming fast enough for interactive use. The same structure could support fuzzy lookup in gazetteers or product catalogues.