フォワードアルゴリズム
Hidden Markov model algorithm

フォワードアルゴリズムは、隠れマルコフモデル（HMM）において、「信念状態」を計算するために使用されます。信念状態とは、証拠の履歴を与えられた場合の、ある時点における状態の確率です。このプロセスはフィルタリングとも呼ばれます。フォワードアルゴリズムは、ビタビアルゴリズムと密接に関連していますが、異なるものです。

導入

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

このような HMM の場合:

隠れマルコフモデルの時間的進化
隠れマルコフモデルの時間的進化

この確率は と表されます。ここではと略される隠れ状態があり、はへの観測値です。 p ( x t | y 1 : t ) {\displaystyle p(x_{t}|y_{1:t})} x ( t ) {\displaystyle x(t)} x t {\displaystyle x_{t}} y 1 : t {\displaystyle y_{1:t}} 1 {\displaystyle 1} t {\displaystyle t}

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

アルゴリズム

順方向アルゴリズムの目的は、結合確率 を 計算することです。表記の便宜上、 を、と略記します。結合確率が計算されれば、他の確率と は簡単に得られます。 p ( x t , y 1 : t ) {\displaystyle p(x_{t},y_{1:t})} x ( t ) {\displaystyle x(t)} x t {\displaystyle x_{t}} ( y ( 1 ) , y ( 2 ) , . . . , y ( t ) ) {\displaystyle (y(1),y(2),...,y(t))} y 1 : t {\displaystyle y_{1:t}} p ( x t , y 1 : t ) {\displaystyle p(x_{t},y_{1:t})} p ( x t | y 1 : t ) {\displaystyle p(x_{t}|y_{1:t})} p ( y 1 : t ) {\displaystyle p(y_{1:t})}

状態と観測はともに離散的な有限確率変数であると仮定する。隠れマルコフモデルの状態遷移確率、観測／出力確率、および初期事前確率は既知であると仮定する。さらに、観測の順序は既知であると仮定する。 x t {\displaystyle x_{t}} y t {\displaystyle y_{t}} p ( x t | x t − 1 ) {\displaystyle p(x_{t}|x_{t-1})} p ( y t | x t ) {\displaystyle p(y_{t}|x_{t})} p ( x 0 ) {\displaystyle p(x_{0})} y 1 : t {\displaystyle y_{1:t}}

単純に計算すると、すべての可能な状態シーケンス について周辺化を行う必要があり、その数は とともに指数関数的に増加します。代わりに、順方向アルゴリズムでは、隠れマルコフモデル（HMM）の条件付き独立性規則を利用して、再帰的に計算を実行します。 p ( x t , y 1 : t ) {\displaystyle p(x_{t},y_{1:t})} { x 1 : t − 1 } {\displaystyle \{x_{1:t-1}\}} t {\displaystyle t}

再帰を説明するために、

α ( x t ) = p ( x t , y 1 : t ) = ∑ x t − 1 p ( x t , x t − 1 , y 1 : t ) {\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})} 。

連鎖律を使って展開すると、 p ( x t , x t − 1 , y 1 : t ) {\displaystyle p(x_{t},x_{t-1},y_{1:t})}

α ( x t ) = ∑ 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 \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})} 。

は以外のすべてから条件付きで独立しており、は 以外のすべてから条件付きで独立しているので、これは次のように単純化される。 y t {\displaystyle y_{t}} x t {\displaystyle x_{t}} x t {\displaystyle x_{t}} x t − 1 {\displaystyle x_{t-1}}

α ( x t ) = p ( y t | x t ) ∑ x t − 1 p ( x t | x t − 1 ) α ( 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})} 。

したがって、およびはモデルの放出分布と遷移確率によって与えられ、これらは既知であると仮定されているため、からを素早く計算して、指数関数的な計算時間の発生を回避できます。 p ( y t | x t ) {\displaystyle p(y_{t}|x_{t})} p ( x t | x t − 1 ) {\displaystyle p(x_{t}|x_{t-1})} α ( x t ) {\displaystyle \alpha (x_{t})} α ( x t − 1 ) {\displaystyle \alpha (x_{t-1})}

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

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

ここで、 は遷移確率行列、は時刻 における実際の観測値に対応する放出確率行列の i 行目、はアルファベクトルです。 はとの転置行列間のアダマール積です。 A = [ a i j ] {\displaystyle \mathbf {A} =[a_{ij}]} b t {\displaystyle \mathbf {b} _{t}} B = [ b i j ] {\displaystyle \mathbf {B} =[b_{ij}]} y t = i {\displaystyle y_{t}=i} t {\displaystyle t} α t = [ α ( x t = 1 ) , … , α ( x t = n ) ] T {\displaystyle \mathbf {\alpha } _{t}=[\alpha (x_{t}=1),\ldots ,\alpha (x_{t}=n)]^{T}} ⊙ {\displaystyle \odot } b t {\displaystyle \mathbf {b} _{t}} A α t − 1 {\displaystyle \mathbf {A} \mathbf {\alpha } _{t-1}}

初期条件は、事前確率に従って設定される。 x 0 {\displaystyle x_{0}}

α ( x 0 ) = p ( y 0 | x 0 ) p ( x 0 ) {\displaystyle \alpha (x_{0})=p(y_{0}|x_{0})p(x_{0})} 。

順方向アルゴリズムを用いて結合確率が計算されると、関連する結合確率は次のように 簡単に得られる。 α ( x t ) = p ( x t , y 1 : t ) {\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})} p ( y 1 : t ) {\displaystyle p(y_{1:t})}

p ( y 1 : t ) = ∑ x t p ( x t , y 1 : t ) = ∑ x t α ( x t ) {\displaystyle p(y_{1:t})=\sum _{x_{t}}p(x_{t},y_{1:t})=\sum _{x_{t}}\alpha (x_{t})}

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

p ( x t | y 1 : t ) = p ( x t , y 1 : t ) p ( y 1 : t ) = α ( x t ) ∑ x t α ( x 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})}}.}

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

x ^ t M A P = arg ⁡ max x t p ( x t | y 1 : t ) = arg ⁡ max x t α ( 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推定値は次のように与えられる。 x t {\displaystyle x_{t}}

x ^ t M M S E = E [ x t | y 1 : t ] = ∑ x t x t p ( x t | y 1 : t ) = ∑ x t x t α ( x t ) ∑ x t α ( 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})}}.}

フォワードアルゴリズムは、マルコフジャンプ線形システムなどの隠れマルコフモデルのバリエーションからの観測も考慮するように簡単に変更できます。

擬似コード

  1. 初期化
    t = 0 {\displaystyle t=0} 、
    遷移確率、、 p ( x t | x t − 1 ) {\displaystyle p(x_{t}|x_{t-1})}
    放出確率、、 p ( y t | x t ) {\displaystyle p(y_{t}|x_{t})}
    観察されたシーケンス、 y 1 : T {\displaystyle y_{1:T}}
    事前確率、 α ( x 0 ) {\displaystyle \alpha (x_{0})}
  2. 〜のために t = 1 {\displaystyle t=1} T {\displaystyle T}
    α ( x t ) = p ( y t | x t ) ∑ x t − 1 p ( x t | x t − 1 ) α ( 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})} 。
  3. 戻る p ( x T | y 1 : T ) = α ( x T ) ∑ x T α ( x T ) {\displaystyle p(x_{T}|y_{1:T})={\frac {\alpha (x_{T})}{\sum _{x_{T}}\alpha (x_{T})}}}

例

この例では、海藻の観測状態から天候の可能性のある状態を観察する方法について説明します。3 日連続で海藻を観測し、乾燥、湿潤、じめじめの順に変化させました。天候の可能性のある状態は、晴れ、曇り、雨のいずれかです。全体として、このような天候のシーケンスが考えられます。このようなすべての状態シーケンスを調査するには、計算コストが非常に高くなります。この複雑さを軽減するために、フォワード アルゴリズムが役立ちます。このアルゴリズムでは、上記の導出に示すように、シーケンス ステップの条件付き独立性を使用して部分確率を計算します。したがって、適切な観測/放出確率(前回の観測から時刻 t で観測された状態の確率) と、遷移確率を使用して計算された時刻 t でその状態に到達する確率の合計との積として確率を計算できます。これにより、問題の複雑さが軽減され、検索空間全体を探索する必要がなくなり、以前に計算された と遷移確率のみを使用できるようになります。 3 3 = 27 {\displaystyle 3^{3}=27} α ( x t ) = p ( x t , y 1 : t ) = p ( y t | x t ) ∑ x t − 1 p ( x t | x t − 1 ) α ( x t − 1 ) {\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})} p ( y t | x t ) {\displaystyle p(y_{t}|x_{t})} y t {\displaystyle y_{t}} α {\displaystyle \alpha }

複雑

順方向アルゴリズムの計算量は です。ここでは潜在変数の可能な状態の数（上記の例の気象条件の数など）、 は 観測されたシーケンスの長さです。これは、計算量が である、すべての可能な状態を探索するアドホックな手法から明らかに簡略化されています。 Θ ( n m 2 ) {\displaystyle \Theta (nm^{2})} m {\displaystyle m} n {\displaystyle n} Θ ( n m n ) {\displaystyle \Theta (nm^{n})}

アルゴリズムのバリエーション

  • ハイブリッドフォワードアルゴリズム: [1]ハイブリッドフォワードアルゴリズム (HFA) と呼ばれるフォワードアルゴリズムの変形は、調整可能なノードを持つラジアル基底関数 (RBF) ニューラルネットワークの構築に使用できます。RBF ニューラルネットワークは、従来のサブセット選択アルゴリズムによって構築されます。ネットワーク構造は、段階的なフォワードネットワーク構成と連続 RBF パラメータ最適化の両方を組み合わせることによって決定されます。これは、一般化が優れた簡潔な RBF ニューラルネットワークを効率的かつ効果的に生成するために使用されます。これは、連続パラメータ空間でのネットワーク構造の決定とパラメータの最適化を同時に行うことで実現されます。HFA は、統合された分析フレームワークを使用して混合整数難問題に取り組んでおり、ネットワークパフォーマンスの向上とネットワーク構築のメモリ使用量の削減につながります。
  • ハイブリッドシステムにおける最適制御のためのフォワードアルゴリズム：[2]このフォワードアルゴリズムの変種は、プロセス制御とオペレーション制御を統合した製造環境の構造に着目したものです。コスト関数の修正された条件下で成立する、最適状態軌道構造の新しい特性を導出します。これにより、フォワードアルゴリズムよりも効率的であり得る、最適制御を明示的に決定するための、複雑性が低くスケーラブルなアルゴリズムを開発できます。
  • 連続フォワードアルゴリズム：[3]連続フォワードアルゴリズム（CFA）は、ラジアル基底関数（RBF）ニューラルネットワークを用いた非線形モデリングおよび同定に使用できます。提案されたアルゴリズムは、ネットワーク構築とパラメータ最適化という2つのタスクを統合された分析フレームワーク内で実行し、2つの重要な利点を提供します。第一に、連続パラメータ最適化によってモデル性能を大幅に向上させることができます。第二に、すべての候補回帰変数を生成・保存することなくニューラルネットワーク表現を構築できるため、メモリ使用量と計算量が大幅に削減されます。

歴史

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

アプリケーション

フォワードアルゴリズムは、観測シーケンスが既知である状況で、特定の状態にある確率を決定する必要があるアプリケーションで主に使用されます。このアルゴリズムは、Baum-Welch [5]や一般的なEMアルゴリズムを用いてデータを受け取りながらモデルを学習できるあらゆる場面で適用できます。フォワードアルゴリズムは、モデルから期待されるデータに対するデータの確率を教えてくれます。例えば金融分野では、有形資産の売買時期を決定する際に役立ちます。

隠れマルコフモデル（HMM）が適用されるあらゆる分野に応用可能です。特に人気のある分野としては、品詞タグ付けや音声認識といった自然言語処理分野が挙げられます。[4]最近では、バイオインフォマティクスの分野でも利用されています。

フォワードアルゴリズムは、天気の推測にも適用できます。数日間連続した天気と観測状態との関係を記述したHMM（Human Model Model）を作成できます（例として、乾燥、湿潤、じめじめ、晴れ、曇り、雨など）。HMMが与えられた場合、任意の観測シーケンスを再帰的に観測する確率を計算することができます。そして、中間状態に到達する確率を、その状態に至るすべての可能な経路の合計として計算できます。したがって、最終観測における部分確率は、すべての可能な経路を通ってそれらの状態に到達する確率を保持します。

参照

参考文献

  1. ^ Peng, Jian-Xun, Kang Li, De-Shuang Huang. 「RBFニューラルネットワーク構築のためのハイブリッドフォワードアルゴリズム」Neural Networks, IEEE Transactions on 17.6 (2006): 1439-1451.
  2. ^ Zhang, Ping、Christos G. Cassandras. 「ハイブリッドシステムの最適制御のための改良フォワードアルゴリズム」Automatic Control、IEEE Transactions on 47.10 (2002): 1735-1739。
  3. ^ Peng, Jian-Xun, Kang Li, George W. Irwin. 「RBFニューラルモデリングのための新しい連続フォワードアルゴリズム」Automatic Control, IEEE Transactions on 52.1 (2007): 117-122.
  4. ^ ab Lawrence R. Rabiner、「隠れマルコフモデルと音声認識における応用に関するチュートリアル」IEEE紀要、77(2)、p.257–286、1989年2月。10.1109/5.18626
  5. ^ Zhang, Yanxue, Dongmei Zhao, Jinxing Liu. 「マルチステップ攻撃におけるBaum-Welchアルゴリズムの応用」 The Scientific World Journal 2014.

さらに読む

  • ラッセルとノーヴィグの「人工知能、現代的アプローチ」は、2010年版の570ページから、このテーマと関連するトピックについて簡潔に解説しています。
  • スミス、パドライク、デイヴィッド・ヘッカーマン、マイケル・I・ジョーダン。「隠れマルコフ確率モデルのための確率的独立性ネットワーク」ニューラルコンピューティング9.2（1997）：227-269。[1]
  • リード、ジョナサン.「隠れマルコフモデルと動的計画法」オスロ大学 (2011). [2]
  • コールシャイン、クリスチャン「隠れマルコフモデル入門」[3]
  • ファビオ・マンガニエロ、ミルコ・マルケッティ、ミシェル・コラジャンニ著「侵入検知システムにおける多段階攻撃の検知とアラート相関」情報セキュリティとアシュアランス、シュプリンガー・ベルリン・ハイデルベルク、2011年、101-110ページ。[4]
  • Zhang, Ping、Christos G. Cassandras。「ハイブリッドシステムの最適制御のための改良フォワードアルゴリズム」Automatic Control、IEEE Transactions on 47.10 (2002): 1735-1739。
  • ストラトノビッチ, RL「条件付きマルコフ過程」確率理論とその応用5巻2号（1960年）：156～178頁。

ソフトウェア

  • 隠れマルコフモデルRパッケージには、順方向手順の計算と取得の機能が含まれています。
  • momentuHMM R パッケージは、HMM を使用および推論するためのツールを提供します。
  • Python用GHMMライブラリ
  • HMMS 用の Haskell ライブラリである hmm パッケージは、Forward アルゴリズムを実装します。
  • Java 用ライブラリには、機械学習および人工知能アルゴリズムの実装が含まれています。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Forward_algorithm&oldid=1321857928"