メッセージ伝播法の入門から最先端まで
第４回講義資料

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

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

AMP[3-1]

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

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

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

𝐾𝐾体i.i.d.性の定義

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

6

中心極限定理に関する注意
大数の強法則は無相関等の弱い仮定で主張できるが、中心極限定理を主張するためには確率変数列の独立性が必要である。
中心極限定理の反例[4-2]
𝑁𝑁 − 1体i.i.d.標準ガウス確率変数列 𝑋𝑋𝑛𝑛 𝑁𝑁
𝑛𝑛=1 で、和𝑌𝑌 =𝑁𝑁 −1/2 ∑𝑁𝑁
𝑛𝑛=1 𝑋𝑋𝑛𝑛 の分布が𝒩𝒩(0,1)に収束しない例が存在する。

[4-2] K. Takeuchi, "A family of counterexamples to the central limit theorem based on binary linear
codes," IEICE Trans. Fundamentals., vol. E102-A, no. 5, pp. 738-740, May 2019.

7

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

𝑨𝑨 ∈ ℝ𝑀𝑀×𝑁𝑁 を平均0分散1/𝑀𝑀のi.i.d.要素を持つ行列とする。
𝑀𝑀−1 𝒘𝒘 2 は極限𝑀𝑀 → ∞で𝜎𝜎 2 > 0に確率収束する。

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

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

注意本資料では、例えば𝑀𝑀−1 𝒘𝒘 2 が収束する等のような技術的な仮定に関する議論を省略する。
8

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

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

補題４.２𝒖𝒖 ∈ ℝ𝑁𝑁 を任意の決定論的なベクトルとする。
極限𝑀𝑀−1 𝒖𝒖 2 → 𝑎𝑎が存在する。

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

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

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

10補題４.２の証明
一般性を失うことなく、𝒗𝒗の最初の𝐾𝐾個の要素からなるベクトル𝒗𝒗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.
要素を持つベクトルである。

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

補題４.２の証明
𝑨𝑨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=
� 𝑢𝑢𝑛𝑛2 → 𝑎𝑎.
𝑀𝑀𝑛𝑛=𝐾𝐾+1

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

∎12

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

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

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

111
1𝑡𝑡
222
�
𝒙𝒙 − 𝒙𝒙+𝒘𝒘 → 𝜎𝜎 + Ψ𝑡𝑡−1 𝑣𝑣 𝑡𝑡−1 .
𝛿𝛿 𝑁𝑁𝑀𝑀𝛿𝛿

13状態発展方程式の導出
�𝑡𝑡 + 𝑨𝑨𝑡𝑡 T 𝒘𝒘𝑡𝑡 .
𝝃𝝃 = { 𝑨𝑨𝑡𝑡 T 𝑨𝑨𝑡𝑡 − 𝑰𝑰} 𝒙𝒙 − 𝒙𝒙

前ページの結果と大数の強法則とから、

11𝑡𝑡+12
��𝑡𝑡 + (𝑨𝑨𝑡𝑡 )T 𝒛𝒛𝑡𝑡𝒙𝒙 − 𝒙𝒙
=𝒙𝒙 − 𝜂𝜂𝑡𝑡 𝒙𝒙𝑁𝑁𝑁𝑁𝑁𝑁

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

2= Ψ𝑡𝑡 𝑣𝑣 𝑡𝑡 .

∎14