前向きアルゴリズムはHMMで、文字列sが出力される確率を計算するアルゴリズムです。
HMMから出力される文字列sについて、前向きアルゴリズムでは、sを出力するすべてのパスを考慮し、sの出力確率を計算します。
数式化すると、次のようになります。
\[ P(s|\theta ) = \sum_{\pi}P(s,\pi | \theta) \]
この確率を求めるために、次のような漸化式を考えます。
状態がqkのときに、s[1..i]が出力される確率をfk(i)とすると、fl(i+1)は次のようになります。
この漸化式に基づいて、すべての状態遷移について計算します。そして、sの出力確率は次のように計算されます。