これらのキーワードがハイライトされています:Viterbiアルゴリズム
隠れMarkovモデル \(\lambda=(A,B,\pi)\) が既知の場合に,与えられた観測系列 \(O=O_1 O_2 \cdots O_T\) から,最尤推定になる状態系列 \(Q=q_1 q_2 \ldots q_T\) を動的計画法で求めるアルゴリズム.
入力
- 隠れMarkovモデル:\(\lambda=(A,B,\pi)\)
- 状態:\(\{S_i\}_i^N\)
- 遷移確率分布 \(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]\)
- 観測系列:観測されたシンボルの系列 \(O=O_1 O_2 \cdots O_T\)
出力
- 最尤推定した状態系列 \(q_1^\ast,q_2^\ast,\ldots,q_T^\ast\)
定義
- 時刻 \(t\) までの観測系列と \(q_t=S_i\) を出力する,最も確率の高いパス
\(\delta_t(i)=\;\max_{q_1,q_2,\ldots,q_{t-1}}\;\Pr[q_1 q_2 \cdots q_t=S_i, O_1 O_2 \ldots O_t|\lambda]\)
- 時刻 \(t\) で \(\delta_t(i)\) を最大化した状態 \(\psi_t(i)\)
アルゴリズム
- 初期化:
- \(\delta_1(i)=\pi_i b_i(O_1),\;i=1,\ldots,N\)
- \(\psi_1(i)=0\)
- 再帰:
- \(\delta_t(j)=\;\max_{1\le i\le N}\;[\delta_{t-1}(i)a_{ij}]b_j(O_t),\;\;t=2,\ldots,T,\;j=1,\ldots,N\)
- \(\psi_t(j)=\arg\max_{1\le i\le N}\;[\delta_{t-1}(i)a_{ij}],\;\;t=2,\ldots,T,\;j=1,\ldots,N\)
- 終了:
- \(P^\ast=\;\max_{1\le i\le N}\; \delta_T(i)\)
- \(q^\ast_T=\arg\max_{1\le i\le N}\; \delta_T(i)\)
- パス(状態系列)のバックトラック:
- \(q_t^\ast=\psi_{t+1}(q_{t+1}^\ast),\;t=T{-}1,T{-}2,\ldots,1\)
--しましま
関連項目†
リンク集†
関連文献†