Viterbi サーチ ( one-pass DP )

Viterbiサーチ(one-pass DP)は各認識単語の最後の状態を意味するグリッド と単語の最初の状態を意味するグリッドの遷移において尤度の高い遷移を選 択していく。認識単位を単語とした場合のアルゴリズムを表 2.2に示す。

表 2.2: Viterbiサーチのアルゴリズム

［定義］

$l_w$：単語$w$における状態数

$a^w_{ij}$：単語$w$における状態$s_i$から状態$s_j$への遷移確率

$b^w_j(v)$：単語$w$の状態$s_j$におけるベクトル$v$の出力確率

$Q$：語彙数

$T$：入力フレーム数

$O(t)$：フレーム$t$における観測ベクトル

$G_t(w_0,i)$：単語$w_0$,状態$i$での

フレーム$t$までの最大累積尤度

［初期化］

$w_0=0,...,Q-1$においてstep1を実行

1) $G_0(w_0,0) = 0.0$

$start$は文頭を意味

［ Viterbiサーチ］

$t=0,1,..,T-1$においてstep2 $\sim$ step6を実行

3) $w_0=0,...,Q-1$においてstep4を実行

4) $i=0,1,...,l_{w_0}-2$においてstep5を実行

5) $G_t(w_0,i)=$

$\max( G_{t-1}(w_0,i) \times a^{w_0}_{i,i} \times b^{w_0}_i(O_t),$

$G_{t-1}(w_0,i-1) \times a^{w_0}_{i-1,i} \times b^{w_0}_{i-1}(O_t))$

［単語境界の計算］

7) $w_0=0,1,...,Q-1$ においてstep8を実行

8) $\Delta = \mathop{\rm max}_{ 0\leq w_1 \leq Q-1 } ( G_{t-1}(w_1,l_{w_1}-2)$

$\times a^{w_1}_{l_{w_1}-2,l_{w_1}-1} \times b^{w_1}_{l_{w_1}-1}(O_t) \times P(w_0\vert w_2,w_1) ^ \alpha$

もし $\Delta \geq G_t(w_0,0)$ ならば $G_t(w_0,0)=\Delta$

図2.5に、このアルゴリズムの簡略図を示す。この 図では、認識語彙数を$w_a$と$w_b$の2単語で、単語のHMMは 4-state 3-loop で、状態は0から2までとする。縦軸はHMMの状態で、横軸は時間で、奥行きは 語彙を示している。 ○ 1は時間$t-1$において単語$w_a$状態が0、 ○ 2は時間$t-1$において単語$w_b$状態が1、 ○ 3は時間$t$において単語$w_a$状態が0、 ○ 4は時間$t-1$において単語$w_b$状態が2、 ○ 5は時間$t-1$において単語$w_a$状態が2、 ○ 6は時間$t$において単語$w_b$状態が2、 を意味するグリッド（最大累積尤度）であるとする。

単語の最初の状態を意味するグリッド以外は、前時刻の同一状態と前時刻の １つ前の最大累積尤度の２遷移のうち、最大累積尤度の高い方を選択する。 例えば、○ 6は○ 2の遷移と○ 4から遷移の最大累積尤度の高 い方を選択する。しかし、単語の最初の状態を意味するグリッドは、前時刻 の最初の同一の最大累積尤度と各認識単語の最後の最大累積尤度の高い方を 選択する。例えば、 ○ 3 は ○ 1, ○ 5, ○ 6 の遷移の尤度の 高い方を選択する。

なお、単語のbigramを利用するときは、 ○ 3は○ 5にbigramの値( $p(w_a\vert w_a) ^\alpha$) を掛けたものと ○ 4にbigramの値( $p(w_a\vert w_b) ^ \alpha$), ($\alpha$: language weight)の遷移の尤度の高い方を選択する。

これを全状態に対して計算を行なう。

図 2.5: one-passのアルゴリズム