確率伝播アルゴリズムとはー 脳の認識機構と関係が深い「確率伝播アルゴリズム」について、極力分かりやすく解説する ー2010-02-26
産業技術総合研究所 脳神経情報研究部門
一杉 裕志

内容
• 確率論の基礎知識の復習• ベイジアンネットとは• 確率伝播アルゴリズム

背景• ベイジアンネットを用いて大脳皮質の機能を実現する研究が大きく進展しつつある。しかし関連論文はベイジアンネットの基礎知識がないと重要性を理解しずらい。
• ベイジアンネットの基本事項は数学的には実は難しくない。四則演算しか使わない。
• しかし確率論の独特の記法のため独学には敷居が高い。本資料ではできるかぎり親切に説明することを試みる。

確率論の基礎知識の復習確率論の基礎知識の復習• 確率変数 X が x という値を取る確率：P( X = x)
– 省略した記法： P(x)• 確率変数 X の確率分布： P( X )P( X , Y )• 同時確率：P( X ) = ∑ P( X , Y )• 周辺化：
Y• 条件付確率：P( X , Y ) = P ( X | Y ) P (Y )• ベイズの定理： P(Y | X ) = P( X | Y ) P(Y ) / P( X )P ってなに？
• 中に書かれる文字列と文脈によって異なる意味を持つ。
• 仮に「確率変数 X が値 x をとる確率」を表す
関数を p_X(x) とすると：– 確率 P(X=x) （略記 P(x)）は値 p_X(x) のこと。
– 確率分布 P(X) は関数 p_X のこと。

• 例えば P( X ) = ∑ P( X , Y ) は、こういう意味：
p_X = g• 参考：

Ywhere g ( x) =∑ p_X_Y( x, y)y∈Domain (Y )「確率の記法 - カーネル法Wiki」

http://www.neurosci.aist.go.jp/~akaho/kernel/index.php?%B3%CE%CE%A8%A4%CE%B5%AD%CB%A1

P 以外も要注意• P 単独で出てきて関数 p_X を表すこともある。小文字の p や q も同様。
• P と同様に、X ごとに定義される関数が λ X (x)と書かれずに λ (x) と書かれたり、 X と Y の組み合わせごとに定義される関数が λYX (x) と書かれずに λY (x) と書かれることもある。
– （本資料ではこういう省略は避けている。）– プログラミング言語的に解釈すると、すべての確率変数は型が違うから関数名の多重定義が可能ということかもしれない。

Σの文法• 総和の記号Σは足し算よりは優先度が高いが掛け算よりは低い。
⎛⎞⎛⎞
A∑ CD + E ∑ GH = A⎜ ∑ (CD ) ⎟ + E ⎜ ∑ (GH ) ⎟BF⎝ B⎠⎝ F⎠• 右から左に結合。

⎛ ⎛ ⎛ ⎛⎞⎞⎞⎞D ∑ F = ∑ ⎜ B⎜⎜ ∑ ⎜⎜ D⎜ ∑ F ⎟ ⎟⎟ ⎟⎟ ⎟∑A B∑⎜CEA ⎝ ⎝ C ⎝⎝ E ⎠ ⎠ ⎠ ⎟⎠• 総積の記号ΠもΣと同様。

⎛⎞
D = ∑ ⎜⎜ B∏ D ⎟⎟
∑A B∏
A ⎝CC
⎠

少なくとも[Pearl 1988]と「ビショップ本」はこういう文法のようである。
ただしたまにΠが掛け算よりも優先度が高い（ΠaΠb=(Πa)(Πb)）こともあるので要注意。

周辺化(marginalization)について• 周辺化とは、いくつかの確率変数を「無視」（marginalize ）した同時確率を求めること。
– marginalize :社会的に無視［過小評価］する, 主流から追いやる
三省堂 EXCEED英和辞典 http://dictionary.goo.ne.jp/leaf/ej2/43872/m0u/marginalize/P( X ) = ∑ P( X , Y )例：Y• 変数がたくさんあっても同様。

P(X=0,Y=0)=0.2

P(X=1,Y=0)=0.1

P(Y=0)=0.3

P(X=0,Y=1)=0.4

P(X=1,Y=1)=0.3

P(Y=1)=0.7

P(X=0)=0.6

P(X=1)=0.4

P(C , E ) = ∑∑∑∑ P ( A, B, C , D, E , F )A

BDF• 条件付確率でも同様。

P( X | Z ) = ∑ P( X , Y | Z )• これはだめ：YP( X | Z ) = ∑ P( X | Y , Z ) ???
Yベイズの定理についてP( X , Y ) = P(Y , X )条件付確率の定義から P ( X , Y ) = P ( X | Y ) P (Y )対称性から

P(Y , X ) = P(Y | X ) P( X )よってP ( X | Y ) P (Y ) = P(Y | X ) P( X )P(X)>0 ならば両辺を P(X) で割って、ベイズの定理が得られる。

P(Y | X ) = P( X | Y ) P(Y ) / P( X )なお、P ( X ) = ∑ P ( X , Y ) = ∑ P ( X | Y ) P (Y )Y

こうも書く：なので、YP( X | Y ) P(Y )P(Y | X ) =∑ P( X | Y ) P(Y )Y

X の値が与えられているなら、分子はΣP(Y|X)=1にするための正規化定数と考えて、こうも書く。

P(Y | X ) =1α

P ( X | Y ) P (Y )

ベイジアンネットとは

同時確率が分かっていればいろいろなことが計算できる• 例：芝生が濡れているとき、雨が降った確率を求めよ。ただし P(S,W,R,C) は与えられているものとする。
S: スプリンクラーが動いた
P( R = yes | W = yes)
W: 芝生が濡れている
P(W = yes, R = yes)
R: 雨が降った=
C: 雲が出ている
P(W = yes)

条件付確率の定義より∑∑ P(S ,W = yes, R = yes, C )=周辺化∑∑∑ P(S ,W = yes, R, C )S

CSRC

同時確率の素朴な記憶の仕方• 全ての値をテーブルで持つ。
• 変数が n 個あると O(2n) のサイズが必要。
→ n が大きくなると実用的でない！
SWRC

P(S,W,R,C)

nononono0.68nonono

yes

0.08

...

...

...

...

...

yes

yes

yes

yes

0.02
サイズ 24=16

ベイジアンネット• 同時確率の表を小さなサイズの条件付確率表の積に分解して効率的に（近似）表現できる場合がある。
→ そうやって表現したものがベイジアンネット
例： P ( S , W , R, C ) = P (W | S , R ) P (C | R ) P ( S ) P ( R )必要な条件付確率表：
上の式の内容を図で書くとこう：

SWRC

P(S=yes)
0.2

S
nono
yes
yes

Rno
yes
no
yes

P(R=yes)
0.02

P(W=yes|S,R)
0.120.80.90.98

R P(C=yes|R)
no 0.3yes 0.995

サイズ 4+2+1+1=8

矢印について• 矢印は必ずしも「因果関係」である必要はない。
• 矢印は推論時の情報の流れではない。あとで見るように、推論時には逆向きにも情報が流れる。
• n 個の確率変数の同時確率は実は n(n-1)/2本の矢印を使って必ず分解できるが、その場合は効率は良くならない。少ない矢印で表現できてはじめて効率がよくなる。

確率伝播アルゴリズム

確率伝播アルゴリズム(beliefpropagation algorithm)とは• ベイジアンネットにおいて、確率変数の事後確率を効率的に計算するアルゴリズム。
– 「伝播」は正しくは「でんぱ」と読むが「でんぱん」と誤読されることも多い。「伝搬」は誤読に起因する誤字。
– 信念伝播アルゴリズムとも訳される。

原理• 掛け算の足し算に対する分配法則：
a(b+c) = ab + ac
– 左辺は演算２回だが右辺は演算３回
nni =1i =1a ∑ bi = ∑ abi– 左辺は演算 n 回だが右辺は 2n-1 回。

• 因子のくくりだしを積極的に適用すれば、事後確率計算に必要な演算数を劇的に減らせる。
• さらに、演算の中間結果の重複計算を避けることで、効率を上げている。

簡単なベイジアンネットの例• 簡単なネットワークならば、それ専用の確率伝播アルゴリズムの導出は難しくない。
A• このネットワークを例に、D の観測値が与えられた時の事後確率 P(A|D), P(B|D), P(C|D) を計算するアルゴリズムを導出してみる。

BC

D

P( A, B, C , D)
= P ( D | C ) P (C | B) P( B | A) P( A)事後確率の計算式
P (C , D) 1
P(C | D) == ∑∑ P( A, B, C , D)
P( D)
α B A
1= ∑∑ (P( D | C ) P(C | B ) P ( B | A) P ( A) )ただし正規化定数
α = P(D) とする⎛⎛⎞⎞⎜= P ( D | C )⎜ ∑ P (C | B )⎜ ∑ P ( B | A) P ( A) ⎟ ⎟⎟
α⎝ A
⎠⎠⎝ B

P(D|C)はB, A に依存せず、P(C|B)はAに依存しないのでΣの外にくくりだせる。

α B

A

1

同様に

P( B | D) =1⎛⎞⎛⎞
P(D|C)
P(C|B)
P(B|A)
P(A)⎟⎜ ∑⎜∑⎟β⎝ C⎠⎠⎝ A⎞1⎛ ⎛⎞P( A | D) = ⎜⎜ ∑ ⎜ ∑ P( D | C )P(C | B) ⎟ P( B | A) ⎟⎟ P( A)γ⎝ B ⎝C⎠⎠

注：因子のくくりだし方は一通りとは限らないが、ここではこうくくりだす。

メッセージ• 関数 m AB , mBC , mDC , mCB , mBA を下記のように定義。 mXY を「XからYへのメッセージ」と呼ぶ。
m AB (a) = P ( A = a )mBC (b) = ∑ P( B = b | A) P( A) = ∑ P( B = b | A)m AB ( A)A

A

mDC (c) = P( D = d | C = c)

mCB (b) = ∑ P( D = d | C ) P(C | B = b) = ∑ mDC (C ) P(C | B = b)
CC⎛⎞mBA (a ) = ∑ ⎜ ∑ P( D = d | C )P(C | B) ⎟ P( B | A = a)
B ⎝ C⎠
= ∑ mCB ( B) P( B | A = a)B

メッセージの意味• メッセージ mZXは、事後確率 P(X|D) の計算に必要な情報のうち、 X に隣接するノード Z より先にあるものを全て集めたもの。

UmUX
X

mYXY

メッセージの中身• ノード X が n 個の値を取り得るとすると、
mXY(x) 、 mYX(x) として送られるものは実質的には n 次元数値ベクトル。
ノードX
x1

x2

...

xn

y1

y2

...

ym

(m XY ( x1 ), m XY ( x2 ),L , m XY ( xn ))ノードY(mYX ( x1 ), mYX ( x2 ),L , mYX ( xn ))確率伝播アルゴリズム
m AB (a ) = P(a )mBC (b) = ∑ P (b | a )m AB (a )amDC (c) = P (d | c)
Am AB

mBAB

c

mBA (a) = ∑ mCB (b) P (b | a )
bmBC

mCB

mCB (b) = ∑ mDC (c) P(c | b)

P (c | d ) =C

P(b | d ) =mDC
D

事後確率の計算
式を、メッセージを使った式に書きかえると、確率伝播アルゴリズムが得られる。

P(a | d ) =

1α1

β1γ

mDC (c)∑ P (c | b)mBC (b)bmCB (b)mBC (b)mBA (a )m AB (a )注：引数を小文字（値）に統一したが、大文字（確率変数）にしても意味するところは変わらない。

確率伝播アルゴリズムの性質• 一般に、 X が送るメッセージおよび X の事後確率は、 X に送られてくるメッセージと X の条件付確率表だけから計算できる！
（ただしメッセージを送る順序には注意。）• 局所的な情報だけを使ってアルゴリズムが実行されると言う意味で、神経回路と似ている。

• ここでは観測変数を D としたが、どれが観測変数であっても、観測変数以外のノードがやる計算は変わらない！
• １つの固定した神経回路を使って様々な推論が行えることを示している。

行われている計算
P(b | a )m (a )m (b) P(b | a )∑∑•とかという形のAB

CBab

計算がたくさん出てくるところに注目。
これは２つのベクトルの内積計算。
• 簡単な神経回路で実現可能。
– （ただし複雑なベイジアンネットではこうならないので注意。）

mBA (ai ) を計算する
ニューロン

結合の重み：
例：右図は下記の計算をする神経回路

P(b j | ai )a1

a2 ...

ai... anb1b2 ...

bj... bmmBA (a) = ∑ mCB (b) P(b | a )bmCB (b j )

を出力する
ニューロン

もう１つ簡単な例：[Rao 2005] のネットワーク

LFCI

P ( I , C , L, F )= P( I | C ) P(C | L, F ) P( L) P( F )同時確率の計算式
P( I , C ) 1= ∑∑ P ( I , C , L, F )P(C | I ) =α L F
P( I )
1= ∑∑ P( I | C ) P (C | L, F ) P ( L) P ( F )α L=1α

ただし正規化定数 α = P (I )FP ( I | C )∑∑ P (C | L, F ) P ( L) P ( F )LF

L と F に依存しない因子 P(I|C) をΣの外にくくりだす。

1⎛⎞⎞⎛
P( L | I ) = ⎜⎜ ∑ P( I | C )⎜ ∑ P(C | L, F ) P( F ) ⎟ ⎟⎟ P( L)
β⎝ C
⎠⎠⎝ F

同様に

1⎛
⎛
⎞⎞
P ( F | I ) = ⎜⎜ ∑ P ( I | C )⎜ ∑ P (C | L, F ) P( L) ⎟ ⎟⎟ P( F )γ⎝C⎝ L⎠⎠メッセージ• 関数 mLC , mFC , mIC , mCL , mCF を下記のように定義。
mLC ( L) = P( L)mFC ( F ) = P( F )mIC (C ) = P( I = I ' | C )⎛⎞mCL ( L) = ∑ P( I = I ' | C )⎜ ∑ P(C | L, F ) P ( F ) ⎟C⎝ F⎠
= ∑ mIC (C )∑ P (C | L, F )mFC ( F )CF⎛⎞
mCF ( F ) = ∑ P( I = I ' | C )⎜ ∑ P(C | L, F ) P ( L) ⎟C⎝ L⎠= ∑ mIC (C )∑ P (C | L, F )mLC ( L)CL

確率伝播アルゴリズム
mLC (l ) = P(l )mFC ( f ) = P ( f )LFmCFmLC

mIC (c) = P(i | c)

mCL (l ) = ∑ mIC (c)∑ P(c | l , f )mFC ( f )cmCLCmFC

fmCF ( f ) = ∑ mIC (c)∑ P(c | l , f )mLC (l )cP (c | i ) =mIC
IP(l | i ) =1α1βP( f | i) =1γ

lmIC (c)∑∑ P(c | l , f )mLC (l )mFC ( f )fl

mCL (l )mLC (l )mCF ( f )mFC ( f )メッセージの様々な記法• どれも意味は同じ。

X

mYX (x)X

m XY (x)Y

本資料

mY → XX

m X →YY[Rao 2005][Chikkerur, Serreand Poggio 2009]

λY (x)π Y (x)Y[Pearl 1988][George and Hawkins 2005][Ichisugi 2007]

「loop のある」ベイジアンネット• 矢印の向きを無視するとサイクル（循環構造）があるベイジアンネットを「loop がある」と言う。

矢印の向きを無視したときサイクルがある。
loop のあるベイジアンネットの例

loopy belief propagation• ベイジアンネットに loop があると、確率伝播アルゴリズムは使えない。
– メッセージの計算式が相互依存して計算できない。

• それでもあえて確率伝播アルゴリズムを適用し、適当な初期値からはじめてメッセージの再計算・伝播を繰り返すと、多くの場合メッセージの値が収束する。
– これを loopy belief propagation と呼び、近似解法としてよく使われている。
– 伝播の順序は重要でない。→ 非同期神経回路！

マルコフ確率場(Markov random field)• ベイジアンネットはノード間の結合に向きがある（非対称な結合）。向きのない（対称な）結合を使ったモデルはマルコフ確率場と呼ばれる。
• マルコフ確率場に対しても確率伝播アルゴリズムが定義される。考え方は同じ。

belief revision algorithm• 各変数の周辺事後確率ではなく、MPE （尤度最大の値の組）を求めるためのアルゴリズム。
• 考え方は belief propagation と同じ。和演算の代わりに max を使う。
• 脳の認識アルゴリズムは loopy beliefrevision の近似かも。
[Litvak and Ullman 2009]http://www.mitpressjournals.org/doi/abs/10.1162/neco.2009.05-08-783

大脳皮質のモデルの対立軸• 下記の対立軸があるが、現在特に論争になっているというほどではない。
– belief propagation vs. belief revision– 尤度 vs. 対数尤度
– ベイジアンネット vs. マルコフ確率場 vs. ヘルムホルツマシン– 発火頻度コーディング vs. 膜電位コーディング– （私の予想は、 belief revision, 尤度、ベイジアンネット、発火頻度コーディング。）

参考ＵＲＬ• 「脳とベイジアンネットＦＡＱ」
http://staff.aist.go.jp/y-ichisugi/besom/brain-bayesnet-faq.html• 「脳を理解するための情報源メモ」＃ベイジアンネット
http://staff.aist.go.jp/y-ichisugi/besom/brain-memo.html#Bayesian-network参考文献• [Pearl 1988]
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
Judea Pearl: Morgan Kaufmann Pub ; ISBN: 1558604790• 「ビショップ本」下 第８章 グラフィカルモデル
・ パターン認識と機械学習 上 - ベイズ理論による統計的予測
C. M. ビショップ (著), 元田 浩 (翻訳), 栗田 多喜夫 (翻訳), 樋口 知之 (翻訳), 松本 裕治 (翻訳), 村田昇 (翻訳) 出版社: シュプリンガー・ジャパン株式会社 (2007/12/10) ISBN-13: 978-4431100133
・ パターン認識と機械学習 下 - ベイズ理論による統計的予測
C. M. ビショップ (著), 元田 浩 (翻訳), 栗田 多喜夫 (翻訳), 樋口 知之 (翻訳), 松本 裕治 (翻訳), 村田昇 (翻訳) 出版社: シュプリンガー・ジャパン株式会社 (2008/7/11) ISBN-13: 978-4431100317

最後に• このくらいの基礎知識があれば、下記の論文が読めるはず。（？）[Lee 2003]
http://www.cnbc.cmu.edu/~tai/papers/lee_mumford_josa.pdf[George and Hawkins 2005]
http://www.cnbc.cmu.edu/cns/papers/GeorgeHawkinsIJCNN05.pdf[Rao 2005]
http://www.cs.washington.edu/homes/rao/nreport_bayes_atten05.pdf[Ichisugi 2007]
http://staff.aist.go.jp/y-ichisugi/besom/20070509ijcnn-paper.pdf[Chikkerur, Serre and Poggio 2009]http://dspace.mit.edu/bitstream/handle/1721.1/49416/MIT-CSAIL-TR-2009-047.pdf?sequence=1[Litvak and Ullman 2009]http://www.mitpressjournals.org/doi/abs/10.1162/neco.2009.05-08-783• 質問大歓迎。

大脳皮質とベイジアンネット
関連文献
••

•

[Lee 2003] Lee, T.S., Mumford, D. (2003) Hierarchical Bayesianinference in the visual cortex. Journal of Optical Society of America,A. . 20(7): 1434-1448.
http://www.cnbc.cmu.edu/~tai/papers/lee_mumford_josa.pdf[George and Hawkins 2005] George, D. Hawkins, J., A hierarchical
Bayesian model of invariant pattern recognition in the visual cortex, In
proc. of IJCNN 2005, vol. 3, pp.1812-1817, 2005.
http://www.cnbc.cmu.edu/cns/papers/GeorgeHawkinsIJCNN05.pdf[Rao 2005] R. Rao., Bayesian inference and attention in the visualcortex. Neuroreport 16(16), 1843-1848, 2005.
http://www.cs.washington.edu/homes/rao/nreport_bayes_atten05.pdf

大脳皮質とベイジアンネット
関連文献•••[Ichisugi 2007] Yuuji ICHISUGI,The cerebral cortex model that selforganizes conditional probability tables and executes belief
propagation,In Proc. of International Joint Conference on Neural
Networks (IJCNN2007), pp.1065--1070, Aug 2007.
http://staff.aist.go.jp/y-ichisugi/besom/20070509ijcnn-paper.pdf[Chikkerur, Serre and Poggio 2009] Sharat Chikkerur, Thomas Serreand Tomaso Poggio: A Bayesian inference theory of attention:neuroscience and algorithms, Computer Science and Artificial
Intelligence Laboratory Technical Report, MIT-CSAIL-TR-2009-047
CBCL-280, October 3, 2009http://dspace.mit.edu/bitstream/handle/1721.1/49416/MIT-CSAIL-TR2009-047.pdf?sequence=1[Litvak and Ullman 2009] Shai Litvak, Shimon Ullman: Cortical
Circuitry Implementing Graphical Models, Neural Computation 21,3010.3056 (2009)http://www.mitpressjournals.org/doi/abs/10.1162/neco.2009.05-08-783