Noisy-Channel Spelling Correction

Every time you type "teh" and your phone silently fixes it to "the", a small probabilistic argument has just run in the background. The fix feels magical, but the logic behind it has a name: the noisy-channel model.

The idea comes from Claude Shannon's 1948 information theory. Imagine the word you intended to type passes through a noisy channel — your fingers — and arrives on screen as a garbled version. The corrector's job is to invert the channel: given the garbled output, find the intended word that most plausibly produced it.

Bayes' theorem turns that intuition into a formula. The best correction $\hat{w}$ of a typed string $t$ is:

$$\hat{w} = \underset{w \in \text{vocabulary}}{\arg\max}\; P(w \mid t) = \underset{w}{\arg\max}\; P(t \mid w) \cdot P(w)$$

Two factors compete: $P(t \mid w)$, the error model (how likely you are to type $t$ when you meant $w$), and $P(w)$, the language model (how common $w$ is in ordinary text). The winner is whichever candidate word maximizes their product.

This solved version of autocorrect — combining an error model with a language model — was popularized in NLP by researchers at Bell Labs and IBM in the 1990s, and brought to wide attention by Peter Norvig's celebrated 2007 essay "How to Write a Spelling Corrector."

Type a word — misspelled or not — and the corrector will generate every candidate within edit distance 1 (one insertion, deletion, substitution, or transposition), score each by $P(t \mid w) \cdot P(w)$, and rank them best-first.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="input-row">
  <input id="typo" type="text" placeholder="{{placeholder}}" maxlength="20" autocomplete="off" spellcheck="false" />
  <button id="correct-btn" type="button">{{btn_correct}}</button>
</div>
<div id="results" class="results" role="region" aria-live="polite"></div>
<div class="btns-row">
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_style}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.input-row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
input { flex: 1 1 160px; font: 1rem system-ui, sans-serif; padding: .42rem .7rem;
        border: 1px solid #adb1b8; border-radius: 8px; outline: none; }
input:focus { border-color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.results { min-height: 2rem; margin-bottom: .5rem; }
.results table { width: 100%; border-collapse: collapse; font-size: .88rem; }
.results th { text-align: left; padding: .3rem .5rem; color: #555; font-weight: 600;
              border-bottom: 2px solid #cdd9e3; }
.results td { padding: .28rem .5rem; border-bottom: 1px solid #e8eef3; }
.results tr.top-row td { font-weight: 700; color: #0a7d33; }
.results tr.exact-row td { font-weight: 700; color: #1d3557; }
.results .bar-cell { min-width: 80px; }
.bar-bg { background: #e8eef3; border-radius: 4px; height: 10px; }
.bar-fill { background: #1d3557; border-radius: 4px; height: 10px; }
.msg { font-size: .95rem; font-weight: 600; padding: .4rem 0; }
.msg.ok { color: #0a7d33; }
.msg.bad { color: #c92f3c; }
.btns-row { display: flex; gap: .5rem; }

// Code not found

Notice how the top candidate is almost always what you intended. The error model penalizes candidates that require an unlikely substitution; the language model boosts common words. A rare but correctly spelled word can still lose to a very common near-neighbor — that is the tension at the heart of autocorrect.

The formula $\hat{w} = \arg\max_w P(t \mid w) \cdot P(w)$ looks clean, but estimating both factors well is where the work lives.

Generating candidates. For a word of length $n$ over an alphabet of size $\sigma$, edit-distance-1 gives $O(n \cdot \sigma)$ candidates — a few thousand for English. Distance 2 squares that; real systems prune aggressively.

The error model $P(t \mid w)$. The simplest version treats all single-character errors as equally likely — the "uniform channel." Better systems use a confusion matrix trained on observed typos: the probability that someone types "ie" when they meant "ei" differs from the probability of a random substitution. Keyboard-distance models go further, weighting nearby keys higher.

The language model $P(w)$. A unigram model counts how often each word appears in a large corpus — the approach in the interactive demo above. Real systems use n-gram models (conditioning on the surrounding words) or neural language models that represent meaning as vectors. Context changes everything: "their" vs "there" vs "they're" are all common words, and only the sentence decides which is right.

Why it connects to information theory. Shannon's channel capacity theorem tells us there exist codes that can recover the original message with arbitrarily low error — but spelling correction cannot use those codes, because the "channel" (human fingers) is fixed and noisy in its own idiosyncratic way. What Bayes gives us is the optimal decision rule given the channel we have.

Modern neural spell checkers (integrated into large language models) subsume the noisy-channel decomposition into a single end-to-end model, but the Bayesian intuition remains the clearest lens for understanding why any correction is preferred over another.

The noisy-channel view of text is one of the most productive framings in all of NLP:

• Keyboard autocorrect: every smartphone keyboard runs a variant of this model, typically augmented with a neural language model trained on billions of keystrokes.
• Search query correction: when Google suggests "did you mean …?", it is scoring candidate queries by their edit distance to what you typed, weighted by query frequency — the same formula.
• OCR post-processing: characters scanned from images arrive with substitution errors that have their own confusion matrix (e.g., "0" vs "O", "l" vs "1"). A channel model cleans the output.
• Speech recognition: the acoustic model plays the role of $P(t \mid w)$ and the language model plays $P(w)$; decoding is exactly the noisy-channel arg-max.
• Machine translation: the original IBM models (Brown et al., 1993) framed translation as a noisy channel from target language to source language, then inverted it with Bayes — the founding insight of statistical MT.

Understand the noisy-channel model and you hold the conceptual key to a wide swath of language technology. It also connects naturally to Bayesian inference, where the same prior-times-likelihood structure appears across all of statistics.

Spelling correction looks like a simple string-matching task, but underneath it is Bayesian inference applied to a communication channel. The word you intended is the hidden signal; your keystrokes are the noisy output; and Bayes' theorem is the optimal decoder.

The formula $\hat{w} = \arg\max_w P(t \mid w) \cdot P(w)$ packages two kinds of knowledge — how fingers err and how language flows — into a single ranking. Get both factors right and you get autocorrect that feels like mind-reading. Get them wrong and you get the notorious autocorrect fails that flood the internet.

The same math that fixes "teh" → "the" also decodes speech, cleans up OCR, and originally powered machine translation. Bayes was doing NLP long before the term existed.