belief revision アルゴリズムとは
2010-03-25
産業技術総合研究所 脳神経情報研究部門
一杉 裕志

内容
• max と argmax• MPE(most probable explanation)• 脳とMPE• belief revision アルゴリズム• 確率伝播アルゴリズムと belief revision アルゴリズムの一般形

前提知識• 下記資料をお読みください。
「確率伝播アルゴリズムとは」
http://staff.aist.go.jp/y-ichisugi/besom/20100226what-is-bp.pdf– 以下の概念を解説しています。
• 確率論の基礎– 同時確率、条件付確率、周辺化、ベイズの定理• ベイジアンネット• 確率伝播アルゴリズム

概要• 脳が行う認識アルゴリズムの候補として、確率伝播アルゴリズムよりも、 MPE を計算する belief revision アルゴリズムの方が有望に思えるので、それについて解説する。
• belief revision アルゴリズムについては 書籍[Pearl 1988] に書かれているが、分かりにくい点があるので、自分なりに補足して説明する。
（間違いがあればご指摘ください。）

max と argmax

max• max(a,b) は、 a と b のうち大きいほうの値。
例： max(3,5)=5• maxxf(x) は、x の定義域の中で最大の f(x) の値。
( − ( x − 2) 2 )例： x∈{1,2,3,4} の時、 max
x= max(−1,0,−1,−4) = 0• 本文書ではΣと同様の文法に従うものとする。
• [Pearl 1988] も同様。

max B max D max F = max( B max( D max F ))ACEACE

argmax• argmaxx f(x) は、 f(x) を最大にする時の xの値。
– 例： x ∈{1,2,3,4} の時、
arg max(−( x − 2) 2 ) = 2x

• [Pearl 1988] p.255 では maxx-1 f(x) と表記しているが、同じもの。

多変数の場合下記の関係が成り立つ。

max f (a, b) = max(max f (a, b)) = max(max f (a, b))a ,babba

arg max f (a, b) = (arg max(max f (a, b)), arg max(max f (a, b)))( a ,b )abba

例：
f(1,1)=1f(2,1)=4f(3,1)=6f(4,1)=4maxaf(a,1)=6f(1,2)=2f(2,2)=2f(3,2)=2f(4,2)=5maxaf(a,2)=5f(1,3)=5f(2,3)=3f(3,3)=1f(4,3)=1maxaf(a,3)=5f(1,4)=3f(2,4)=7f(3,4)=3f(4,4)=2maxaf(a,4)=7maxbf(1,b)=5maxbf(2,b)=7maxbf(3,b)=6maxbf(4,b)=5maxa,bf(a,b)=7

MPE (most probableexplanation)

MPE (most probableexplanation)• ベイジアンネット内すべての変数の集合を Wとし、その一部の変数の観測値 e が与えられた時、 W の値の組 w のうち P(w|e) を最大にするものを MPE と呼ぶ。
w* = arg max P (w | e)w

• 意味は「観測事実に対する一番ありそうな解釈」、「一番もっともらしい説明」。
参考： [Pearl 1988] p.250

MPEと同時確率• 観測値が与えられていない変数の集合の値の組を h とすると、ＭＰＥ は下記のようにも書ける。
h* = arg max P (h | e)h= arg max P (h, e) / P (e) = arg max P (h, e)hhw* = h * ∪e

• h* をＭＰＥと呼ぶ場合もある。

具体例• 下記ネットワークにおいて B, D の観測値 b,d, が与えられたとする。MPE となる値の組
A=a*,C=c*,E=e* は下記のように定義される値。
(a*, c*, e*)= arg max P (a, c, e | b, d )ABC( a ,c ,e )= arg max P (a, b, c, d , e)
( a ,c ,e )DE脳とMPE

曖昧図形とＭＰＥ• 人間は壺にも横顔にも解釈できる曖昧図形を、ある瞬間にはそのどちらか１つだと認識し、決して壺５１％横顔４９％というような認識はしない。
つまり、脳の認識の結果は、確率伝播アルゴリズムが計算する「ノードごとの周辺事後確率」よりも、MPEの方に似ている。

ＥＭアルゴリズムとＭＰＥ• 脳の学習アルゴリズムとして、ＥＭアルゴリズムは有望な候補だろう。
– 感覚連合野のニューロンを隠れ変数と考える。

• 隠れ変数の確率分布の代わりに、 k-mean のように１つの値（=MPE）を使うことについて[Nealand Hinton 1998] ６章で少し論じられている。
– 計算量が少なくて済むという利点がある。
– 理論的には必ずしも収束しないが、全く ad hoc で無意味、というわけでもない。
•

なおk-meanはEMのある極限と見なせる。（ビショップ本下 p.159 参照）

モンテカルロＥＭと近似ＭＰＥ• 隠れ変数の確率分布の代わりに、確率分布から得られたサンプルを使うモンテカルロＥＭアルゴリズムがある。サンプルが１つだけの場合、確率的ＥＭと呼ぶ。(ビショップ本 下 p.250-251)• 近似MPE計算は局所解に陥ることがあるが、それにより厳密MPEよりもサンプル抽出のよい近似になる、かもしれない？

確率分布

サンプル５個
サンプル１個MPEの局所解belief revisioin アルゴリズム

belief revision アルゴリズムとは• loop のないベイジアンネットにおいて、MPEの厳密解を効率的に計算するアルゴリズム。
– 確率伝播アルゴリズムほど知名度がないので、定訳はない？
• 信念改訂アルゴリズムと呼ぶのが適切か？

– 人工知能の分野で belief revision という用語があるようだが、まったく別のもの。

• 隠れマルコフモデル(HMM)専用の beliefrevision アルゴリズムは、ビタビ(Viterbi )アルゴリズムとしてよく知られている。

原理• a >=0 のとき
max(ab, ac) = a max(b, c)– 同様にmaxx(a f(x)) = a maxxf(x)• したがって確率伝播アルゴリズムの導出と同様の最適化が行える。

簡単なベイジアンネットの例

A• このネットワークを例に、D の観測値 d が与えられた時のＭＰＥ :(a*,b*,c*)=argmax(a,b,c) P(A=a,B=b,C=c,D=d)を計算するアルゴリズムを導出してみる。

BCD

P( A, B, C , D)
= P ( D | C ) P (C | B) P( B | A) P( A)ＭＰＥの計算式
c* = arg max max P (a, b, c, d )a ,bc= arg max (max ( P(d | c) P(c | b) P(b | a ) P (a )))a ,bc= arg max ( P(d | c) max( P(c | b) max( P(b | a ) P (a )) ) )
bca

同様に

b* = arg max max P(a, b, c, d )ba ,c= arg max (max P(d | c) P(c | b)) (max P (b | a ) P(a ))cba

a* = arg max max P(a, b, c, d )ab ,c= arg max (max (max P (d | c) P(c | b)) P(b | a )) P (a )abc

メッセージ• 関数を下記のように定義。確率伝播アルゴリズムの時と同様にを「XからYへのメッセージ」と呼ぶ。
m AB (a ) = P (a )mBC (b) = max P (b | a ) P (a ) = max P (b | a )m AB (a )aamDC (c) = P(d | c)
mCB (b) = max P(d | c) P(c | b) = max mDC (c) P (c | b)
ccmBA (a ) = max (max P(d | c) P(c | b)) P(b | a )bc= max mCB (b) P (b | a )bbelief revisionアルゴリズム
m AB (a ) = P(a)mBC (b) = max P(b | a)m AB (a )amDC (c) = P (d | c)
AmCB (b) = max mDC (c) P(c | b)
cmBA (a ) = max mCB (b) P(b | a )bB

c* = arg max mDC (c) max P(c | b)mBC (b)cCbb* = arg max mCB (b)mBC (b)ba* = arg max mBA (a )m AB (a )Dabelief revision アルゴリズムの性質• belief revision アルゴリズムは、確率伝播アルゴリズムのΣをmaxに、正規化を argmax変えたものに一致する。
• 確率伝播アルゴリズムと同様に、一般に下記の性質を持っている。
– X が送るメッセージおよび x* は、 X に送られてくるメッセージと X の条件付確率表という局所的な情報だけから計算できる。
– どれが観測変数であっても、観測変数以外のノードが行う計算は変わらない。

max を実行する神経回路•max P(b | a )m AB (a) とか max mCB (b) P(b | a) という形
abの計算がたくさん出てくる。
この計算は神経回路にとって、内積計算ほどは簡単ではない。
• しかしながら、 大脳皮質内に存在しそうな比較的簡単な神経回路でmax が実現可能なことが示されている。 [Litvak and Ullman 2009]
a + max(b-a, 0) = max(a,b) という関係をうまく使う。
ニューロンは非負の値しか出力しないので max(b-a,0) の演算は簡単に実現できる。
抑制性入力 -a
興奮性入力 b出力max(b-a,0)脳と belief revision• ベイジアンネット（有向グラフ）ではなくマルコフ確率場（無向グラフ）で loopy beliefrevision を実行する spiking neuron の神経回路モデルが提案されている。 [Litvak andUllman 2009]• 大脳皮質が確率伝播アルゴリズムを実行している証拠はいくつかある。これらの証拠はbelief revision アルゴリズムの証拠にもなる可能性がある。
– 今後、より詳細に検討していく予定。

確率伝播アルゴリズムと
belief revision アルゴリズムの一般形

loop のないベイジアンネットに対する確率伝播アルゴリズム [Pearl 1988]
BEL( x) = αλ ( x)π ( x)U1π ( x) = ∑ P( x |u1 , L, um )∏ π X (uk )u1 ,L,u mπX(uk)kλ ( x) = ∏ λY ( x)πYl(x)ll

π Y ( x) = β1π ( x)∏ λY ( x)lj ≠l

λ X (uk ) = β 2 ∑ λ ( x)x...

Y1j...

Uk

Um...

XλX(uk)λYl(x)

Yl... Yn∑ P( x |u ,L, u )∏ π (u )1u1 ,L,u m / u km

Xii≠k[Pearl 1988] p.182 。少し表記は変えてある。
なお、最上端、最下端ノードなどの境界条件については [Pearl 1988] p.181 参照

補足• BEL(x) が変数 x の周辺事後確率。αは正規化定数。 α = 1 / ∑ λ ( x)π ( x)x• β 1,β2はメッセージの正規化定数だが、なくてもかまわない。(p.168)• π(x),λ(x)はX内部の一時変数。他のノードに送られるメッセージではない。
∑ という意味。 u 以外の全ての• ∑ はkui の値の組についての総和。
• ∏ は ∏ という意味。 k 以外の全ての iについての総積。
u1 ,L,u m / u k

u1 ,L,u k −1 ,u k +1 ,L,u mi ≠ki =1,L, k −1, k +1,L, nメッセージに含まれる情報の性質• メッセージ送信相手からの情報を除外している。
λX(Uk)
U1...

Uk...

Um...

U1xi

Y1...

...

Umxi

Yl

λ X (uk ) = β 2 ∑ λ ( x)
x

Uk...

Yn...

Y1πYl(x)

Yl...

Yn

∑ P( x |u ,L, u )∏ π (u )1u1 ,L,u m / u kmXi≠ki

π Y ( x) = β1π ( x)∏ λY ( x)lj ≠ljloop のないベイジアンネットに対する
belief revision アルゴリズム [Pearl 1988]• [Pearl 1988] p.255 では下記のように表現されている。
– ただし関数名につく＊（アスタリスク）は省略した。使用する記号も少し変えた。
– 誤りと思われる点を２点修正した。

F ( x, u1 ,L , u m ) = (∏ λYl ( x)) P ( x | u1 ,L , u m )∏ π X (u k )lx* = arg max BEL( x)k

かっこを追加x

BEL( x) = max F ( x, u1 ,L , um )u1 ,L,u m

λ X (uk ) =βは不要なので削除

max ( F ( x, u1 , L , um ) / π X (uk ))x ,u1 ,L,u m / u k

BEL( x)π Yl ( x) = β
λYl ( x)belief revision アルゴリズムの[Pearl 1988]の表現を変形してみる
BEL( x) = max F ( x, u1 , L, um )u1 ,L,u m= max (∏ λYl ( x)) P( x | u1 , L , um )∏ π X (uk )u1 ,L,u mlk= (∏ λYl ( x)) max P( x | u1 , L , um )∏ π X (uk ) = λ ( x)π ( x)u1 ,L,u ml

λ X (uk ) ==kmax ( F ( x, u1 ,L , um ) / π X (uk ))x ,u1 ,L,u m / u kmax (∏ λYl ( x)) P( x | u1 , L, um )∏ π X (ui )x ,u1 ,L,u m / u ki≠kl= max λ ( x) max P( x | u1 , L, um )∏ π X (ui )xu1 ,L,u m / u ki≠kBEL( x)π Yl ( x) = β= βπ ( x)∏ λY j ( x)λYl ( x)j ≠l

結局、確率伝播アルゴリ
ズムのΣをmaxに変えたものに一致する。(p.256にもそう書いてある。)

loop のないベイジアンネットに対する
belief revision アルゴリズム
x* = arg max BEL( x)U1x

BEL( x) = λ ( x)π ( x)πX(uk)π ( x) = max P( x | u1 , L, um )∏ π X (uk )u1 ,L,u mπYl(x)kλ ( x) = ∏ λY ( x)...

Y1ll...

Uk

Um...

XλX(uk)λYl(x)

Yl... Yn

π Y ( x) = β1π ( x)∏ λY ( x)lj ≠ljλ X (uk ) = β 2 max λ ( x) max P( x | u1 ,L, um )∏ π X (ui )xu1 ,L,u m / u ki≠k

最上端、最下端ノードなどの境界条件は確率伝播アルゴリズムと同じ。
[Pearl 1988] p.256 参照。

参考文献
••

[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••[Neal and Hinton 1998] Radford Neal, Geoffrey E. Hinton, A View of
the EM algorithm that justifies incremental, sparse, and other variants,
In Learning in Graphical Models (1998), pp. 355-368.
http://www.cs.toronto.edu/pub/radford/emk.pdf[Litvak and Ullman 2009] Shai Litvak, Shimon Ullman: CorticalCircuitry Implementing Graphical Models, Neural Computation 21,3010.3056 (2009)http://www.mitpressjournals.org/doi/abs/10.1162/neco.2009.05-08-783