Noisy channel model


The noisy channel model is a framework used in spell checkers,
question answering, speech recognition, and machine translation.
In this model, the goal is to find the intended word given a word where the
letters have been scrambled in some manner.

Definition

Given an alphabet, let be the set
of all finite strings over. Let the dictionary
of valid words be some subset of, i.e.,
The noisy channel is the matrix
where is the intended word and
is the scrambled word that was actually received.

Example

Consider the English alphabet
. Some subset
makes up the dictionary of valid English
words.
There are several mistakes that may occur while typing, including:
  1. Missing letters, e.g., ' instead of letter
  2. Accidental letter additions, e.g., ' instead of mistake
  3. Swapping letters, e.g., ' instead of received
  4. Replacing letters, e.g., ' instead of finite
To construct the noisy channel matrix, we must consider
the probability of each mistake, given the intended word
. These probabilities may be gathered, for
example, by considering the Levenshtein distance between
and or by comparing the draft of an essay with one that has
been manually edited for spelling.

Error-correction

The goal of the noisy channel model is to find the intended word given the
scrambled word that was received. The decision function
is a function that, given a scrambled word, returns
the intended word.
Methods of constructing a decision function include the
maximum likelihood rule, the
maximum a posteriori rule, and the
minimum distance rule.
In some cases, it may be better to accept the scrambled word as the intended
word rather than attempt to find an intended word in the dictionary. For
example, the word schönfinkeling may not be in the dictionary, but might
in fact be the intended word.