記法

$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}$$