確率伝搬法
確率伝搬法 (かくりつでんぱんほう、) あるいはSum-productメッセージ伝達法 () とは、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデル上で作用する、メッセージ伝達のアルゴリズムである。このアルゴリズムは、既に観測されているノードの状態を基に、観測されていないノードの周辺分布をそれぞれ計算する。確率伝搬法は主に人工知能や情報理論の分野で広く用いられており、低密度パリティ検査符号、ターボ符号、自由エネルギー近似、充足可能性問題を含む、数多くの応用の成功が経験的に確かめられている。
確率伝搬法という表記について、一般に「伝搬は誤りで、伝播が正しい」と言われることがあるが、工学分野では電波法において「電波伝搬」という用語が正式に採用されており、情報分野においても「ループ伝搬」という用語が用いられている例がある。確率伝搬法についても、伝播ではなく伝搬の語が用いられてきた歴史的経緯があるため、本稿では「伝播」ではなく「伝搬」に統一する。
このアルゴリズムは1982年にジューディア・パールにより提案されたもので、当初は木構造上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている。
一例を示す。"X"=("X""v")を結合確率質量関数"p"をもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布"X""i"は、単純に"p"を"X""i"以外のノードについて和をとることで表現できる:
しかし、この計算は仮に確率変数が100個の二値変数であったとしても、この確率変数全体の場合の数は299 ≈ 6.338 × 1029と非常に多くなるため、コンピュータ上で計算することは相当な困難を伴うものである。確率伝搬法では対象の確率変数のグラフ構造を利用することによって、この周辺分布の計算をより効率的に行う。