雑音のある通信路モデル

雑音のある通信路モデル（ざつおんのあるつうしんろモデル、テンプレート:Lang-en）は、スペルチェッカ、質問応答システム 、音声認識、機械翻訳に使用されるフレームワークである。このモデルでは、何らかの形で文字が乱されている単語から、意図した単語が何であるかを見つけることが目的である。

定義

アルファベット $\mathrm{\Sigma }$ が与えられたとき、${\mathrm{\Sigma }}^{*}$ を $\mathrm{\Sigma }$ による全ての有限文字列の集合とし、有効な単語からなる辞書 $D$ を ${\mathrm{\Sigma }}^{*}$ の部分集合（すなわち $D\subseteq {\mathrm{\Sigma }}^{*}$ ）とする。

雑音のある通信路は行列

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

である。ここで、$w\in D$ は意図した単語、$s\in {\mathrm{\Sigma }}^{*}$ は実際に受信された乱された単語である。

例

英語のアルファベット $\mathrm{\Sigma }=\{a,b,c,...,y,z,A,B,...,Z,...\}$ を考える。いくつかの部分集合 $D\subseteq {\mathrm{\Sigma }}^{*}$ は、有効な英語の単語の辞書を構成する。

入力中に、以下のような間違いが発生する可能性がある。

1. 文字の脱落（例: letterがテンプレート:Notatypoになる）
2. 文字の追加（例: mistakeがテンプレート:Notatypoになる）
3. 文字の入れ替え（例: receivedがテンプレート:Notatypoになる）
4. 文字の置換（例: finiteがテンプレート:Notatypoになる）

雑音のある通信路行列 $\mathrm{\Gamma }$ を構築するには、与えられた意図した単語（全ての $w\in D$ と $s\in {\mathrm{\Sigma }}^{*}$ についての $\mathrm{Pr}(s|w)$）について、それぞれの間違いの確率を考慮する必要がある。これらの確率は、$s$ と $w$ の間のレーベンシュタイン距離を考慮して、あるいは、エッセイの草稿と手作業で綴りを編集したものとを比較することによって、集めることができる。

誤り訂正

雑音のある通信路モデルの目標は、受信した乱された単語から、意図した単語を見つけることである。決定関数 $\sigma :{\mathrm{\Sigma }}^{*}\to D$ は、乱された単語を与えると、目的の単語を返す関数である。

決定関数を構成する方法には、最尤推定法、最大事後法、テンプレート:仮リンクがある。

乱された単語をそのまま意図した単語として受け入れる方が、辞書内の目的の単語を見つけようとするよりも良い場合もある。 たとえば、schönfinkeling（curryingの別名）という単語は辞書にないかもしれないが、実際には意図された単語かもしれない。

関連項目

• 符号理論

出典

• テンプレート:Cite journal