確率伝搬法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/17 10:15 UTC 版)
確率伝搬法 (かくりつでんぱんほう、英: belief propagation) あるいはSum-productメッセージ伝達法 (英: sum-product message passing) とは、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデル上で作用する、メッセージ伝達のアルゴリズムである。このアルゴリズムは、既に観測されているノードの状態を基に、観測されていないノードの周辺分布をそれぞれ計算する。確率伝搬法は主に人工知能や情報理論の分野で広く用いられており、低密度パリティ検査符号、ターボ符号、自由エネルギー近似、充足可能性問題を含む、数多くの応用の成功が経験的に確かめられている。
確率伝搬法という表記について、一般に「伝搬は誤りで、伝播が正しい」と言われることがあるが、工学分野では電波法において「電波伝搬」という用語が正式に採用されており、情報分野においても「ループ伝搬」という用語が用いられている例がある。確率伝搬法についても、伝播ではなく伝搬の語が用いられてきた歴史的経緯があるため、本稿では「伝播」ではなく「伝搬」に統一する。
このアルゴリズムは1982年にジューディア・パール[1]により提案されたもので、当初は木構造上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した[2]。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている[3]。
一例を示す。X=(Xv)を結合確率質量関数pをもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布Xiは、単純にpをXi以外のノードについて和をとることで表現できる:
- 確率伝搬法のページへのリンク
