Forwardアルゴリズム(トレリス法)

時刻$t$ の時に $o_1,o_2,...,o_t$ という観測系列を出力して，状態$j$ にいる 確率を次のように定義する．

$$\alpha_t (j) = P(o_1,o_2,...,o_t,s_t = j \mid \lambda)$$ (23)

$P(O \mid \lambda)$ は $\alpha_t (j)$ の漸化式を，次のように計算することによっ て求めることができる．

$$\alpha (i,t) = \left\{ \begin{array}{ll} \log \pi_{i} & (t = 0) \... ... \alpha (j,t-1) a_{ji} b_{ji}(y_t) & (t = 1, 2, \cdots ,T ) \end{array} \right.$$ (24)

これを計算して,最後に

$$P(y \vert M) = \sum_{i, s_i \in F} \alpha (i,T)$$ (25)

を求めれば良い.

このアルゴリズムでは，直前のフレームにおける確率 $\alpha_{t-1} (i)$ から $\alpha_t (j)$ $1 \leq j \leq N)$ を求める。

図4は，前記の図2のHMMがラベル系列$abb$ を出力する例に適応した例で ある. このように出力ラベル系列が対応する時間経過を横軸にして，各状態を縦に並べ て状態遷移を示した図で考えると理解しやすい． $\alpha_t (j)$ は，トレリス上の左上（初期状態）から右下（最終状態）に向かっ て順次求まる[4].

これを対数で計算するアルゴリズムを，ここではForwardアルゴリズムと呼ぶ．

図 4: トレリス上の $\alpha _t (i)$ の計算