情報通信システム(特)論II
Information and Communication Systems II

第７回講義資料
Lecture notes 7

確率伝播法
Belief Propagation

豊橋技術科学大学
Toyohashi University of Technology

電気・電子情報工学系
Department of Electrical and Electronic Information Engineering

准教授 竹内啓悟
Associate Professor

Keigo Takeuchi

1無線通信路(Wireless channels)
物理層における無線通信システムのほとんどは、物理法則に基づいて以下のシステムでモデル化できる。
Almost all wireless communication systems in the physical layer can be modeled with thefollowing system based on physical laws.

無線通信路の離散時間統計モデル(Discrete-time statistical model of wireless channels)
𝒚𝒚 = 𝑯𝑯𝑯𝑯 + 𝒘𝒘,𝒘𝒘 ∼ 𝒞𝒞𝒞𝒞(𝟎𝟎, 𝑁𝑁0 𝑰𝑰𝑀𝑀 )𝒙𝒙 ∈ ℂ𝑁𝑁 ：送信ベクトル(Transmitted vector)
𝑯𝑯 ∈ ℂ𝑀𝑀×𝑁𝑁 ：通信路行列(Channel matrix)

𝑦𝑦 ∈ ℂ𝑀𝑀 ：受信ベクトル(Received vector)

𝒘𝒘 ∼ 𝒞𝒞𝒞𝒞(𝟎𝟎, 𝑁𝑁0 𝑰𝑰𝑀𝑀 )：加法的白色ガウス雑音(AWGN)ベクトル
Additive white Gaussian noise (AWGN) vector

統計的仮定(Statistical assumptions)• 送信ベクトル𝒙𝒙は平均𝟎𝟎である。(The transmitted vector 𝒙𝒙 is zero mean.)• 確率変数𝑯𝑯、𝒙𝒙、𝒘𝒘は独立である。(𝑯𝑯, 𝒙𝒙, and 𝒘𝒘 are independent random variables.)2

Achievable sum rate per output dimension

達成可能な総和レートの比較(Comparisons for achievable sum rates)

Load 𝑁𝑁/𝑀𝑀

i.i.d. Rayleigh fading, 𝑁𝑁 → ∞, and 𝑃𝑃/𝑁𝑁0 = 10 dB.

3

事後平均推定量(Posterior mean estimator)
各データシンボル𝑥𝑥𝑛𝑛 は有限個の信号点集合ℳ ⊂ ℂ上で値を取るとする。
Suppose that each data symbol 𝑥𝑥𝑛𝑛 takes values on a finite constellation ℳ ⊂ ℂ.

事後平均推定量(Posterior mean estimator)
𝑝𝑝 𝒚𝒚 𝑯𝑯, 𝒙𝒙 𝑝𝑝(𝒙𝒙) ∑𝒙𝒙∈ℳ 𝑁𝑁 𝒙𝒙𝑝𝑝 𝒚𝒚 𝑯𝑯, 𝒙𝒙 𝑝𝑝(𝒙𝒙)=.
𝔼𝔼 𝒙𝒙 𝑯𝑯, 𝒚𝒚 = � 𝒙𝒙
∑𝒙𝒙∈ℳ 𝑁𝑁 𝑝𝑝 𝒚𝒚 𝑯𝑯, 𝒙𝒙 𝑝𝑝(𝒙𝒙)𝑝𝑝(𝒚𝒚|𝑯𝑯)
𝑁𝑁𝒙𝒙∈ℳ

計算量(Complexity)
直接計算すると、少なくとも𝑂𝑂( ℳ 𝑁𝑁 )回の足し算が必要である。
Direct computation requires at least 𝑂𝑂( ℳ 𝑁𝑁 ) addtions.

計算量の少ない近似計算法はあるか？
Is there an approximate and low-complexity method?
4

ファクターグラフ表現(Factor graph representation)
データベクトル𝒙𝒙の要素は独立と仮定する。
Assume the independence of the elements of the data vector 𝒙𝒙.

𝑦𝑦1ℎ11=𝑦𝑦20ℎ12ℎ22𝑥𝑥1
𝑤𝑤1ℎ13 0 𝑥𝑥2+ 𝑤𝑤 .
0 ℎ24 𝑥𝑥32𝑥𝑥4𝑝𝑝(𝑥𝑥2 )𝑝𝑝(𝑥𝑥3 )𝑦𝑦1

𝑦𝑦2

ファクターグラフ(Factor graph)𝑝𝑝(𝑥𝑥1 )𝑥𝑥1

𝑝𝑝(𝑦𝑦1 |𝑯𝑯, 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 )𝑥𝑥2

𝑥𝑥3𝑝𝑝(𝑥𝑥4 )𝑥𝑥4𝑝𝑝(𝑦𝑦2 |𝑯𝑯, 𝑥𝑥2 , 𝑥𝑥4 )5ファクターグラフの書き方(How to draw a factor graph)1. 推定すべき未知の確率変数を変数ノードと呼び、丸で書く。事前分
布や既知の確率変数によって決まる制約を表すノードをファクターノードと呼び、四角で書く。
Unknown random variables to be estimated are called variable nodes, denoted by circles.
Nodes representing constraints due to prior distributions or known random variables arereferred to as factor nodes, denoted by squares.

2. 通信路行列の要素ℎ𝑚𝑚,𝑛𝑛 が0でないとき、ファクターノード𝑦𝑦𝑚𝑚 と変数ノード𝑥𝑥𝑛𝑛 を接続する。

When an element ℎ𝑚𝑚,𝑛𝑛 of the channel matrix is non-zero, the factor node 𝑦𝑦𝑚𝑚 is connectedto the variable node 𝑥𝑥𝑛𝑛 .

注意(Remark)
事前分布を表すファクターノードは省略される場合がある。
Factor nodes representing prior distributions may be omitted.

6木構造のファクターグラフ(Factor graph with tree structure)𝑥𝑥1𝑥𝑥2𝑥𝑥3𝑦𝑦1𝑦𝑦2𝑥𝑥1𝑥𝑥4

サイクルがない。
There are no cycles.

確率構造(Probabilistic structure)

𝑥𝑥2

𝑦𝑦1

𝑦𝑦2𝑥𝑥3𝑥𝑥4

𝑝𝑝 𝒚𝒚 𝑯𝑯, 𝒙𝒙 = 𝑝𝑝 𝑦𝑦1 𝑯𝑯, 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 𝑝𝑝 𝑦𝑦2 𝑯𝑯, 𝑥𝑥2 , 𝑥𝑥4 .

𝑦𝑦2 が𝑝𝑝(𝑦𝑦1 |𝑯𝑯, 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 )で出てきた𝑥𝑥1 や𝑥𝑥3 に依存しないことが重要である。
It is important that 𝑦𝑦2 is independent of 𝑥𝑥1 and 𝑥𝑥3 , which appeared in 𝑝𝑝(𝑦𝑦1 |𝑯𝑯, 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ).

7木構造のファクターグラフ(Factor graph with tree structure)
Depth 0Depth 1
Depth 2Depth 3Depth 4性質(Properties)• ファクターノードは子ノードを持つ。(Any factor node has child nodes.)• 根ノードを除いて、各ノードは親ノードを一つ持つ。
With the exception of the root node, any node has one parent node8

局所構造(Local structure)
ファクターグラフは深さ2𝐷𝐷の木であるとしよう。
Suppose that the factor graph is a tree with depth 2𝐷𝐷.

𝒳𝒳𝑖𝑖 = {𝑥𝑥𝑖𝑖,1 , … , 𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖 }：深さ2𝑖𝑖にある変数ノード(Variable nodes in depth 2𝑖𝑖.)
𝒴𝒴𝑖𝑖 = {𝑦𝑦𝑖𝑖,1 , … , 𝑦𝑦𝑖𝑖,𝑚𝑚𝑖𝑖 }：深さ2𝑖𝑖 + 1にあるファクターノード(Factor nodes in depth 2𝑖𝑖 + 1.)
𝑛𝑛𝑖𝑖,𝑚𝑚 ：𝑦𝑦𝑖𝑖,𝑚𝑚 の親を指定する番号(Index indicating the parent of 𝑦𝑦𝑖𝑖,𝑚𝑚 )𝑚𝑚𝑖𝑖,𝑛𝑛 ：𝑥𝑥𝑖𝑖,𝑛𝑛 の親を指定する番号(Index indicating the parent of 𝑥𝑥𝑖𝑖,𝑛𝑛 )𝒞𝒞f (𝑖𝑖, 𝑚𝑚)：𝑦𝑦𝑖𝑖,𝑚𝑚 の子供を指定する番号集合(Set of indices indicating the children of 𝑦𝑦𝑖𝑖,𝑚𝑚 )𝒞𝒞v (𝑖𝑖, 𝑛𝑛)：𝑥𝑥𝑖𝑖,𝑛𝑛 の子供を指定する番号集合(Set of indices indicating the children of 𝑥𝑥𝑖𝑖,𝑛𝑛 )𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚
𝑦𝑦𝑖𝑖−1,𝑚𝑚𝑖𝑖,𝑛𝑛
� 𝑓𝑓𝑖𝑖,𝑚𝑚 = 1𝑦𝑦𝑖𝑖,𝑚𝑚 𝑓𝑓𝑖𝑖,𝑚𝑚 (𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 |𝒳𝒳𝑖𝑖+1,𝑚𝑚 )𝑚𝑚∈∅𝑥𝑥𝑖𝑖,𝑛𝑛𝑥𝑥𝑖𝑖+1,𝑛𝑛|𝒞𝒞 𝑖𝑖,𝑚𝑚 |𝑥𝑥𝑖𝑖+1,𝑛𝑛1
f𝑦𝑦𝑖𝑖,𝑚𝑚1𝑦𝑦𝑖𝑖,𝑚𝑚|𝒞𝒞 𝑖𝑖,𝑛𝑛 |v
𝒳𝒳𝑖𝑖+1,𝑚𝑚 = {𝑥𝑥𝑖𝑖+1,𝑛𝑛 : 𝑛𝑛 ∈ 𝒞𝒞f 𝑖𝑖, 𝑚𝑚 }𝐷𝐷−1 𝑚𝑚𝑖𝑖

𝐷𝐷−1 𝑛𝑛𝑖𝑖𝑖𝑖=0 𝑚𝑚=1𝑖𝑖=0 𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑖𝑖,𝑛𝑛

𝑝𝑝 𝒚𝒚 𝑯𝑯, 𝒙𝒙 ≝ � � 𝑓𝑓𝑖𝑖,𝑚𝑚 (𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 |𝒳𝒳𝑖𝑖+1,𝑚𝑚 ) = � ��𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛 𝒳𝒳𝑖𝑖+1,𝑚𝑚 .

9

周辺事後分布の計算(Computation of marginal posterior distributions)
一般性を失うことなく、根ノード𝑥𝑥0,1 の周辺事後分布を計算する。

Without loss of generality, we compute the marginal posterior distribution of the root node 𝑥𝑥0,1 .
𝑁𝑁

𝑝𝑝 𝑥𝑥0,1 𝑯𝑯, 𝒚𝒚 = � 𝑝𝑝(𝒙𝒙|𝑯𝑯, 𝒚𝒚) ∝ � 𝑝𝑝 𝒚𝒚 𝑯𝑯, 𝒙𝒙 � 𝑝𝑝 𝑥𝑥𝑛𝑛 .
∖𝑥𝑥0,1∖𝑥𝑥0,1𝑛𝑛=1

総和は𝑥𝑥0,1 を固定した全組み合わせ{𝒙𝒙 ∈ ℳ 𝑁𝑁 : 𝑥𝑥0,1 fixed}に関して取られる。
The summation is over all possible combinations {𝒙𝒙 ∈ ℳ 𝑁𝑁 : 𝑥𝑥0,1 fixed} for fixed 𝑥𝑥0,1 .

木であるための条件(Tree condition)𝑖𝑖 ≠ 0に対して{𝒳𝒳𝑖𝑖,𝑚𝑚 : for all 𝑚𝑚}は𝒳𝒳𝑖𝑖 の分割である。
{𝒳𝒳𝑖𝑖,𝑚𝑚 : for all 𝑚𝑚} is a disjoint partition of 𝒳𝒳𝑖𝑖 for 𝑖𝑖 ≠ 0.

∪𝑚𝑚 𝒳𝒳𝑖𝑖,𝑚𝑚 = 𝒳𝒳𝑖𝑖 ,𝒳𝒳𝑖𝑖,𝑚𝑚 ∩ 𝒳𝒳𝑖𝑖,𝑚𝑚′ = ∅ for 𝑚𝑚 ≠ 𝑚𝑚′ .

𝑝𝑝(𝒚𝒚|𝑯𝑯, 𝒙𝒙)の因子分解を使って、(Using the factor decomposition of 𝑝𝑝(𝒚𝒚|𝑯𝑯, 𝒙𝒙) yields)
𝐷𝐷−1 𝑛𝑛𝑖𝑖

𝑝𝑝 𝑥𝑥0,1 𝑯𝑯, 𝒚𝒚 ∝ 𝑝𝑝(𝑥𝑥0,1 ) � � �

� {𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛 𝒳𝒳𝑖𝑖+1,𝑚𝑚 𝑝𝑝(𝒳𝒳𝑖𝑖+1,𝑚𝑚 )}∖𝑥𝑥0,1 𝑖𝑖=0 𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑖𝑖,𝑛𝑛10

確率伝播法(Belief propagation (BP))
𝐷𝐷−𝑖𝑖
ファクターノード𝑦𝑦𝑖𝑖,𝑚𝑚 から変数ノード𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 へのメッセージ𝑞𝑞𝑚𝑚→𝑛𝑛(𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 )
𝑖𝑖,𝑚𝑚
𝐷𝐷−𝑖𝑖
Message 𝑞𝑞𝑚𝑚→𝑛𝑛(𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 ) passed from the factor node 𝑦𝑦𝑖𝑖,𝑚𝑚 to the variable node 𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚𝑖𝑖,𝑚𝑚

𝐷𝐷−𝑖𝑖
𝑞𝑞𝑚𝑚→𝑛𝑛𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 = � 𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 𝒳𝒳𝑖𝑖+1,𝑚𝑚𝑖𝑖,𝑚𝑚𝒳𝒳𝑖𝑖+1,𝑚𝑚

�𝑛𝑛∈𝒞𝒞f (𝑖𝑖,𝑚𝑚)

𝐷𝐷−(𝑖𝑖+1)

𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥𝑖𝑖+1,𝑛𝑛 ) .

𝐷𝐷−𝑖𝑖
変数ノード𝑥𝑥𝑖𝑖,𝑛𝑛 からファクターノード𝑦𝑦𝑖𝑖−1,𝑚𝑚𝑖𝑖,𝑛𝑛 へのメッセージ𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥𝑖𝑖,𝑛𝑛 )𝑖𝑖,𝑛𝑛
𝐷𝐷−𝑖𝑖
Message 𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥𝑖𝑖,𝑛𝑛 ) passed from the variable node 𝑥𝑥𝑖𝑖,𝑛𝑛 to the variable node 𝑦𝑦𝑖𝑖−1,𝑚𝑚𝑖𝑖,𝑛𝑛𝑖𝑖,𝑛𝑛

𝐷𝐷−𝑖𝑖
𝑞𝑞𝑚𝑚→𝑛𝑛𝑖𝑖,𝑚𝑚𝑥𝑥𝑖𝑖+1,𝑛𝑛1

𝐷𝐷−𝑖𝑖
𝑚𝑚𝑛𝑛→𝑚𝑚𝑥𝑥𝑖𝑖,𝑛𝑛 ∝ 𝑝𝑝 𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑛𝑛𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚

�𝑚𝑚∈𝒞𝒞v (𝑖𝑖,𝑛𝑛)𝑦𝑦𝑖𝑖,𝑚𝑚 𝑓𝑓𝑖𝑖,𝑚𝑚 (𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 |𝒳𝒳𝑖𝑖+1,𝑚𝑚 )𝑥𝑥𝑖𝑖+1,𝑛𝑛|𝒞𝒞 𝑖𝑖,𝑚𝑚 |f𝐷𝐷−𝑖𝑖𝑞𝑞𝑚𝑚→𝑛𝑛(𝑥𝑥𝑖𝑖,𝑛𝑛 ) .

𝑦𝑦𝑖𝑖−1,𝑚𝑚𝑖𝑖,𝑛𝑛𝑦𝑦𝑖𝑖,𝑚𝑚1𝑥𝑥𝑖𝑖,𝑛𝑛

メッセージは葉から根に向かって計算される。

𝐷𝐷−𝑖𝑖
𝑚𝑚𝑛𝑛→𝑚𝑚𝑖𝑖,𝑛𝑛𝑦𝑦𝑖𝑖,𝑚𝑚|𝒞𝒞 𝑖𝑖,𝑛𝑛 |v

The messages are computed from the leafs toward the root.
11

周辺事後分布の計算(Computation of marginal posterior distributions)定理7.1(Theorem 7.1)
𝑝𝑝 𝑥𝑥0,1 𝑯𝑯, 𝒚𝒚 ∝ 𝑝𝑝 𝑥𝑥0,1

𝐷𝐷𝑞𝑞𝑚𝑚→1𝑥𝑥0,1 .

�𝑚𝑚∈𝒞𝒞v 0,1

証明(Proof) 深さ𝐷𝐷に関する帰納法によって証明する。
𝐷𝐷 = 1の場合
Case of 𝐷𝐷 = 1∵The proof is by induction with respect to the depth 𝐷𝐷.

𝑝𝑝 𝑥𝑥𝑛𝑛 𝑯𝑯, 𝒚𝒚 ∝ 𝑝𝑝(𝑥𝑥0,1 ) �= 𝑝𝑝 𝑥𝑥0,1= 𝑝𝑝 𝑥𝑥0,1

��∖𝑥𝑥0,1 𝑚𝑚∈𝒞𝒞v 0,1

� 𝑓𝑓0,𝑚𝑚 𝑥𝑥0,1 𝒳𝒳1,𝑚𝑚

𝑚𝑚∈𝒞𝒞v 0,1 𝒳𝒳1,𝑚𝑚

�𝑚𝑚∈𝒞𝒞𝑣𝑣 0,1

1𝑞𝑞𝑚𝑚→1𝑥𝑥0,1 .

1𝑞𝑞𝑚𝑚→1𝑥𝑥0,1 = � 𝑓𝑓0,𝑚𝑚 𝑥𝑥0,1 𝒳𝒳1,𝑚𝑚𝒳𝒳1,𝑚𝑚{𝑓𝑓0,𝑚𝑚 𝑥𝑥0,1 𝒳𝒳1,𝑚𝑚 𝑝𝑝(𝒳𝒳1,𝑚𝑚 )}0𝑝𝑝 𝑥𝑥1,𝑛𝑛 ∝ 𝑚𝑚𝑛𝑛→𝑚𝑚𝑥𝑥1,𝑛𝑛 .

�𝑛𝑛∈𝒞𝒞f (0,𝑚𝑚)

�𝑛𝑛∈𝒞𝒞f (0,𝑚𝑚)

𝑝𝑝(𝑥𝑥1,𝑛𝑛 )0𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥1,𝑛𝑛 ) ,12

定理7.1の証明(Proof of Theorem 7.1)
𝐷𝐷 = 𝑑𝑑の場合に定理は正しいと仮定して、𝐷𝐷 = 𝑑𝑑 + 1の場合を示す。
We prove the case 𝐷𝐷 = 𝑑𝑑 + 1 under the assumption of the correctness for 𝐷𝐷 = 𝑑𝑑.

𝐷𝐷 = 1の場合と同様に、𝒳𝒳𝑑𝑑+1 に関する総和を計算する。
We repeat the proof for 𝐷𝐷 = 1 to compute the summation over 𝒳𝒳𝑑𝑑+1𝑑𝑑 𝑛𝑛𝑖𝑖

𝑝𝑝 𝑥𝑥0,1 𝑯𝑯, 𝒚𝒚 ∝ 𝑝𝑝(𝑥𝑥0,1 ) � � �

� {𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛 𝒳𝒳𝑖𝑖+1,𝑚𝑚 𝑝𝑝(𝒳𝒳𝑖𝑖+1,𝑚𝑚 )}∝ 𝑝𝑝(𝑥𝑥0,1 ) � � �

� {𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛 𝒳𝒳𝑖𝑖+1,𝑚𝑚 𝑝𝑝(𝒳𝒳𝑖𝑖+1,𝑚𝑚 )}∖𝑥𝑥0,1 𝑖𝑖=0 𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑖𝑖,𝑛𝑛
𝑑𝑑−1 𝑛𝑛𝑖𝑖∖𝑥𝑥0,1 𝑖𝑖=0 𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑖𝑖,𝑛𝑛𝑛𝑛𝑑𝑑⋅�∵�

𝑛𝑛′ =1 𝑚𝑚′ ∈𝒞𝒞v 𝑑𝑑,𝑛𝑛′

1𝑞𝑞𝑚𝑚′ →𝑛𝑛′ 𝑥𝑥𝑑𝑑,𝑛𝑛′ .

1𝑞𝑞𝑚𝑚→𝑛𝑛
𝑥𝑥𝑑𝑑,𝑛𝑛 = � 𝑓𝑓𝑑𝑑,𝑚𝑚 𝑥𝑥𝑑𝑑,𝑛𝑛 𝒳𝒳𝑑𝑑+1,𝑚𝑚𝒳𝒳𝑑𝑑+1,𝑚𝑚

𝑚𝑚𝑛𝑛0 ′ →𝑚𝑚 𝑥𝑥𝑑𝑑+1,𝑛𝑛′ ∝ 𝑝𝑝 𝑥𝑥𝑑𝑑+1,𝑛𝑛′ .

�𝑛𝑛′ ∈𝒞𝒞f (𝑑𝑑,𝑚𝑚)

𝑚𝑚𝑛𝑛0 ′ →𝑚𝑚 (𝑥𝑥𝑑𝑑+1,𝑛𝑛′ ) ,13

定理7.1の証明(Proof of Theorem 7.1)
𝐷𝐷 = 𝑑𝑑の場合に帰着する。(We reduce the formula to the case of 𝐷𝐷 = 𝑑𝑑.)

{𝒳𝒳𝑖𝑖,𝑚𝑚 }は𝒳𝒳𝑖𝑖 の分割なので、(Since {𝒳𝒳𝑖𝑖,𝑚𝑚 } is a disjoint partition of 𝒳𝒳𝑖𝑖 , we have)𝑛𝑛𝑑𝑑−1��𝑛𝑛𝑑𝑑−1𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑑𝑑−1,𝑛𝑛

𝑝𝑝 𝒳𝒳𝑑𝑑,𝑚𝑚 = ��𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑑𝑑−1,𝑛𝑛 𝑛𝑛∈𝒞𝒞𝑓𝑓 (𝑑𝑑−1,𝑚𝑚)

それゆえ、(Thus,)

𝑑𝑑−2 𝑛𝑛𝑖𝑖

𝑝𝑝 𝑥𝑥0,1 𝑯𝑯, 𝒚𝒚 ∝ 𝑝𝑝(𝑥𝑥0,1 ) � � �∵�𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑑𝑑−1,𝑛𝑛

𝑚𝑚1𝑛𝑛′ →𝑚𝑚

𝑑𝑑,𝑛𝑛𝑝𝑝(𝑥𝑥𝑑𝑑,𝑛𝑛 ) = � 𝑝𝑝(𝑥𝑥𝑑𝑑,𝑛𝑛 ) .
𝑛𝑛=1

� {𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛 𝒳𝒳𝑖𝑖+1,𝑚𝑚 𝑝𝑝(𝒳𝒳𝑖𝑖+1,𝑚𝑚 )}∖𝑥𝑥0,1 𝑖𝑖=0 𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑖𝑖,𝑛𝑛

𝑛𝑛𝑑𝑑−1

⋅�

�

𝑛𝑛𝑑𝑑

𝑛𝑛𝑑𝑑

𝑓𝑓𝑑𝑑−1,𝑚𝑚 𝑥𝑥𝑑𝑑−1,𝑛𝑛 𝒳𝒳𝑑𝑑,𝑚𝑚 ⋅ � 𝑚𝑚1𝑛𝑛′ →𝑚𝑚

𝑥𝑥𝑑𝑑,𝑛𝑛′ ∝ 𝑝𝑝 𝑥𝑥𝑑𝑑,𝑛𝑛′′�𝑚𝑚′∈𝒞𝒞v (𝑑𝑑,𝑛𝑛′ )𝑛𝑛′ =1𝑑𝑑,𝑛𝑛′

1𝑞𝑞𝑚𝑚𝑚→𝑛𝑛′ (𝑥𝑥𝑑𝑑,𝑛𝑛′ ) .

𝑥𝑥𝑑𝑑,𝑛𝑛′ .

14

定理7.1の証明(Proof of Theorem 7.1)
𝑝𝑝� 𝑥𝑥𝑑𝑑,𝑛𝑛 = 𝑚𝑚1𝑛𝑛→𝑚𝑚𝑑𝑑,𝑛𝑛 𝑥𝑥𝑑𝑑,𝑛𝑛 を深さ2𝑑𝑑にある変数ノードの事前分布とみなすと、Regarding 𝑝𝑝� 𝑥𝑥𝑑𝑑,𝑛𝑛 = 𝑚𝑚1𝑛𝑛→𝑚𝑚𝑑𝑑,𝑛𝑛 𝑥𝑥𝑑𝑑,𝑛𝑛 as the prior distributions of the variable nodes in depth 2𝑑𝑑 yileds

𝑑𝑑−1 𝑛𝑛𝑖𝑖

𝑝𝑝 𝑥𝑥0,1 𝑯𝑯, 𝒚𝒚 ∝ 𝑝𝑝 𝑥𝑥0,1 � � �

� {𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛 𝒳𝒳𝑖𝑖+1,𝑚𝑚 𝑝𝑝(𝒳𝒳𝑖𝑖+1,𝑚𝑚 )} ,∖𝑥𝑥0,1 𝑖𝑖=0 𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑖𝑖,𝑛𝑛

ただし、𝑝𝑝 𝒳𝒳𝑑𝑑,𝑚𝑚 = ∏𝑛𝑛∈𝒞𝒞f (𝑑𝑑,𝑚𝑚) 𝑝𝑝(𝑥𝑥� 𝑑𝑑,𝑛𝑛 )と再定義する。
where 𝑝𝑝 𝒳𝒳𝑑𝑑,𝑚𝑚 = ∏𝑛𝑛∈𝒞𝒞f(𝑑𝑑,𝑚𝑚) 𝑝𝑝(𝑥𝑥� 𝑑𝑑,𝑛𝑛 ) is re-defined.

∵𝑛𝑛𝑑𝑑

� 𝑚𝑚1𝑛𝑛′ →𝑚𝑚𝑛𝑛′ =1𝑑𝑑,𝑛𝑛′𝑛𝑛𝑑𝑑−1𝑥𝑥𝑑𝑑,𝑛𝑛′ = ��𝑛𝑛=1 𝑚𝑚∈𝒞𝒞v 𝑑𝑑−1,𝑛𝑛

それゆえ、定理は帰納法の仮定から従う。
Thus, the theorem follows from the induction hypothesis.

𝑝𝑝(𝒳𝒳� 𝑑𝑑,𝑚𝑚 ) .
∎15確率伝播法の計算量(Complexity of BP)
最も支配的な計算はファクターノードから変数ノードに送るメッセージの更新である。
The most dominant computation is the update of messages passed from each factor node to variable nodes.

𝐷𝐷−𝑖𝑖
𝑞𝑞𝑚𝑚→𝑛𝑛𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 = � 𝑓𝑓𝑖𝑖,𝑚𝑚 𝑥𝑥𝑖𝑖,𝑛𝑛𝑖𝑖,𝑚𝑚 𝒳𝒳𝑖𝑖+1,𝑚𝑚𝑖𝑖,𝑚𝑚𝒳𝒳𝑖𝑖+1,𝑚𝑚

�𝑛𝑛∈𝒞𝒞f (𝑖𝑖,𝑚𝑚)

𝐷𝐷−(𝑖𝑖+1)

𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥𝑖𝑖+1,𝑛𝑛 ) .

周辺化に𝑂𝑂 𝒞𝒞f 𝑖𝑖, 𝑚𝑚 |ℳ||𝒞𝒞f(𝑖𝑖,𝑚𝑚| の計算時間がかかる。
The marginalization is computed in 𝑂𝑂 𝒞𝒞f 𝑖𝑖, 𝑚𝑚 |ℳ||𝒞𝒞f(𝑖𝑖,𝑚𝑚| time.

疎なファクターグラフ(Sparse factor graph)
ファクターノードの次数 𝒞𝒞f 𝑖𝑖, 𝑚𝑚 + 1が定数のとき、確率伝播法の計算量は𝑀𝑀や𝑁𝑁に関して線形になる。変数ノードも同じ性質を満たすグラフを疎グラフと呼ぶ。
The complexity of BP is linear in 𝑀𝑀 and 𝑁𝑁 when the degrees 𝒞𝒞f 𝑖𝑖, 𝑚𝑚 + 1 of factor nodes are constant. Agraph is called sparse if the variable nodes satisfy the same property.

16Loopy BP
木でないファクターグラフにも確率伝播法を適用することはできる。
It is possible to apply BP to factor graphs with no tree structure.

𝑡𝑡
ファクターノード𝑦𝑦𝑚𝑚 から変数ノード𝑥𝑥𝑛𝑛 へのメッセージ𝑞𝑞𝑚𝑚→𝑛𝑛(𝑥𝑥𝑛𝑛 )𝑡𝑡
Message 𝑞𝑞𝑚𝑚→𝑛𝑛(𝑥𝑥𝑛𝑛 ) passed from the factor node 𝑦𝑦𝑚𝑚 to the variable node 𝑥𝑥𝑛𝑛

𝑑𝑑f −1𝑡𝑡
𝑞𝑞𝑚𝑚→𝑛𝑛
𝑥𝑥𝑛𝑛 = � 𝑓𝑓𝑚𝑚 𝑥𝑥𝑛𝑛 𝑥𝑥𝑛𝑛1 , … , 𝑥𝑥𝑛𝑛𝑑𝑑 −1 � 𝑚𝑚𝑛𝑛𝑡𝑡−1(𝑥𝑥𝑛𝑛𝑖𝑖 ) .
𝑖𝑖 →𝑚𝑚f∖𝑥𝑥𝑛𝑛𝑖𝑖=1

𝑡𝑡
変数ノード𝑥𝑥𝑛𝑛 からファクターノード𝑦𝑦𝑚𝑚 へのメッセージ𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥𝑛𝑛 )𝑡𝑡
Message 𝑚𝑚𝑛𝑛→𝑚𝑚(𝑥𝑥𝑛𝑛 ) passed from the variable node 𝑥𝑥𝑛𝑛 to the variable node 𝑦𝑦𝑚𝑚

𝑑𝑑v −1𝑡𝑡
𝑞𝑞𝑚𝑚→𝑛𝑛𝑥𝑥𝑛𝑛1

𝑡𝑡
𝑡𝑡
𝑚𝑚𝑛𝑛→𝑚𝑚𝑥𝑥𝑛𝑛 ∝ 𝑝𝑝 𝑥𝑥𝑛𝑛 � 𝑞𝑞𝑚𝑚
(𝑥𝑥𝑛𝑛 ) .
𝑖𝑖 →𝑛𝑛

𝑥𝑥𝑛𝑛

𝑦𝑦𝑚𝑚

𝑖𝑖=1

𝑓𝑓𝑚𝑚 (𝑥𝑥𝑛𝑛 |𝑥𝑥𝑛𝑛1 , … , 𝑥𝑥𝑛𝑛𝑑𝑑 −1 )𝑥𝑥𝑛𝑛𝑑𝑑 −1
ff

𝑦𝑦𝑚𝑚1

𝑦𝑦𝑚𝑚

𝑥𝑥𝑖𝑖,𝑛𝑛𝑡𝑡
𝑚𝑚𝑛𝑛→𝑚𝑚𝑦𝑦𝑚𝑚𝑑𝑑v −117

Loopy BP

疎なファクターグラフ(Sparse factor graphs)
メッセージの更新を有限回で止める限り、疎グラフは漸近的に木に見える。
A sparse graph looks like a tree asymptotically as long as message updates stop in finite iterations.

• 低密度パリティ検査符号(Low-density parity-check (LDPC) codes)• ビットインターリーブ符号化変調(Bit-interleaved coded modulation)

密で一様なファクターグラフ(Dense and uniform factor graphs)
BPはサイクルを通じて戻ってくるメッセージを除去する機能を備えている。
BP includes a mechanism that cancels messages returned via cycles.

• Massive multiple-input multiple-output (MIMO)

18