メッセージ伝播法入門
第４回講義資料

状態発展法：発見的アプローチ
九州大学
平成３０年１０月１０日～１０月１２日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1AMPと状態発展方程式
観測モデル

AMP[3-1]

𝒚𝒚 = 𝑨𝑨𝑨𝑨 + 𝒘𝒘,𝒘𝒘 ∼ 𝒩𝒩(𝟎𝟎, 𝜎𝜎 2 𝑰𝑰𝑀𝑀 )′𝑡𝑡−1 + 𝑨𝑨T 𝒛𝒛𝑡𝑡−1
�𝜂𝜂𝒙𝒙
𝑡𝑡−1𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨�
𝒙𝒙𝑡𝑡 +𝛿𝛿�𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙
�𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 .
𝒙𝒙

状態発展方程式[3-4]1𝑡𝑡2𝑣𝑣 = 𝜎𝜎 + Ψ𝑡𝑡 𝑣𝑣 𝑡𝑡−1 ,𝛿𝛿Ψ𝑡𝑡+1 𝑣𝑣 = 𝔼𝔼 𝑥𝑥1 − 𝜂𝜂𝑡𝑡 𝑥𝑥1 + 𝑣𝑣𝜔𝜔12𝒛𝒛𝑡𝑡−1 ,𝑣𝑣 0 = 1,,𝜔𝜔1 ∼ 𝒩𝒩 0,1 .

2

発見的導出の手順[3-4]1. 観測モデルを反復回数𝑡𝑡ごとに独立な仮想的モデルに置き換える。
𝒚𝒚𝑡𝑡 = 𝑨𝑨𝑡𝑡 𝒙𝒙 + 𝒘𝒘𝑡𝑡 ,𝒘𝒘𝑡𝑡 ∼ 𝒩𝒩(𝟎𝟎, 𝜎𝜎 2 𝑰𝑰𝑁𝑁 ){𝑨𝑨𝑡𝑡 }と{𝒘𝒘𝑡𝑡 }はそれぞれ𝑨𝑨と𝒘𝒘に従うi.i.d.系列

2. AMPからオンサーガ項を取り除く。
�𝑡𝑡 ,𝒛𝒛𝑡𝑡 = 𝒚𝒚𝑡𝑡 − 𝑨𝑨𝑡𝑡 𝒙𝒙

3.

�𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙
�𝑡𝑡 + (𝑨𝑨𝑡𝑡 )T 𝒛𝒛𝑡𝑡 .
𝒙𝒙

大システム極限で、性能解析を行う。
3大数の強法則[4-1]𝑋𝑋𝑛𝑛 𝑁𝑁
𝑛𝑛=1 を二次モーメントが有界な確率変数列とし、𝑆𝑆𝑁𝑁 = ∑𝑁𝑁
𝑛𝑛=1 𝑋𝑋𝑛𝑛 を定義する。
∞

�

𝑁𝑁=1𝕍𝕍 𝑆𝑆𝑁𝑁
< ∞.
2𝑁𝑁

上記を満たすならば、以下の大数の強法則が従う。
𝑆𝑆𝑁𝑁 − 𝔼𝔼[𝑆𝑆𝑁𝑁 ]𝑇𝑇𝑁𝑁 =→ 0 almost surely as 𝑁𝑁 → ∞.
𝑁𝑁注意

無相関な確率変数列は条件を満たす。
[4-1] R. Lyons, “Strong laws of large numbers for weakly correlated random variables,”Michigan Math. J., vol. 35, no. 3, pp. 353–359, 1988.
4

中心極限定理[4-2]{𝑋𝑋𝑛𝑛 }を平均𝜇𝜇𝑛𝑛 分散𝜎𝜎𝑛𝑛2 の独立な確率変数列とし、
2𝑠𝑠𝑁𝑁2 = ∑𝑁𝑁𝜎𝜎を定義する。
𝑛𝑛𝑛𝑛=1𝑁𝑁

1lim 2 � 𝔼𝔼[ 𝑋𝑋𝑛𝑛 − 𝜇𝜇𝑛𝑛 2 1 𝑋𝑋𝑛𝑛 − 𝜇𝜇𝑛𝑛 > 𝜖𝜖𝑠𝑠𝑁𝑁 ) = 0 for any 𝜖𝜖 > 0.
𝑁𝑁→∞ 𝑠𝑠𝑁𝑁
𝑛𝑛=1

上記の条件を満たすならば、以下の中心極限定理が従う。
𝑁𝑁注意1
� (𝑋𝑋𝑛𝑛 − 𝜇𝜇𝑛𝑛 ) → 𝒩𝒩 0,1 in distribution as 𝑁𝑁 → ∞.
𝑠𝑠𝑁𝑁
𝑛𝑛=1ある𝛼𝛼 > 0に対して、𝑋𝑋𝑛𝑛 の2 + 𝛼𝛼次モーメントが存在すればよい。

5

補題４.１𝒘𝒘 ∈ ℝ𝑀𝑀 を任意の決定論的なベクトルとする。

𝑨𝑨 ∈ ℝ𝑀𝑀×𝑁𝑁 を平均0分散1/𝑀𝑀のi.i.d.要素を持つ行列とする。

ベクトル𝒗𝒗 = 𝑨𝑨T 𝒘𝒘は以下を満たす。

• 𝒗𝒗は大システム極限で平均𝟎𝟎共分散行列𝑀𝑀−1 𝒘𝒘 2 𝑰𝑰𝑁𝑁のガウス確率ベクトルに分布収束する。

注意
本資料では、例えば𝑀𝑀−1 𝒘𝒘 2 が大システム極限で収束する
等のような技術的な仮定に関する記載をすべて省略する。
6

補題４.１の証明
𝒗𝒗が平均0のi.i.d.要素を持つことは、𝑨𝑨の列ベクトルの独立性から従う。
𝒗𝒗の最初の要素を評価すると、𝑀𝑀𝒗𝒗 1 = � 𝑤𝑤𝑚𝑚 𝐴𝐴𝑚𝑚𝑚 .
𝑚𝑚=1

中心極限定理より、 𝒗𝒗 1 の分布は大システム極限で𝒩𝒩(0, 𝑀𝑀−1 𝒘𝒘 2 )に収束する。
∎7

𝐾𝐾体独立性の定義

ある自然数𝐾𝐾(≤ 𝑁𝑁)に対して、𝑁𝑁次元確率ベクトル𝒗𝒗 ∈ ℝ𝑁𝑁 が以下の性質を満たすとき、𝒗𝒗を平均𝜇𝜇分散𝜎𝜎 2 の𝐾𝐾体独立な確率ベクトルと呼ぶ。
• 𝒗𝒗から任意の𝐾𝐾個の異なる要素を取り出してできるベクトルはi.i.d.要素を持ち、各要素は平均𝜇𝜇分散𝜎𝜎 2 である。
注意
さらに、各要素がガウス分布に従う場合、𝒗𝒗は𝐾𝐾体独立なガウス確率ベクトルと呼ばれる。

8

補題４.２𝒖𝒖 ∈ ℝ𝑁𝑁 を任意の決定論的なベクトルとする。

𝑨𝑨 ∈ ℝ𝑀𝑀×𝑁𝑁 を平均0分散1/𝑀𝑀のi.i.d.要素を持つ行列とする。

ベクトル𝒗𝒗 = 𝑨𝑨T 𝑨𝑨 − 𝑰𝑰𝑁𝑁 𝒖𝒖は以下を満たす。

• 任意の有限な𝐾𝐾 ∈ ℕに対して、𝒗𝒗は大システム極限で平均0分散𝑀𝑀−1 𝒖𝒖 2 の𝐾𝐾体独立なガウス確率ベクトルに分布収束する。

9

補題４.２の証明
一般性を失うことなく、𝒗𝒗の最初の𝐾𝐾個の要素からなるベクトル𝒗𝒗1 ∈ ℝ𝐾𝐾 に注目する。

𝒗𝒗1 = 𝑨𝑨1T 𝑨𝑨1 , 𝑨𝑨2 𝒖𝒖 − 𝒖𝒖1 = 𝑨𝑨1T 𝑨𝑨1 − 𝑰𝑰𝐾𝐾 𝒖𝒖1 + 𝑨𝑨1T 𝑨𝑨2 𝒖𝒖2 ,𝑨𝑨 = 𝑨𝑨1 , 𝑨𝑨2∈ ℝ𝑀𝑀×𝐾𝐾 × ℝ𝑀𝑀× 𝑁𝑁−𝐾𝐾 .

𝒖𝒖1𝒖𝒖 = 𝒖𝒖 ∈ ℝ𝐾𝐾 × ℝ𝑁𝑁−𝐾𝐾 .
2

大数の強法則から、𝑀𝑀 → ∞において𝑨𝑨1T 𝑨𝑨1 は𝑰𝑰𝐾𝐾 に概収束するため、右辺第一項も𝟎𝟎に概収束する。

第二項はi.i.d.要素を持つベクトルなので、𝒗𝒗1 も漸近的にi.i.d.
要素を持つベクトルである。

それゆえ、第二項の一番目の要素のガウス性を示せばよい。
10

補題４.２の証明
𝑨𝑨1T 𝑨𝑨2 𝒖𝒖2 1 =𝑁𝑁1

� 𝑢𝑢𝑛𝑛 𝑋𝑋𝑛𝑛 ,𝑀𝑀 𝑛𝑛=𝐾𝐾+1𝑋𝑋𝑛𝑛

𝑀𝑀𝑀𝑀= 𝑨𝑨1T 𝑨𝑨2 1𝑛𝑛 = � 𝐴𝐴𝑚𝑚𝑚 𝐴𝐴𝑚𝑚𝑚𝑚 .
𝑚𝑚=1{𝐴𝐴𝑚𝑚𝑚 }の条件の下で、{𝑋𝑋𝑛𝑛 }は平均0のi.i.d.確率変数列である。
𝔼𝔼 𝑋𝑋𝑛𝑛2 𝐴𝐴𝑚𝑚𝑚

𝑀𝑀𝑀𝑀𝑚𝑚=1𝑚𝑚=1= 𝑀𝑀 � 𝐴𝐴2𝑚𝑚𝑚 𝔼𝔼 𝐴𝐴2𝑚𝑚𝑚𝑚 = � 𝐴𝐴2𝑚𝑚𝑚 → 1.

特に上記の性質から、{𝑋𝑋𝑛𝑛 }はi.i.d.標準確率変数列である。
𝕍𝕍1𝑁𝑁

� 𝑢𝑢𝑛𝑛 𝑋𝑋𝑛𝑛

𝑀𝑀 𝑛𝑛=𝐾𝐾+1

𝑁𝑁

1
12=
� 𝑢𝑢𝑛𝑛 →𝒖𝒖 2 .
𝑀𝑀
𝑀𝑀𝑛𝑛=𝐾𝐾+1

中心極限定理より、 𝑨𝑨1T 𝑨𝑨2 𝒖𝒖2 1 の漸近ガウス性を得る。

∎11

状態発展方程式の導出
�𝑡𝑡 2 → Ψ𝑡𝑡 (𝑣𝑣 𝑡𝑡−1 )を仮定して、大システム極限で𝑁𝑁 −1 𝒙𝒙 − 𝒙𝒙�𝑡𝑡+1 2 → Ψ𝑡𝑡+1 (𝑣𝑣 𝑡𝑡 )を示す。
𝑁𝑁 −1 𝒙𝒙 − 𝒙𝒙�𝑡𝑡 = 𝑨𝑨𝑡𝑡 𝒙𝒙 − 𝒙𝒙�𝑡𝑡 + 𝒘𝒘𝑡𝑡 .
観測モデルから、 𝒛𝒛𝑡𝑡 = 𝒚𝒚𝑡𝑡 − 𝑨𝑨𝑡𝑡 𝒙𝒙
閾値関数𝜂𝜂𝑡𝑡 の入力は、

�𝑡𝑡 + (𝑨𝑨𝑡𝑡 )T 𝒛𝒛𝑡𝑡 = 𝒙𝒙 + { 𝑨𝑨𝑡𝑡 T 𝑨𝑨𝑡𝑡 − 𝑰𝑰} 𝒙𝒙 − 𝒙𝒙�𝑡𝑡 + 𝑨𝑨𝑡𝑡 T 𝒘𝒘𝑡𝑡 .
𝒙𝒙

任意の𝐾𝐾 ∈ ℕに対して、補題４.１と補題４.２から、右辺の第二項と第三項の和は、平均0分散𝑣𝑣 𝑡𝑡 の𝐾𝐾体独立なガウス確率ベクトルに分布収束する。
𝑣𝑣 𝑡𝑡 =

11
1
1𝑡𝑡
2
22
�
𝒙𝒙 − 𝒙𝒙+𝒘𝒘 → 𝜎𝜎 + Ψ𝑡𝑡 𝑣𝑣 𝑡𝑡−1 .
𝛿𝛿 𝑁𝑁𝑀𝑀𝛿𝛿

12状態発展方程式の導出
前ページの結果と大数の強法則とから、
11𝑡𝑡+12��𝑡𝑡 + (𝑨𝑨𝑡𝑡 )T 𝒛𝒛𝑡𝑡𝒙𝒙 − 𝒙𝒙
=𝒙𝒙 − 𝜂𝜂𝑡𝑡 𝒙𝒙
𝑁𝑁𝑁𝑁𝑁𝑁

1= � 𝑥𝑥𝑛𝑛 − 𝜂𝜂𝑡𝑡 𝑥𝑥𝑛𝑛 + 𝜉𝜉𝑛𝑛𝑁𝑁𝑛𝑛=1→ 𝔼𝔼 𝑥𝑥1 − 𝜂𝜂𝑡𝑡 𝑥𝑥1 +22𝑣𝑣 𝑡𝑡 𝜔𝜔1

2= Ψ𝑡𝑡+1 𝑣𝑣 𝑡𝑡 .

�𝑡𝑡 + 𝑨𝑨𝑡𝑡 T 𝒘𝒘𝑡𝑡 .
𝝃𝝃 = { 𝑨𝑨𝑡𝑡 T 𝑨𝑨𝑡𝑡 − 𝑰𝑰} 𝒙𝒙 − 𝒙𝒙∎13