類似アルゴリズムと複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/25 02:50 UTC 版)
「確率伝搬法」の記事における「類似アルゴリズムと複雑性」の解説
類似のアルゴリズムとしては一般にビタビアルゴリズムが挙げられる。ビタビアルゴリズムはmax-productあるいはmin-sumアルゴリズムとしても知られており、関連するモデルの最大化問題を解く。具体的には、このアルゴリズムは周辺分布を求めるのではなく、大域的関数を最大化される値 x {\displaystyle \mathbf {x} } を求める。これは確率的に尤も起こりうる値を選択することと等価であり、arg max記号を用いて定義できる: arg max x g ( x ) . {\displaystyle \arg \max _{\mathbf {x} }g(\mathbf {x} ).} この問題の解法としては確率伝搬法とほぼ等価であり、和の記号を最大値に置き換えるだけでよい。 グラフィカルモデル上での周辺化や最大化のような推定問題は、厳密解や相対誤差以下の近似解を得ようとした場合においてNP困難な問題である。正確には、上で定義された周辺化の問題は#P完全であり、最大化はNP完全である。
※この「類似アルゴリズムと複雑性」の解説は、「確率伝搬法」の解説の一部です。
「類似アルゴリズムと複雑性」を含む「確率伝搬法」の記事については、「確率伝搬法」の概要を参照ください。
ウィキペディア小見出し辞書の「類似アルゴリズムと複雑性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 類似アルゴリズムと複雑性のページへのリンク
