スケーリング

forward-backward アルゴリズムによって、 $\alpha _t(i)$ や $\beta_t (i)$ を求める際、入力系列が長いために、計算が進むにつれてこれらの値が小さくなり、計算機で扱える最小値よりも小さくなることがある（アンダーフロー）。特にシンボル出力確率が連続分布を仮定している連続分布型HMM（2.1.9章）において、この現象が顕著になる。このアンダーフローを回避するために、 $\alpha _t(i)$ や $\beta_t (i)$ に適当な係数を掛けたスケーリングという方法が知られている [60] [4]。スケーリングを導入したforward-backward アルゴリズムを以下に示す。

スケーリングを適用した forward probability

初期化
全ての状態 $i(1\leq i \leq N)$ に対して

$\begin{displaymath} \alpha^*_0(i) = \alpha_0(i) = \pi_i \end{displaymath}$ (2.17)

$\begin{displaymath} \alpha'_0(i) = C_0\alpha^*_0(i) = C_0\alpha_0(i) \end{displaymath}$ (2.18)

とする。
導出過程
時間軸に沿って、全ての状態 $i(1\leq i \leq N)$ に対し、 $\alpha'_t$ を次のように計算する。

$\begin{displaymath} \alpha^*_t(i) = \sum_{j=1}^N \alpha'_{t-1}(j)a_{ji}b_{ji}(o_t) \end{displaymath}$ (2.19)

$\begin{displaymath} \alpha'_t(i) = C_t\alpha^*_t(i) = C_0C_1...C_t\alpha_t(i) \end{displaymath}$ (2.20)

とする。
結果

$\begin{displaymath} P( O \mid \lambda ) = \prod_{t=0}^T C_t \end{displaymath}$ (2.21)

この式は積の形であるので、実際に計算する時はアンダーフローを回避するため対数で $P(O \mid \lambda)$ を算出する。

$\begin{displaymath} \log P( O \mid \lambda ) = \log \bigl( - \sum_{t=0}^T C_t \bigr) \end{displaymath}$ (2.22)

但し、時刻におけるスケーリング係数は以下の式で求める。

$\displaystyle C_t = \left[ \sum_{i=1}^N \alpha^*_t(i)\right] ^{-1}$

(2.23)

これにより、全時刻において

$\displaystyle \sum_{i=1}^N \alpha'_t(i) = 1$

(2.24)

となるため、forward probabilityのアンダーフローが回避できる。

スケーリングを適用したbackward probability

backward probability では forward probabilityで算出したスケーリング定数を用いる。

全ての状態 $i(1\leq i \leq N)$ に対して

$\begin{displaymath} \beta^*_T(i) = \beta_T(i) = 1 \end{displaymath}$ (2.25)

$\begin{displaymath} \beta'_T(i) = C_T\beta^*_T(i) = C_T\beta_T(i) \end{displaymath}$ (2.26)

とする。
時間軸に沿って、全ての状態 $i(1\leq i \leq N)$ に対し、 $\beta'_t$ を次のように計算する。

$\begin{displaymath} \beta^*_t(i) = \sum_{j=1}^N a_{ij}b_{ij}(o_{t+1})\beta'_{t+1}(j) \end{displaymath}$ (2.27)

$\begin{displaymath} \beta'_t(i) = C_t\beta^*_t(i) = C_tC_{t-1}...C_t\beta_t(i) \end{displaymath}$ (2.28)

スケーリング法を用いて算出した $\alpha'_t(i)$ 、 $\beta'_t(i)$ とスケーリングを用いない $\alpha _t(i)$ 、 $\beta_t (i)$ の間には次式のような関係がある。

$\displaystyle \alpha'_t(i)$	$\textstyle =$	$\displaystyle \prod_{\tau =1}^t C_{\tau} \alpha_t(i)$	(2.29)
$\displaystyle \beta'_t(i)$	$\textstyle =$	$\displaystyle \prod_{\tau =t}^t C_{\tau} \beta_t(i)$	(2.30)

スケーリング適用時のパラメータの再推定

スケーリングを行なう場合の各パラメータの更新式は次式となる。

初期状態確率

$\begin{displaymath} \bar{\pi_i } = \alpha'_0 (i) \beta'_0 (i) {\hspace{1cm}} (1 \leq i \leq N) \end{displaymath}$ (2.31)
状態遷移確率

$\begin{displaymath} \bar{a}_{ij} = \frac{\displaystyle{\sum_{t=1}^T \alpha'_{t... ...e{\sum_{t=1}^T \alpha'_{t-1} (i) \beta'_{t-1} (i) / C_{t-1}}} \end{displaymath}$ (2.32)
シンボル出力確率

$\begin{displaymath} \bar{b}_{ij} (o_t) = \frac{\displaystyle{\sum_{{t=1} \atop... ..._{t=1}^T \alpha'_{t-1} (i) a_{ij} b_{ij} (o_t) \beta'_t (j)}} \end{displaymath}$ (2.33)