Backword アルゴリズム

Backwardアルゴリズム は，入力シンボル系列において時系列の逆方向の尤度で ある．forward アルゴリズムと逆の方向から計算する．図10にこ の例を示す．横軸は時系列で縦軸は状態を意味する．最終状態から，初期状態 に向かって計算する．

backwordアルゴリズムのgridの値は $\beta_t (i)$ とし て表記する． $\beta_t (i)$ は最後の状態から時刻$t$ まで状態$i$ における逆方 向の尤度を意味する． forwardアルゴリズムのgridの値 $\alpha_t (i)$ と逆 方向である．

$\beta_4 (3)=1.0$ $\beta_4 (2)=0.0$ $\beta_4 (1)=0.0$ $\beta_4 (0)=0.0$ から始まる．

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

$$\beta_{t} (j)= \beta_{t+1}(j+1) \times a_{j,j+1} \times b_{j} (O_t)$$

$$\hspace{3cm} + \beta_{t+1}(j) \times a_{j,j} \times b_{j} (O_t)$$

各gridの計算式を以下に示す．

$\beta_4 (3)=1.0$

$\beta_3(2)= \beta_4(3) \times a_{2,3} \times b_2 (O_3) = \beta_4(3) \times a_{2,3} \times b_2 (\gamma) \\ \hspace{1.1cm} = 1.0 \times 0.9 \times 0.8 = 0.72$

$\beta_2(2)= \beta_3(2) \times a_{2,2} \times b_2 (O_2) = \beta_3(2) \times a_{2,2} \times b_2 (\beta) \\ \hspace{1.1cm} = 0.72 \times 0.1 \times 0.1 = 0.0072$

$\beta_2(1)= \beta_3(2) \times a_{1,2} \times b_1 (O_2) = \beta_3(2) \times a_{1,2} \times b_1 (\beta) \\ \hspace{1.1cm} = 0.72 \times 0.4 \times 0.3 = 0.0864$

$\beta_1(1)= \beta_2(2) \times a_{1,2} \times b_1 (O_1) + \beta_2(1) \times a_... ...4 \times 0.6 \times 0.4 \\ \hspace{1.1cm} = 0.021888 (\fallingdotseq 0.02189)$

$\beta_1(0)= \beta_2(1) \times a_{0,1} \times b_0 (O_1) = \beta_2(1) \times a_{... ...space{1.1cm} = 0.0864 \times 0.3 \times 0.7 =0.018144 (\fallingdotseq 0.01814)$

$\beta_0(0)= \beta_1(1) \times a_{0,1} \times b_0 (O_0) + \beta_1(0) \times a_... ...\times 0.7 \times 0.7 \\ \hspace{1.1cm} = 0.01348704 (\fallingdotseq 0.01349)$

なお　Backwordアルゴリズムにおいて最後に計算するgrid $\beta_0(0)$ の値と Forwardアルゴリズムにおいて最後に計算するgrid $\alpha_4 (3)$ の値は，同じになる． つまり，以下の式に着目してもらいたい．

$尤度= \beta_0(0) = \alpha_4 (3) =0.01349$

図: backward アルゴリズム