ビタビアルゴリズム

背景

「pyopenjtalkの仕組み」という記事で、MeCabの形態素解析に使われているビタビアルゴリズムに触れた
ここでは、ビタビアルゴリズムそのものを掘り下げて整理する

ビタビアルゴリズムの起源

Andrew J. Viterbiが1967年に発表した論文Error bounds for convolutional codes and an asymptotically optimum decoding algorithm（IEEE Transactions on Information Theory, vol. 13, pp. 260-269）が出典
元々は、通信における畳み込み符号の復号のために考案されたアルゴリズム
その後、隠れマルコフモデル（HMM）のデコーディング、音声認識、そしてMeCabのような形態素解析まで、幅広い分野に応用されるようになった

マルコフ連鎖と隠れマルコフモデル

ビタビアルゴリズムの背景には、マルコフ連鎖と隠れマルコフモデル（HMM）という考え方がある。

マルコフ連鎖（Markov Chain）

ある時点の状態が、直前の状態だけに依存し、それ以前の履歴には依存しないという性質（マルコフ性）を持つ確率過程
状態の集合と、状態間の遷移確率によって定義される

隠れマルコフモデル（HMM）

マルコフ連鎖に従って遷移する状態の系列が、直接には観測できない（隠れている）というモデル
代わりに、各状態から確率的に出力される観測値だけが観測できる
HMMは、以下の3つの要素で定義される
- 初期状態確率（Initial probabilities, $\pi$）: 最初にどの状態から始まるかの確率分布
- 状態遷移確率行列（Transition matrix, $A$）: ある状態から別の状態へ遷移する確率
- 出力確率（Emission probabilities, $B$）: ある状態にいるときに、特定の観測値が出力される確率
MeCabの形態素解析に当てはめると、品詞や単語といった裏の系列（状態）が直接には観測できず、実際に書かれた表層文字列（観測値）だけが見えている、という構造に対応する

ブルートフォース法との比較

観測系列$O$が与えられたとき、それを生み出した可能性が最も高い状態系列$Q$を求める問題を、デコーディング問題と呼ぶ。

最も素朴な解法は、あり得る全ての状態系列を列挙し、それぞれの尤度を計算して比較するブルートフォース法（総当たり法）
状態数を$N$、系列の長さを$T$とすると、あり得る状態系列の数は$N^T$通りになり、系列が長くなるほど組み合わせが指数的に爆発する
例えば$N=10$、$T=20$でも$10^{20}$通りという非現実的な数になり、実用上は計算できない
ビタビアルゴリズムは、この組み合わせ爆発を避けながら、ブルートフォース法と同じ最適解を多項式時間で求める方法

動的計画法としてのビタビアルゴリズム

ビタビアルゴリズムの核心は、「未来を全部見る」のではなく「ここまでで一番いい過去だけを持って進む」という考え方。これは動的計画法（Dynamic Programming, DP）の典型例になる。

ある地点に複数の経路で到達できる場合、そこから先の話には、その地点までの累積コストが最小の経路だけが関係する
つまり、同じ地点に到達した経路のうち、負けている経路はその時点で切り捨ててよい
全ての分割パターンを総当たりする代わりに、各地点で最良の経路だけを覚えておくことで、計算量を大きく減らせる

MeCabでの具体例

MeCabの形態素解析を例に、ビタビアルゴリズムの動きを追ってみる。

例えば「東京都」という文があったとき、辞書から複数の分割候補が出てくる。

「東京」＋「都」
「東」＋「京都」
「東京都」

MeCabはまず、文の各位置から始まる単語候補を全て並べて、ラティスと呼ばれる網目状のグラフを作る。ラティスの各ノードには、以下2種類のコストが割り当てられる。

単語そのもののコスト（辞書に登録された、その単語らしさを表すコスト）
直前の単語との接続コスト（品詞の並びとしての自然さを表すコスト）

イメージとして、以下のようなラティスができる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
BOS
 ├─ 東京   (100)
 │    └─ 都   (+50)
 │
 ├─ 東     (200)
 │    └─ 京都 (+300)
 │
 └─ 東京都 (80)
          ↓
         EOS

ビタビアルゴリズムは、文の先頭（BOS）から順番に、各ノードまでの最小累積コストを計算していく。

$$ C(v) = \min_{u} \{ C(u) + \mathrm{connectionCost}(u,v) + \mathrm{wordCost}(v) \} $$

$C(v)$はノード$v$までの最小累積コスト、$u$は$v$の直前になりうる各ノード。重要なのは、同じ地点に複数の経路で到達したとき、一番安かった経路だけを覚えておけばよいという点。

上の例で言えば、以下のようになる。

「東京」→「都」: 累積コスト150
「東」→「京都」: 累積コスト500
「東京都」: 累積コスト80

このうち「東京都」1語だけの経路が最も安いため、これが採用される。文末（EOS）まで計算した後、EOSから「どのノードから来たか」を逆向きに辿る（バックトラック）ことで、最適な形態素列が得られる。

MeCabの処理の流れをまとめると、以下のようになる。

辞書から形態素候補を出す
ラティスを作る
各ノードについて最小累積コストを計算する
各ノードについて、最良の直前ノードを記録する
文末から先頭へバックトラックする

HMMにおける一般的な定式化

MeCabのラティスでの定式化は、コストの最小化という形だったが、隠れマルコフモデル（HMM）の文脈では、前述の初期状態確率$\pi$・遷移確率行列$A$・出力確率$B$を使った確率の最大化という形で、同じアルゴリズムが使われる。

まず、時刻1（最初の観測）における各状態の確率は、初期状態確率と出力確率から以下のように求まる。

$$ \delta_1(j) = \pi_j \cdot b_j(o_1) $$

時刻$t$、状態$j$における最良経路の確率$\delta_t(j)$は、以下の漸化式で計算できる。

$$ \delta_t(j) = \max_{i} \left[ \delta_{t-1}(i) \cdot a_{ij} \right] \cdot b_j(o_t) $$

$a_{ij}$は遷移確率行列$A$の要素（状態$i$から状態$j$への遷移確率）、$b_j(o_t)$は出力確率$B$の要素（状態$j$で観測値$o_t$が出力される確率）。MeCabのコスト最小化は、確率の対数を取って符号を反転させたもの（負の対数尤度）とみなせば、この確率最大化の定式化と本質的に同じ計算になる。ブルートフォース法が全ての状態系列について愚直に尤度を計算するのに対し、この漸化式は各時刻・各状態について直前までの最良値だけを使い回すことで、同じ最適解を効率的に求めている。

計算量のメリット

文の長さが$n$、各位置での候補数を$k$とすると、全ての分割パターンを総当たりで比較する場合、組み合わせの数は指数的に増えていく。一方ビタビアルゴリズムでは、各地点で最良の経路だけを保持しながら進むため、計算量は文の長さと候補数にほぼ比例する程度に収まる。全探索を避けながら、最終的には全体最適な経路を見つけられるというのが、動的計画法としてのビタビアルゴリズムの強み。

まとめ

ビタビアルゴリズムは、1967年にAndrew Viterbiが畳み込み符号の復号のために考案した動的計画法
背景には、初期状態確率$\pi$・遷移確率行列$A$・出力確率$B$で定義される隠れマルコフモデル（HMM）がある
素朴なブルートフォース法では状態数$N$・系列長$T$に対し$N^T$通りの組み合わせを比較する必要があるが、「ここまでの最良の経路だけを残しながら進む」ことで、同じ最適解を効率的に求められる
MeCabの形態素解析では、単語コストと接続コストの和を最小化する経路探索として使われている
HMMの文脈では、確率の最大化という形で同じアルゴリズムが使われ、コスト最小化と数学的に対応している
音声認識・通信・形態素解析など、系列の背後にある最適な経路を求める問題に広く応用されている

参考文献

Viterbi, A.J. (1967). “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.” IEEE Transactions on Information Theory, Vol. 13, pp. 260-269.
Viterbi algorithm - Species and Gene Evolution