単語のtrigramを使用したときのViterbiサーチ

Viterbiサーチ(one-pass DP)は各認識単語の最後の状態と単語の最初の状態の遷移において trigramの確率を掛けることによって音響モデルと言語のtrigramモデルが簡 単に結合できる。ただし、 trigramは２つ前の単語が決定されて初めて現在 の単語の出現確率が計算できるためViterbiサーチのグリッドは、現在の単語 と１つ前の単語の最大累積尤度を、つねに保持する必要がある。そのため bigramと比較すると、必要なメモリ量が大幅に増加する。認識単位を単語と した場合のアルゴリズムを表 2.4に示す。

表 2.4: 単語のtrigramを用いたViterbiサーチのアルゴリズム

［定義］

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

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

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

$P(w_0\vert w_2,w_1)$ 単語$w_2,w_1$が出現したときに

$w_0$に遷移する確率

$Q$：語彙数

$T$：入力フレーム数

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

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

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

$\alpha$ ：音響尤度と言語の連鎖確率の結合値

［初期化］

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

1) $G_0(start,w_0,0) = P(w_0\vert start,start) ^ \alpha$

$start$は文頭を意味

［ Viterbiサーチ］

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

2) $w_1=0,...,Q-1$においてstep3を実行

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

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

5) $G_t(w_1,w_0,i)=$

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

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

［単語境界の計算］

6) $w_1=0,1,...,Q-1$ においてstep7を実行

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

8) $\Delta = \mathop{\rm max}_{ 0\leq w_2 \leq Q-1 } ( G_{t-1}(w_2,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_1,w_0,0)$ ならば $G_t(w_1,w_0,0)=\Delta$

図2.12に、このアルゴリズムの簡略図を示す。この 図では、認識語彙数を$W_1$と$W_2$の2単語で、単語のHMMは 4-state 3-loop で、状態は1から3までとする。縦軸はHMMの状態で、横軸は時間で、奥行きは 語彙を示している。

○ 1は時間$t-1$において現在の語が$w_2$で前の語が$w_2$で状態が0、 ○ 2は時間$t-1$において現在の語が$w_2$で前の語が$w_2$で状態が1、 ○ 3は時間$t$において現在の語が$w_2$ で前の語が$w_2$で状態が1、 ○ 4は時間$t-1$において現在の語が$w_2$で前の語が$w_2$で状態が2、 ○ 5は時間$t-1$において現在の語が$w_2$で前の語が$w_1$で状態が2、 ○ 6は時間 $t-1$において現在の語が$w_1$で前の語が$w_2$で状態が0、 ○ 7は時間$t$において現在の語が$w_1$で前の語が$w_2$で状態が0までの最大累積尤度であるとする。

単語の最初の状態以外は、前時刻の同一状態と前時刻の１つ前の最大累積尤度 の２遷移のうち、最大累積尤度の高い方を選択する。例えば、○ 3は ○ 1の遷移と○ 2から遷移の最大累積尤度の高い方を選択する。しか し、単語の最初の状態は、前時刻の最初の同一の最大累積尤度と各認識単語の 最後の最大累積尤度に現在の単語に遷移するtrigramの連鎖確率値を掛けたも のから遷移の最大累積尤度の高い方を選択する。例えば、○ 7は ○ 4にtrigramの値 ( $p(w_1\vert w_2,w_2) ^ \alpha$) を掛けたものと ○ 5にtrigramの値 ( $p(w_1\vert w_1,w_2) ^ \alpha$) と○ 6の遷移の尤 度の高い方を選択する。これを全状態に対して計算を行なう。

図 2.12: 単語のtrigramを利用したときのViterbiサーチ