フォワード-バックワードアルゴリズム

フォワード-バックワード アルゴリズムは、隠れマルコフ モデルの推論 アルゴリズムであり、一連の観測/出力が与えられた場合にすべての隠れ状態変数の事後周辺分布を計算します。つまり、すべての隠れ状態変数について分布を計算します。この推論タスクは通常、スムージングと呼ばれます。このアルゴリズムは、動的計画法の原理を利用して、2 つのパスで事後周辺分布を取得するために必要な値を効率的に計算します。最初のパスは時間を順方向に進め、2 番目のパスは時間を逆方向に進めます。これが、フォワード-バックワード アルゴリズムという名前です。 ${\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})}$

フォワード-バックワード アルゴリズムという用語は、シーケンス モデルに対してフォワード-バックワード方式で動作する一般的なアルゴリズムのクラスに属するアルゴリズムを指す場合にも使用されます。この意味で、この記事の残りの部分での説明は、このクラスの特定のインスタンスの 1 つだけを指します。

最初のパスでは、順方向-逆方向アルゴリズムは、すべての に対して、シーケンスの最初の観測が与えられた場合に特定の状態になる確率を提供する順方向確率のセット、つまり を計算します。2 番目のパスでは、アルゴリズムは、任意の開始点 が与えられた場合に残りの観測が観測される確率を提供する逆方向確率のセット、つまり を計算します。これらの 2 つの確率分布のセットを組み合わせると、観測シーケンス全体が与えられた場合に、特定の時点における状態の分布を取得できます。 ${\displaystyle t\in \{1,\dots ,T\}}$${\displaystyle t}$${\displaystyle P(X_{t}\ |\ o_{1:t})}$${\displaystyle t}$${\displaystyle P(o_{t+1:T}\ |\ X_{t})}$

${\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}}$${\displaystyle o_{1:t}}$${\displaystyle X_{t}}$

上で概説したように、アルゴリズムには 3 つのステップが含まれます。

1. 将来確率を計算する
2. 逆確率を計算する
3. 平滑化された値を計算します。

前方ステップと後方ステップは、「前方メッセージ パス」と「後方メッセージ パス」とも呼ばれます。これらの用語は、一般的なビリーフ プロパゲーションアプローチで使用されるメッセージ パッシングに由来します。シーケンス内の各単一観測で、次の観測での計算に使用される確率が計算されます。スムージング ステップは、後方パス中に同時に計算できます。このステップにより、アルゴリズムは出力の過去の観測を考慮に入れて、より正確な結果を計算できます。

フォワード-バックワードアルゴリズムは、任意の時点で最も可能性の高い状態を見つけるために使用できます。ただし、最も可能性の高い状態のシーケンスを見つけるために使用することはできません ( Viterbi アルゴリズムを参照)。

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

与えられた隠れマルコフモデルに関連する確率分布を、次のように行列表記に変換します。隠れマルコフモデルのすべての可能な状態を表す与えられたランダム変数の遷移確率は、列インデックスがターゲット状態を表し、行インデックスが開始状態を表す行列で表されます。行ベクトル状態から増分行ベクトル状態への遷移は、 と記述されます。以下の例は、各ステップ後に同じ状態に留まる確率が 70%、他の状態に遷移する確率が 30% であるシステムを表しています。遷移行列は次のようになります。 ${\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} }$

${\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% です。システムの状態を表す任意の行ベクトル ( ) が与えられた場合、イベント j を観測する確率は次のようになります。 ${\displaystyle \mathbf {\pi } }$

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

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

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

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

${\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}}} }$

ここで、は前のステップからのスケーリングされたベクトルを表し、は結果のベクトルのエントリの合計が 1 になるスケーリング係数を表します。スケーリング係数の積は、最終状態に関係なく、指定されたイベントを観測する合計確率です。 ${\displaystyle \mathbf {{\hat {f}}_{0:t-1}} }$${\displaystyle c_{t}}$

${\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})}$

つまり、特定の状態 ( ) から開始すると仮定し、この状態からすべての将来のイベントを観測する確率に関心があります。初期状態は既知であると仮定しているため (つまり、この状態の事前確率 = 100%)、次のように開始します。 ${\displaystyle X_{t}=x_{i}}$

${\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)}$

これを理解するには、 が、時刻 t に状態を通過する方法で特定のイベントを観測する確率を提供することに留意してください。この確率には、時刻 t までのすべてのイベントをカバーする前方確率と、すべての将来のイベントを含む後方確率が含まれます。これが方程式で探している分子であり、観測シーケンスの合計確率で割ってこの値を正規化し、 の確率のみを抽出します。これらの値は、前方確率と後方確率を組み合わせて最終的な確率を計算するため、「平滑化値」と呼ばれることもあります。 ${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$${\displaystyle x_{i}}$${\displaystyle X_{t}=x_{i}}$

したがって、これらの値は、時刻 t における各状態にある確率を提供します。そのため、これらの値は、任意の時点での最も可能性の高い状態を決定するのに役立ちます。「最も可能性の高い状態」という用語は、いくぶん曖昧です。最も可能性の高い状態は、特定の時点で正しい可能性が最も高い状態ですが、個別に可能性の高い状態のシーケンスは、最も可能性の高いシーケンスではない可能性があります。これは、各ポイントの確率が互いに独立して計算されるためです。状態間の遷移確率は考慮されないため、2 つの時点 (t と t+1) で、その時点ではどちらも最も可能性の高い状態でありながら、同時に発生する可能性が非常に低い状態 (つまり ) が得られる可能性があります。観測シーケンスを生成する最も可能性の高い状態のシーケンスは、Viterbi アルゴリズムを使用して見つけることができます。 ${\displaystyle \mathbf {\gamma _{t}} (i)}$${\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 になるようにスケーリングする必要があります。これは、以前に見つかった 's を使用して後方確率をスケーリングしなかったためです。したがって、上記の後方確率ベクトルは、実際には将来の観測値に基づいて、時刻 t における各状態の確率を表しています。これらのベクトルは実際の後方確率に比例するため、結果はさらにスケーリングする必要があります。 ${\displaystyle c_{t}}$

${\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}} }$

順方向-逆方向アルゴリズムは、空間 で時間複雑度 で実行されます。ここで、は時間シーケンスの長さ、 は状態アルファベット内のシンボルの数です。^[1] このアルゴリズムは、各ステップで値を再計算することにより、時間複雑度 で定数空間で実行することもできます。^[2]比較のために、ブルートフォース手順では、すべての可能な状態シーケンスを生成し、各状態シーケンスと観測された一連のイベントの結合確率を計算します。これは、時間複雑度になります。ブルートフォースは、可能な隠しノードシーケンスの数が通常非常に多いため、現実的な問題では扱いにくいです。 ${\displaystyle O(S^{2}T)}$${\displaystyle O(ST)}$${\displaystyle T}$${\displaystyle S}$${\displaystyle O(S^{2}T^{2})}$${\displaystyle S^{T}}$ ${\displaystyle O(T\cdot S^{T})}$

一般的なフォワード-バックワードアルゴリズムの拡張版であるアイランドアルゴリズムは、メモリ使用量を少なくする代わりに実行時間を長くし、時間とメモリを消費します。さらに、プロセスモデルを反転して空間時間アルゴリズムを取得することも可能ですが、反転したプロセスは存在しないか、条件が悪くなる可能性があります。^[3]${\displaystyle O(S^{2}T\log T)}$${\displaystyle O(S\log T)}$${\displaystyle O(S)}$${\displaystyle O(S^{2}T)}$

さらに、固定ラグスムージング（FLS）アルゴリズムなどのオンラインスムージングを通じて効率的に計算するためのアルゴリズムも開発されています。^[4]${\displaystyle \mathbf {f_{0:t+1}} }$

アルゴリズムforward_backwardは
    入力: guessState
           intシーケンスインデックス
    出力: 結果

     シーケンスインデックスがシーケンスの末尾を過ぎている場合は
        1 を
    返し、 ( guessState、シーケンスインデックス) が以前に見られたことがある場合は保存された結果を返します。
        

    結果 := 0

    各隣接状態n
        について: result  := result + ( guessStateからnシーケンスインデックス
                            の指定された観測要素)
                            × 後方(n,シーケンスインデックス+ 1)

    ( guessState、sequenceIndex )の結果を保存します。

     結果を返す

Python プログラミング言語で表現されたHMM ( Viterbi アルゴリズムと同様) が与えられます。

states  =  ( '健康' 、 '発熱' ) 
end_state  =  'E'
 
観察 =  ( '正常' 、 '寒い' 、 'めまい' )
 
start_probability  =  { '健康' :  0.6 、 '発熱' :  0.4 }
 
transition_probability  =  { 
   '健康'  :  { '健康' :  0.69 ,  '発熱' :  0.3 ,  'E' :  0.01 }, 
   '発熱'  :  { '健康' :  0.4 ,  '発熱' :  0.59 ,  'E' :  0.01 }, 
   }
 
放出確率 =  { 
   '健康'  :  { '正常' :  0.5 、 '風邪' :  0.4 、 'めまい' :  0.1 }、
   '発熱'  :  { '正常' :  0.1 、 '風邪' :  0.3 、 'めまい' :  0.6 }、
   }

前方後方アルゴリズムの実装は次のように記述できます。

def  fwd_bkw ( observes ,  states ,  start_prob ,  trans_prob ,  emm_prob ,  end_st ): 
"""Forward–backward algorithm.""" # アルゴリズムの前方部分fwd = [] for i , observer_i in enumerate ( observes ): 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 ][観測値 i ]  * 前回のf_sum

        fwd.append ( f_curr ) f_prev = f_curr​​
          

    p_fwd  =  sum ( f_curr [ k ]  *  trans_prob [ k ] [ end_st ] 状態kについて )  

    # アルゴリズムの逆方向部分
    bkw  =  [] 
    for  i ,  observer_i_plus  in  enumerate ( reversed ( observes [ 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 ][ observer_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 ][観測値[ 0 ]]  *  b_curr [ l ]  （状態におけるlについて ）  

    # 2つの部分をマージする
    posterior  =  [] 
    for  i  in  range ( len ( observes )): 
        posterior . append ({ st :  fwd [ i ][ st ]  *  bkw [ i ][ st ]  /  p_fwd  for  st  in  states })

     p_fwd  ==  p_bkw
    をアサートし、fwd 、bkw 、posteriorを返す。   

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

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

実行例では、順方向-逆方向アルゴリズムが次のように使用されます。

定義 例(): 
    return  fwd_bkw (観測値、
                   状態、
                   開始確率、
                   遷移確率、
                   放出確率、
                   終了状態)

>>> for  line  in  example (): 
...     print ( * line ) 
... 
{'Healthy': 0.3, 'Fever': 0.040000000000000001} {'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、「隠れマルコフモデルと音声認識における選択されたアプリケーションに関するチュートリアル」、IEEE論文集、77 (2)、p. 257–286、1989 年 2 月。10.1109/5.18626
• ローレンス・R・ラビナー、BH Juang（1986年1月）。 「隠れマルコフモデルの紹介」。IEEE ASSP マガジン: 4–15。
• ユージン・チャーニアック（1993年）「統計的言語学習」マサチューセッツ州ケンブリッジ：MIT出版。ISBN 978-0-262-53141-2。
• スチュアート・ラッセル、ピーター・ノーヴィグ (2010)。『人工知能 現代的アプローチ 第3版』。ニュージャージー州アッパーサドルリバー：ピアソン・エデュケーション/プレンティス・ホール。ISBN 978-0-13-604259-4。

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