情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

ベーテ自由エネルギーと Loopy belief Propagation に現れる
グラフのゼータ関数について
渡辺 有祐∗
Yusuke Watanabe

福水 健次 ∗
Kenji Fukumizu

Abstract: In this paper, we show a new formula which connects the Hessian of the Bethe
free energy and the multivariable graph zeta function. Utilizing this formula, we show
new methods for analyses of Loopy Belief Propagation (LBP) algorithm. We mainly proveand discuss the formula in the case of binary pairwise model. First, we give a suﬃcientcondition that the Hessian of the Bethe free energy is positive deﬁnite, which shows nonconvexity for graphs with multiple cycles. The formula clariﬁes the relation between thelocal stability of a ﬁxed point of LBP and local minima of the Bethe free energy. We also
propose a new approach to the uniqueness of LBP ﬁxed point, and show various conditionsof uniqueness. Finally, we discuss the extension to more general class of graphical models
including multinomial models and Gaussian models.
Keywords: Loopy Belief Propagation, Bethe free energy, graph zeta function

1

導入

Pearl によるビリーフプロパゲーション（Belief Propagation, BP）アルゴリズム [1] は、木構造を持つ確率モデルに対して効率的に分配関数や周辺確率分布を厳密計
算することが知られていた。さらにサイクルをもつようなグラフ上の確率モデルに対してもこのアルゴリズムを
そのまま適用すると、各種の応用において非常に高い近似性能を与えることが経験的に知られている [2]。このように拡張されたアルゴリズムは通常ルーピービリーフ
プロパゲーション (Loopy Belief Propagation, LBP) と呼ばれている。LBP は BP とは違って、複雑なふるまいをするアルゴリズムであり、それについて理解を深めることは重要な問題である。
この LBP アルゴリズムはベーテ自由エネルギーと密接に関係している [3] という大変興味深い性質を持っている。すなわち、LBP アルゴリズムの固定点がベーテ
自由エネルギーの勾配がゼロの点と一対一に対応する。
この論文ではまず最初に、バイナリかつペアワイズなモデルに対して「ベーテ自由エネルギーの行列式は、正の因子を除いて、グラフの多変数ゼータ関数の逆数に等しい」という公式を証明する。その後でこの公式を三つ∗ 総合研究大学院大学

複合科学研究科 統計科学専攻、統計数理研究所, 106-8569 東京都港区南麻布 4-6-7, tel.03-3446-1501, e-mailwatay@ism.ac.jp,fukumizu@ism.ac.jp
Institute of Statistical Mathematics, 4-6-7, Minami-Azabu,
Minato-Ku, Tokyo, 106-8569の問題に応用する。
まず第一に、この公式をベーテ自由エネルギーのヘッセ行列の正定値性に関する議論に応用する。ベーテ自由エネルギーは一般には凸でないことが知られており、これが LBP の振動現象や固定点が多数出現することの一つの原因になっている。したがって、ヘッセ行列が正定値である範囲を知ることは興味のある問題である。この論文ではヘッセ行列が正定値である簡単な十分条件を与える。そしてさらにベーテ自由エネルギーが凸である必
要十分条件はグラフがツリー、又はただ一つのサイクルを持つグラフであることを証明する。
第二の応用として、LBP の固定点の安定性とその点でのベーテ自由エネルギーの局所的な構造の関係を議論する。LBP はベーテ自由エネルギーを単純に小さくする
ようなアルゴリズムではないため、その関係は非自明である。それについて Heskes [4] は、局所安定な LBP の
固定点はベーテ自由エネルギーの極小であることを示している。本論文では、グラフのゼータ関数に現れる行列のスペクトルについて考え、Heskes の結果を拡張する。
第三に、LBP の固定点の一意性について議論する。
まず、「LBP の固定点の指数の和は 1」という定理を示し、それとゼータ関数とヘッセ行列の公式を組み合わせるというアプローチで一意性を議論する。特にこの方法で「二つの一次独立なサイクルを持つグラフ上で、

attractive でない相互作用の場合」を考えると、LBP の∑

固定点は一意的であるということを示す。

xj bij (xi , xj ) = bi (xi ) と bij (xi , xj ) > 0 は自動的に

ここまではバイナリペアワイズのモデルに対する話で満たされる。

あった。本論文の一番最後では、ゼータ関数とベーテ自次に、ベーテ自由エネルギーをギブス自由エネルギー

由エネルギーの公式が一般の有限状態のグラフィカルモの計算可能な近似物として導入しよう。真の確率分布 (1)デルや、ガウス型のモデルに拡張できることを述べる。

は変分問題 p(x) = argminp̂ FGibbs (p̂) によって特徴づけられる。（最小は全ての (xi )i∈V 上の確率分布に関して

2

LBP とベーテ自由エネルギーとる。）ギブス自由エネルギー FGibbs (p̂) は FGibbs (p̂) =この論文を通じ、G = (V, E) は頂点集合 V と無向辺
集合 E をもつ連結グラフとする。頂点数は N 、辺の本数は M とする。以下ではバイナリ xi ∈ {±1} の場合を考える。変数 x = (xi )i∈V 上の確率分布が次のような形で与えられる場合（ペアワイズ型）を考えよう:∏
1 ∏p(x) =
ψij (xi , xj )ψi (xi ),Z
ij∈E

KL(p̂||p) − log Z によって定義され、p̂ に関する凸関数∫である。（ただし、KL(p̂||p) = p̂ log(p̂/p) は p̂ から pへのカルバックライブラーダイバージェンス。）∑
一方、ベーテ近似においては制約条件 xi ,xj bij (xi , xj ) =∑1,
xj bij (xi , xj ) = bi (xi ), bij (xi , xj ) > 0 を満たし
た {bi (xi ), bij (xi , xj )} に関するで最小化を考える。この

(1)

i∈V

ような制約条件を満たす {bi (xi ), bij (xi , xj )} のことを

pseudomarginal という。次で定義されるギブス自由エ

ただしここで Z は規格化定数であり ψij と ψi は正値のネルギーの変形をベーテ自由エネルギーという。
（di :=関数である。一般性を失うことなく ψi (xi ) = exp(hi xi ),|Ni | は頂点の次数。）

ψij (xi , xj ) = exp(Jij xi xj ) としてよい。
∑
各種の応用において、周辺分布 pi (xi ) := x\{xi } p(x)∑と pij (xi , xj ) := x\{xi xj } p(x) を計算することが必要になる。グラフがツリーであればこれらは Pearl のビ
リーフプロパゲーション（BP）アルゴリズムで効率的

F (b) := −−+初期化されたメッセージ µi→j (xj ) が割り当てられ、次のようにして更新される。

µnewi→j (xj ) ∝∑∏ψji (xj , xi )ψi (xi )µk→i (xi ), (2)

文では、メッセージはすべての辺について並列に更新するものと考える。
メッセージがある固定点 {µ∞i→j (xj )} に収束したとす
るとき、pi (xi ), pij (xi , xj ) の近似は次のように計算される。
bi (xi ) ∝ ψi (xi )

+

k∈Ni

bij (xi , xj ) ∝ ψij (xi , xj )ψi (xi )ψj (xj )∏ ∞∏ ∞µk→i (xi )µk→j (xj ),∑(3)k∈Nj \i∑= 1 ,xi bi (xi ) = 1と規格化するものとする。式 (2) と (3) より, 関係式
ただし、

xi ,xj bij (xi , xj )∑(1 − di )i∈V∑bi (xi ) log bi (xi ).

(4)

xi

ベーテ自由エネルギー F の定義域は pseudomarginal の全体であり、極小はただ一つとは限らない。この変分問題で得られる {bi (xi ), bij (xi , xj )} は LBP によって得られるそれと同じである [3]。正確には、ベーテ自由エネ
一対一に対応する。

χij = Ebij [xi xj ] を使おう。このとき pseudomarginals
は以下のように表示される。:
bij (xi , xj ) =bi (xi ) =1(1 + mi xi + mj xj + χij xi xj ),4

1(1 + mi ).
2(5)

同様に F の定義域は次のようになる：{
L(G) := {mi , χij } ∈ RN +M ; 1 + mi xi + mj xj + χij xi xj > 0}
ij ∈ E xi , xj = ±1 .

µ∞k→i (xi ),k∈Ni \jbij (xi , xj ) log bij (xi , xj )以下の議論の都合上、冗長性のない変数 mi = Ebi [xi ],ただし Ni は i ∈ V の近傍の頂点の集合である。通常は∑
xi =±1 µi→j (xj ) = 1 のように規格化される。この論∏∑ ∑ルギーの勾配ゼロの点の全体と LBP の固定点の全体がk∈Ni \jxibi (xi ) log ψi (xi )ij∈E xi xj

が経験的に知られており、この方法はルーピービリーフ

ある。すなわち、各有向辺に対して、まず最初に適当に∑∑i∈V xi

合でも BP をそのまま適用すると良い近似を与えること

LBP はメーッセージを伝搬していくアルゴリズムでbij (xi , xj ) log ψij (xi , xj )ij∈E xi xj

かつ厳密に計算できる [1]。グラフがサイクルを持つ場

プロパゲーション（LBP) と呼ばれている。

∑ ∑F のヘッセ行列 ∇2 F とは {mi , χij } に関する二階微分からなる、大きさ N + M の正方行列である。これはL(G) 上の行列値関数とみることができる。ちなみに、∇2 F は Jij と hi に依存しないことに注意しよう。

ゼータ関数とベーテ自由エネルギー3

しよう。この公式は定理 3 の証明で非常に重要な働きをのヘッセ行列3.1

次に多変数ゼータ関数のもう一つの行列式表示を証明果たすことになる。

ゼータ関数と伊原の公式

定理 2 (伊原の公式の多変数版). V 上の関数の全体をまずグラフに関する用語を準備しよう。グラフ G の⃗各無向辺を逆向きの無向辺のペアとみて、有向辺集合 E⃗ = 2M である。各有向辺 e ∈ E⃗にをつくる。よって |E|
対して、o(e) ∈ V を e の始点とし、t(e) ∈ V を e の終⃗ に対し、その逆を ē、対応点とする。さらに、各 e ∈ E

C(V ) と書くことにする。C(V ) の二つの線形作用素を
以下のように定義する。
( ∑(D̂f )(i) :=⃗e∈Et(e)=i(Âf )(i) :=する無向辺を [e] = [ē] ∈ E と書くことにする。

G の閉測地線とは有向辺の列 (e1 , . . . , ek ) であってt(ei ) = o(ei+1 ), ei ̸= ēi+1 (i = 1, . . . , k − 1), t(ek ) =o(e1 ), ek ̸= e¯1 を満たすものである。二つの閉測地線は一方が他方の巡回置換で与えられる時 同値という。閉測地線 c = (e1 , . . . , ek ) の m 回繰り返し、

∑

⃗
e∈E
t(e)=iue uē )f (i),
1 − ue uēuef (o(e)).
1 − ue uē

ただしここで f ∈ C(V ) である。このとき以下の公式が成立する。

det(I − UM) = det(I + D̂ − Â)mc = (e1 , . . . , ek , e1 , . . . , ek , . . . . . . , e1 , . . . , ek ) を c のmultiple という。さらに、閉測地線がほかの閉測地線の multiple になっていないとき、その同値類を素サイ(8)∏(1 − ue uē ). (9)[e]∈E

証明. 三つの作用素 O, T ∗ , ι を以下のように定義する:∑(Of )(e) := f (o(e)), (T ∗ g)(i) :=g(e),クルという。

⃗
e∈E,t(e)=i

さて、P を素サイクルの全体としよう。与えられた重み u = (ue )e∈E⃗ に対して、多変数ゼータ関数[5] は以下で定義されるζG (u) :=∏(1 − g(p))−1 .

すると明らかに M = OT ∗ − ι が成り立つ。よって、()
det(I − U M) = det I − T ∗ (I + Uι)−1 UO det(I + Uι)を得る。ただしここで n × m, m × n の行列 A, B に対p∈P

ただしここで、p = (e1 , . . . , ek ),⃗f ∈ C(V ) , g ∈ C(E).

(ιg)(e) := g(ē),g(p) := ue1 · · · uek として det(In − AB) = det(Im − BA) が成り立つことをし、また ue ∈ C は収束性のため十分に小さいとする。

用いた。

例 1. G がツリーのとき、素サイクルは存在しないので、て、I + Uι の (e, ē) ブロックは
[
]
1 ue

ζG (u) = 1 である。長さ N のサイクル状のグラフ CN では、素サイクルは (e1 , e2 , . . . , eN ) と (ēN , ēN −1 , . . . , ē1 )∏N∏N
しかないので ζCN (u) = (1− l=1 uel )−1 (1− l=1 uēl )−1ι は自然な基底でブロック対角行列になっている。よっuē1である。ただしこれら二つの場合を除くと、素サイクルである。したがって det(I + Uι) =は一般に無限個あることに注意しよう。

成立する。

多変数ゼータ関数は次のような行列式表示を持つ。これにより、多変数ゼータの定義域は全 C2M 上に延長さ⃗ と書こう。C(E)⃗れる。有向辺上の関数の全体を C(E)に作用する行列 M を1e ̸= ē′ かつ o(e) = t(e′ ) の場合,
Me,e′ :=
0
それ以外の場合f ∈ C(V ) に対して,()
T ∗ (I + Uι)−1 UOf (i))∑ ((I + Uι)−1 UOf (e)===ζG (u) = det(I − UM)−1 ,但し、 U は Ue,e′ := ue δe,e′ なる対角行列である。

∑⃗
e∈E,t(e)=iと定義する。
定理 1 ([5], Theorem 3).

∑⃗e∈E,t(e)=i(7)[e]∈E (1 − ue uē ) が最後に T ∗ (I + Uι)−1 UO = Â − D̂ を確認しよう。

⃗
e∈E,t(e)=i

(6)

∏

(
)
1
(UOf )(e) − ue (UOf )(ē)
1 − ue uē
()
1ue f (o(e)) − ue uē f (o(ē))
1 − ue uē= (Âf )(i) − (D̂f )(i)となっていることが確認できる。

⃗ に対して ue = u として多変数ゼータ
全ての e ∈ E

定理 3 はベーテ自由エネルギーのヘッセ行列の行列式関数を一変数化したしたものは伊原ゼータ関数 [6] と呼は本質的に det(I − UM) （すなわち多変数ゼータの逆

ばれている。ここでは ζG (u) と書くことにする。この場数）に等しいことを言っている。節５で示すように UM

合、定理 2 はは LBP の固定点においては、更新則の線形化に他ならζG (u)−1 = (1−u2 )M det(I+u2uD−A) (10)
1 − u2
1 − u2となる。この式 (10) は伊原の公式などと呼ばれている。
ただし D は次数行列、A は隣接行列と呼ばれ以下で定義されるないので、この公式は LBP に関する種々の性質を導く。

4

正定値性条件への応用
ベーテ自由エネルギーの凸性は LBP の解の一意性を保証することもあり興味を持たれてきた。Pakzad ら [7](Df )(i) := di f (i), (Af )(i) :=∑f (o(e)), f ∈ C(V ).

⃗e∈E,t(e)=iと Heskes [8] は凸性の十分条件を示し、ツリー又はただ一つのサイクルを持つグラフではベーテ自由エネルギーが凸であることを証明した。この節では主公式の一つの

3.2

主公式

応用として、そのような大域的な構造の代わりに局所的定理 3 (主公式). 以下の公式が L(G) の任意の点で成りな構造について議論する。
以下、正方行列 X に対して, Spec(X) ⊂ C はその固

立つ:

∏

∏

det(I − UM) = det(∇2 F )bij (xi , xj )ij∈E xi ,xj =±1∏ ∏×

bi (xi )1−di 22N +4M (11)i∈V xi =±1

ここで bij , bi は式 (5) によって与えられる。また、
χij − mi mj(12)
ui→j :=
1 − m2j有値全体を表す。また、X のスペクトル半径（固有値の絶対値の最大値）を ρ(X) と書く。
定理 4. M は式 (6) で与えられたものとする。さらに{mi , χij } ∈ L(G) に対して U は式 (12) で与えられるものとする。このとき、Spec(UM) ⊂ C \ R≥1 ならば∇2 F が点 {mi , χij } で正定値。
証明. 点 t ∈ [0, 1] に対して mi (t) := mi , χij := tχij +と定めている。

(1−t)mi mj と定義する。すると {mi (t), χij (t)} ∈ L(G),略証. 定義から容易にヘッセ行列の (E,E)-ブロックは対角行列であることが分かる。この対角成分を使って(V,E)-ブロックと (E,V)-ブロックの成分を消す。言い換
えると、正方行列 X を det X = 1 でかつ[]Y ( 0 )
T
2
X (∇ F )X =∂2F
0∂χij ∂χklとなるようにとる。長い計算を実行すると、

∑(χik −mi mk )2
1
+ k∈Ni (1−m2 )(1−m
2 −m2 +2m m χ −χ2 ) 1−m2ii k ikii
kik(Y )i,j =: i = j の場合,

χik −mi mk
−Ai,j: そのほかの場合
1−m2 −m2 +2m m χ −χ2iを得る。式 uj→i =

j

i

j

ij

ij

χij −mi mjを使えば IN + D̂ − Â =1−m2i

Y W となることが分かる。ただしここで Â, D̂ は式 (8)で定義されたものであり、W は Wi,j := δi,j (1 − m2i ) で定義される対角行列である。以上より∏∏
det(I − UM) = det(Y )(1 − m2i )(1 − ue uē )
i∈V

[e]∈E

= (11) の右辺が成立する。第一の等式には定理 2 が使われていることに注意しておく。

{mi (1), χij (1)} = {mi , χij } が成り立つ。この区間では、
U(t) と ∇2 F (t) が {mi (t), χij (t)} によって同様に定まる。明らかに U(t) = tU である。よって Spec(UM) ⊂C \ R≥1 より、det(I − tUM) ̸= 0 ∀ t ∈ [0, 1] が成立する。よって定理 3 より det(∇2 F (t)) ̸= 0 がこの区間上で成立する。一方 ∇2 F (0) が正定値行列であることは容易に確認できる。対称行列 ∇2 F (t) の固有値は実数で、な
おかつ t に関して連続なので ∇2 F (1) の固有値はすべて正の実数であることが分かる。

ui→j と uj→i の対称化を
βi→j = βj→i :=χij − mi mj{(1 − m2i )(1 − m2j )}1/2=

Covbij [xi , xj ]{Varbi [xi ]Varbj [xj ]}1/2(13)のようにして定める。つまり、ui→j uj→i = βi→j βj→i が成り立つ。βi→j = βj→i なので、しばしば βi→j を βij と略記する。最後の式より、|βij | < 1 が成立することが見て取れる。対角行列 Z, B を (Z)e,e′ := δe,e′ (1 − m2t(e) )1/2 ,(B)e,e′ := δe,e′ βe のように定義しよう。すると BM =Z U MZ −1 が成立する。よって Spec(UM) = Spec(BM)が成り立つ。

次の系はヘッセ行列が正定値であることのより明示的⃗ によって記述され、更新態は η = (ηe )e∈E⃗ ∈ C(E),な条件を pseudomarginals の相関係数の言葉で与える。

式 (2) はその上の変換 T とみられる。LBP の固定点は⃗ T (η ∞ ) = η ∞ } と書ける。
{η ∞ ∈ C(E);系 1. α を M のペロン・フロベニウス固有値とする。
⃗
Lα−1 (G) := {{mi , χij } ∈ L(G); |βe | < α−1 ∀e ∈ E}と定義する。このとき ∇2 F は Lα−1 (G) 上で正定値である。

固定点 η ∞ はこの点の十分近くから出発すると必ずこの点に収束するとき、局所安定という。局所安定性は固定点における T の線形化 T ′ によって決定される。論文 [11] でも議論されているとおり、η ∞ が局所安定であ証明. |βe | < α−1 であるので、ρ(BM) < ρ(α−1 M) = 1

る必要十分条件は Spec(T ′ (η ∞ )) ⊂ {λ ∈ C; |λ| < 1} でが成立する ([9] Theorem 8.1.18)。よって Spec(BM) ∩ある。

R≥1 = ϕ。
α−1 は原点からそれに一番近い伊原ゼータの極への距離に他ならない。例 1 より、 ζG (u) = 1（G はツリー）、

ζCN (u) = (1 − uN )−2 である。よって α−1 はそれぞれ∞、1 である。これらの場合 |βe | < 1 が常に成り立つことより、Lα−1 (G) = L(G) で F は L(G) 上で凸である。
これは [8] の結果の別証明になっている。一般に [9] の定理 8.1.22 を使うと mini∈V di − 1 ≤ α ≤ maxi∈V di − 1が言える。

LBP の振動現象を抑えるため、更新式の緩和 (damp)
Tϵ := (1 − ϵ)T + ϵI はしばしば有用である。ただしここで 0 ≤ ϵ < 1 は緩和の強さを表すパラメタで I は単位行列である。固定点がある強さの緩和のもとで局所安定である必要十分条件は Spec(T ′ (η ∞ )) ⊂ {λ ∈ C; Reλ < 1}である。

LBP 更新式の線形化 T ′ (η ∞ ) を Furtlehner らに従って良い座標系で表示しよう。
定理 5 ([12], Proposition 4.5). ui→j は LBP 固定点 η ∞非凸性に関しては主公式から次のことが分かる。

において式 (3), (5), (12) で与えられたものとする。線

系 2. t < 1 で {mi (t) := 0, χij (t) := t} ∈ L(G) とおく。
このとき、形化 T ′ (η ∞ ) は UM に相似である。つまりある正則行

lim det(∇2 F (t))(1 − t)M +N −1 = −2−M −N +1 (M − N )κ(G),定理 3 において det(I −T (η ∞ )) = det(I −UM) となが成立する。ただし κ(G) は全域木の個数である。特にるので、定理 3 は線形化行列とベーテ自由エネルギーの局グラフが連結で二つ以上の一次独立なサイクルをもつと所的な構造の直接的な関係を表していると言える。さらt→1き（つまり M − N ≥ 1）、F は L(G) 上で凸ではない。

列が存在して P UM = P T ′ (η ∞ )P −1 が成立する。
′に定理 4 より、LBP の固定点は Spec(T ′ (η ∞ )) ⊂ C\R≥1のときベーテ自由エネルギーの極小であることがわかる。

証明. 主張の式は橋本の定理 [10] から導かれる。橋本の定理は伊原ゼータ関数の u → 1 での極限を与える。
（詳

以上をまとめると以下のことが分かる。{λ ∈ C; Reλ <この節の結果をまとめると、F が L(G) が凸である必1} は C\R≥1 に含まれるので、（十分に緩和して）局所安
定な固定点はベーテ自由エネルギーの極小である。これはHeskes [4] によって示されている。さらに、Spec(T ′ (η ∞ ))要十分条件はグラフがツリーまたは１−サイクルのグラが C \ R≥1 に含まれるが、{λ ∈ C; Reλ < 1} に含まれフであることである。我々の知る限り、これは新しい結ないときその固定点はベーテ自由エネルギーの極小であ果である。

るのにどう緩和しても局所安定ではないことがいえる。

細略）後半の主張は明らか。

どのような条件のもとではベーテ自由エネルギーの極5安定性への応用
この節では LBP の局所安定性とベーテ自由エネルギーの LBP 固定点周りでの局所的な構造を議論する。Heskes[4] は（十分に緩和して）局所安定な固定点はベーテ自由エネルギーの極小であることを示した。その逆は必ずしも成り立たないことが知られている。このギャップがどれ程のものなのか以下で見ていこう。

小は（緩和された）LBP の局所安定な固定点になっているのかは興味ある問題であろう。現時点ではこの問題に完全には答えられないが、attractive なモデル（Jij ≥ 0）に関しては次の結果が得られる。この定理は要するに、相互作用と外場の強さを連続的に動かしていくとき、安定な固定点が不安定化する点はベーテ自由エネルギーの極小が鞍点化する点に等しいことを言っている。

まず最初に LBP の更新式を離散力学系としてみよ

定理 6. 連続的にパラメトライズされた attractive なモう。今考えているモデルはバイナリだったので、各メッデル {ψij (t), ψi (t)} を考える。
（例えば t は温度：ψij (t) =セージ µi→j (xj ) はスカラーパラメタ ηi→j でパラメト

exp(t−1 Jij xi xj ), ψi (t) = exp(t−1 hi xi )）与えられた t に対して、LBP を走らせ、安定な固定点に到達したとす

ライズできる。各時刻における LBP アルゴリズムの状

る。ここで、t を動かし、 t = t0 でこの固定点が不安定化したとすると、そのベーテ自由エネルギーの極小がt = t0 で鞍点に変化する。
略証. まず、attractive であることから ui→j ≥ 0 が常に成り立つ。あとはペロン・フロベニウスの定理と定理 3より明らか。
定理 6 は [11] の定理２の拡張になっている。（彼らは

図 1: 勾配 0 の点の指数を足すと 1

hi = 0 で mi = 0 の場合のみを考えている。）

補題 1. 任意の LBP 固定点において βij は式 (13) によっ

6

LBP 固定点の一意性問題への応用
LBP 固定点の一意性は、LBP が収束するときにはその固定点がベーテ自由エネルギーの最小であることを保て与えられたものとする。このとき |βij | ≤ tanh(|Jij |),sgn(βij ) = sgn(Jij ) が成立する。
証明. 式 (3) より、ある θi , θj が存在して bij (xi , xj ) ∝証するので、過去たくさん議論されてきた。その方法とexp(Jij xi xj + θi xi + θj xj ) が成立する。等号は θi = 0

しては minmax 問題に変形する [8]、縮小写像になる条かつ θj = 0 のとき成立する。

件を調べる [13, 14]、Gibbs 測度の一意性を考える [15]などが考えられてきた。ここではそれらとは異なり、微定理 7 と補題 3 より論文 [14] で示されている一意性

分トポロジー的な手法を使う。我々の手法においては定の条件が直ちに出てくる。（ただし [14] ではこの条件の理 3 と合わせて、以下の定理が重要である。

もとでもっと強く、ただ一つの解への収束性まで示して定理 7. 任意の q ∈ (∇F )−1 (0) に対して det ∇2 F (q) ̸= 0と仮定する。

∑()
sgn det ∇2 F (q) = 1,いる。）
系 3 ([14]). ρ(J M) < 1 ならば LBP の固定点はただ一つである。ただしここで J は Je,e′ = tanh(|Je |)δe,e′ はで定まる対角行列である。

q:∇F (q)=0

ここで x > 0 のとき sgn(x) = 1、x < 0 のとき sgn(x) =−1 である。この和の各項（+1 または −1）を q における F の指数という。
ベーテ自由エネルギーの勾配がゼロの点 (∇F )−1 (0)は LBP の固定点に他ならないことに注意しよう。この定理は LBP の固定点全てに関して指数を足し上げると１になることを言っている。
この定理の証明は省略する。この定理を証明するにあたり、ベーテ自由エネルギーの重要な性質は qn →証明. |βij | ≤ tanh(|Jij |) であるので ρ(BM) ≤ ρ(J M) <1 が成立する。よって det(I − BM) = det(I − U M) > 0
であり、LBP の固定点の指数は必ず１である。
系 3 の証明では、絶対値の評価のみを用いた。以下の系 4 では符号の情報も使う。この系を述べるために用語′を準備しよう。相互作用 {Jij , hi } と {Jij, h′i } は (si ) ∈′{±1}V が存在して Jij= Jij si sj h′i = hi si を満たすとき同値であるという。同値なモデルはゲージの変換

xi → xi si で得られるので、LBP 固定点の一意性は等しいことに注意しよう。

∂L(G) に対し ∥∇F (qn )∥ → ∞ が成り立つことである。
ただしここで ∂L(G) は L(G) ⊂ RN +M の境界集合である。

であるとする。(つまり M − N + 1 = 2。) このとき、一般に、関数 F の定義域が一次元の場合は勾配ゼロ

attractive なモデルに同値でない限り、LBP 固定点はたの点における指数とは二回微分の符号に他ならない。この場合に適切な境界条件のもとで定理 7 が成り立つことは図 1 から直感的に納得されるであろう。
もし何らかの方法で、前もって LBP の固定点の指数

系 4. 連結グラフ G の一次独立なサイクルの個数が２だ一つ存在する。
完全な証明を与える代わりに一つの例で示そう。
例 2. V := {1, 2, 3, 4},が必ず１であることを保証できれば LBP の固定点はた

E := {12, 13, 14, 23, 34} なるグラフを考える。相互作

だ一つであることが証明できる。LBP を実行する前か用は任意の {hi } と {−J12 , J13 , J14 , J23 , J34 } （Jij ≥ 0）

らわかる知識としては以下がある。

で与えられるものとする。（図 2 参照。）任意の 0 ≤β13 , β23 , β14 , β34 < 1 と −1 < β12 ≤ 0 に対して det(I −各ファクター α ∈ F 、変数頂点 i ∈ V に対して、

xα = (xi )i∈α 上の指数型分布族 Eα と xi 上の指数型
分布族 Ei が与えられているとする。これらの十分統計量を ϕα (xα ), ϕi (xi ) と書くことにし、次元を rα , ri と
図 2: 例 2 のグラフ

図 3: グラフ Ĝ

する。さらに ϕα が i ∈ α で ϕi を含むとする。すなわち

ϕα (xα ) = (ϕi1 (xi1 ), . . . , ϕik (xik ), ϕ̂α (xα ))ここで、α = {i1 , . . . , ik } とした。さらに「与えられた指数型分布族は周辺化でとじている」ということを仮定す∑る。すなわち、もし p(xα ) ∈ Eα ならば xα \i p(xα ) ∈ Ei
である。たとえば、有限状態で任意のファクターグラフ

図 4: 他の二種類

BM) > 0 を示せば十分。G の素サイクルの集合は Ĝ
(図 3) のそれと一対一に対応する。したがって、det(I −BM) = det(I − B̂ M̂) が成立する。ただしここで β̂e1 =β12 β23 , β̂e2 = β13 ,β̂e3 = β34 。−1 < β̂e1 ≤ 0 と 0 ≤β̂e2 , β̂e3 < 1 より、det(I − B̂ M̂) = (1− β̂e1 β̂e2 − β̂e1 β̂e3 −β̂e2 β̂e3 − 2β̂e1 β̂e2 β̂e3 )(1 − β̂e1 β̂e2 − β̂e1 β̂e3 − β̂e2 β̂e3 +
2β̂e1 β̂e2 β̂e3 ) > 0 が言える。ほかの場合は Ĝ または図 4のグラフに同様に帰着できる。

で書かれるモデルやガウス型モデルはこれらの状況に合う。LBP のアルゴリズムは自然にこのクラスのモデルに対して定義される。

LBP の固定点では期待値パラメタ η i = Ebi [ϕi ] とη α = Ebα [ϕα ] は局所的な整合性条件 (η α )i = η i を各
α ∋ i で満たす。ベーテ自由エネルギーはこのような条件を満たす期待値パラメターの関数になっている。また、
LBP の固定点はベーテ自由エネルギーの勾配ゼロの点に一致する。
定理 8 (定理３の拡張). 整合性条件を満たすような期待一方 attractive なモデルに関しては LBP の固定点は必ずしも唯一つではない。[11, 14]
過去の LBP 固定点の一意性に関する結果はすべて、|Jij | を何らかの意味で上から抑える条件のもとで得ら値パラメタ {η i , η α } に対して以下の公式が成立。
ζG (u)−1= det(∇2 F )∏det(Varbα [ϕα ])α∈F∏det(Varbi [ϕi ])1−di ,i∈Vれている。系 4 はそれとはまったく異なるタイプの条件−1
ただしここで uα
Covbα [ϕj , ϕi ] は rj ×
i→j := Varbj [ϕj ]のもとで一意性を示していることに注意しておく。

ri の行列である。

7

一般的なモデルに対しての拡張
ここまでのところ、バイナリ、ペアワイズのモデルのみを考えてきた。しかし、定理 3 はもっと一般のモデル

最後に付け加えると fractional belief propagation [16]型のベーテ自由エネルギーの変形に対しても定理 8 は拡張できることが分かっている。この場合はバックトラッ
クを許す Bartholdi 型のゼータ関数が現れる。[17]にまで拡張できる。この節では、この拡張について手短に述べる。詳細は今後の論文に譲りたい。
⃗ をファクターグラフとしよう。e ∈ E⃗はG = (V ∪F, E)
ファクター o(e) を始点とし、変数頂点 t(e) を終点とする
有向辺であるとする。G の閉測地線とは (e1 , e2 , . . . , ek )なる有向辺の列であって i ∈ Z/kZ で t(ei ) ∈ o(ei+1 ),t(ei ) ̸= t(ei+1 ) を満たすもののことである。G の素サイクルも普通のグラフのときと同様に定義される。与えられた正の整数の集合 {ri }i∈V , rj × ri 行列の集合{uαi→j }i,j∈α に対し、ゼータ関数の拡張は∏
1
ζG (u) :=o(ek )o(e1 )[C]∈P det(I − ut(ek−1 )→t(ek ) · · · ut(ek )→t(e1 ) )8

おわりに
最後に今後の課題について述べる。
まず定理 8 を Generalized Belief Propagation (GBP)や Expectation Propagation の場合に対して、拡張ができるのかは興味のある問題である。特に、GBP に拡張するのに必要になるゼータ関数の拡張は数学的にも興味深い対象である可能性がある。
一方 LBP の重要な応用の一つである LDPC 符号についての研究では、Koetter [18] らは pseudo-codewordsと多変数のゼータ関数との関係を示している。ガウス型のモデルでは, Johnson [19] らがゼータ的な分配関数のによって定義される。ただしここで C = (e1 , e2 , . . . , ek )展開公式を与えている。これらの仕事と我々の仕事は基とした。この場合も定理 1 と同様な行列式表示が存在

本的には大きく違っているが、その背後に何らかの関係する。

性があるかどうかは今後の興味深い研究課題である。

本論文ではベーテ自由エネルギーに関する議論に終始し、真の自由エネルギー（分配関数）についてはほとん
ど触れなかった。池田らの論文 [20, 21] では、情報幾何的な LBP の解釈を導入し、ベーテ近似と厳密解の間の展開を導出している。我々の方法の中においても、ベーテ近似と真の値を関係付けるような何らかの明確な定理を見出すことは重要な課題である。

Acknowledgements
本研究は学術振興会特別研究員奨励費 (20-993) と基盤研究Ｃ (19500249) の助成を受けたものである。

References[1] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, 1988.
[2] K. Murphy, Y. Weiss, and M.I. Jordan. Loopy belief
propagation for approximate inference: An empirical
study. UAI, 15:467–475, 1999.
[3] J.S. Yedidia, W.T. Freeman, and Y. Weiss. Generalized belief propagation. NIPS, 13:689–95, 2001.
[4] T. Heskes. Stable ﬁxed points of loopy belief propagation are minima of the Bethe free energy. NIPS, pages
343–350, 2002.
[5] H.M. Stark and A.A. Terras. Zeta functions of ﬁnite
graphs and coverings. Adv. in Math., 121(1):124–165,
1996.
[6] Y. Ihara. On discrete subgroups of the two by two projective linear group over p-adic ﬁelds. Journal of theMathematical Society of Japan, 18(3):219–235, 1966.
[7] P. Pakzad and V. Anantharam. Belief propagationand statistical physics. CISS, 2002.
[8] T. Heskes. On the uniqueness of loopy belief propagation ﬁxed points. Neural Comput., 16(11):2379–2413,
2004.
[9] R.A. Horn and C.R. Johnson. Matrix analysis. Cambridge University Press, 1990.
[10] K. Hashimoto. On zeta and L-functions of ﬁnite
graphs. Internat. J. Math, 1(4):381–396, 1990.
[11] JM Mooij and HJ Kappen. On the properties of
the Bethe approximation and loopy belief propagation on binary networks. J. Stat. Mech: Theor. Exp.,(11):P11012, 2005.
[12] C. Furtlehner, J.M. Lasgouttes, and A. De La Fortelle.
Belief propagation and Bethe approximation for traﬃc
prediction. INRIA RR-6144, 2007.
[13] A.T. Ihler, JW Fisher, and A.S. Willsky. Loopy belief propagation: Convergence and eﬀects of message
errors. JMLR, 6(1):905–936, 2006.
[14] J. M. Mooij and H. J. Kappen. Suﬃcient Conditions
for Convergence of the Sum-Product Algorithm. IEEE
Trans. on Inf. Th., 53(12):4422–4437, 2007.
[15] S. Tatikonda and M.I. Jordan. Loopy belief propagation and Gibbs measures. UAI, 18:493–500, 2002.

[16] W. Wiegerinck and T. Heskes. Fractional belief propagation. Advances in Neural Information Processing
Systems, pages 455–462, 2003.
[17] L. Bartholdi. Counting Paths in Graphs. Enseign.
Math., 45:83–131, 1999.
[18] R. Koetter, W.C.W. Li, PO Vontobel, and JL Walker.
Pseudo-codewords of cycle codes via zeta functions.
IEEE Information Theory Workshop, 2004.
[19] J.K. Johnson, V.Y. Chernyak, and M. Chertkov.
Orbit-Product Representation and Correction ofGaussian Belief Propagation. ICML, 2009.
[20] S. Ikeda, T. Tanaka, and S. Amari. Stochastic reasoning, free energy, and information geometry. NeuralComputation, 16(9):1779–1810, 2004.
[21] S. Ikeda, T. Tanaka, and S. Amari.
Information geometry of turbo and low-density parity-check
codes. IEEE Transactions on Information Theory,50(6):1097–1114, 2004.