Viterbiアルゴリズム

Viterbiアルゴリズムは，シンボル列$O$を生成したモデル$M$における最適 な状態遷移系列(最適経路)と，その経路上での確率を求めるためのアルゴリ ズムであり，本実験では，HMMの初期モデルの作成，音節境界位置の計算に使 われている．シンボル列 $o^{T}_{1}=o_{1} ... o_{T}$に対する 最適経路は，状態遷移確率 $P(o^{T}_{1},q^{T}_1\vert M)$を最大にするような経路 $q^{T}_{1}=q_{1} ... q_{T}$である．Viterbiアルゴリズムの詳細 について参考文献[12]より引用し，説明する．

時刻tにおいて，状態 $q_{i}(1 \leq i \leq N)$がシンボル列 $o^{t}_{1}=o_{1},o_{2}, …, o_{T}$生成する確率の最大値 $\delta (i)$を求める．

$$\delta_{t}(i) = \max_{q^{t}_{1}}P(q^{t-1}_{1},X_{t} = q_{i},o^{t}_{1}｜M)$$

$\delta_{t}(i)$ は，以下のように再帰的に計算できる．

$$\delta_{t+1}(i) = \max_{i}[\delta_{t}a_{ij}]b_{j}(o_{t+1})$$

ここで，$a_{ij}$ は状態 $q_{i}$ から $q_{j}$ に遷移する確率， $b_{i}(o_{t})$ は状態 $q_{i}$ でシンボル $o_{t}$ を出力する確率で ある．
また，状態遷移系列を復元するために， $\delta_{t+1}(i)$ を与える直前の状 態 $i$ を $\psi(・)$ に記憶しておく．

$$\psi_{t+1}(j) = \arg\max_{i}[\delta_{t}(i)a_{ij}]$$

再帰計算が終了したら，時刻 $t = T$ における最適経路を， $t = T - 1, ... , 1$ において，

$$\hat{q}_{t} = \psi_{t+1}(\hat{q}_{t+1})$$

により復元する．ただし， $\hat{q}_{T} = \arg\max_{i} \delta_{T}(i)$ で ある．

以上の操作により，最適経路 $q^{T}_{1} = \hat{q}_{1} … \hat{q}_{T}$ が 求められる．