Forward-Backward アルゴリズム

HMM $\lambda (\pi,A,B)$が観測系列 $O=o_1,o_2,...,o_T$を生成す る尤度 $P(O \mid \lambda)$を求めるには、まず長さ$T$の全ての状 態系列に対して、確率の計算を行なうことが考えられる。 可能な状態系列 $S=s_0,s_1,...,s_T$が$O$を生成する確率を次のように定義する。

$$P(O \mid S,\lambda ) = \prod _{t=1}^T P(O_t \mid s_t,\lambda )$$ (2.5)

各観測は、確率的に独立とみなして、

$$P(O \mid S,\lambda ) = b_{s_0 s_1} (o_1) \cdot b_{s_1 s_2} (o_2) \cdot ... \cdot b_{s_{T-1} s_T}(o_T)$$ (2.6)

一方、状態系列$S$の生成確率は次のようになる。

$$P(S \mid \lambda ) = \pi_{s_1} a_{s_1 s_2} a_{s_2 s_3} ... a_{s_{T-1} s_T}$$

$$= a_{s_0 s_1} a_{s_1 s_2} ... a_{s_{T-1} s_T}$$ (2.7)

したがって、観測系列$O$のモデル$\lambda$における生成確率（尤 度）は、

$$P(O \mid \lambda ) = \sum_{all S} P(O \mid \lambda ) P(O \mid S,\lambda )$$

$$= \sum_{all s_0...s_T} \pi_{s_0} a_{s_0 s_1} b_{s_0 s_1} (o_1) \cdo... ..._1 s_2} b_{s_1 s_2} (o_2) \cdot ... \cdot a_{s_{T-1} s_T} b_{s_{T-1} s_T} (o_T)$$ (2.8)

この方法による計算量はO($2TN^T$)になり、実質的に計算不可能で ある。計算量を削減した実用的なアルゴリズムとして forward-backward アルゴリズムがある。