Noisy channel model

Summarize Timeline Fact Check

See Chapter B of.^[1]

Given an alphabet ${\displaystyle \Sigma }$, let ${\displaystyle \Sigma ^{*}}$ be the set of all finite strings over ${\displaystyle \Sigma }$. Let the dictionary ${\displaystyle D}$ of valid words be some subset of ${\displaystyle \Sigma ^{*}}$, i.e., ${\displaystyle D\subseteq \Sigma ^{*}}$.

The noisy channel is the matrix

${\displaystyle \Gamma _{ws}=\Pr(s|w)}$,

where ${\displaystyle w\in D}$ is the intended word and ${\displaystyle s\in \Sigma ^{*}}$ is the scrambled word that was actually received.

The goal of the noisy channel model is to find the intended word given the scrambled word that was received. The decision function ${\displaystyle \sigma$ :\Sigma ^{*}\to D} 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.

Consider the English alphabet ${\displaystyle \Sigma =\{a,b,c,...,y,z,A,B,...,Z,...\}}$. Some subset ${\displaystyle D\subseteq \Sigma ^{*}}$ makes up the dictionary of valid English words.

There are several mistakes that may occur while typing, including:

1. Missing letters, e.g., leter instead of letter
2. Accidental letter additions, e.g., misstake instead of mistake
3. Swapping letters, e.g., recieved instead of received
4. Replacing letters, e.g., fimite instead of finite

To construct the noisy channel matrix ${\displaystyle \Gamma }$, we must consider the probability of each mistake, given the intended word (${\displaystyle \Pr(s|w)}$ for all ${\displaystyle w\in D}$ and ${\displaystyle s\in \Sigma ^{*}}$). These probabilities may be gathered, for example, by considering the Damerau–Levenshtein distance between ${\displaystyle s}$ and ${\displaystyle w}$ or by comparing the draft of an essay with one that has been manually edited for spelling.

Summarize Timeline Fact Check

One naturally wonders if the problem of translation could conceivably be treated as a problem in cryptography. When I look at an article in Russian, I say: 'This is really written in English, but it has been coded in some strange symbols. I will now proceed to decode.

See chapter 1, and chapter 25 of.^[2]

Suppose we want to translate a foreign language to English, we could model ${\displaystyle P(E|F)}$ directly: the probability that we have English sentence E given foreign sentence F, then we pick the most likely one ${\displaystyle {\hat {E}}=\arg \max _{E}P(E|F)}$. However, by Bayes law, we have the equivalent equation:$${\displaystyle {\hat {E}}={\underset {E\in {\text{ English }}}{\operatorname {argmax} }}\overbrace {P(F\mid E)} ^{\text{translation model }}\overbrace {P(E)} ^{\text{language model}}}$$The benefit of the noisy-channel model is in terms of data: If collecting a parallel corpus is costly, then we would have only a small parallel corpus, so we can only train a moderately good English-to-foreign translation model, and a moderately good foreign-to-English translation model. However, we can collect a large corpus in the foreign language only, and a large corpus in the English language only, to train two good language models. Combining these four models, we immediately get a good English-to-foreign translator and a good foreign-to-English translator.^[3]

The cost of noisy-channel model is that using Bayesian inference is more costly than using a translation model directly. Instead of reading out the most likely translation by ${\displaystyle \arg \max _{E}P(E|F)}$, it would have to read out predictions by both the translation model and the language model, multiply them, and search for the highest number.