確率伝搬法
確率伝搬法 (かくりつでんぱんほう、英: belief propagation) あるいはSum-productメッセージ伝達法 (英: sum-product message passing) とは、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデル上で作用する、メッセージ伝達のアルゴリズムである。このアルゴリズムは、既に観測されているノードの状態を基に、観測されていないノードの周辺分布をそれぞれ計算する。確率伝搬法は主に人工知能や情報理論の分野で広く用いられており、低密度パリティ検査符号、ターボ符号、自由エネルギー近似、充足可能性問題を含む、数多くの応用の成功が経験的に確かめられている。
確率伝搬法という表記について、一般に「伝搬は誤りで、伝播が正しい」と言われることがあるが、工学分野では電波法において「電波伝搬」という用語が正式に採用されており、情報分野においても「ループ伝搬」という用語が用いられている例がある。確率伝搬法についても、伝播ではなく伝搬の語が用いられてきた歴史的経緯があるため、本稿では「伝播」ではなく「伝搬」に統一する。
このアルゴリズムは1982年にジューディア・パール[1]により提案されたもので、当初は木構造上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した[2]。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている[3]。
一例を示す。X=(Xv)を結合確率質量関数pをもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布Xiは、単純にpをXi以外のノードについて和をとることで表現できる:
確率伝播法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/02 00:52 UTC 版)
タンパク質設計のための確率伝播法（belief propagation）では、アルゴリズムは、各残基が近隣する残基の各回転異性体の確率について持っている確率を記述したメッセージを交換する。このアルゴリズムは、反復ごとにメッセージを更新し、収束するまで、または一定の反復回数まで反復する。タンパク質設計において収束は保証されていない。ある残基 i が隣接残基 j のすべての回転異性体 (rj に送るメッセージ mi→ j(rj は次のように定義される。 m i → j ( r j ) = max r i ( e − E i ( r i ) − E i j ( r i , r j ) T ) ∏ k ∈ N ( i ) ∖ j m k → i ( r i ) {\displaystyle m_{i\to j}(r_{j})=\max _{r_{i}}{\Big (}e^{\frac {-E_{i}(r_{i})-E_{ij}(r_{i},r_{j})}{T}}{\Big )}\prod _{k\in N(i)\backslash j}m_{k\to i(r_{i})}} max-productとsum-productの両方の確率伝播が、タンパク質設計の最適化に使用されている。
※この「確率伝播法」の解説は、「タンパク質設計」の解説の一部です。
「確率伝播法」を含む「タンパク質設計」の記事については、「タンパク質設計」の概要を参照ください。
- 確率伝播法のページへのリンク
