ビタビアルゴリズム

ビタビアルゴリズム（英: Viterbi algorithm）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（英: 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つの例として畳み込み符号化がある。その場合、性能を許容可能なレベルに維持しつつ、デコーダの履歴の深さを制限できる。ビタビアルゴリズムは非常に効率的だが、さらに計算負荷を削減する変形版も存在する。メモリ使用量は一定となる傾向がある。

具体例

遠く離れた地に友人がいて、毎日その友人と電話をして彼がその日何をしたかを聞くものとする。その友人は、公園を散歩すること、買い物をすること、部屋を掃除することという3つのことにしか興味が無い。ある日にどれをするかは、その日の天気だけに依存する。その友人が住んでいる地の天気に関する具体的情報は、別経路では全く得られないが、一般的傾向はわかっている。彼が電話で話した毎日の行動に基づいて、その場所の天気を推測してみよう。 天気の変動は離散マルコフ連鎖になっているものとする。状態としては「雨; Rainy」と「晴れ; Sunny」の2つだけだが、直接観測することはできないので、我々にとってはそれが「隠された」状態である。毎日、友人は「散歩; walk」、「買い物; shop」、「掃除; clean」のいずれかを行う可能性がある。彼は何をしたかを電話連絡してくるので、それが「観測された」状態となる。システム全体としては、隠れマルコフモデル (HMM) となる。

その地域の天気の傾向はわかっていて、平均的にその友人が何をする傾向があるかもわかっている。言い換えれば、HMM のパラメータは既知である。これを Python で書くと次のようになる。

states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
    }

このコードにおいて、start_probability は最初に友人が電話してきたときに HMM がどの状態にあるかを表している（つまり、雨の可能性がやや高いということしか知らない）。ここで使われている確率分布は定常時のものではない（定常時の確率分布はだいたい {'Rainy': 0.571, 'Sunny': 0.429} である）。transition_probability は、このマルコフ連鎖での天気の変化を表している。この例では、今日が雨だった場合に翌日が晴れとなる可能性は 30% しかない。emission_probability は、友人がある活動を行う確率を示している。雨だった場合、50% の確率で部屋を掃除する。晴れだった場合、60% の確率で外を散歩する。

友人と三日間続けて話をしたところ、初日は散歩、二日目は買い物、三日目は掃除をしたという。ここで2つの疑問が生じる。この観測されたシーケンスの全体としての確率はどうなるか? そして、この観測結果を説明する最も尤もらしい天気のシーケンスはどうなるか? 第一の疑問には前向きアルゴリズムで答えられる。第二の疑問にはビタビアルゴリズムで答えられる。これら2つのアルゴリズムは構造的に非常に近いので（実際、これらは同じ抽象アルゴリズムのインスタンスである）、1つの関数として次のように実装できる。

 def forward_viterbi(y, X, sp, tp, ep):
    T = {}
    for state in X:
        ##          prob.      V. path  V. prob.
        T[state] = (sp[state], [state], sp[state])
    for output in y:
        U = {}
        for next_state in X:
            total = 0
            argmax = None
            valmax = 0
            for source_state in X:
                (prob, v_path, v_prob) = T[source_state]
                p = ep[source_state][output] * tp[source_state][next_state]
                prob *= p
                v_prob *= p
                total += prob
                if v_prob > valmax:
                    argmax = v_path + [next_state]
                    valmax = v_prob
            U[next_state] = (total, argmax, valmax)
        T = U
    ## apply sum/max to the final states:
    total = 0
    argmax = None
    valmax = 0
    for state in X:
        (prob, v_path, v_prob) = T[state]
        total += prob
        if v_prob > valmax:
            argmax = v_path
            valmax = v_prob
    return (total, argmax, valmax)

関数 forward_viterbi は、次のような引数をとる。y は観測シーケンスであり、例では ('walk', 'shop', 'clean') となる。X は隠された状態の集合である（例では states）。sp は初期の確率である（例では start_probability）。tp は遷移確率である（例では transition_probability）。ep は隠された状態から観測された状態への対応確率である（例では emission_probability）。

このアルゴリズムは、T と U というマッピングを使う。これらは、状態から3つ組 (prob, v_path, v_prob) へのマッピングであり、prob は初期状態から現在状態までの全経路の確率、v_path は現在状態までのビタビ経路、v_prob は現在状態までのビタビ経路の確率である。マッピング T は与えられた時点 $t$ についてのこの情報を保持し、メインループで構築する U は $t+1$ の時点についての同様の情報を保持する。マルコフ性があるため、$t$ 以前の時点に関する情報は不要である。

このアルゴリズムでは、まず $T$ を初期の確率で初期化する。ある状態の全体確率は単にその状態の初期の確率となる。初期状態へのビタビ経路は、その状態のみを含むシングルトン経路である。ビタビ経路の確率は、初期の確率と等しい。

メインループでは、y から順に観測結果を取り出す。T はそこまでの時点での正しい情報を含むが、現在の観測時点に関する情報は含まない。このアルゴリズムでは次に、考えられる次の状態についての3つ組 (prob, v_path, v_prob) を計算する。与えられた次の状態の全体確率 total は、その状態に到達する全経路の確率の総和によって得られる。より正確に言えば、このアルゴリズムは考えられる全ての元の状態について繰り返している。それぞれの元の状態について T は、その状態に到達する全経路の全体確率を保持している。この確率に、その状態で現在の観測値が得られる確率と次の状態に遷移する確率をかける。それによって得られる確率 prob を total に加算する。ビタビ経路の確率も同様に求められるが、その場合は全経路の総和を計算するのではなく、最大値を持つ経路を選択する。初期状態では、最大値 valmax はゼロに設定されている。元の状態について、その状態までのビタビ経路の確率は既知である。この場合も同様に、その状態で現在の観測値が得られる確率と次の状態に遷移する確率をその時点までのビタビ経路の確率にかけ、それが valmax の現在値よりも大きい場合は valmax を置き換える。ビタビ経路そのものは、最大値に対応した状態系列を argmax として保持する。このように計算された3つ組 (prob, v_path, v_prob) が U に格納され、全ての可能な次の状態について U の計算が完了した時点で、それを T に代入する。

最後に総和と最大をとる（最後の実際の観測結果を処理した後に仮想的な観測結果を処理するようにすれば、メインループ内でもできる）。

当初の例にこのアルゴリズムを適用する場合、次のようになる。

def example():
    return forward_viterbi(observations,
                           states,
                           start_probability,
                           transition_probability,
                           emission_probability)
print example()

これにより、['walk', 'shop', 'clean'] という並びの全体確率は 0.033612、ビタビ経路は ['Sunny', 'Rainy', 'Rainy', 'Rainy'] となる。3つ目の観測結果から3つ目の状態と4つ目の状態への遷移が求められるので、ビタビ経路には4つ目の状態も含まれている。つまり、与えられた観測結果から、友人が散歩に出た初日は晴れだったが、その後雨が降り続いている可能性が最も高いと言える。

このアルゴリズムを実装する際、多くの言語では浮動小数点数を使うと思われるが、p が小さいと結果としてアンダーフローを生じる危険性がある。これを防ぐ技法として、確率の対数をとり、計算を全てその対数値で行う方法がある。最終的な値が対数で得られたら、それに適切な指数関数を適用すれば、真の値が求められる。

拡張

反復ビタビ復号と呼ばれるアルゴリズムでは、与えられた HMM に最もよくマッチする観測結果内の部分系列を探し出す。反復ビタビ復号は、評価が収束するまで繰り返しビタビアルゴリズム（の変形したもの）を呼び出す。

別のアルゴリズムとして遅延ビタビアルゴリズムが提案されている。これは本当に必要になるまでノードを展開しない方式で、ソフトウェアでは通常のビタビアルゴリズムよりも少ない手順数で同じ結果が得られる。しかし、これをハードウェアで並列化するのは容易ではない。

参考文献

• Andrew J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, IEEE Transactions on Information Theory 13(2):260–269, April 1967. （ビタビアルゴリズムは section IV にある）
• G. D. Forney. The Viterbi algorithm. Proceedings of the IEEE 61(3):268–278, March 1973.
• L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2):257–286, February 1989.
• J Feldman, I Abou-Faycal and M Frigo. A Fast Maximum-Likelihood Decoder for Convolutional Codes.

関連項目

• バウム・ウェルチアルゴリズム
• 前方誤り訂正

外部リンク

• アンドリュー・ビタビへのインタビュー ビタビアルゴリズム発見に関する背景が語られている。
• Perl によるビタビアルゴリズムの実装例
• Python によるビタビアルゴリズムの実装例