Cotangent complex

2013-05-24T20:04:37Z

173.174.110.162: Grammar: In the first sentence I changed "... is a roughly a universal..." to "... is roughly a universal...".

{{Orphan|date=December 2011}}

The '''noisy channel model''' is a framework used in [[spell checker]]s,
[[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 <math>\Sigma</math>, let <math>\Sigma^*</math> be the set
of all finite strings over <math>\Sigma</math>. Let the dictionary
<math>D</math> of valid words be some subset of <math>\Sigma^*</math>, i.e.,
<math>D\subseteq\Sigma^*</math>.

The '''noisy channel''' is the matrix

:<math>\Gamma_{ws} = \Pr(s|w)</math>,

where <math>w\in D</math> is the intended word and <math>s\in\Sigma^*</math>
is the scrambled word that was actually received.

== Example ==

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

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

# Missing letters, e.g., ''leter'' instead of ''letter''
# Accidental letter additions, e.g., ''misstake'' instead of ''mistake''
# Swapping letters, e.g., ''recieved'' instead of ''received''
# Replacing letters, e.g., ''fimite'' instead of ''finite''

To construct the noisy channel matrix <math>\Gamma</math>, we must consider
the probability of each mistake, given the intended word
(<math>\Pr(s|w)</math> for all <math>w\in D</math> and
<math>s\in\Sigma^*</math>). These probabilities may be gathered, for
example, by considering the [[Levenshtein distance]] between <math>s</math>
and <math>w</math> 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'''
<math>\sigma : \Sigma^* \to D</math> is a function that, given a scrambled word, returns
the intended word.

Methods of constructing a decision function include the
[[maximum likelihood|maximum likelihood rule]], the
[[maximum a posteriori|maximum a posteriori rule]], and the
[[Minimum_distance#Coding_Theory|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.

== See also ==

* [[Coding theory]]

== References ==
{{Refbegin}}
* {{cite journal
| last1 = Brill | first1 = Eric | last2 = Moore | first2 = Robert C.
| title = An Improved Error Model for Noisy Channel Spelling Correction
|date=Jan 2000
| journal = Proceedings of ACL 2000
| url = https://research.microsoft.com/apps/pubs/default.aspx?id=66833
}}
{{Refend}}

[[Category:Automatic identification and data capture]]
[[Category:Computational linguistics]]
[[Category:Statistical natural language processing]]

formulasearchengine - User contributions [en]

Cotangent complex