Forward Algorithm
記法
\(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}
\]