メッセージ伝播法の入門から最先端まで 第３回講義資料
近似的メッセージ伝播法
九州大学
令和元年１０月９日 豊橋技術科学大学 電気・電子情報工学系
准教授 竹内啓悟
ベイズ最適 AMP
�𝒙𝒙 𝑡𝑡+1 = 𝜂𝜂 �𝒙𝒙 𝑡𝑡 + 𝑨𝑨 T 𝒛𝒛 𝑡𝑡 ; 𝑣𝑣 𝑡𝑡 .
𝒛𝒛 𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨�𝒙𝒙 𝑡𝑡 + 𝜂𝜂 ′ �𝒙𝒙 𝑡𝑡−1 + 𝑨𝑨 T 𝒛𝒛 𝑡𝑡−1 ; 𝑣𝑣 𝑡𝑡−1
𝛿𝛿 𝒛𝒛 𝑡𝑡−1 ,
𝑣𝑣 𝑡𝑡 = 𝜎𝜎 2 + 1
𝛿𝛿 MMSE 𝑣𝑣 𝑡𝑡−1 ,
更新式信号の事前分布が既知である必要がある。
AWGN観測モデル ̅𝑥𝑥 𝑛𝑛 = 𝑥𝑥 𝑛𝑛 + 𝑣𝑣𝜔𝜔 𝑛𝑛 , 𝜔𝜔 𝑛𝑛 ∼ 𝒩𝒩 0, 1 .
事後平均𝜂𝜂 ̅𝑥𝑥 𝑛𝑛 ; 𝑣𝑣 = 𝔼𝔼 𝑥𝑥 𝑛𝑛 ̅𝑥𝑥 𝑛𝑛 , 𝑣𝑣 .
最小平均二乗誤差（MMSE）
MMSE 𝑣𝑣 = 𝔼𝔼 𝑥𝑥 𝑛𝑛 − 𝜂𝜂 ̅𝑥𝑥 𝑛𝑛 ; 𝑣𝑣 2 .
AMP[3-1]
�𝒙𝒙 𝑡𝑡+1 = 𝜂𝜂 𝑡𝑡 �𝒙𝒙 𝑡𝑡 + 𝑨𝑨 T 𝒛𝒛 𝑡𝑡 .
𝒛𝒛 𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨�𝒙𝒙 𝑡𝑡 + 𝜂𝜂 𝑡𝑡−1 ′ �𝒙𝒙 𝑡𝑡−1 + 𝑨𝑨 T 𝒛𝒛 𝑡𝑡−1
𝛿𝛿 𝒛𝒛 𝑡𝑡−1 ,
更新式
初期値
𝒙𝒙 0 = 𝟎𝟎, 𝒛𝒛 −1 = 𝟎𝟎.
閾値関数を関数列
{𝜂𝜂 𝑡𝑡 }
に一般化[3-1] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,” Proc. Nat. Acad. Sci., vol. 106, no. 45, pp. 18914–18919, Nov. 2009.
閾値関数の例
Soft thresholding (ST)
[3-2] D. L. Donoho and I. M. Johnstone, “Minimax risk over 𝑙𝑙𝑝𝑝-balls for 𝑙𝑙𝑞𝑞-error,”
Probab. Theory Relat. Fields, vol. 99, no. 2, pp. 277-303, Jun. 1994.
𝜂𝜂 𝑡𝑡 𝑥𝑥 = 𝜂𝜂 ST 𝑥𝑥; 𝜃𝜃 𝑡𝑡 = � 𝑥𝑥 − 𝜃𝜃 𝑡𝑡 for 𝑥𝑥 > 𝜃𝜃 𝑡𝑡 0 for 𝑥𝑥 ≤ 𝜃𝜃 𝑡𝑡 𝑥𝑥 + 𝜃𝜃 𝑡𝑡 for 𝑥𝑥 < −𝜃𝜃 𝑡𝑡 .
ミニマックス最適性[3-2]𝑟𝑟 opt 𝑎𝑎 = inf 𝜂𝜂 sup
𝑝𝑝 𝑥𝑥
𝑛𝑛: 𝔼𝔼 𝑥𝑥
𝑛𝑛 𝑝𝑝 1/𝑝𝑝≤𝑎𝑎 𝔼𝔼 𝑥𝑥 𝑛𝑛 − 𝜂𝜂 𝑥𝑥 𝑛𝑛 + 𝑣𝑣𝜔𝜔 𝑛𝑛 𝑞𝑞 . 𝑟𝑟 ST 𝑎𝑎 = inf 𝜃𝜃 sup
𝑝𝑝 𝑥𝑥
𝑛𝑛: 𝔼𝔼 𝑥𝑥
𝑛𝑛 𝑝𝑝 1/𝑝𝑝≤𝑎𝑎 𝔼𝔼 𝑥𝑥 𝑛𝑛 − 𝜂𝜂 ST 𝑥𝑥 𝑛𝑛 + 𝑣𝑣𝜔𝜔 𝑛𝑛 ; 𝜃𝜃 𝑞𝑞 ,
任意の𝑝𝑝, 𝑞𝑞 > 0
に対して、lim 𝑎𝑎↓0 𝑟𝑟 ST (𝑎𝑎)
𝑟𝑟 opt (𝑎𝑎) = 1 .
𝜃𝜃 𝑡𝑡
−𝜃𝜃 𝑡𝑡
ミニマックス最適性の意義
ミニマックス最適性
• 𝐿𝐿 𝑝𝑝
制約を満たす分布の中で最悪な信号分布を想定•
パラメータ𝜃𝜃
を最適値に設定•
極限𝑎𝑎 ↓ 0
でST
関数は𝐿𝐿 𝑞𝑞
誤差を最小化最適解の唯一性は主張していない。
𝐿𝐿 𝑝𝑝
制約の意義𝑝𝑝 𝑥𝑥 𝑛𝑛 = 1 − 𝜌𝜌 𝛿𝛿 𝑥𝑥 𝑛𝑛 + 𝜌𝜌𝜌𝜌 𝑥𝑥 𝑛𝑛 , ∫ 𝑥𝑥 𝑝𝑝 𝜌𝜌 𝑥𝑥 𝑑𝑑𝑥𝑥 = 𝑀𝑀 𝑝𝑝 < ∞.
𝜌𝜌 < 𝑎𝑎 𝑝𝑝 /𝑀𝑀 𝑝𝑝
を満たす分布は、𝐿𝐿 𝑝𝑝
制約を満たす。上記の信号分布のクラスでは信号密度
𝜌𝜌
が0
に収束する。パラメータ 𝜃𝜃 𝑡𝑡 の最適化 [2-3,3-3,3-1]
1.
状態発展法による性能解析2.
閾値𝜌𝜌 SE
の定義3.
閾値基準によるパラメータ𝜃𝜃 𝑡𝑡
の最適化[3-3] T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of capacity-approaching irregular low- density parity-check codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 619–637, Feb. 2001.
状態発展法 [3-4]
[3-4] M. Bayati and A. Montanari, “The dynamics of message passing on dense graphs, with applications to compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 764–785, Feb. 2011.
状態発展法の解説は、第４～８回講義資料を参照 状態発展方程式
̅𝑣𝑣 𝑡𝑡 = 𝜎𝜎 2 + 1
𝛿𝛿 Ψ ̅𝑣𝑣 𝑡𝑡−1 , 𝜆𝜆 𝑡𝑡−1 , ̅𝑣𝑣 −1 = 1.
𝑀𝑀=𝛿𝛿𝛿𝛿→∞ lim 1
𝑁𝑁 𝔼𝔼 𝒙𝒙 − �𝒙𝒙 𝑡𝑡+1 2 = Ψ ̅𝑣𝑣 𝑡𝑡 , 𝜆𝜆 𝑡𝑡 .
Ψ 𝑣𝑣, 𝜆𝜆 = 𝔼𝔼 𝑥𝑥 1 − 𝜂𝜂 ST 𝑥𝑥 1 + 𝑣𝑣𝜔𝜔 1 ; 𝜆𝜆 𝑣𝑣 2 .
誤差の漸近評価
閾値を
𝜃𝜃 𝑡𝑡 = 𝜆𝜆 𝑡𝑡 ̅𝑣𝑣 𝑡𝑡
と表現しなおした。数値的評価
信号密度
𝜌𝜌
のBG事前分布、𝜎𝜎 2 = 0
、𝛿𝛿 = 0.65
、最適な𝜆𝜆 𝑡𝑡
閾値 [2-4, 3-1]
𝜌𝜌 SE 𝜆𝜆 𝑡𝑡 , 𝑝𝑝 𝑥𝑥 1 , 𝛿𝛿 = sup 𝜌𝜌 > 0: lim 𝑡𝑡→∞ lim
𝜎𝜎
2→0 ̅𝑣𝑣 𝑡𝑡 = 0 . 𝜌𝜌 SE 𝛿𝛿 = sup
{𝜆𝜆
𝑡𝑡>0} 𝑝𝑝 𝑥𝑥 inf
1
:ℙ 𝑥𝑥
1=0 =1−𝜌𝜌 𝜌𝜌 SE ( 𝜆𝜆 𝑡𝑡 , 𝑝𝑝 𝑥𝑥 1 , 𝛿𝛿 ) ,
定義ただし、
閾値の意義
閾値
𝜌𝜌 SE
は、ノイズの分散𝜎𝜎 2
が0
に収束する場合に、最悪の 信号分布を想定したときに大システム極限における平均二 乗誤差が0
に収束するような最大の信号密度𝜌𝜌
に等しい。Soft Thresholding の閾値の下界
閾値の下界
𝜌𝜌 SE ≥ sup
𝜆𝜆>0
𝛿𝛿 − 2 1 + 𝜆𝜆 2 𝑃𝑃 G −𝜆𝜆 − 𝜆𝜆𝑝𝑝 G 𝜆𝜆
1 + 𝜆𝜆 2 − 2 1 + 𝜆𝜆 2 𝑃𝑃 G −𝜆𝜆 − 𝜆𝜆𝑝𝑝 G 𝜆𝜆 .
ただし、𝑝𝑝 G
と𝑃𝑃 G
はそれぞれ標準ガウス分布の確率密度関数と累積分布関数を表す。
下界を最適化するパラメータ
𝜆𝜆 𝑡𝑡 = 𝜆𝜆 opt ≡ argsup
𝜆𝜆>0
𝛿𝛿 − 2 1 + 𝜆𝜆 2 𝑃𝑃 G −𝜆𝜆 − 𝜆𝜆𝑝𝑝 G 𝜆𝜆
1 + 𝜆𝜆 2 − 2 1 + 𝜆𝜆 2 𝑃𝑃 G −𝜆𝜆 − 𝜆𝜆𝑝𝑝 G 𝜆𝜆 .
閾値の下界が最大になるように𝜆𝜆 𝑡𝑡
を設定閾値の評価の概要 [3-1]
𝜌𝜌 SE 𝜆𝜆 𝑡𝑡 , 𝑝𝑝 𝑥𝑥 1 , 𝛿𝛿 = sup 𝜌𝜌 > 0: lim 𝑡𝑡→∞ 𝜎𝜎 lim
2→0 ̅𝑣𝑣 𝑡𝑡 = 0
性質１不動点方程式
̅𝑣𝑣 = 𝛿𝛿 −1 Ψ ̅𝑣𝑣, 𝜆𝜆 𝑡𝑡
は解̅𝑣𝑣 = 0
を持つ。性質２
.
関数
Ψ ̅𝑣𝑣, 𝜆𝜆 𝑡𝑡
は̅𝑣𝑣
に関して上に凸である。性質１と性質２から、
≥ sup 𝜌𝜌 > 0: ∃𝑡𝑡 0 s. t. 1
𝛿𝛿 lim 𝑣𝑣↓0 𝜕𝜕
𝜕𝜕𝑣𝑣 Ψ 𝑣𝑣 ; 𝜆𝜆 𝑡𝑡 < 1 for all 𝑡𝑡 ≥ 𝑡𝑡 0 .
上記の閾値の下界は事前分布の詳細に依存しないことが言える。
閾値の下界である理由
𝑡𝑡→∞ lim 𝜎𝜎 lim
2→0 ̅𝑣𝑣 𝑡𝑡 = 0 1
𝛿𝛿 lim 𝑣𝑣↓0 𝜕𝜕
𝜕𝜕𝑣𝑣 Ψ 𝑣𝑣 ; 𝜆𝜆 𝑡𝑡 < 1 for all 𝑡𝑡 ≥ 𝑡𝑡 0
∵
条件から、すべての𝑡𝑡 ≥ 𝑡𝑡 0
に対して̅𝑣𝑣 𝑡𝑡 > ̅𝑣𝑣 𝑡𝑡+1 ≥ 0
が言える。𝑡𝑡→∞ lim 𝜎𝜎 lim
2→0 ̅𝑣𝑣 𝑡𝑡 = inf 𝑡𝑡≥𝑡𝑡
0
𝜎𝜎 lim
2→0 ̅𝑣𝑣 𝑡𝑡 = 0. ∎
逆の主張に対する反例
1
𝛿𝛿 lim 𝑣𝑣↓0 𝜕𝜕
𝜕𝜕𝑣𝑣 Ψ 𝑣𝑣 ; 𝜆𝜆 𝑡𝑡 < 1 only for odd 𝑡𝑡,
𝑡𝑡
が奇数の場合に̅𝑣𝑣 𝑡𝑡 − ̅𝑣𝑣 𝑡𝑡+1 > ̅𝑣𝑣 𝑡𝑡+2 − ̅𝑣𝑣 𝑡𝑡+1
を満たすように、𝜆𝜆 𝑡𝑡+1
を取ればよい。準備１：超関数の意味での微分
任意の急減少関数
𝜙𝜙
に対して以下を満たす関数𝐷𝐷𝐷𝐷
が存在する とき、𝐷𝐷𝐷𝐷
を𝐷𝐷
の超関数の意味での微分と呼び、𝐷𝐷𝑓
と書く。�𝐷𝐷𝐷𝐷 𝑥𝑥 𝜙𝜙 𝑥𝑥 𝑑𝑑𝑥𝑥 = − �𝐷𝐷 𝑥𝑥 𝜙𝜙 ′ 𝑥𝑥 𝑑𝑑𝑥𝑥 .
意義�𝐷𝐷 ′ 𝑥𝑥 𝜙𝜙 𝑥𝑥 𝑑𝑑𝑥𝑥 = − �𝐷𝐷 𝑥𝑥 𝜙𝜙 ′ 𝑥𝑥 𝑑𝑑𝑥𝑥
部分積分 例𝐷𝐷 𝑥𝑥 = � 1 for 𝑥𝑥 > 0 0 for 𝑥𝑥 ≤ 0.
− �𝐷𝐷 𝑥𝑥 𝜙𝜙 ′ 𝑥𝑥 𝑑𝑑𝑥𝑥 = − �
0
∞ 𝜙𝜙 ′ 𝑥𝑥 𝑑𝑑𝑥𝑥 = 𝜙𝜙 0 = �𝛿𝛿 𝑥𝑥 𝜙𝜙 𝑥𝑥 𝑑𝑑𝑥𝑥 .
∵
𝐷𝐷 ′ 𝑥𝑥 = 𝛿𝛿 𝑥𝑥 .
最後の等号はデルタ関数の定義である。
1
ST 関数の微分
𝜂𝜂 𝑡𝑡 𝑥𝑥 = 𝜂𝜂 ST 𝑥𝑥; 𝜃𝜃 = � 𝑥𝑥 − 𝜃𝜃 for 𝑥𝑥 > 𝜃𝜃
0 for 𝑥𝑥 ≤ 𝜃𝜃
𝑥𝑥 + 𝜃𝜃 for 𝑥𝑥 < −𝜃𝜃.
𝜕𝜕 1 𝜂𝜂 ST ≡ 𝜕𝜕𝜂𝜂 ST
𝜕𝜕𝑥𝑥 = � 1 for 𝑥𝑥 > 𝜃𝜃 0 for 𝑥𝑥 ≤ 𝜃𝜃
1 for 𝑥𝑥 < −𝜃𝜃.
𝜕𝜕 1 2 𝜂𝜂 ST = 𝛿𝛿 𝑥𝑥 − 𝜃𝜃 − 𝛿𝛿 𝑥𝑥 + 𝜃𝜃 .
二階微分一階微分
𝜃𝜃
−𝜃𝜃
𝜃𝜃
−𝜃𝜃 𝜂𝜂 ST
𝑥𝑥
𝑥𝑥
𝜕𝜕 1 𝜂𝜂 ST
𝜕𝜕 2 𝜂𝜂 ST ≡ 𝜕𝜕𝜂𝜂 ST
𝜕𝜕𝜃𝜃 = � −1 for 𝑥𝑥 > 𝜃𝜃 0 for 𝑥𝑥 ≤ 𝜃𝜃
1 for 𝑥𝑥 < −𝜃𝜃.
準備２： Stein の補題
𝑍𝑍 ∼ 𝒩𝒩(0, 𝜎𝜎 2 )
とすると、𝔼𝔼 𝑍𝑍𝐷𝐷 𝑍𝑍 = 𝜎𝜎 2 𝔼𝔼 𝐷𝐷 ′ 𝑍𝑍 .
証明𝔼𝔼 𝑍𝑍𝐷𝐷 𝑍𝑍 = �𝑧𝑧𝐷𝐷 𝑧𝑧 𝑝𝑝 𝑧𝑧 𝑑𝑑𝑧𝑧 = −𝜎𝜎 2 �𝐷𝐷 𝑧𝑧 𝑝𝑝 ′ 𝑧𝑧 𝑑𝑑𝑧𝑧
= 𝜎𝜎 2 �𝐷𝐷 ′ 𝑧𝑧 𝑝𝑝 𝑧𝑧 𝑑𝑑𝑧𝑧 = 𝜎𝜎 2 𝔼𝔼 𝐷𝐷 ′ 𝑍𝑍 . ∎
𝑝𝑝 𝑧𝑧 = 1
2𝜌𝜌𝜎𝜎 2 𝑒𝑒 − 𝑧𝑧
2
2𝜎𝜎
2,
閾値の評価
Ψ 𝑣𝑣, 𝜆𝜆 = 𝔼𝔼 𝜂𝜂 𝑥𝑥 1 + 𝑣𝑣𝜔𝜔 1 ; 𝜆𝜆 𝑣𝑣 − 𝑥𝑥 1 2 .
𝜕𝜕Ψ
𝜕𝜕𝑣𝑣 = 𝔼𝔼 2(𝜂𝜂 − 𝑥𝑥 1 ) 𝜕𝜕𝜂𝜂
𝜕𝜕𝑣𝑣
𝜕𝜕
𝜕𝜕𝑣𝑣 𝜂𝜂 = 𝜔𝜔 1
2 𝑣𝑣 𝜕𝜕 1 𝜂𝜂 + 𝜆𝜆
2 𝑣𝑣 𝜕𝜕 2 𝜂𝜂, 𝜕𝜕𝜂𝜂
𝜕𝜕𝜔𝜔 1 = 𝑣𝑣𝜕𝜕 1 𝜂𝜂.
= 𝔼𝔼 𝜕𝜕 1 𝜂𝜂 2 + 𝔼𝔼 𝜂𝜂 − 𝑥𝑥 1 𝜕𝜕 1 2 𝜂𝜂 + 𝜆𝜆
𝑣𝑣 𝔼𝔼 (𝜂𝜂 − 𝑥𝑥 1 )𝜕𝜕 2 𝜂𝜂 .
準備導関数の評価
= 1
𝑣𝑣 𝔼𝔼 𝜔𝜔 1 (𝜂𝜂 − 𝑥𝑥 1 )𝜕𝜕 1 𝜂𝜂 + 𝜆𝜆
𝑣𝑣 𝔼𝔼 (𝜂𝜂 − 𝑥𝑥 1 )𝜕𝜕 2 𝜂𝜂
最後の等号はSteinの補題から従う。
閾値の評価
𝜕𝜕Ψ
𝜕𝜕𝑣𝑣 = 1 + 𝜆𝜆 2 𝔼𝔼 𝑃𝑃 G 𝑥𝑥 1 − 𝜆𝜆 𝑣𝑣
𝑣𝑣 + 𝑃𝑃 G − 𝑥𝑥 1 + 𝜆𝜆 𝑣𝑣 𝑣𝑣
−𝔼𝔼 𝜆𝜆 + 𝑥𝑥 1
𝑣𝑣 𝑝𝑝 G 𝜆𝜆 𝑣𝑣 − 𝑥𝑥 1 𝑣𝑣
スライド１３に示した微分結果を使うと、
+𝔼𝔼 𝑥𝑥 1
𝑣𝑣 − 𝜆𝜆 𝑝𝑝 G 𝑥𝑥 1 + 𝜆𝜆 𝑣𝑣
𝑣𝑣 .
閾値の評価
𝜌𝜌 < 𝛿𝛿 − 2 1 + 𝜆𝜆 2 𝑡𝑡 𝑃𝑃 G −𝜆𝜆 𝑡𝑡 − 𝜆𝜆 𝑡𝑡 𝑝𝑝 G 𝜆𝜆 𝑡𝑡
1 + 𝜆𝜆 2 𝑡𝑡 − 2 1 + 𝜆𝜆 𝑡𝑡 2 𝑃𝑃 G −𝜆𝜆 𝑡𝑡 − 𝜆𝜆 𝑡𝑡 𝑝𝑝 G 𝜆𝜆 𝑡𝑡 for all 𝑡𝑡 ≥ 𝑡𝑡 0 lim 𝑣𝑣↓0
𝜕𝜕Ψ
𝜕𝜕𝑣𝑣 = 1 + 𝜆𝜆 2 ℙ 𝑥𝑥 1 > 0 + ℙ 𝑥𝑥 1 < 0
+2 1 + 𝜆𝜆 2 𝑃𝑃 G −𝜆𝜆 − 𝜆𝜆𝑝𝑝 G 𝜆𝜆 ℙ(𝑥𝑥 1 = 0)
= 1 + 𝜆𝜆 2 𝜌𝜌 + 2𝑃𝑃 G −𝜆𝜆 1 − 𝜌𝜌 − 2𝜆𝜆𝑝𝑝 G (𝜆𝜆)(1 − 𝜌𝜌).
最後の等号で、
