|
ビタビアルゴリズム（）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（forward algorithm）も密接に関連している。これらのアルゴリズムは情報理論の一部である。 このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 ''t'' での最も尤もらしい隠されている事象の計算は、''t'' での観測された事象と ''t'' − 1 での最も尤もらしい隠された事象の系列のみに依存している。これらの前提条件は、全て一次隠れマルコフモデルで満たされている。 「ビタビ経路; Viterbi path」および「ビタビアルゴリズム」という用語は、観測結果について1つの最も尤もらしい説明を与える動的計画法のアルゴリズムに関して使われる。例えば、動的計画法のアルゴリズムを使った統計的構文解析は、文字列について1つの最も尤もらしい解析結果を生じる。そのため、これを「ビタビ構文解析; Viterbi parse」と呼ぶこともある。 ビタビアルゴリズムは、アンドリュー・ビタビがノイズのあるデジタル通信経路における誤り検出訂正手法として生み出したものである。CDMAやGSMといったデジタル携帯電話、ダイヤルアップ接続用モデム、通信衛星、宇宙探査での通信、IEEE 802.11 無線LAN などの畳み込み符号の復号に広く利用されている。また、音声認識、自然言語処理、計算言語学、バイオインフォマティクスなどにも使われている。例えば、音声認識では、音声信号を観測された事象の系列として扱い、それを文字に変換したものがその音声信号に対応した「隠された原因」と見なされる。ビタビアルゴリズムは、与えられた音声信号から最も尤もらしい文字列を見つけ出す。 == 概要 == まず、上述の前提条件について詳しく解説する。ビタビアルゴリズムは状態機械を仮定して動作する。すなわち、モデルとしたシステムは任意の時点で何らかの状態を持つ。状態数は膨大であっても有限であり、リストアップ可能である。各状態がノードとして表される。与えられた状態に対応する状態の複数の系列（経路）が複数考えられるとしても、最も尤もらしい状態経路が1つあり、これを「生存者経路; survivor path」と呼ぶ。これがこのアルゴリズムの基本的な前提である。このアルゴリズムは、ある状態に到達するあらゆる経路を調べ、最も尤もらしい経路を選ぶ。これを状態の並びに対して順次適用するため、あらゆる経路を保持しておく必要はなく、状態1つにつき1つの経路だけを保持する。 第二の重要な前提は、ある状態から別の状態への遷移について増分（通常、数）を付与する点である。この遷移は事象から求められる。 第三の重要な前提は、事象は一般に加算的な意味で経路上で累積するとされる。従って、このアルゴリズムの急所は、各状態についての数を保持する点である。ある事象が起きたとき、このアルゴリズムではこれまでの状態経路の持つ値と新たな遷移における増分を考慮し、最も良いものを選択する。事象に対応した増分は、ある状態から別の状態への遷移確率に依存して決定される。例えばデータ通信において、シンボルの半分を奇数の状態のときに送り、残る半分を偶数の状態のときに送るということも可能である。さらに、多くの場合、状態遷移図は完全に連結されてはいない。単純な例として、自動車は、前進、停止、後退という3つの状態を持つとしたとき、前進から後退への直接の遷移は不可能であり、常に一旦は停止状態になる必要がある。増分と状態値の組合せを計算すると、最良値のみが残り、他の経路は捨てられる。基本アルゴリズムの変形として、後方探索だけでなく前方探索も許すものもある。 経路履歴を記録する必要がある。エンコーダの開始時の状態が既知の状態で、全経路を保持できるだけのメモリがあるなら、経路履歴は有限である。そうでない場合、リソースが限られているため、何らかのプログラム上の解決策を必要とする。1つの例として畳み込み符号化がある。その場合、性能を許容可能なレベルに維持しつつ、デコーダの履歴の深さを制限できる。ビタビアルゴリズムは非常に効率的だが、さらに計算負荷を削減する変形版も存在する。メモリ使用量は一定となる傾向がある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ビタビアルゴリズム」の詳細全文を読む スポンサード リンク
|