tree-trellisサーチ

連続単語認識アルゴリズムとして最も基本的なアルゴリズムは、tree-trellis サーチである。

このアルゴリズムは、テストデータ全てに対して全ての可能性を計算するため、 計算量、メモリ量は膨大になる。しかし、N位までの累積尤度の単語列(N-best リスト)を出力することができる。また、グリッドの選択において最尤なもの を選ぶ方法(Viterbi)とグリッドの尤度を足す方法(trellis)の両者が選択でき る。Trellisで計算をした場合、フレーム単位での状態の位置が明確にならな いため、HMMを用いた音声認識において良く使用されるduration control（状 態継続時間の制限）は意味をもたない。また、任意の時間に おいて単語を認識させることが可能なため、単語スポッタとしても動作が可能 である。

またアルゴリズムにおいて各単語のHMMの最後の状態と後続する単語の最初の 状態の遷移において任意の言語モデルの制約を加えることにより、音響モデル と言語モデルを簡単に結合することができる。つまり、言語モデルは単語 bigramに限らずCYKなどの全てのleft-right型の言語モデルを採り入れること が可能である。

グリッドをTrellisで計算した場合のtree-trellisサーチのアルゴリズムを 表 2.1  および図  2.4 に示す。 なお、１文は$n$個の単語から構成される ( $L = w_0,w_1,w_2,\ldots,w_{n-1}$) と仮定した。

図2.4に、このアルゴリズムの簡略図を示す。この図で は、認識語彙数を$w_a$と$w_b$の2単語で、単語のHMMは 4-state 3-loop で、 状態は0から2までとする。縦軸はHMMの状態で、横軸は時間で、奥行きは語 彙を示している。図中の ○ 1は時間$0$から時間$t-1$までの単語$w_a$の状態0、 ○ 2は時間$0$から時間$t-1$までの単語$w_a$の状態1、 ○ 3は時間$0$から時間$t-1$までの単語$w_a$の状態2、 ○ 4は時間$0$から時間$t$までの単語$w_a$の状態2、 ○ 5は時間$0$から時間$t-1$までの連続2単語$w_a,w_a$の状態0、 ○ 6は時間$0$から時間$t-1$までの連続2単語$w_a,w_b$の状態0、 ○ 7は時間$0$から時間$t$までの連続2単語$w_a,w_a$の状態0、 ○ 8は時間$0$から時間$t$までの連続2単語$w_a,w_b$の状態0、 の累積尤度であるとする。

図 2.4: tree-trellisサーチのアルゴリズム

tree-trellisサーチのtrellis計算においては、単語の最初の状態0を意味するグリッド 以外は、前時刻の同一状態を意味するグリッドの尤度と前時刻の１つ前の状 態のグリッドの尤度の２状態を加えて現時刻のグリッドの尤度を計算する。 例えば、○ 4は○ 1の遷移と○ 2から遷移の累積尤度の総和とする。

しかし、単語の最初の状態0を意味するグリッドは、前時刻の同一のグリッ ドの累積尤度とレベルが１つ下の単語の最終状態を意味するグリッドの累積 尤度の総和とする。例えば、○ 7 は○ 3の遷移と○ 5の遷移 の累積尤度の総和とする。

これを全グリッドに対して計算を行なう。

なお、このとき言語モデルの確率値を掛けることにより音響モデルと言語モデ ルが結合できる。例えば、○ 7 は○ 3の遷移と○ 5の遷移の累 積尤度に単語bigram $P(w_b\vert w_a) ^\alpha$, ($\alpha$: language weight)を掛 けることによって、単語のbigramと単語のHMMが簡潔に結合できる。

表 2.1: 連続単語認識におけるtree-trellisサーチのアルゴリズム

［定義］

$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_n,..,w_0,i)$：単語$w_n$から単語$w_0$までの状態$i$での

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

［初期化］

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

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

.

.

.

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

3) $G_0(w_n,...,w_0,0) = 0.0$

［ 単語内での計算］

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

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

.

.

.

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

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

7) $G_t(w_n,...,w_0,i)=$

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

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

［単語境界の計算］

8) $w_n=0,1,...,Q-1$ においてstep10を実行

.

.

.

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

10) $G_t(w_n,...,w_0,0) = \Sigma_{w_0} ( G_{t-1}(w_n,w_{n-1},...,w_0,l_{w_0}-2)$

$\times a^{w_0}_{l_{w_0}-2,l_{w_0}-1} \times b^{w_0}_{l_{w_0}-1}(O_t) + G_t(w_n,...,w_0,0))$