記法

\(x_{i…j}\) （ただし \(i \le j\)）は \(i\) 番目から \(j\) 番目の要素からなる部分列 \(x_i\ldots x_j\)を表す．

Viterbi変数（Viterbi AlgorithmのDP変数）

Viterbi Algorithmは，出力列 \(x_{1…T}=x_1\ldots x_T\)との同時確率が最大の状態列 \(\hat{h_{1…T}}=\hat{h_1}\ldots\hat{h_T}\)を推定する．
Viterbi変数 \(v_i(t)\) は，時刻 \(t\) における状態が \(s_i\) である場合の出力部分列 \(x_{1…t}\) と状態部分列 \(h_{1…t}\) の同時確率の最大値である．
\[
v_i(t) \equiv \max_{h_{1…t-1}|h_t=s_i} P(x_{1…t},h_{1…t})
\]
\(\max_{h_{1…t-1}|h_t=s_i}\)は，\(h_t=s_i\)の条件のもとで\(h_{1…t-1}\)について最大をとる記号である．時刻 \(t\) における状態が \(s_i\) である場合の条件付き確率ではないことに注意せよ．

Viterbi Algorithm

\[
\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\begin{eqnarray}
\mbox{初期化}: &(t=0)& v_0(0)=1; v_i(0)=0 \mbox{ for all } i>0\\
\mbox{再帰}: &(t=1,\ldots,T)& v_j(t)=e_j(x_t) \max_i(v_i(t-1)a_{ij})\\
& & ptr_t(j)=\argmax_i(v_i(t-1)a_{ij})\\
\mbox{終了処理}: & & P(x_{1…T},\hat{h_{1…T}})=\max_i(v_i(T))\\
& & \hat{h_T}=\argmax_i(v_o(T))\\
\mbox{トレースバック}: &(t=T,\ldots,1)& \hat{h_{t-1}}=ptr_t(\hat{h_t})
\end{eqnarray}
\]