前方後方アルゴリズム

前方後方アルゴリズムは、隠れマルコフモデルのための推論アルゴリズムであり、一連の観測値／放出値が与えられた場合に、すべての隠れ状態変数の事後周辺分布を計算します。${\displaystyle o_{1:T}:=o_{1},\dots ,o_{T}}$つまり、すべての隠れ状態変数に対して計算します。${\displaystyle X_{t}\in \{X_{1},\dots ,X_{T}\}}$分布${\displaystyle P(X_{t}\ |\ o_{1:T})}$この推論タスクは通常、平滑化と呼ばれます。このアルゴリズムは、動的計画法の原理を利用して、事後周辺分布を取得するために必要な値を2回のパスで効率的に計算します。最初のパスは時間的に前進し、2回目のパスは時間的に後退します。そのため、フォワードバックワードアルゴリズムと呼ばれます。

順方向・逆方向アルゴリズムという用語は、シーケンスモデルに対して順方向・逆方向の処理を行うアルゴリズム全般を指す場合にも用いられる。この意味で、本稿の残りの部分で説明するアルゴリズムは、このクラスの特定の一例のみを対象とする。

最初のパスでは、フォワードバックワードアルゴリズムは、すべての$t ∈ {1, \dots , T}$最初の条件が与えられた場合に特定の状態になる確率${\displaystyle t}$シーケンス内の観測値、つまり${\displaystyle P(X_{t}\ |\ o_{1:t})}$2回目の処理では、アルゴリズムは一連の後方確率を計算し、任意の開始点から残りの観測値を観測する確率を示します。${\displaystyle t}$つまり${\displaystyle P(o_{t+1:T}\ |\ X_{t})}$これら2つの確率分布を組み合わせることで、観測シーケンス全体が与えられた場合の、任意の時点における状態の分布を得ることができます。

${\displaystyle P(X_{t}\ |\ o_{1:T})=P(X_{t}\ |\ o_{1:t},o_{t+1:T})\propto P(o_{t+1:T}\ |\ X_{t})P(X_{t}|o_{1:t})}$

最後のステップは、ベイズの定理と条件付き独立性の適用から導かれる。${\displaystyle o_{t+1:T}}$そして$o1:t$与えられた${\displaystyle X_{t}}$。

上記で概説したように、このアルゴリズムは3つのステップから構成されます。

1. 前方確率の計算
2. 逆確率の計算
3. 平滑化された値を計算しています。

順方向ステップと逆方向ステップは、「順方向メッセージ伝達」と「逆方向メッセージ伝達」とも呼ばれます。これらの用語は、一般的な信念伝播アプローチで使用されるメッセージ伝達に由来します。シーケンス内の各観測において、次の観測での計算に使用される確率が計算されます。平滑化ステップは、逆方向パス中に同時に計算できます。このステップにより、アルゴリズムは過去の出力観測を考慮に入れ、より正確な結果を計算できます。

前方後方アルゴリズムは、任意の時点における最も可能性の高い状態を見つけるために使用できます。ただし、最も可能性の高い状態のシーケンスを見つけるために使用することはできません（ビタビアルゴリズムを参照）。

以下の説明では、確率分布の代わりに確率値の行列を使用します。ただし、順方向・逆方向アルゴリズムは、一般的に連続確率モデルと離散確率モデルの両方に適用できます。

与えられた隠れマルコフモデルに関連する確率分布を、以下のように行列表記に変換します。遷移確率${\displaystyle \mathbf {P} (X_{t}\mid X_{t-1})}$与えられた確率変数の${\displaystyle X_{t}}$隠れマルコフモデルにおけるすべての可能な状態を表す行列は、${\displaystyle \mathbf {T} }$列インデックス${\displaystyle j}$ターゲット状態と行インデックスを表します${\displaystyle i}$開始状態を表します。行ベクトル状態からの遷移$\displaystyle \mathbf {\pi _{t}} }$増分行ベクトル状態へ$\displaystyle \mathbf {\pi _{t+1}} }$次のように書かれています${\displaystyle \mathbf {\pi _{t+1}} =\mathbf {\pi _{t}} \mathbf {T} }$以下の例は、各ステップ後に同じ状態にとどまる確率が70%、他の状態に遷移する確率が30%であるシステムを表しています。遷移行列は次のようになります。

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

典型的なマルコフモデルでは、状態ベクトルにこの行列を乗算して、次の状態の確率を求めます。隠れマルコフモデルでは状態は未知であり、代わりに可能な状態に関連付けられたイベントを観測します。イベント行列は次の形式になります。

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

特定の状態が与えられた場合にイベントを観測する確率を提供します。上記の例では、状態 1 の場合、イベント 1 は 90% の確率で観測され、イベント 2 はこの状態では 10% の確率で発生します。対照的に、状態 2 の場合、イベント 1 は 20% の確率でしか観測されず、イベント 2 は 80% の確率で発生します。システムの状態を表す任意の行ベクトル (${\displaystyle \mathbf {\pi } }$) の場合、事象 j を観測する確率は次のようになります。

${\displaystyle \mathbf {P} (O=j)=\sum _{i}\pi _{i}B_{i,j}}$

特定の状態が観測されたイベント j につながる確率は、状態行ベクトル (${\displaystyle \mathbf {\pi } }$）観測行列（${\displaystyle \mathbf {O_{j}} =\mathrm {diag} (B_{*,o_{j}})}$対角要素のみを含む行列。上記の例を続けると、イベント1の観測行列は次のようになります。

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

これにより、新しい非正規化確率状態ベクトルを計算できます。${\displaystyle \mathbf {\pi '} }$ベイズの定理により、各要素の尤度で重み付け${\displaystyle \mathbf {\pi } }$生成されたイベント1：

${\displaystyle \mathbf {\pi '} =\mathbf {\pi } \mathbf {O_{1}} }$

これで、この一般的な手順を、我々の観測系列に特化したものにすることができる。初期状態ベクトルを仮定すると${\displaystyle \mathbf {\pi } _{0}}$（これは順方向・逆方向手順の繰り返しによってパラメータとして最適化できる）から始め、${\displaystyle \mathbf {f_{0:0}} =\mathbf {\pi } _{0}}$そして、最初の観測値の尤度に基づいて状態分布と重みを更新します。

${\displaystyle \mathbf {f_{0:1}} =\mathbf {\pi } _{0}\mathbf {T} \mathbf {O_{o_{1}}} }$

このプロセスは、以下の方法を用いて追加の観察を行いながら進めることができます。

$\displaystyle \mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

この値は、前方非正規化確率ベクトルです。このベクトルの i 番目の要素は、以下の情報を提供します。

$\displaystyle \mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}$

通常、各ステップで確率ベクトルを正規化し、その要素の合計が1になるようにします。そのため、各ステップでスケーリング係数が導入されます。

$\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

どこ${\displaystyle \mathbf {{\hat {f}}_{0:t-1}} }$前のステップからのスケーリングされたベクトルを表し、${\displaystyle c_{t}}$これは、結果として得られるベクトルの要素の合計が1になるようにするスケーリング係数を表します。スケーリング係数の積は、最終状態に関係なく、与えられた事象を観測する全確率です。

$${\displaystyle \mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})=\prod _{s=1}^{t}c_{s}}$$

これにより、スケーリングされた確率ベクトルを次のように解釈することができます。

${\displaystyle \mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } _{0})}$

したがって、スケーリング係数の積は、時刻 t までに与えられたシーケンスを観測する全確率を与え、スケーリングされた確率ベクトルは、この時刻に各状態にある確率を与えることがわかります。

同様の手順で後方確率を求めることができます。これらは以下の確率を提供することを目的としています。

${\displaystyle \mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})}$

つまり、ここでは特定の状態から始めると仮定します（${\displaystyle X_{t}=x_{i}}$）、そして今、私たちはこの状態から将来起こるすべての事象を観測する確率に関心があります。初期状態は既知であると仮定されているため（つまり、この状態の事前確率は100%）、次のように始めます。

${\displaystyle \mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}}$

ここで注目すべきは、前方確率では行ベクトルを使用していたのに対し、ここでは列ベクトルを使用している点です。次に、以下の方法で逆算することができます。

${\displaystyle \mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}} }$

このベクトルも正規化して要素の合計が1になるようにすることもできますが、通常はそうしません。各要素は特定の初期状態が与えられた場合の将来のイベントシーケンスの確率を含んでいることに注目すると、このベクトルを正規化することは、将来のイベントが与えられた場合の各初期状態の尤度を求めるためにベイズの定理を適用することと同等になります（最終状態ベクトルの事前分布が一様であると仮定した場合）。しかし、同じ方法でこのベクトルをスケーリングする方が一般的です。${\displaystyle c_{t}}$前方確率計算で使用される定数。 ${\displaystyle \mathbf {b_{T:T}} }$スケーリングはされませんが、後続の操作では以下を使用します。

${\displaystyle \mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}} }$

どこ${\displaystyle \mathbf {{\hat {b}}_{t:T}} }$これは、前述のスケーリングされたベクトルを表します。この結果、スケーリングされた確率ベクトルは、後方確率と次の関係にあることがわかります。

${\displaystyle \mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}}$

これは、これらの値を掛け合わせることで、特定の時刻 t において各状態にある確率の合計を求めることができるため、非常に有用です。

${\displaystyle \mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } _{0})={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } _{0})}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)}$

これを理解するためには、次の点に注目します。${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$与えられた事象を状態を通過する形で観測する確率を提供する${\displaystyle x_{i}}$時刻 t において。この確率には、時刻 t までのすべてのイベントをカバーする前方確率と、将来のすべてのイベントを含む後方確率が含まれます。これが、我々の式で求めている分子であり、この値を正規化して、次の確率のみを抽出するために、観測シーケンスの総確率で割ります。${\displaystyle X_{t}=x_{i}}$これらの値は、前方確率と後方確率を組み合わせて最終的な確率を算出するため、「平滑化値」と呼ばれることもあります。

値${\displaystyle \mathbf {\gamma _{t}} (i)}$したがって、時刻 t において各状態にある確率が与えられます。そのため、任意の時点で最も可能性の高い状態を決定するのに役立ちます。「最も可能性の高い状態」という用語はやや曖昧です。最も可能性の高い状態は特定の時点で最も正しい可能性が高い状態ですが、個別に可能性の高い状態のシーケンスが最も可能性の高いシーケンスであるとは限りません。これは、各時点の確率が互いに独立して計算されるためです。状態間の遷移確率は考慮されていないため、2 つの時点 (t と t+1) で、どちらもその時点で最も可能性の高い状態でありながら、同時に発生する確率が非常に低い状態が得られる可能性があります。${\displaystyle \mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})}$観測シーケンスを生成した最も可能性の高い状態のシーケンスは、ビタビアルゴリズムを使用して見つけることができます。

この例では、Russell & Norvig 2010 第15章 567ページにある傘の世界を基にしています。この世界では、他人が傘を持っているか持っていないかの観察に基づいて天気を推測したいと考えています。天気には2つの状態があると仮定します。状態1 = 雨、状態2 = 雨なし。天気は毎日同じ状態が続く確率が70%、変化する確率が30%であると仮定します。遷移確率は次のようになります。

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

また、各状態において、2つの事象のうちいずれか1つが発生すると仮定します。事象1＝傘あり、事象2＝傘なし。各状態におけるこれらの事象の発生条件付き確率は、確率行列で与えられます。

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

次に、次のような一連の出来事を観察します：{傘、傘、傘なし、傘、傘}。これを計算では次のように表します。

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

ご了承ください${\displaystyle \mathbf {O_{3}} }$「傘をさしていない」という点が他のものと異なる。

前方確率を計算する際には、まず以下から始めます。

${\displaystyle \mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}}$

これは、観測前に天候がどの状態にあるか分からないことを示す、事前状態ベクトルです。状態ベクトルは行ベクトルとして与えられるべきですが、以下の計算を読みやすくするために、行列の転置行列を使用します。計算式は次の形式で表されます。

${\displaystyle (\mathbf {{\hat {f}}_{0:t}} )^{T}=c_{t}^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}}$

の代わりに：

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}} }$

変換行列も転置されていることに注意してください。ただし、この例では転置行列は元の行列と等しくなります。これらの計算を実行し、結果を正規化すると、次のようになります。

${\displaystyle (\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

後方確率については、まず以下から始めます。

${\displaystyle \mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}}$

すると、（逆順の観測値を使用し、異なる定数で正規化して）以下の値を計算できます。

${\displaystyle \mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

最後に、平滑化された確率値を計算します。これらの結果も、後方確率をスケーリングしなかったため、エントリの合計が 1 になるようにスケーリングする必要があります。${\displaystyle c_{t}}$は既に見つかっています。したがって、上記の逆確率ベクトルは、将来の観測結果が与えられた場合の時刻 t における各状態の尤度を実際に表しています。これらのベクトルは実際の逆確率に比例するため、結果はさらに 1 回スケーリングする必要があります。

${\displaystyle (\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\circ {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\circ {\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.4846\\0.0741\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\circ {\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.3324\\0.0728\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\circ {\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1246\\0.2806\end{pmatrix}}={\begin{pmatrix}0.3075\\0.6925\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\circ {\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4584\\0.1003\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\circ {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

値に注目してください${\displaystyle \mathbf {\gamma _{0}} }$に等しい${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$そしてそれは${\displaystyle \mathbf {\gamma _{5}} }$に等しい${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$これは当然のことながら、${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$そして${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$初期状態ベクトルと最終状態ベクトル（それぞれ）に対して一様な事前分布から始め、すべての観測値を考慮に入れます。ただし、${\displaystyle \mathbf {\gamma _{0}} }$等しくなるのは${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$初期状態ベクトルが一様事前分布（つまり、すべてのエントリが等しい）を表す場合。そうでない場合${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$最も可能性の高い初期状態を見つけるには、初期状態ベクトルと組み合わせる必要があります。したがって、順方向確率だけで最も可能性の高い最終状態を計算するのに十分であることがわかります。同様に、逆方向確率を初期状態ベクトルと組み合わせることで、観測結果に基づいて最も可能性の高い初期状態を求めることができます。順方向確率と逆方向確率を組み合わせるだけで、初期点と最終点の間の最も可能性の高い状態を推測できます。

上記の計算から、3日目を除くすべての日において最も可能性の高い気象状態は「雨」であることがわかります。しかし、これらの計算はそれ以上のことを教えてくれます。なぜなら、異なる時間における各状態の確率を定量化する方法を提供してくれるからです。おそらく最も重要なのは、${\displaystyle \mathbf {\gamma _{5}} }$これは、観測シーケンスの終了時点における状態ベクトルに関する我々の知識を定量化するものです。そして、これを用いて、明日の様々な気象状態の確率や、傘を目にする確率を予測することができます。

前方後方アルゴリズムは、時間計算量で実行されます。${\displaystyle O(S^{2}T)}$宇宙空間で${\displaystyle O(ST)}$、 どこ${\displaystyle T}$は時間シーケンスの長さであり、${\displaystyle S}$は状態アルファベットの記号の数です。^{[ 1 ]} このアルゴリズムは定数空間で実行でき、時間計算量は です。${\displaystyle O(S^{2}T^{2})}$各ステップで値を再計算することによって。^{[ 2 ]}比較のために、総当たり手順では考えられるすべての値を生成することになる。${\displaystyle S^{T}}$状態シーケンスを計算し、各状態シーケンスと観測された一連のイベントとの同時確率を計算すると、時間計算量は${\displaystyle O(T\cdot S^{T})}$現実的な問題では、考えられる隠れノードのシーケンスの数が非常に多いため、総当たり攻撃は現実的に不可能である。

一般的な順方向・逆方向アルゴリズムの改良版であるアイランドアルゴリズムは、メモリ使用量の削減と引き換えに実行時間を長くし、${\displaystyle O(S^{2}T\log T)}$時間と${\displaystyle O(S\log T)}$さらに、プロセスモデルを反転させてメモリを取得することが可能です。${\displaystyle O(S)}$空間、${\displaystyle O(S^{2}T)}$時間アルゴリズムですが、逆プロセスが存在しないか、条件が悪い可能性があります。^{[ 3 ]}

さらに、計算するためのアルゴリズムが開発されている。${\displaystyle \mathbf {f_{0:t+1}} }$固定ラグ平滑化（FLS）アルゴリズムなどのオンライン平滑化によって効率的に処理される。^{[ 4 ]}

アルゴリズムforward_backwardの入力: guessState int sequenceIndex出力:結果sequenceIndexがシーケンスの末尾を超えている場合は 1を 返す。 ( guessState , sequenceIndex )が以前に見られた場合は保存された結果を返す。結果:= 0 各隣接状態 n について: result := result + ( guessStateから遷移確率n は、 sequenceIndex にある指定された観測要素です。 × Backward(n, sequenceIndex + 1) ( guessState、sequenceIndex )の結果を保存します 結果を返す

Pythonプログラミング言語で表現されたHMM（ビタビアルゴリズムと同様）が与えられています。

状態= ( "健康" , "発熱" )終了状態= "E"観測値= ( "正常 " , "寒い " , "めまい" )開始確率= { "健康" : 0.6 , "発熱" : 0.4 }transition_probability = { "Healthy" : { "Healthy" : 0.69 , "Fever" : 0.3 , "E" : 0.01 }, "Fever" : { "Healthy" : 0.4 , "Fever" : 0.59 , "E" : 0.01 }, }emission_probability = { "Healthy" : { "normal" : 0.5 , "cold" : 0.4 , "dizzy" : 0.1 }, "Fever" : { "normal" : 0.1 , "cold" : 0.3 , "dizzy" : 0.6 }, }

フォワードバックワードアルゴリズムの実装は、次のように記述できます。

def fwd_bkw ( observations , states , start_prob , trans_prob , emm_prob , end_st ): """フォワードバックワードアルゴリズム。""" # アルゴリズムのフォワード部分fwd = [] for i , observation_i in enumerate ( observations ): f_curr = {} for st in states : if i == 0 : # フォワード部分の基本ケースprev_f_sum = start_prob [ st ] else : prev_f_sum = sum ( f_prev [ k ] * trans_prob [ k ][ st ] for k in states )f_curr [ st ] = emm_prob [ st ][ observation_i ] * prev_f_sumfwd.append ( f_curr ) f_prev = f_curr​​p_fwd = sum ( f_curr [ k ] * trans_prob [ k ][ end_st ] for k in states )# アルゴリズムの逆方向部分bkw = [] for i , observation_i_plus in enumerate ( reversed ( observations [ 1 :] + ( None ,))): b_curr = {} for st in states : if i == 0 : # 逆方向部分の基本ケースb_curr [ st ] = trans_prob [ st ][ end_st ] else : b_curr [ st ] = sum ( trans_prob [ st ][ l ] * emm_prob [ l ][ observation_i_plus ] * b_prev [ l ] for l in states )bkw.insert ( 0 , b_curr ) b_prev = b_curr​​p_bkw = sum ( start_prob [ l ] * emm_prob [ l ][ observations [ 0 ]] * b_curr [ l ] for l in states )# 2つの部分をマージするposterior = [] for i in range ( len ( observations )): posterior . append ({ st : fwd [ i ][ st ] * bkw [ i ][ st ] / p_fwd for st in states })assert p_fwd == p_bkw return fwd , bkw , posterior

この関数はfwd_bkw、次の引数を取ります。 xは観測のシーケンス（例['normal', 'cold', 'dizzy']：） states、 は隠れ状態のセット、 a_0は開始確率、 aは遷移確率、 およびeは放出確率です。

コードの簡潔さのために、観測シーケンスはx空ではなく、 すべての状態 i,j に対して および が定義されているa[i][j]と仮定します。e[i][j]

実行例では、順方向・逆方向アルゴリズムを以下のように使用します。

def example (): return fwd_bkw ( observations , states , start_probability , transition_probability , emission_probability , end_state , )

>>> for line in example (): ... print ( * line ) ... {'Healthy': 0.3, 'Fever': 0.04000000000000001} {'Healthy': 0.0892, 'Fever': 0.03408} {'Healthy': 0.007518, 'Fever': 0.028120319999999997} {'Healthy': 0.0010418399999999998, 'Fever': 0.00109578} {'Healthy': 0.00249, 'Fever': 0.00394} {'Healthy': 0.01, 'Fever': 0.01} {'Healthy': 0.8770110375573259, '発熱': 0.1229889624426741} {'健康': 0.623228030950954, '発熱': 0.3767719690490461} {'健康': 0.2109527048413057, '発熱': 0.7890472951586943}

• バウム・ウェルチアルゴリズム
• ビタビアルゴリズム
• BCJRアルゴリズム

• Lawrence R. Rabiner、「隠れマルコフモデルと音声認識における応用例に関するチュートリアル」、Proceedings of the IEEE、77（2）、p.  257–286、1989年2月。10.1109/5.18626
• ローレンス・R・ラビナー、BH Juang（1986年1月）。 「隠れマルコフモデルの紹介」。IEEE ASSP マガジン: 4–15。
• ユージン・チャーニアック（1993）。統計的言語学習。マサチューセッツ州ケンブリッジ：MIT Press。ISBN 978-0-262-53141-2。
• スチュアート・ラッセル、ピーター・ノーヴィグ（2010）。人工知能：現代的アプローチ 第3版。ニュージャージー州アッパーサドルリバー：ピアソン・エデュケーション／プレンティス・ホール。ISBN 978-0-13-604259-4。

• 順方向・逆方向アルゴリズムを教えるためのインタラクティブなスプレッドシート（​​スプレッドシートと、手順を追って解説した記事）
• 前方後方アルゴリズムを含む隠れマルコフモデルのチュートリアル
• Javaで実装されたAIアルゴリズム集（HMMおよびフォワード・バックワードアルゴリズムを含む）