Viterbiアルゴリズム (Viterbi algorithm)

隠れ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)\)

アルゴリズム

  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 (2494d)