記法

\(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}
\]