Noisy-Channel Models, Edit Distance, and Advanced Language-Model Issues
On this page
Noisy-Channel Models, Edit Distance, and Advanced Language-Model Issues (Self-learning supplement)
Recall first
For a misspelled observation teh, what two probabilities should a spelling corrector combine to prefer the? How does edit distance generate candidates rather than choose among them?
First principles
The noisy-channel model assumes a clean message x passed through a channel that produces observation y. Bayes gives
argmax_x P(x|y) = argmax_x P(y|x) P(x).
P(x) is the language model: is the candidate plausible in context? P(y|x) is the channel/error model: how likely is the observed error given the candidate? The denominator P(y) is constant for ranking. This decomposition separates language knowledge from corruption likelihood.
Worked example. For teh, candidates might include the, ten, and tech. Edit distance supplies plausible nearby candidates. The channel may favor a transposition of adjacent letters, raising P(teh|the). A sentence model may favor the in the cat, while a domain model could favor tech elsewhere. The winner is the product (or sum of log scores), not simply the closest string.
Levenshtein edit distance is the minimum number of insertions, deletions, substitutions, and (in some variants) transpositions needed to transform one string into another. Dynamic programming uses D[i,j] for prefixes:
D[i,j] = min(D[i−1,j]+1, D[i,j−1]+1, D[i−1,j−1]+cost).
Initialize D[i,0]=i, D[0,j]=j. For teh → the, one adjacent transposition is needed in a Damerau variant; ordinary Levenshtein sees two substitutions. Distance is a candidate-generation/feature signal, not a probability or semantic similarity.
Advanced LM issues include long context, domain adaptation, calibration, tokenization, OOVs, code-switching, and comparing models with different units. Interpolation, backoff, subword modeling, cache/context models, and neural LMs address some limits, each adding assumptions or compute.
Exercise — reveal after answering
Why can the nearest edit-distance candidate still be wrong?
Answer: Several candidates can have equal/low distance, while context and error likelihood differ. Edit distance lacks sentence meaning and a learned channel model.
Exam lens
Memorize the Bayes factorization and DP recurrence. Say edit distance proposes/ranks candidates; the noisy channel combines it with a language model. The syllabus term “advanced issues” is broad: use sparsity, OOV, domain, long context, and evaluation as examples.
Rapid revision checklist
- Write
P(x|y) ∝ P(y|x)P(x). - Define channel vs language model.
- State Levenshtein operations and base cases.
- Distinguish distance from probability.
Key takeaways
- Noisy-channel correction is Bayesian candidate ranking.
- Edit distance is dynamic programming over prefixes.
- Better language modeling does not remove the need for a realistic error channel.