Forward アルゴリズム

3.+.1667em2節の計算方法において，計算の多くが重複している．計算の 重複を避けて尤度を計算する方法として，計算の途中を覚えておく動的計画法 が利用できる．この計算方法をforward アルゴリズムと呼んでいる．このアル ゴリズムは図による説明がわかりやすい．Model A のパラメータを利用したと きのアルゴリズムの動きを図6で説明する．図の横軸は時系列，縦 軸は状態，これらの格子点である黒丸はgrid と呼ばれ、計算の途中を覚えてお く場所であり，その値を， $\alpha_i(j)$ と表記する． $\alpha_i(j)$ は，時刻 0 から時刻$i$ まで状態$j$ において，入力シンボル系列を出力する確率の総和 を意味する．また，$O_t$ は時刻$t$ において観測されるシンボルである．横 軸，斜め軸にある数値が，それぞれの状態遷移とシンボル出力確率の積である ことに注意してほしい．計算順序は，入力シンボル系列が１つ入るごとに縦方 向に計算を行う．尤度は，最終時刻の最終状態のgridの値になる．

forwardアルゴリズムのgridの計算式を以下に示す．

$$\alpha_{t}(j)= \alpha_{t-1}(j) \times a_{j,j} \times b_{j} (O_{t-1})$$

$$\hspace{3cm} + \alpha_{t-1}(j-1) \times a_{j-1,j} \times b_{j-1} (O_{t-1})$$

Model Aのパラメータを利用したときの各gridの計算式を以下に示す．

$\alpha_0(0)= 1.0$

$\alpha_1(0) = \alpha_0(0) \times a_{0,0} \times b_0 (O_0) = \alpha_0(0) \times a_{0,0} \times b_0 (\alpha) \\ \hspace{1.1cm}=1.0 \times 0.7 \times 0.7 = 0.49$

$\alpha_1(1)= \alpha_0(0) \times a_{0,1} \times b_0 (O_0) = \alpha_0(0) \times a_{0,1} \times b_0 (\alpha) \\ \hspace{1.1cm}= 1.0 \times 0.3 \times 0.7 = 0.21$

$\alpha_2(1)= \alpha_1(1) \times a_{1,1} \times b_1 (O_1) + \alpha_1(0) \times... ...pace{1.1cm} = 0.21 \times 0.6 \times 0.4 + 0.49 \times 0.3 \times 0.7 = 0.1533$

$\alpha_2(2)= \alpha_1(1) \times a_{1,2} \times b_1 (O_1) = \alpha_1(1) \time... ...} \times b_1 (\alpha) \\ \hspace{1.1cm} = 0.21 \times 0.4 \times 0.4 = 0.0336$

$\alpha_3(2)= \alpha_2(2) \times a_{2,2} \times b_2 (O_2) + \alpha_2(1) \times... ...3 \times 0.4 \times 0.3 \\ \hspace{1.1cm} = 0.018732 (\fallingdotseq 0.01873)$

$\alpha_4(3) = \alpha_3(2) \times a_{2,3} \times b_2 (O_3) = \alpha_3(2) \tim... ...e{1.1cm} = 0.018732 \times 0.9 \times 0.8 = 0.01348704 (\fallingdotseq 0.01349)$

$$尤度 = \alpha_4(3) = 0.01348704$$

得られた尤度は，3.+.1667em2節で得られた尤度と等しい．

図: forward アルゴリズム