順方向アルゴリズム

隠れマルコフモデル（HMM）における順方向アルゴリズムは、「信念状態」、すなわち過去の証拠に基づいて特定の時点における状態の確率を計算するために使用されます。このプロセスはフィルタリングとも呼ばれます。順方向アルゴリズムは、ビタビアルゴリズムと密接に関連していますが、異なるアルゴリズムです。

順方向アルゴリズムと逆方向アルゴリズムは、いくつかの分野における標準的な数学的手順に付けられた単なる名称のように見えるため、確率論の文脈で捉えるべきである。例えば、「順方向アルゴリズム」も「ビタビ」も、ケンブリッジ数学百科事典には掲載されていない。これらのアルゴリズムから得られる主な知見は、変数の有向グラフ（和積ネットワークを参照）の文脈において、ベイズ更新と推論を計算効率よく構成する方法である。

このようなHMMの場合：

この確率は次のように表されます。${\displaystyle p(x_{t}|y_{1:t})}$。 ここ${\displaystyle x(t)}$は隠れた状態であり、略して${\displaystyle x_{t}}$そして$\displaystyle y_{1:t}}$観察結果は以下の通りです${\displaystyle 1}$に${\displaystyle t}$。

後方アルゴリズムは、過去の推定値を改善したい場合に将来の履歴を考慮に入れることで前方アルゴリズムを補完します。これは平滑化と呼ばれ、前方/後方アルゴリズムは以下を計算します。${\displaystyle p(x_{t}|y_{1:T})}$のために$1<t<T$したがって、完全な順方向/逆方向アルゴリズムはすべての証拠を考慮に入れます。各タイムステップで信念状態を計​​算できますが、厳密には、これを行うと最も可能性の高い状態シーケンスが生成されず、むしろ、過去の履歴に基づいて各タイムステップで最も可能性の高い状態が生成されます。最も可能性の高いシーケンスを実現するには、ビタビアルゴリズムが必要です。これは、観測の履歴に基づいて最も可能性の高い状態シーケンス、つまり、を最大化する状態シーケンスを計算します。${\displaystyle p(x_{0:t}|y_{0:t})}$。

順方向アルゴリズムの目標は、同時確率を計算することです。${\displaystyle p(x_{t},y_{1:t})}$表記の便宜上、${\displaystyle x(t)}$として${\displaystyle x_{t}}$そして${\displaystyle (y(1),y(2),...,y(t))}$として$\displaystyle y_{1:t}}$結合確率が${\displaystyle p(x_{t},y_{1:t})}$計算された他の確率${\displaystyle p(x_{t}|y_{1:t})}$そして${\displaystyle p(y_{1:t})}$容易に入手できる。

両州${\displaystyle x_{t}}$観察$\displaystyle y_t}}$は離散的で有限な確率変数であると仮定される。隠れマルコフモデルの状態遷移確率${\displaystyle p(x_{t}|x_{t-1})}$観測/放出確率${\displaystyle p(y_{t}|x_{t})}$、および初期事前確率${\displaystyle p(x_{0})}$は既知であると仮定される。さらに、観測のシーケンスは$\displaystyle y_{1:t}}$は既知であると仮定される。

コンピューティング${\displaystyle p(x_{t},y_{1:t})}$素朴に言えば、考えられるすべての状態シーケンスを周辺化する必要があるだろう${\displaystyle \{x_{1:t-1}\}}$の数は指数関数的に増加する${\displaystyle t}$その代わりに、順方向アルゴリズムは隠れマルコフモデル（HMM）の条件付き独立性のルールを利用して、再帰的に計算を実行します。

再帰を実証するために、

${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})}$。

連鎖律を用いて展開する${\displaystyle p(x_{t},x_{t-1},y_{1:t})}$すると、次のように書ける

${\displaystyle \alpha (x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})}$。

なぜなら$\displaystyle y_t}}$すべてから条件付きで独立しているが、${\displaystyle x_{t}}$、 そして${\displaystyle x_{t}}$すべてから条件付きで独立しているが、${\displaystyle x_{t-1}}$これは、

${\displaystyle \alpha (x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})}$。

したがって、${\displaystyle p(y_{t}|x_{t})}$そして${\displaystyle p(x_{t}|x_{t-1})}$はモデルの放出分布と遷移確率によって与えられ、これらは既知であると仮定すると、迅速に計算できる。$\displaystyle \alpha (x_{t})$から$\displaystyle \alpha (x_{t-1})$そして、指数関数的な計算時間の発生を回避する。

上記の再帰式は、より簡潔な形で記述できます。${\displaystyle a_{ij}=p(x_{t}=i|x_{t-1}=j)}$遷移確率と${\displaystyle b_{ij}=p(y_{t}=i|x_{t}=j)}$放出確率を とすると、

${\displaystyle \mathbf {\alpha } _{t}=\mathbf {b} _{t}^{T}\odot \mathbf {A} \mathbf {\alpha } _{t-1}}$

どこ${\displaystyle \mathbf {A} =[a_{ij}]}$は遷移確率行列であり、$\displaystyle \mathbf {b} _{t}}$は放出確率行列の i 番目の行です。${\displaystyle \mathbf {B} =[b_{ij}]}$これは実際の観測結果と一致する。${\displaystyle y_{t}=i}$その時${\displaystyle t}$、 そして$\displaystyle \mathbf {\alpha } _{t}=[\alpha (x_{t}=1),\ldots ,\alpha (x_{t}=n)]^{T}}$はアルファベクトルです。${\displaystyle \odot }$は転置間のアダマール積である$\displaystyle \mathbf {b} _{t}}$そして$\displaystyle \mathbf {A} \mathbf {\alpha } _{t-1}}$。

初期条件は、事前確率に基づいて設定されます。${\displaystyle x_{0}}$として

${\displaystyle \alpha (x_{0})=p(y_{0}|x_{0})p(x_{0})}$。

結合確率が${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})}$順方向アルゴリズムを使用して計算されているため、関連する同時確率を容易に得ることができます${\displaystyle p(y_{1:t})}$として

${\displaystyle p(y_{1:t})=\sum _{x_{t}}p(x_{t},y_{1:t})=\sum _{x_{t}}\alpha (x_{t})}$

そして必要な条件付き確率${\displaystyle p(x_{t}|y_{1:t})}$として

${\displaystyle p(x_{t}|y_{1:t})={\frac {p(x_{t},y_{1:t})}{p(y_{1:t})}}={\frac {\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.}$

条件付き確率が計算されたら、次の点推定値も求めることができます。${\displaystyle x_{t}}$例えば、MAP推定値は${\displaystyle x_{t}}$は

${\displaystyle {\widehat {x}}_{t}^{MAP}=\arg \max _{x_{t}}\;p(x_{t}|y_{1:t})=\arg \max _{x_{t}}\;\alpha (x_{t}),}$

MMSE推定値は${\displaystyle x_{t}}$は

${\displaystyle {\widehat {x}}_{t}^{MMSE}=\mathbb {E} [x_{t}|y_{1:t}]=\sum _{x_{t}}x_{t}p(x_{t}|y_{1:t})={\frac {\sum _{x_{t}}x_{t}\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.}$

順方向アルゴリズムは、マルコフジャンプ線形システムなどの隠れマルコフモデルの変種からの観測値も考慮するように簡単に変更できます。

これは、海藻の状態から考えられる気象状態を観察する例です。海藻の状態を3日間連続で観察した結果、乾燥、湿潤、水浸しの順になりました。考えられる気象状態は、晴れ、曇り、雨です。合計で、$3^3=27$このような気象シーケンス。このような可能な状態シーケンスをすべて探索することは、計算コストが非常に高くなります。この複雑さを軽減するために、フォワードアルゴリズムが役立ちます。このアルゴリズムのコツは、シーケンスステップの条件付き独立性を使用して部分確率を計算することです。${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})}$上記の導出で示されているように。したがって、適切な観測/放出確率の積として確率を計算できます。${\displaystyle p(y_{t}|x_{t})}$（状態の確率）$\displaystyle y_t}}$（以前の観測から時刻 t で確認された）と、遷移確率を使用して計算された時刻 t でその状態に到達する確率の合計。これにより、問題の複雑さが、探索空間全体を探索することから、以前に計算された${\displaystyle \alpha }$と遷移確率。

順方向アルゴリズムの複雑さは$\displaystyle \Theta (nm^{2})$、 どこ${\displaystyle m}$は潜在変数の可能な状態の数（上記の例の気象条件の数など）であり、${\displaystyle n}$ は観測されたシーケンスの長さです。これは、すべての可能な状態を探索するアドホックな方法からの明確な削減であり、その複雑さは$\displaystyle \Theta (nm^{n})$。

• ハイブリッド順方向アルゴリズム：^{[ 1 ]}順方向アルゴリズムの変種であるハイブリッド順方向アルゴリズム（HFA）は、調整可能なノードを持つ放射基底関数（RBF）ニューラルネットワークの構築に使用できます。RBFニューラルネットワークは、従来の部分集合選択アルゴリズムによって構築されます。ネットワーク構造は、段階的な順方向ネットワーク構成と連続的なRBFパラメータ最適化の両方を組み合わせることによって決定されます。これは、汎化性能に優れた簡潔なRBFニューラルネットワークを効率的かつ効果的に生成するために使用されます。これは、連続パラメータ空間での同時ネットワーク構造決定とパラメータ最適化によって実現されます。HFAは、統合された解析フレームワークを使用して混合整数困難問題に取り組み、ネットワークパフォーマンスの向上とネットワーク構築のためのメモリ使用量の削減につながります。

• ハイブリッドシステムにおける最適制御のための順方向アルゴリズム：^{[ 2 ]}この順方向アルゴリズムの変種は、プロセス制御とオペレーション制御を統合する製造環境の構造に着想を得ています。コスト関数の修正された条件下で成り立つ最適状態軌道構造の新しい特性を導出します。これにより、順方向アルゴリズムよりも効率的な、最適制御を明示的に決定するための低複雑度でスケーラブルなアルゴリズムを開発できます。

• 連続順方向アルゴリズム：^{[ 3 ]}連続順方向アルゴリズム（CFA）は、放射基底関数（RBF）ニューラルネットワークを使用した非線形モデリングおよび識別に使用できます。提案されたアルゴリズムは、統合された分析フレームワーク内でネットワーク構築とパラメータ最適化の2つのタスクを実行し、2つの重要な利点を提供します。第一に、連続的なパラメータ最適化によりモデルのパフォーマンスを大幅に向上させることができます。第二に、すべての候補回帰変数を生成および保存することなくニューラル表現を構築できるため、メモリ使用量と計算の複雑さが大幅に削減されます。

フォワードアルゴリズムは、デコード問題を解決するために使用されるアルゴリズムの1つです。音声認識^{[ 4 ]}やパターン認識、HMMを使用する計算生物学などの関連分野の発展以来、フォワードアルゴリズムは人気を集めています。

フォワードアルゴリズムは、観測シーケンスが分かっている場合に特定の状態にある確率を決定する必要があるアプリケーションで主に使用されます。このアルゴリズムは、Baum-Welch ^{[ 5 ]}または一般的なEMアルゴリズムを使用してデータを受け取りながらモデルをトレーニングできる場所であればどこでも適用できます。フォワードアルゴリズムは、モデルから期待されるものに関してデータの確率を教えてくれます。応用例の1つは金融分野であり、有形資産の売買時期を決定するのに役立ちます。

隠れマルコフモデル（HMM）を適用するすべての分野に応用できます。一般的なものとしては、品詞タグ付けや音声認識などの自然言語処理分野があります。^{[ 4 ]}最近では、バイオインフォマティクスの分野でも使用されています。

順方向アルゴリズムは、天気予報にも適用できます。数日間連続して観測された天候と観測状態との関係を記述するHMM（隠れマルコフモデル）を用意します（例として、乾燥、湿潤、じめじめ、晴れ、曇り、雨など）。HMMに基づいて、任意の観測シーケンスの確率を再帰的に計算することを検討できます。次に、中間状態に到達する確率を、その状態に至るすべての可能な経路の合計として計算します。したがって、最終観測の部分確率は、すべての可能な経路を経てそれらの状態に到達する確率を保持します。

• ビタビアルゴリズム
• 前方後方アルゴリズム
• バウム・ウェルチアルゴリズム

• ラッセルとノーヴィグの『人工知能：現代的アプローチ』（ 2010年版、570ページ以降）は、このテーマおよび関連トピックについて簡潔に解説している。
• Smyth、Padhraic、David Heckerman、およびMichael I. Jordan。「隠れマルコフ確率モデルのための確率的独立性ネットワーク」。Neural computation 9.2 (1997): 227-269。
• リード、ジョナサン。「隠れマルコフモデルと動的計画法」。オスロ大学（2011年）。
• コールシャイン、クリスチャン著『隠れマルコフモデル入門』
• Manganiello, Fabio、Mirco Marchetti、Michele Colajanni。「侵入検知システムにおける多段階攻撃検知とアラート相関」。Information Security and Assurance。Springer Berlin Heidelberg、2011年。101-110ページ。
• Zhang, Ping、Christos G. Cassandras。「ある種のハイブリッドシステムの最適制御のための改良された順方向アルゴリズム」。IEEE Transactions on Automatic Control 47.10 (2002): 1735-1739。
• Stratonovich, RL「条件付きマルコフ過程」確率論とその応用5巻2号（1960年）：156-178頁。

• 隠れマルコフモデルRパッケージには、順方向手順の計算と取得のための機能が含まれています。
• momentuHMM Rパッケージは、 HMMの使用と推論のためのツールを提供します。
• Python用GHMMライブラリ
• HMMS用のHaskellライブラリであるhmmパッケージは、Forwardアルゴリズムを実装しています。
• Java用ライブラリには、機械学習および人工知能アルゴリズムの実装が含まれています。