メモリ量および計算量を削減したBaum-Welchアルゴリズム

遷移出力型で状態数$N$のErgodic HMM のパラメータ $\lambda= ( \Pi,A,B)$を次のように定義した。

$\Pi = { \pi_N (i); i=1,..,N}$	初期状態確率
$A = { a_N (i,j); i=1,..,N, j=1,..,N }$	状態遷移確率
$B ={ b_N (i,j,k); i=1,..,N, j=1,..,N, k=1,..,V }$	シンボル出力確率

ただし$V$は語彙数。

本稿で提案するアルゴリズムは次の２つで構成される。

○ 1 小さいシンボル出力確率の削除

Baum-Welchアルゴリズムを使用してパラメータを推定するとき、シンボル出力 確率 $b_N(i,j,k)$ が閾値より小さいとき0にして、再推定およびメモリか ら削除する。

一般的には forward probability $\alpha_t (j)$ は以下の式で計算される。

$$\alpha_t(j)= [ \sum_{i} \alpha_{t-1}(i) a_N(i,j)] b_N(i,j,O_t)$$ (9.6)

この式の代わりに、本節では以下の式を使用する。

$$\alpha_t(j)= \left\{ \begin{array}{@{ }ll} \sum_{i} [ \alp... ...> C \\ 0.0 & if b_N(i,j,O_t) \leq C \end{array}\right.$$ (9.7)

これによりメモリ量および計算量が削減できる。実験では閾値$C$を $10.0 ^ { -300 }$にした。なお類似したアルゴリズムが文献[37]に おいて提案されている。

○ 2 状態数の逐次増加

状態数が大きなErgodic HMMのパラメータを再学習する場合、大量のメモリが 必要になる。そこで状態数を逐次的に増加させる。$N$状態のErgodic HMM の パラメータが既に推定されたとして、$2N$状態の Ergodic HMMの初期状態確率 および状態遷移確率の初期パラメータを次のように計算する。

$$\pi_{2N} (i) = 0.5 \times \pi_N (i/2) \hspace{2cm} i=1,..,2N$$ (9.8)

$$a_{2N} (i,j) = 0.5 \times a_N (i/2,j/2) \hspace{1.5cm} i=1,..,2N, j=1,..,2N$$ (9.9)

ここで $/$ は小数点以下切り上げを意味。

シンボル出力確率の初期パラメータは乱数を利用して次のように計算する。

$$b_{2N} (i,j,k) = b_N(i/2,j/2,k) \times random(i,j,k)$$ (9.10)

$$i=1,..,2N, j=1,..,2N, k=1,..,V$$

ただし $\sum_k b_{2N}(i,j,k)=1.0$ となるように正規化する。

状態数が大きなErgodic HMMのパラメータは以下のフローを繰り返すことで学習できる。

1. １状態のErgodic HMMを作成する。初期状態確率および状態遷移確率は1.0、シンボル出力確率は乱数とする。
2. 学習アルゴリズム○ 1を用いてHMMのパラメータの再推定をする。
3. 学習アルゴリズム○ 2を利用して、再推定された$N$状態のHMMのパラメータから$2N$状態のHMMの初期パラメータを計算する。
4. 学習アルゴリズム○ 1を用いてHMMのパラメータの再推定をする。