これらのキーワードがハイライトされています：Markovモデル マルコフモデル Markov連鎖 マルコフ連鎖
隠れ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
--しましま
関連項目†
リンク集†
関連文献†
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
