ビタビアルゴリズム

ビタビアルゴリズムは、観測された一連の事象を説明する可能性が最も高い隠れた事象のシーケンスを見つける動的計画法アルゴリズムです。このアルゴリズムの結果は、しばしばビタビパスと呼ばれます。これは、隠れマルコフモデル（HMM）で最も一般的に使用されます。たとえば、医師が数日間にわたって患者の症状を観察した場合（観測された事象）、ビタビアルゴリズムは、それらの症状を引き起こした可能性が最も高い基礎疾患のシーケンス（隠れた事象）を特定することができます。

このアルゴリズムは、 CDMAおよびGSMデジタル携帯電話、ダイヤルアップモデム、衛星、深宇宙通信、および802.11無線 LANで使用される畳み込み符号の復号に広く応用されています。また、音声認識、音声合成、ダイアリゼーション、^{[ 1 ]}キーワードスポッティング、計算言語学、およびバイオインフォマティクスでもよく使用されています。たとえば、音声テキスト変換(音声認識) では、音響信号が観測されたシーケンスであり、テキストの文字列はその信号の「隠れた原因」です。ビタビ アルゴリズムは、音響信号が与えられた場合に最も可能性の高いテキストの文字列を見つけます。

ビタビアルゴリズムは、1967年にノイズの多いデジタル通信リンク上の畳み込み符号の復号アルゴリズムとして提案したアンドリュー・ビタビにちなんで名付けられました。 ^{[ 2 ]}しかし、ビタビ、ニードルマンとヴンシュ、ワグナーとフィッシャーによるものを含め、少なくとも7人の独立した発見があり、複数の発明の歴史があります。^{[ 3 ]} 1987年には早くも、品詞タグ付けの方法として自然言語処理に導入されました。

ビタビパスとビタビアルゴリズムは、確率を含む最大化問題に動的計画法アルゴリズムを適用する際の標準的な用語となっています。^{[ 3 ]} 例えば、統計的構文解析では、動的計画法アルゴリズムを使用して、文字列の最も可能性の高い単一の文脈自由導出（構文解析）を発見できます。これは一般に「ビタビ構文解析」と呼ばれています。^{[ 4 ] [ 5 ] [ 6 ]}別の応用例として、ターゲット追跡があります。これは、一連の観測に最大尤度を割り当てるトラックを計算します。^{[ 7 ]}

隠れ状態のセットを持つ隠れマルコフモデルが与えられた場合${\displaystyle S}$、可能な放出（観測）のセット M、およびシーケンス${\displaystyle T}$観察結果${\displaystyle o_{0},o_{1},\dots ,o_{T-1}}$ビタビアルゴリズムは、それらの観測結果を生成した可能性のある隠れ状態の最も可能性の高いシーケンスを見つけます。各タイムステップで${\displaystyle t}$アルゴリズムは、観測値のみに基づいて部分問題を解決します。$ot$考慮される。

サイズが 2 つの行列${\displaystyle T\times \left|{S}\right|}$構築される：

• ${\displaystyle P_{t,s}}$状態に到達する最大確率が含まれています${\displaystyle s}$観察中${\displaystyle t}$そこに至るまでの考えられるすべての状態のシーケンスの中で。
• ${\displaystyle Q_{t,s}}$以前に使用された状態を追跡します${\displaystyle s}$この最大確率状態系列において。

させて$\displaystyle \pi _{s}}$そして${\displaystyle a_{r,s}}$それぞれ初期確率と遷移確率とし、${\displaystyle b_{s,o}}$観測する確率${\displaystyle o}$州で${\displaystyle s}$すると、${\displaystyle P}$漸化式^{[ 8 ]によって与えられる。}$${\displaystyle P_{t,s}={\begin{cases}\pi _{s}\cdot b_{s,o_{t}}&{\text{if }}t=0,\\\max _{r\in S}\left(P_{t-1,r}\cdot a_{r,s}\cdot b_{s,o_{t}}\right)&{\text{if }}t>0.\end{cases}}}$$ の式${\displaystyle Q_{t,s}}$は同一です${\displaystyle t>0}$ただし、${\displaystyle \max }$に置き換えられます${\displaystyle \arg \max }$、 そして${\displaystyle Q_{0,s}=0}$ビタビパスは、以下の最大値を選択することによって見つけることができます。${\displaystyle P}$最終タイムステップで、そして${\displaystyle Q}$逆方向に。

関数Viterbi(states, init, trans, emit, obs)は、入力states: S 個の隠れ 状態、入力init: 各状態の初期確率、 入力trans: S × S 遷移行列、 入力emit: S × M 放出行列、 入力obs: T 個の観測値のシーケンスです。 prob ← T × S ゼロ行列 前へ ← 空のT×S行列 各州sについて、​​ prob[0][s] = init[s] * emit[s][obs[0]] t = 1からT - 1まで繰り返す// t = 0 は既に処理済み各状態 s in statesについて繰り返す各状態 r in statesについて繰り返す new_prob ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]] もしnew_prob > prob[t][s]ならば prob[t][s] ← new_prob prev[t][s] ← r パス ← 長さTの空の配列 path[T - 1] ← 確率が最大となる状態 s[T - 1][s] t = T - 2から0まで、以下を実行する path[t] ← prev[t + 1][path[t + 1]] 戻りパス 終了

アルゴリズムの時間計算量は${\displaystyle O(T\times \left|{S}\right|^{2})}$どの状態遷移が非ゼロの確率を持つかが分かっている場合、それらの遷移のみを反復することで、より精度の高い境界値を求めることができます。${\displaystyle r}$リンク先${\displaystyle s}$内側のループでは、償却分析を用いると、複雑さは${\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}$、 どこ${\displaystyle E}$はグラフのエッジの数、つまり遷移行列の非ゼロ要素の数です。

医師は、患者が健康か発熱しているかを判断したいと考えている。医師が得られる唯一の情報は、患者に体調を尋ねることである。患者は、体調は正常、めまいがする、または寒いと答えるかもしれない。

患者の健康状態は離散マルコフ連鎖として機能していると考えられています。「健康」と「発熱」の2つの状態がありますが、医師はそれらを直接観察することはできません。つまり、医師には隠されています。毎日、患者が医師に「気分は普通です」「寒いです」「めまいがします」と伝える確率は、その日の患者の健康状態のみに依存します。

観測値（正常、風邪、めまい）と隠れ状態（健康、発熱）は、隠れマルコフモデル（HMM）を構成します。過去の経験から、このモデルの確率は次のように推定されています。

init = {"Healthy": 0.6, "Fever": 0.4} トランス = { 「健康」：{「健康」：0.7、「発熱」：0.3}、 「発熱」：{「健康」：0.4、「発熱」：0.6}、 } 発する = { 「健康」：{「正常」：0.5、「風邪」：0.4、「めまい」：0.1}、 「発熱」：{「正常」：0.1、「風邪」：0.3、「めまい」：0.6}、 } 

このコードでは、 は、init患者が最初に健康である可能性についての医師の信念を表します。ここで使用されている特定の確率分布は、{'Healthy': 0.57, 'Fever': 0.43}遷移確率に基づく平衡分布ではないことに注意してください。遷移確率は、trans基となるマルコフ連鎖における健康状態の変化を表します。この例では、今日健康な患者が明日発熱する確率はわずか 30% です。放出確率はemit、基となる状態 (健康または発熱) が与えられた場合の各観測 (正常、風邪、またはめまい) の可能性を表します。健康な患者は、正常である可能性が 50% あり、発熱している患者は、めまいを感じる可能性が 60% あります。

ある患者が3日連続で来院し、1日目は体調が正常だったが、2日目は寒気を感じ、3日目はめまいがすると報告した。

まず、初日に健康であるか発熱しているかの確率を計算します。患者が初日に健康で、体調が正常であると報告する確率は${\displaystyle 0.6\times 0.5=0.3}$同様に、患者が初日に発熱し、その後も体調は正常だと報告する確率は${\displaystyle 0.4\times 0.1=0.04}$。

次の各日の確率は、前日から直接計算できます。たとえば、1日目に正常と報告した後、2日目に健康で風邪を訴える確率が最も高いのは、次の最大値です。${\displaystyle 0.3\times 0.7\times 0.4=0.084}$そして${\displaystyle 0.04\times 0.4\times 0.4=0.0064}$これは、患者が発熱して回復したというよりも、その2日間は健康だった可能性が高いことを示唆している。

その他の確率は以下の表にまとめられています。

表から、患者は3日目に発熱した可能性が最も高いことがわかります。さらに、「発熱」で終わる状態のシーケンスが存在し、そのシーケンスで今回の観測結果が得られる確率は0.01512です。このシーケンスは正確には（健康、健康、発熱）であり、これは最大値を計算する際に使用された状態を遡って調べることで見つけることができます（これは各日の最良の推測値ですが、常にそうとは限りません）。言い換えれば、観測された活動を考慮すると、患者は1日目と2日目（その日は寒さを感じていたにもかかわらず）は健康であった可能性が最も高く、3日目にのみ発熱したと考えられます。

ビタビアルゴリズムの動作は、格子図を用いて視覚化することができる。ビタビ経路とは、基本的にこの格子図を通る最短経路のことである。

ビタビアルゴリズムの一般化である最大和アルゴリズム（または最大積アルゴリズム）は、ベイジアンネットワーク、マルコフ確率場、条件付き確率場など、多数のグラフィカルモデルにおける潜在変数の全部または一部の最も可能性の高い割り当てを見つけるために使用できます。潜在変数は一般に、隠れマルコフモデル（HMM）にやや似た方法で接続される必要があり、変数間の接続数は限られており、変数間に何らかの線形構造が存在します。この一般的なアルゴリズムはメッセージパッシングを伴い、信念伝播アルゴリズム（フォワードバックワードアルゴリズムの一般化）と実質的に類似しています。

反復ビタビ復号と呼ばれるアルゴリズムを使用すると、与えられた隠れマルコフモデルに（平均的に）最もよく一致する観測のサブシーケンスを見つけることができます。このアルゴリズムは、ターボコードを扱うために Qi Wang らによって提案されました。^{[ 9 ]}反復ビタビ復号は、修正されたビタビアルゴリズムを繰り返し呼び出し、収束するまでフィラーのスコアを再推定することによって機能します。

代替アルゴリズムとして、レイジービタビアルゴリズムが提案されている。^{[ 10 ]}実用的な関心のある多くのアプリケーションでは、妥当なノイズ条件下では、レイジーデコーダ（レイジービタビアルゴリズムを使用）は、元のビタビデコーダ（ビタビアルゴリズムを使用）よりもはるかに高速である。元のビタビアルゴリズムは可能な結果のトレリス内のすべてのノードを計算するが、レイジービタビアルゴリズムは評価するノードの優先順位付きリストを順番に保持し、必要な計算回数は通常、同じ結果を得るための通常のビタビアルゴリズムよりも少なく（決して多くはない）、ハードウェアで並列化するのはそれほど簡単ではない。

ソフト出力ビタビアルゴリズム（SOVA）は、古典的なビタビアルゴリズムの変種である。

SOVAは、入力シンボルの事前確率を考慮した修正パスメトリックを使用し、決定の信頼性を示すソフト出力を生成する点で、従来のビタビアルゴリズムとは異なります。

SOVAの最初のステップは、各時刻tにおいて1つの固有のノードを通過する生存パスを選択することです。各ノードには2つの分岐が収束するため（1つの分岐が生存パスを形成するために選択され、もう1つは破棄されます）、選択された分岐と破棄された分岐の間の分岐メトリック（またはコスト）の差は、選択におけるエラーの量を示します。

このコストは、スライディングウィンドウ全体（通常は少なくとも5つの制約長に相当）にわたって累積され、ビタビアルゴリズムのハードビット決定の信頼性のソフト出力尺度を示す。

• 期待値最大化アルゴリズム
• バウム・ウェルチアルゴリズム
• 前方後方アルゴリズム
• 順方向アルゴリズム
• エラー訂正コード
• ビタビ復号器
• 品詞タグ付け
• A*探索アルゴリズム

• Viterbi AJ (1967年4月)「畳み込み符号のエラー限界と漸近的に最適な復号アルゴリズム」IEEE Transactions on Information Theory . 13 (2): 260–269 . doi : 10.1109/TIT.1967.1054010 .（注：ビタビ復号アルゴリズムについては第IV節で説明します。）購読が必要です。
• Feldman J、Abou-Faycal I 、Frigo M (2002)「畳み込み符号のための高速最大尤度デコーダ」IEEE第56回車両技術会議議事録、第1巻、 371～ 375 ページ。CiteSeerX 10.1.1.114.1314。doi : 10.1109/ VETECF.2002.1040367。ISBN   978-0-7803-7467-6. S2CID 9783963 . 
• Forney GD (1973年3月)「ビタビアルゴリズム」IEEE論文集61 ( 3): 268–278 . doi : 10.1109/PROC.1973.9030 .購読が必要です。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第 16.2 節 ビタビ復号」 . Numerical Recipes: The Art of Scientific Computing (第 3 版). ニューヨーク: Cambridge University Press. ISBN 978-0-521-88068-82011年8月11日にオリジナルからアーカイブされました。 2011年8月17日に取得。
• Rabiner LR (1989年2月)「隠れマルコフモデルと音声認識における応用例に関するチュートリアル」Proceedings of the IEEE 77 ( 2): 257–286 . CiteSeerX 10.1.1.381.3454 . doi : 10.1109/5.18626 . S2CID 13618539 .  （HMMにおける順伝播アルゴリズムとビタビアルゴリズムについて説明する。）
• Shinghal, R. およびGodfried T. Toussaint、「修正ビタビアルゴリズムによるテキスト認識の実験」、IEEE Transactions on Pattern Analysis and Machine Intelligence、Vol. PAMI-l、1979 年 4 月、pp.  184–193。
• Shinghal, R. およびGodfried T. Toussaint、「修正ビタビアルゴリズムのソース統計に対する感度」、IEEE Transactions on Pattern Analysis and Machine Intelligence、vol. PAMI-2、1980 年 3 月、pp.  181–185。

• Wikibooks の Java、F#、Clojure、C# での実装
• チップ・フレミングによる、ビタビ復号を用いた畳み込み符号化に関するチュートリアル
• ビタビアルゴリズムの説明を含む、隠れマルコフモデルツールキット（C言語で実装）のチュートリアル。
• アンドリュー・J・ヴィテルビ博士によるヴィテルビアルゴリズム（scholarpedia.org）。