確率伝搬法

確率伝搬法 (かくりつでんぱんほう、英: belief propagation) あるいはSum-productメッセージ伝達法 (英: sum-product message passing) とは、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデル上で作用する、メッセージ伝達のアルゴリズムである。このアルゴリズムは、既に観測されているノードの状態を基に、観測されていないノードの周辺分布をそれぞれ計算する。確率伝搬法は主に人工知能や情報理論の分野で広く用いられており、低密度パリティ検査符号、ターボ符号、自由エネルギー近似、充足可能性問題を含む、数多くの応用の成功が経験的に確かめられている。

確率伝搬法という表記について、一般に「伝搬は誤りで、伝播が正しい」と言われることがあるが、工学分野では電波法において「電波伝搬」という用語が正式に採用されており、情報分野においても「ループ伝搬」という用語が用いられている例がある。確率伝搬法についても、伝播ではなく伝搬の語が用いられてきた歴史的経緯があるため、本稿では「伝播」ではなく「伝搬」に統一する。

このアルゴリズムは1982年にジューディア・パールにより提案されたもので、当初は木構造上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている。

一例を示す。X=(X_v)を結合確率質量関数pをもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布X_iは、単純にpをX_i以外のノードについて和をとることで表現できる:

$p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ').$

しかし、この計算は仮に確率変数が100個の二値変数であったとしても、この確率変数全体の場合の数は2⁹⁹ ≈ 6.338 × 10²⁹と非常に多くなるため、コンピュータ上で計算することは相当な困難を伴うものである。確率伝搬法では対象の確率変数のグラフ構造を利用することによって、この周辺分布の計算をより効率的に行う。

Sum-productアルゴリズムの概要

確率伝搬法は因子グラフ上で実行するアルゴリズムである。ここで、因子グラフとは変数Vと因子Uによって構成されている2部グラフであり、変数と因子の間にはエッジが張られている。このグラフを用いることで、以下の結合確率質量関数を書き下せる。

$p(\mathbf {x} )=\prod _{u\in U}f_{u}(\mathbf {x} _{u})$

ここで、x_uは因子ノードuに隣接している変数を表すベクトルである。任意のベイジアンネットワークとマルコフ確率場は因子グラフの形で表現できる。

このアルゴリズムはメッセージと呼ばれる、変数x_vを引数にとる関数をノード間のエッジに沿って伝搬させる。これらのメッセージはある変数が他の変数に影響を与える『相互作用』を含む。メッセージには2種類存在する:

• 変数ノードvから因子ノードuへ渡すメッセージ。メッセージの計算は隣接しているすべての因子グラフの積を取ることによって表現される(ただし、対象の因子ノードからのメッセージは除くものとする。除く代わりに、対象の因子ノードからのメッセージは"1"を送るものとして計算することもできる):

$\mu _{v\to u}(x_{v})=\prod _{u^{*}\in N(v)\setminus \{u\}}\mu _{u^{*}\to v}(x_{v}).$

ここで、N(v)は変数ノードvに隣接する、すべての因子ノードの集合とする。$N(v)\setminus \{u\}$が空集合であるならば、$\mu _{v\to u}(x_{v})$は一様分布として計算する。

• 因子ノードuから変数ノードvへ渡すメッセージ。メッセージの計算は隣接している他のノードからのメッセージの積をとり、x_v以外のすべての変数について周辺化を行うことで表現される:

$\mu _{u\to v}(x_{v})=\sum _{\mathbf {x} '_{u}:x'_{v}=x_{v}}f_{u}(\mathbf {x} '_{u})\prod _{v^{*}\in N(u)\setminus \{v\}}\mu _{v^{*}\to u}(x'_{v^{*}}).$

ここで、N(u)は因子ノードuに隣接する、すべての変数ノードの集合とする。$N(u)\setminus \{v\}$が空集合であるならば、$\mu _{u\to v}(x_{v})=f_{u}(x_{v})$とする。

明らかに、確率伝搬法の名前の由来は上の公式から来るものである。このアルゴリズムによって、結合確率分布に対する周辺分布の計算という困難な問題が、単純なメッセージの積と和の計算に減少できる。

木構造である場合の厳密解

確率伝搬法の最も簡単な形は、対象の因子グラフが木構造となる場合である。この場合、確率伝搬法は周辺分布の厳密解を計算でき、以下の2段階のステップの後に終了する。

このアルゴリズムを開始する前に、対象のグラフの内一つのノードを根として定める。また、任意の根でない、一つのノードしか接続されていないノードを葉と呼ぶ。

一段階目のステップでは、メッセージの計算を葉ノードから始める。各々のノードはエッジを通して、受けとったメッセージを根ノードに向けて伝搬する。グラフは木構造であるため、対象のノードにメッセージを渡す前に、他のすべての近接ノードからメッセージを受けとれることが保証される。この伝搬則は、根ノードがすべての近接ノードからメッセージを受け取るまで繰り返される。

二段階目のステップでは、根ノードから葉ノードに向けてメッセージを送信する。この場合、メッセージは前回とは逆の方向から伝搬される。すべての葉ノードがメッセージを受け取った際に、このアルゴリズムは終了する。

計算が完了した後、各々のノードの周辺分布は隣接している因子ノードからのメッセージの積に比例する:

$p_{X_{v}}(x_{v})\propto \prod _{u\in N(v)}\mu _{u\to v}(x_{v}).$

同様に、ある因子に属している変数の集合の周辺分布は、変数からのメッセージとその因子の積に比例する:

$p_{X_{u}}(\mathbf {x} _{u})\propto f_{u}(\mathbf {x} _{u})\prod _{v\in N(u)}\mu _{v\to u}(x_{u}).$

これらの計算は数学的帰納法によって証明できる。

一般的なグラフに関しての近似アルゴリズム

奇妙な事に、一般的なグラフに関しても木構造と同様のアルゴリズムを用いることができる。このアルゴリズムは対象のグラフが一般にループを含むことから"loopy" belief propagationアルゴリズムと呼ばれることもある。対象のグラフが葉を含んでいないため、このアルゴリズムは確率伝搬法の伝搬規則は僅かながら修正される必要がある。まず、最初にすべての変数間のメッセージを1に初期化する。次に、各反復回数ごとに上の定義を用いたメッセージの更新を、(たとえ十分な反復によって、葉や木構造の部分グラフから既知のメッセージが来た場合においても)すべてのメッセージに対して行う。対象のグラフが木構造である場合、loopy belief propagationの手続きは、対象のグラフの直径に等しい反復回数以内で、本来の確率伝搬法で得られるメッセージへ収束する。

loopy belief propagationアルゴリズムの正確な収束条件は未だに明らかでないが、単一のループを含むグラフにおいては、厳密解ではないにしろ、常に収束することが知られている。その他にもloopy belief propagationが唯一の固定点に収束するための十分条件(必要条件でない)がいくつか存在する。一方で、メッセージが発散したり、各反復回数毎に解が振動するようなグラフも存在する。EXITチャートのような手法を用いて、確率伝搬法の経過やその収束状況について近似的に可視化し、調査することもできる。

周辺化のための近似手法としては、他にも変分法やモンテカルロ法を含むいくつかの手法が提案されている。

一般的なグラフ上で厳密な周辺分布解を求めるための一つとしてジャンクションツリーアルゴリズムが挙げられる。これは対象のグラフを木構造へ修正し、その後に確率伝搬法を適用する。ジャンクションツリーではループを含むクラスタを単一のノードにまとめループを消去することで、確率伝搬法の収束性を保証している。

類似アルゴリズムと複雑性

類似のアルゴリズムとしては一般にビタビアルゴリズムが挙げられる。ビタビアルゴリズムはmax-productあるいはmin-sumアルゴリズムとしても知られており、関連するモデルの最大化問題を解く。具体的には、このアルゴリズムは周辺分布を求めるのではなく、大域的関数を最大化される値$\mathbf {x}$を求める。これは確率的に尤も起こりうる値を選択することと等価であり、arg max記号を用いて定義できる:

$\arg \max _{\mathbf {x} }g(\mathbf {x} ).$

この問題の解法としては確率伝搬法とほぼ等価であり、和の記号を最大値に置き換えるだけでよい。

グラフィカルモデル上での周辺化や最大化のような推定問題は、厳密解や相対誤差以下の近似解を得ようとした場合においてNP困難な問題である。正確には、上で定義された周辺化の問題は#P完全であり、最大化はNP完全である。

自由エネルギーとの関係

sum-productアルゴリズムは熱力学における自由エネルギーと関連がある。Zを分配関数とすると、因子グラフで表現された確率分布

$P(\mathbf {X} )={\frac {1}{Z}}\prod _{f_{j}}f_{j}(x_{j})$

は、ある系における内部エネルギーの測度として見ることができる。すなわち

$E(\mathbf {X} )=\log \prod _{f_{j}}f_{j}(x_{j}).$

である。対象の系における自由エネルギーは以下の通りである:

$F=U-H=\sum _{\mathbf {X} }P(\mathbf {X} )E(\mathbf {X} )+\sum _{\mathbf {X} }P(\mathbf {X} )\log P(\mathbf {X} ).$

つまり、sum-productアルゴリズムの収束点は、対象の系の自由エネルギーを最小化する点としても表せることを意味している。同様に、ループを含む反復的な確率伝搬法アルゴリズムの固定点は、近似された自由エネルギーの定留点とも見なせる。

一般化された確率伝搬法(Generalized belief propagation, GBP)

確率伝搬法は通常の場合、因子グラフ上でのメッセージを更新するアルゴリズムとして表現される。メッセージは変数ノードとその近傍である因子ノード間、もしくはその逆を含む。

ここで、グラフ上でのクラスター間におけるメッセージを考える。これが一般化された確率伝搬法アルゴリズムの一つである。そのようなメッセージを伝搬させる際にはまず対象のグラフ上におけるクラスターの集合を定義する必要があるが、それにはいくつかの方法がある。クラスター間でメッセージを交換するというアイデアは初めに物理学者である菊池良一が導入し、現在では菊池のクラスター変分法という名前で知られている。

確率伝搬法の精度を改良する際のもう一つの手法として、対象の場(メッセージ)の分布のレプリカ対称性を破る方法がある。この一般化によってsurvey propagation(SP)と呼ばれる新しい手法が導かれており、充足性やグラフ彩色問題などといったNP完全な問題に対して非常に効率的に解くことができる。

クラスター変分法とsurvey propagationは、確率伝搬法を2つの異なるアプローチによって発展させたアルゴリズムである。

ガウシアン確率伝搬法(Gaussian Belief Propagation, GaBP)

ガウシアン確率伝搬法は確率伝搬法アルゴリズムの別形であり、対象の分布がガウス分布である場合の確率伝搬法を指している。このようなモデルに対する解析は、初めにWeissとFreemanによって行われた。

まず、GaBPアルゴリズムでは以下の周辺化問題について解く:

$P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-1/2x^{T}Ax+b^{T}x)\,dx_{j}$

ここでZは正規化定数、Aは対称正定値行列(分散共分散の逆行列や精度行列としても知られている)、bはシフトベクトルとする。

このようなガウシアンモデルの下では、周辺分布の最大値を推定値とする問題はMAP推定問題と等価である:

${\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-1/2x^{T}Ax+b^{T}x).$

同様に、このMAP推定問題は以下の二次形式の最小化問題と等価である:

${\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.$

最終的に、これは以下の線形方程式の解と等価である:

$Ax=b.$

GaBPアルゴリズムの収束性は(一般的な確率伝搬法の場合と比較して)解析が容易であり、2種類の十分条件が知られている。一つはWeissが2000年に定式化した条件であり、Aが対角優位行列である場合に関して収束性が保証されている。二つめは2006年にJohnsonらが定式化した条件であり、行列のスペクトル半径が下式を満たしている場合に収束する。

$\rho (I-|D^{-1/2}AD^{-1/2}|)<1\,$

ここで、D = diag(A)である。

GaBPアルゴリズムは線形代数の領域と関連がある。具体的には、GaBPアルゴリズムはAが情報行列でbがシフトベクトルである場合の線形方程式Ax=bを解くための反復アルゴリズムとして見ることができる。GaBPアルゴリズムの収束条件はヤコビ法の十分条件と等価であり、かつ、GaBPアルゴリズムの収束速度はヤコビ法、ガウス＝ザイデル法、SOR法などといった古典的な反復手法よりも早いことが経験的に知られている。さらに、GaBPアルゴリズムは共役勾配法の条件下で発生する、計算上の問題に対して耐性があることが示されている。

参考文献

• Frey, Brendan (1998). Graphical Models for Machine Learning and Digital Communication. MIT Press
• デービッド・J・C・マッケイ (2003). Exact Marginalization in Graphs. In David J.C. MacKay, Information Theory, Inference, and Learning Algorithms, pp. 334–340. Cambridge: Cambridge University Press.
• Mackenzie, Dana (2005). Communication Speed Nears Terminal Velocity New Scientist. 9 July 2005. Issue 2507 (Registration required)
• Yedidia, J.S.; Freeman, W.T.; Weiss, Y.; Y. (July 2005). “Constructing free-energy approximations and generalized belief propagation algorithms”. IEEE Transactions on Information Theory 51 (7): 2282–2312. doi:10.1109/TIT.2005.850085. http://www.merl.com/publications/TR2004-040/ 2009年3月28日閲覧。. 
• Yedidia, J.S.; Freeman, W.T.; Y. (January 2003). “Understanding Belief Propagation and Its Generalizations”. In Lakemeyer, Gerhard; Nebel, Bernhard. Exploring Artificial Intelligence in the New Millennium. Morgan Kaufmann. pp. 239–236. ISBN 1-55860-811-7. http://www.merl.com/publications/TR2001-022/ 2009年3月30日閲覧。 
• Bishop, Christopher M (2006). “Chapter 8: Graphical models”. Pattern Recognition and Machine Learning. Springer. pp. 359–418. ISBN 0-387-31073-8. http://research.microsoft.com/%7Ecmbishop/PRML/Bishop-PRML-sample.pdf 2009年3月30日閲覧。 
• Koch, Volker M. (2007). A Factor Graph Approach to Model-Based Signal Separation --- A tutorial-style dissertation
• Wymeersch, Henk (2007). Iterative Receiver Design. Cambridge University Press. ISBN 0-521-87315-0. http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521873154 
• Bickson, Danny. (2009). Gaussian Belief Propagation Resource Page --- Webpage containing recent publications as well as Matlab source code.
• Coughlan, James. (2009). A Tutorial Introduction to Belief Propagation.