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)}\]

--しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-12-27 (木) 19:01:03 (1442d)