記法

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

Forward変数（Forward AlgorithmのDP変数）

Forward Algorithmは，出力列 $x_{1…T}=x_1\ldots x_T$が得られる確率を計算する．
Forward変数 $f_i(t)$ は，時刻 $t$ における状態が $s_i$ である場合の出力部分列 $x_{1…t}$ の確率である．あらゆる状態部分列$h_{1…t}=h_1\ldots h_t$について，出力部分列と状態部分列の同時確率が合計される．
$$f_i(t) \equiv \sum_{h_{1…t-1}|h_t=s_i} P(x_{1…t},h_{1…t})$$
$\sum_{h_{1…t-1}|h_t=s_i}$は，$h_t=s_i$の条件のもとで$h_{1…t-1}$について和をとる記号である．

Forward Algorithm

$$\newcommand{\argmax}{\mathop{\rm argmax}\limits} \begin{eqnarray} \mbox{初期化}: &(t=0)& f_0(0)=1; f_i(0)=0 \mbox{ for all } i>0\\ \mbox{再帰}: &(t=1,\ldots,T)& f_j(t)=e_j(x_t) \sum_i f_i(t-1)a_{i,j}\\ \mbox{終了処理}: & & P(x_{1…T})=\sum_i f_i(T) \end{eqnarray}$$