next up previous contents
次へ: Forward probability 上へ: HMM(Hidden Markov Model,隠れマルコフモデル) 戻る: HMMの基本アルゴリズム   目次


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$を生成する確率を次のように定義する。


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

各観測は、確率的に独立とみなして、
\begin{displaymath}
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)
\end{displaymath} (2.6)

一方、状態系列$S$の生成確率は次のようになる。
$\displaystyle P(S \mid \lambda )$ $\textstyle =$ $\displaystyle \pi_{s_1} a_{s_1 s_2} a_{s_2 s_3} ...
a_{s_{T-1} s_T}$  
  $\textstyle =$ $\displaystyle a_{s_0 s_1} a_{s_1 s_2} ... a_{s_{T-1} s_T}$ (2.7)

したがって、観測系列$O$のモデル$\lambda$における生成確率(尤 度)は、
$\displaystyle P(O \mid \lambda )$ $\textstyle =$ $\displaystyle \sum_{all S} P(O \mid \lambda ) P(O
\mid S,\lambda )$  
  $\textstyle =$ $\displaystyle \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 アルゴリズムがある。



Jin'ichi Murakami 平成13年1月5日