Baum-Welchアルゴリズム

これらのキーワードがハイライトされています：Markovモデル マルコフモデル Markov連鎖 マルコフ連鎖

Baum-Welchアルゴリズム (Baum-Welch algorithm)†

与えられた観測系列 $O=O_1 O_2 \cdots O_T$ から，EMアルゴリズムで隠れMarkovモデルのパラメータ $\lambda=(A,B,\pi)$ を推定するアルゴリズム．

入力

観測系列：観測されたシンボルの系列 $O=O_1 O_2 \cdots O_T$

出力

隠れMarkovモデル：\lambda=(A,B,\pi)
- 遷移確率分布 $A$ ：1次のモデルを想定し，状態 $S_i$ から状態 $S_j$ へ遷移する確率 $a_{ij}=\Pr[q_{t+1}=S_j|q_t=S_i]$
- 観測シンボル確率分布 $B$ ：状態 $S_j$ でシンボル $v_k$ が出力される確率 $b_j(k)=\Pr[v_k|q_t=S_j]$
- 初期状態分布 $\pi$ ：時刻 $t=1$ で状態 $S_i$ にある確率 $\pi_i=\Pr[q_1=S_i]$

定義

時刻 $t$ で状態 $S_i$ にあり，その時刻までの系列を出力する確率 $\alpha_t(i)=\Pr[O_1,O_2,\ldots,O_t,q_t=S_i|\lambda]$
時刻 $t$ で状態 $S_i$ にいるとして，時刻 $t+1$ から最後までの系列を出力する確率 $\beta_t(i)=\Pr[O_{t+1},O_{t+2},\ldots,O_T|q_t=S_i,\lambda]$
時刻 $t$ で状態 $S_i$ にあり，次の時刻 $t+1$ で状態 $S_j$ にいる確率 $\xi_t(i,j)=\Pr[q_t=S_i,q_{t+1}=S_j|O,\lambda]$
時刻 $t$ で状態 $S_i$ にいる確率 $\gamma_t(i)=\Pr[q_t=S_i|O,\lambda]$

↑

アルゴリズム †

モデル $\lambda=(A,B,\pi)$ を均一分布などで初期化．以下のステップを収束するまで反復する．

E-ステップ

現在のモデルを使って ξ や γ の期待値を計算．

αの計算 $\alpha_1(i)=\pi_ib_i(O_1)$ $\alpha_{t+1}(j)=\Bigl[\sum_{i=1}^N \alpha_t(i) a_{ij}\Bigr]b_j(O_{t+1})$
βの計算 $\beta_T(i)=1$ $\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(O_{t+1})\beta_{t+1}(j)$
ξの計算 $\Pr[O|\lambda]=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(O_{t+1})\beta_{t+1}(j)$ $\xi_t(i,j)=\frac{\alpha_t(i)a_{ij}b_j(O_{t+1})\beta_{t+1}(j)}{\Pr[O|\lambda]}$
γの計算 $\gamma_t(i)=\sum_{j=1}^N \xi_t(i,j)$

M-ステップ

モデル $\lambda=(A,B,\pi)$ を更新． $\pi_i=\gamma_1(i)$ $a_{ij}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}$ $b_j(k)=\frac{\sum_{t=1,\mbox{s.t.}O_t=v_k}^T \gamma_t(j)}{\sum_{t=1}^T \gamma_t(j)}$