Viterbiアルゴリズム (Viterbi algorithm)

隠れMarkovモデル \(\lambda=(A,B,\pi)\) が既知の場合に,与えられた観測系列 \(O=O_1 O_2 \cdots O_T\) から,最尤推定になる状態系列 \(Q=q_1 q_2 \ldots q_T\) を動的計画法で求めるアルゴリズム

入力

出力

定義

アルゴリズム

  1. 初期化:
    • \(\delta_1(i)=\pi_i b_i(O_1),\;i=1,\ldots,N\)
    • \(\psi_1(i)=0\)
  2. 再帰:
    • \(\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\)
  3. 終了:
    • \(P^\ast=\;\max_{1\le i\le N}\; \delta_T(i)\)
    • \(q^\ast_T=\arg\max_{1\le i\le N}\; \delta_T(i)\)
  4. パス(状態系列)のバックトラック:
    • \(q_t^\ast=\psi_{t+1}(q_{t+1}^\ast),\;t=T{-}1,T{-}2,\ldots,1\)

--しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:26