確率伝搬法のソースを表示

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

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

このアルゴリズムは1982年に[[ジューディア・パール]]<ref name="Pearl-1982">
{{cite conference|last=Pearl |first=Judea |authorlink=ジューディア・パール
 |year=1982
 |title=Reverend Bayes on inference engines:  A distributed hierarchical approach
 |book-title=Proceedings of the Second National Conference on Artificial Intelligence
 |conference=AAAI-82: Pittsburgh, PA
 |conferenceurl=http://www.aaai.org/Library/AAAI/aaai82contents.php
 |publisher=AAAI Press |location=Menlo Park, California
 |pages=133&ndash;136
 |url=https://www.aaai.org/Papers/AAAI/1982/AAAI82-032.pdf |accessdate=2009-03-28
}}
</ref>により提案されたもので、当初は[[木_(数学)|木構造]]上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した<ref name="KimPearl-1983">
{{cite conference
 |last=Kim |first=Jin H.
 |last2=Pearl |first2=Judea |authorlink2=ジューディア・パール
 |year=1983
 |title=A computational model for combined causal and diagnostic reasoning in inference systems
 |book-title=Proceedings of the Eighth International Joint Conference on Artificial Intelligence
 |conference=IJCAI-83: Karlsruhe, Germany
 |conferenceurl=http://dli.iiit.ac.in/ijcai/IJCAI-83-VOL-1/CONTENT/content.htm
 |volume=1
 |pages=190&ndash;193
 |url=http://dli.iiit.ac.in/ijcai/IJCAI-83-VOL-1/PDF/041.pdf |accessdate=2009-03-28
}}
</ref>。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている<ref name="Pearl-88">
{{Cite book
 |last1=Pearl |first1=Judea |authorlink1=ジューディア・パール
 |year=1988
 |title=Probabilistic Reasoning in Intelligent Systems:  Networks of Plausible Inference
 |edition=2nd
 |location=San Francisco, CA |publisher=Morgan Kaufmann
 |isbn=1-55860-479-0
}}
</ref>。

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

:<math>p_{X_i}(x_i) = \sum_{\mathbf{x}': x'_i=x_i} p(\mathbf{x}').</math>

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

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

:<math>p(\mathbf{x}) = \prod_{u \in U} f_u (\mathbf{x}_u)</math>

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

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

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

::<math>\mu_{v \to u} (x_v) = \prod_{u^* \in N(v)\setminus\{u\} } \mu_{u^* \to v} (x_v).</math>

:ここで、''N''(''v'')は変数ノードvに隣接する、すべての因子ノードの集合とする。<math>N(v)\setminus\{u\}</math>が空集合であるならば、<math>\mu_{v \to u}(x_v)</math>は一様分布として計算する。

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

::<math>\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^*}).</math>

:ここで、''N''(''u'')は因子ノード''u''に隣接する、すべての変数ノードの集合とする。<math>N(u) \setminus \{v\}</math>が空集合であるならば、<math>\mu_{u \to v} (x_v) = f_u(x_v)</math>とする。

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

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

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

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

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

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

:<math> p_{X_v} (x_v) \propto \prod_{u \in N(v)} \mu_{u \to v} (x_v). </math>

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

:<math> p_{X_u} (\mathbf{x}_u) \propto f_u(\mathbf{x}_u) \prod_{v \in N(u)} \mu_{v \to u} (x_u). </math>

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

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

loopy belief propagationアルゴリズムの正確な収束条件は未だに明らかでないが、単一のループを含むグラフにおいては、厳密解ではないにしろ、常に収束することが知られている<ref>
{{Cite journal
 |last=Weiss |first=Yair
 |title=Correctness of Local Probability Propagation in Graphical Models with Loops
 |journal=[[Neural Computation]]
 |year=2000
 |volume=12 |issue=1 |pages=1&ndash;41
 |doi=10.1162/089976600300015880
}}
</ref>。その他にもloopy belief propagationが唯一の固定点に収束するための十分条件(必要条件でない)がいくつか存在する<ref>
{{Cite journal
 |last1=Mooij |first1=J
 |last2=Kappen |first2=H
 |title=Sufficient Conditions for Convergence of the Sum–Product Algorithm
 |journal=[[IEEE Transactions on Information Theory]]
 |volume=53 |issue=12 |pages=4422&ndash;4437 |year=2007
 |doi=10.1109/TIT.2007.909166
}}
</ref>。一方で、メッセージが発散したり、各反復回数毎に解が振動するようなグラフも存在する。EXITチャートのような手法を用いて、確率伝搬法の経過やその収束状況について近似的に可視化し、調査することもできる。

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

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

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

:<math>\arg\max_{\mathbf{x}} g(\mathbf{x}).</math>

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

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

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

:<math>P(\mathbf{X}) = \frac{1}{Z} \prod_{f_j} f_j(x_j)</math>

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

:<math>E(\mathbf{X}) = \log \prod_{f_j} f_j(x_j).</math>

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

:<math>F = U - H = \sum_{\mathbf{X}} P(\mathbf{X}) E(\mathbf{X}) + \sum_{\mathbf{X}}  P(\mathbf{X}) \log P(\mathbf{X}).</math>

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

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

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

確率伝搬法の精度を改良する際のもう一つの手法として、対象の場(メッセージ)の分布のレプリカ対称性を破る方法がある。この一般化によって[[survey propagation]](SP)と呼ばれる新しい手法が導かれており、充足性<ref name="Sat">
{{Cite journal
 |last1=Braunstein |first1=A.
 |last2=Mézard |first2=R.
 |last3=Zecchina
 |title=Survey propagation: An algorithm for satisfiability
 |journal=Random Structures & Algorithms
 |volume=27 |issue=2 |pages=201&ndash;226 |year=2005
 |doi=10.1002/rsa.20057
 |first3=R.
}}
</ref>や[[グラフ彩色|グラフ彩色問題]]などといった[[NP完全]]な問題に対して非常に効率的に解くことができる。

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

==ガウシアン確率伝搬法(Gaussian Belief Propagation, GaBP)==
ガウシアン確率伝搬法は確率伝搬法アルゴリズムの別形であり、対象の分布が[[正規分布|ガウス分布]]である場合の確率伝搬法を指している。このようなモデルに対する解析は、初めにWeissとFreeman<ref name="GPbA">
{{Cite journal
 |last1=Weiss |first1=Yair
 |last2=Freeman |first2=William T.
 |title=Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology
 |journal=[[Neural Computation]]
 |volume=13 |issue=10 |pages=2173&ndash;2200 |month=October |year=2001
 |doi=10.1162/089976601750541769
 |pmid=11570995
}}
</ref>によって行われた。

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

:<math> P(x_i) = \frac{1}{Z} \int_{j \ne i} \exp(-1/2x^TAx + b^Tx)\,dx_j</math>

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

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

: <math>\underset{x}{\operatorname{argmax}}\  P(x) = \frac{1}{Z} \exp(-1/2x^TAx + b^Tx).</math>

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

: <math> \underset{x}{\operatorname{min}}\ 1/2x^TAx - b^Tx.</math>

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

: <math> Ax = b.</math>

GaBPアルゴリズムの収束性は(一般的な確率伝搬法の場合と比較して)解析が容易であり、2種類の十分条件が知られている。一つはWeissが2000年に定式化した条件であり、Aが対角優位行列である場合に関して収束性が保証されている。二つめは2006年にJohnsonら<ref name="johnson">
{{Cite journal
 |first1=Dmitry M. |last1=Malioutov
 |first2=Jason K. |last2=Johnson
 |first3=Alan S. |last3=Willsky
 |title=Walk-sums and belief propagation in Gaussian graphical models
 |journal=[[Journal of Machine Learning Research]]
 |volume=7 |pages=2031–2064 |month=October |year=2006
 |url=http://jmlr.csail.mit.edu/papers/v7/malioutov06a.html |accessdate=2009-03-28
}}
</ref>が定式化した条件であり、行列の[[スペクトル半径]]が下式を満たしている場合に収束する。

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

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

GaBPアルゴリズムは線形代数の領域と関連がある<ref name="Bickson">Gaussian belief propagation solver for systems of linear equations. By O. Shental, D. Bickson, P. H. Siegel, J. K. Wolf, and D. Dolev, IEEE Int. Symp. on Inform. Theory (ISIT), Toronto, Canada, July 2008. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/</ref>。具体的には、GaBPアルゴリズムは''A''が情報行列で''b''がシフトベクトルである場合の線形方程式''Ax=b''を解くための反復アルゴリズムとして見ることができる。GaBPアルゴリズムの収束条件は[[ヤコビ法]]の十分条件と等価であり、かつ、GaBPアルゴリズムの収束速度はヤコビ法、[[ガウス＝ザイデル法]]、[[SOR法]]などといった古典的な反復手法よりも早いことが経験的に知られている<ref name="Bickson2">Linear Detection via Belief Propagation. Danny Bickson, Danny Dolev, Ori Shental, Paul H. Siegel and Jack K. Wolf. In the 45th Annual Allerton Conference on Communication, Control, and Computing, Allerton House, Illinois, Sept. 07. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/</ref>。さらに、GaBPアルゴリズムは[[共役勾配法]]の条件下で発生する、計算上の問題に対して耐性があることが示されている<ref name="Bickson3">Distributed large scale network utility maximization. D. Bickson, Y. Tock, A. Zymnis, S. Boyd and D. Dolev. In the International symposium on information theory (ISIT), July 2009. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/</ref>。

==注釈==
{{Reflist}}

==参考文献==
* Frey, Brendan (1998). ''Graphical Models for Machine Learning and Digital Communication''.  MIT Press
* {{仮リンク|デービッド・J・C・マッケイ|en|David J. C. MacKay}} (2003). Exact Marginalization in Graphs. In David J.C. MacKay, ''Information Theory, Inference, and Learning Algorithms'', pp.&nbsp;334–340. Cambridge: Cambridge University Press.
* Mackenzie, Dana (2005). [http://www.newscientist.com/channel/info-tech/mg18725071.400 ''Communication Speed Nears Terminal Velocity'']  New Scientist. 9 July 2005. Issue 2507 (Registration required)
* {{Cite journal
 |last1=Yedidia |first1=J.S.
 |last2=Freeman |first2=W.T.
 |last3=Weiss |last4=Y.
 |title=Constructing free-energy approximations and generalized belief propagation algorithms
 |journal=[[IEEE Transactions on Information Theory]]
 |volume=51 |issue=7 |pages=2282&ndash;2312 |month=July |year=2005
 |doi=10.1109/TIT.2005.850085
 |url=http://www.merl.com/publications/TR2004-040/ |accessdate=2009-03-28
 |first3=Y.
}}
* {{Cite book
 |last1=Yedidia |first1=J.S.
 |last2=Freeman |first2=W.T. |last3=Y.
 |chapterurl=http://www.merl.com/publications/TR2001-022/  |accessdate=2009-03-30
 |chapter=Understanding Belief Propagation and Its Generalizations
 |title=Exploring Artificial Intelligence in the New Millennium
 |isbn=1-55860-811-7
 |pages=239&ndash;236
 |month=January |year=2003
 |publisher=Morgan Kaufmann
 |editor1-first=Gerhard |editor1-last=Lakemeyer
 |editor2-first=Bernhard |editor2-last=Nebel
}}
* {{Cite book
 |last=Bishop |first=Christopher M
 |title=Pattern Recognition and Machine Learning
 |chapterurl=http://research.microsoft.com/%7Ecmbishop/PRML/Bishop-PRML-sample.pdf |accessdate=2009-03-30
 |chapter=Chapter 8: Graphical models
 |isbn=0-387-31073-8
 |publisher=Springer
 |year=2006
 |pages=359&ndash;418
}}
* Koch, Volker M. (2007). [http://www.volker-koch.com/diss/''A Factor Graph Approach to Model-Based Signal Separation''] --- A tutorial-style dissertation
* {{Cite book
    | last = Wymeersch
    | first = Henk
    | title = Iterative Receiver Design
    | year = 2007
    | publisher = Cambridge University Press
    | url = http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521873154
    | isbn = 0-521-87315-0 }}
* Bickson, Danny. (2009). [http://www.cs.cmu.edu/~bickson/gabp/index.html''Gaussian Belief Propagation Resource Page''] --- Webpage containing recent publications as well as Matlab source code.
* Coughlan, James. (2009). [http://www.ski.org/Rehab/Coughlan_lab/General/TutorialsandReference/BPtutorial.pdf''A Tutorial Introduction to Belief Propagation''].
{{DEFAULTSORT:かくりつてんはん}}
[[Category:グラフィカルモデル]]
[[Category:ベイズ統計]]
[[Category:確率論]]
[[Category:符号理論]]
[[Category:数学に関する記事]]