フレーム同期型フルサーチアルゴリズム

フルサーチアルゴリズム（全探索）は連続音声認識のための基本的なアルゴリ ズムである。このアルゴリズムは全ての単語の組み合わせの尤度を計算するた め、大量の計算量やメモリ量が必要になる。

しかし、以下に示すような長所を持っている。

1. N位までの累積尤度の単語列(N-best リスト)を出力することができる。

2. グリッドの選択において、最尤なものを選択する方法(Viterbi)と尤度を足す方法 (Trellis)の両者が選択できる。

3. グリッドをTrellisで計算をした場合、状態を陽に考慮 する必要がないため、継続時間のコントロールは基本的に必要としない。

4. 音声データの最終フレームにおいて、尤度 の最も高いグリッドを選択して単語系列を認識するため、基本的にtraceback は必要としない。

5. フレーム同期で計算を実行させたとき、任意の時間において最尤の単語 を認識できるため、単語スポッタとしての動作が可能である。

6. 各単語のHMMの最終状態を示すグリッドと後続する単語の最初の状態を 示すグリッドの尤度計算において、任意の言語モデルの制約を加えることによ り、left-right型の言語モデルと音響モデルを容易に結合することができる。

図1に、フルサーチアルゴリズムをフレーム同期で計算 したときの簡略図を示す。この図では、認識語彙数を$w_a$と$w_b$の2Wordで、 単語を認識単位とし、4-state 3-loop のHMM、状態は0から2とする。縦軸は HMMの状態で、横軸は時間で、奥行きは語彙を示している。

図 1: フルサーチのアルゴリズム

図中の ○ 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、 を示すグリッドで、累積尤度が記録されている。

フレーム同期型フルサーチアルゴリズムにおいてグリッドを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が容易に結合できる。