メッセージ伝播法入門
第６回講義資料
状態発展法：厳密なアプローチ２
九州大学
平成３０年１０月１０日～１０月１２日
豊橋技術科学大学 電気・電子情報工学系
准教授 竹内啓悟
主定理 [3-4]
𝒃𝒃𝑡𝑡 ∼ 𝑩𝑩𝑡𝑡𝜷𝜷𝑡𝑡 + 𝝃𝝃𝑡𝑡, 𝝃𝝃𝑡𝑡 ∼ 𝒩𝒩 𝟎𝟎, 𝑀𝑀−1 𝒒𝒒𝑡𝑡⊥ 2𝑰𝑰𝑀𝑀 . 𝒉𝒉𝑡𝑡 ∼ 𝑯𝑯𝑡𝑡𝜶𝜶𝑡𝑡 + 𝜻𝜻𝑡𝑡, 𝜻𝜻𝑡𝑡 ∼ 𝒩𝒩 𝟎𝟎, 𝑀𝑀−1 𝒎𝒎𝑡𝑡⊥ 2𝑰𝑰𝑁𝑁 .
𝜷𝜷𝑡𝑡 = 𝑸𝑸𝑡𝑡†𝒒𝒒𝑡𝑡 = 𝛽𝛽0, … , 𝛽𝛽𝑡𝑡−1 T, 𝜶𝜶𝑡𝑡 = 𝑴𝑴𝑡𝑡†𝒎𝒎𝑡𝑡,
𝒒𝒒𝑡𝑡⊥ = 𝑷𝑷𝑸𝑸⊥ 𝒒𝒒𝑡𝑡. 𝒎𝒎𝑡𝑡⊥ = 𝑷𝑷𝑴𝑴⊥ 𝒎𝒎𝑡𝑡,
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒉𝒉𝑡𝑡′ − 1
𝑀𝑀 𝒎𝒎𝑡𝑡T𝒎𝒎𝑡𝑡′ → 0, (a)
(b) (c)
(d) 1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒒𝒒𝑡𝑡′ − 𝛿𝛿𝜆𝜆𝑡𝑡′−1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒉𝒉𝑡𝑡′−1 → 0.
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒙𝒙 → 0.
(e)
大システム極限で、以下が成り立つ。
1
𝑀𝑀 𝒃𝒃𝑡𝑡T𝒃𝒃𝑡𝑡′ − 1
𝛿𝛿𝑁𝑁 𝒒𝒒𝑡𝑡T𝒒𝒒𝑡𝑡′ → 0.
1
𝑁𝑁 𝒃𝒃𝑡𝑡T𝒘𝒘 → 0,
主定理の証明の流れ
(e)の証明 (d)の証明と同じ。（省略）
(c)の証明 (a)(b)を使う。
(a)の証明 (c)(d)を使う。
(b)の証明 (a)を使う。（省略）
(d)の証明 (b)(e)を使う。
性質 (c) の証明 [3-4]
前者のみを帰納法により証明する。
𝑡𝑡 = 𝜏𝜏, 𝑡𝑡′ ≤ 𝑡𝑡の場合を証明する。
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒉𝒉𝑡𝑡′ − 1
𝑀𝑀 𝒎𝒎𝑡𝑡T𝒎𝒎𝑡𝑡′ → 0 を仮定して 𝑡𝑡 < 𝜏𝜏, 𝑡𝑡′ ≤ 𝑡𝑡に対して、
𝑡𝑡′ < 𝑡𝑡のとき
1
𝑁𝑁 𝒉𝒉𝜏𝜏T𝒉𝒉𝑡𝑡′ ∼ 1
𝑁𝑁 𝜶𝜶𝜏𝜏T𝑯𝑯𝜏𝜏T𝒉𝒉𝑡𝑡′ + 1
𝑁𝑁 𝜻𝜻𝜏𝜏T𝒉𝒉𝑡𝑡′. 性質(b)を使って、
大数の強法則から、第二項は0に概収束する。
第一項に帰納法の仮定と𝜶𝜶𝜏𝜏 = 𝑴𝑴𝜏𝜏†𝒎𝒎𝜏𝜏を使うと、
1
𝑁𝑁 𝒉𝒉𝜏𝜏T𝒉𝒉𝑡𝑡′ → 1
𝑀𝑀 𝜶𝜶𝜏𝜏T𝑴𝑴𝜏𝜏T𝒎𝒎𝑡𝑡′ = 1
𝑀𝑀 𝒎𝒎𝜏𝜏T𝑷𝑷𝑴𝑴∥ 𝜏𝜏𝒎𝒎𝑡𝑡′ = 1
𝑀𝑀 𝒎𝒎𝜏𝜏T𝒎𝒎𝑡𝑡′.
性質 (c) の証明 [3-4]
𝑡𝑡′ = 𝑡𝑡のとき 1
𝑁𝑁 𝒉𝒉𝜏𝜏T𝒉𝒉𝜏𝜏 → 1
𝑁𝑁 𝜶𝜶𝜏𝜏T𝑯𝑯𝜏𝜏T𝑯𝑯𝜏𝜏𝜶𝜶𝜏𝜏 + 1
𝑁𝑁 𝜻𝜻𝜏𝜏T𝜻𝜻𝜏𝜏. 帰納法の仮定と𝜻𝜻𝜏𝜏 ∼ 𝒩𝒩 𝟎𝟎, 𝑀𝑀−1 𝒎𝒎𝜏𝜏⊥ 2𝑰𝑰𝑁𝑁 を使うと、
1
𝑁𝑁 𝒉𝒉𝜏𝜏T𝒉𝒉𝜏𝜏 → 1
𝑀𝑀 𝜶𝜶𝜏𝜏T𝑴𝑴𝜏𝜏T𝑴𝑴𝜏𝜏𝜶𝜶𝜏𝜏 + 1
𝑀𝑀 𝒎𝒎𝜏𝜏⊥ 2
= 1
𝑀𝑀 𝒎𝒎𝜏𝜏T𝑷𝑷𝑴𝑴∥ 𝜏𝜏𝒎𝒎𝜏𝜏 + 1𝑀𝑀 𝒎𝒎𝜏𝜏⊥ 2 = 𝑀𝑀 𝒎𝒎1 𝜏𝜏∥ 2 + 𝑀𝑀 𝒎𝒎1 𝜏𝜏⊥ 2.
𝒎𝒎𝜏𝜏∥ = 𝑷𝑷𝑴𝑴∥ 𝜏𝜏𝒎𝒎𝜏𝜏. ただし、
𝒎𝒎𝜏𝜏∥ T𝒎𝒎𝜏𝜏⊥ = 0なので、 1
𝑁𝑁 𝒉𝒉𝜏𝜏T𝒉𝒉𝜏𝜏 → 1
𝑀𝑀 𝒎𝒎𝜏𝜏T𝒎𝒎𝜏𝜏. ∎
Stein の補題
(𝑍𝑍1, 𝑍𝑍2) ∼ 𝒩𝒩(𝟎𝟎, 𝚺𝚺)とすると、
𝔼𝔼 𝑍𝑍1𝑓𝑓 𝑍𝑍2 = 𝔼𝔼[𝑍𝑍1𝑍𝑍2]𝔼𝔼 𝑓𝑓′ 𝑍𝑍2 .
証明 固有分解𝚺𝚺 = 𝑽𝑽𝚲𝚲𝑽𝑽Tに対して、以下の変数変換を考える。
�𝑍𝑍1
�𝑍𝑍2 = 𝑽𝑽T 𝑍𝑍1
𝑍𝑍2 , 𝑽𝑽 = 𝑉𝑉11 𝑉𝑉12
𝑉𝑉21 𝑉𝑉22 , Λ = 𝜆𝜆1 0 0 𝜆𝜆2 . 𝔼𝔼 𝑍𝑍1𝑓𝑓 𝑍𝑍2 = 𝔼𝔼 𝑉𝑉11 �𝑍𝑍1 + 𝑉𝑉12 �𝑍𝑍2 𝑓𝑓 𝑉𝑉21 �𝑍𝑍1 + 𝑉𝑉22 �𝑍𝑍2
= 𝑉𝑉11𝔼𝔼 �𝑍𝑍2 𝔼𝔼 �𝑍𝑍1 �𝑍𝑍1𝑓𝑓 𝑉𝑉21 �𝑍𝑍1 + 𝑉𝑉22 �𝑍𝑍2
+𝑉𝑉12𝔼𝔼�𝑍𝑍1 𝔼𝔼�𝑍𝑍2 �𝑍𝑍2𝑓𝑓 𝑉𝑉21 �𝑍𝑍1 + 𝑉𝑉22 �𝑍𝑍2 . 最後の等号は、 �𝑍𝑍1と �𝑍𝑍2は互いに独立なためである。
Stein の補題の証明
𝔼𝔼 �𝑍𝑍12 = 𝜆𝜆1と𝔼𝔼 �𝑍𝑍22 = 𝜆𝜆2に注意して、内側の期待値の評価に 一変数のSteinの補題を使う。（第３回講義資料を参照）
𝔼𝔼 𝑍𝑍1𝑓𝑓 𝑍𝑍2 = 𝜆𝜆1𝑉𝑉11𝑉𝑉21𝔼𝔼 𝑓𝑓′ 𝑉𝑉21 �𝑍𝑍1 + 𝑉𝑉22 �𝑍𝑍2 +𝜆𝜆2𝑉𝑉12𝑉𝑉22𝔼𝔼 𝑓𝑓′ 𝑉𝑉21 �𝑍𝑍1 + 𝑉𝑉22 �𝑍𝑍2
= 𝜆𝜆1𝑉𝑉11𝑉𝑉21 + 𝜆𝜆2𝑉𝑉12𝑉𝑉22 𝔼𝔼 𝑓𝑓′ 𝑍𝑍2 . 共分散行列𝚺𝚺 = 𝑽𝑽𝚲𝚲𝑽𝑽Tの非対角成分を計算すると、
𝚺𝚺 12 = 𝜆𝜆1𝑉𝑉11𝑉𝑉21 + 𝜆𝜆2𝑉𝑉12𝑉𝑉22. したがって、Steinの補題を得る。
𝔼𝔼 𝑍𝑍1𝑓𝑓 𝑍𝑍2 = 𝔼𝔼[𝑍𝑍1𝑍𝑍2]𝔼𝔼 𝑓𝑓′ 𝑍𝑍2 . ∎
性質 (d) の証明 [3-4]
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒒𝒒𝑡𝑡′ → 1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝜂𝜂𝑡𝑡′−1 𝒙𝒙 + 𝒉𝒉𝑡𝑡′−1
定義𝒒𝒒𝑡𝑡′ = 𝜂𝜂𝑡𝑡′−1 𝒙𝒙 + 𝒉𝒉𝑡𝑡′−1 − 𝒙𝒙と性質(e)を使うと、
→ 1
𝑁𝑁 �𝑛𝑛=1
𝑁𝑁
𝔼𝔼 𝒉𝒉𝑡𝑡 𝑛𝑛𝜂𝜂𝑡𝑡′−1 𝑥𝑥𝑛𝑛 + 𝒉𝒉𝑡𝑡′−1 𝑛𝑛 .
最後の表現は、大数の強法則のためである。性質(b)から 𝒉𝒉𝑡𝑡′はi.i.d.ガウス要素を持つため、Steinの補題を使うと、
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒒𝒒𝑡𝑡′ → 1
𝑁𝑁 �𝑛𝑛=1
𝑁𝑁
𝔼𝔼 𝒉𝒉𝑡𝑡 𝑛𝑛 𝒉𝒉𝑡𝑡′−1 𝑛𝑛 𝔼𝔼 𝜂𝜂𝑡𝑡′′−1 𝑥𝑥𝑛𝑛 + 𝒉𝒉𝑡𝑡′−1 𝑛𝑛 .
性質 (d) の証明 [3-4]
𝒉𝒉𝑡𝑡はi.i.d.な要素を持つため、
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒒𝒒𝑡𝑡′ → 1
𝑁𝑁 𝔼𝔼 𝒉𝒉𝑡𝑡T𝒉𝒉𝑡𝑡′−1 1
𝑁𝑁 �𝑛𝑛=1
𝑁𝑁
𝔼𝔼 𝜂𝜂𝑡𝑡′′−1 𝑥𝑥𝑛𝑛 + 𝒉𝒉𝑡𝑡′−1 𝑛𝑛 . 𝜆𝜆𝑡𝑡′−1 = 𝜂𝜂𝑡𝑡′′−1 𝒙𝒙 + 𝒉𝒉𝑡𝑡′−1
定義 𝛿𝛿 を使うと、
1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒒𝒒𝑡𝑡′ − 𝛿𝛿𝜆𝜆𝑡𝑡′−1
𝑁𝑁 𝒉𝒉𝑡𝑡T𝒉𝒉𝑡𝑡′−1 → 0.
大数の強法則から、
∎
性質 (a) の証明 [3-4]
𝑩𝑩𝑡𝑡 + (𝟎𝟎, 𝑴𝑴𝑡𝑡−1𝚲𝚲𝑡𝑡−1) = 𝑨𝑨𝑸𝑸𝑡𝑡, 𝑯𝑯𝑡𝑡 − 𝑸𝑸𝑡𝑡 = 𝑨𝑨T𝑴𝑴𝑡𝑡.
𝑨𝑨 ∼ {𝑩𝑩𝑡𝑡 + (𝟎𝟎, 𝑴𝑴𝑡𝑡−1𝚲𝚲𝑡𝑡−1)}𝑸𝑸𝑡𝑡† + 𝑴𝑴𝑡𝑡† T𝑯𝑯𝑡𝑡T𝑷𝑷𝑸𝑸⊥𝑡𝑡 + 𝚽𝚽𝑴𝑴⊥𝒕𝒕�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 .
𝒃𝒃𝑡𝑡 ∼ 𝑩𝑩𝑡𝑡𝜷𝜷𝑡𝑡 + �
𝑡𝑡′=0 𝑡𝑡−2
𝛽𝛽𝑡𝑡′+1𝜆𝜆𝑡𝑡′𝒎𝒎𝑡𝑡′ + 𝑴𝑴𝑡𝑡 𝑴𝑴𝑡𝑡T𝑴𝑴𝑡𝑡 −1𝑯𝑯𝑡𝑡T𝒒𝒒𝑡𝑡⊥ 上記の制約式の下で、補題５.１を使うと、
ただし、𝑸𝑸𝑡𝑡T𝑷𝑷𝑸𝑸⊥𝑡𝑡 = 𝑶𝑶を使った。
定義𝒃𝒃𝑡𝑡 = 𝑨𝑨𝒒𝒒𝑡𝑡 − 𝜆𝜆𝑡𝑡−1𝒎𝒎𝑡𝑡−1に上記を代入して、
−𝜆𝜆𝑡𝑡−1𝒎𝒎𝑡𝑡−1 + 𝚽𝚽𝑴𝑴⊥𝒕𝒕�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡.
性質 (a) の証明 [3-4]
𝑴𝑴𝑡𝑡 𝑴𝑴𝑡𝑡T𝑴𝑴𝑡𝑡 −1𝑯𝑯𝑡𝑡T𝒒𝒒𝑡𝑡⊥ = 1
𝛿𝛿𝑁𝑁 𝑴𝑴𝑡𝑡𝑮𝑮𝑡𝑡−1𝑯𝑯𝑡𝑡T𝒒𝒒𝑡𝑡 − 1
𝛿𝛿𝑁𝑁 𝑴𝑴𝑡𝑡𝑮𝑮𝑡𝑡−1𝑯𝑯𝑡𝑡T𝑸𝑸𝑡𝑡𝜷𝜷𝑡𝑡.
𝑮𝑮𝑡𝑡 = 𝑀𝑀−1𝑴𝑴𝑡𝑡T𝑴𝑴𝑡𝑡とし、𝒒𝒒𝑡𝑡⊥ = 𝒒𝒒𝑡𝑡 − 𝑸𝑸𝑡𝑡𝜷𝜷𝑡𝑡を使って第三項を評価する。
1
𝛿𝛿𝑁𝑁 𝑯𝑯𝑡𝑡T𝒒𝒒𝑡𝑡 𝑡𝑡′ = 1
𝛿𝛿𝑁𝑁 𝒉𝒉𝑡𝑡T′𝒒𝒒𝑡𝑡 → 𝜆𝜆𝑡𝑡−1
𝑁𝑁 𝒉𝒉𝑡𝑡T′𝒉𝒉𝑡𝑡−1 → 𝜆𝜆𝑡𝑡−1
𝑀𝑀 𝒎𝒎𝑡𝑡T′𝒎𝒎𝑡𝑡−1.
1
𝛿𝛿𝑁𝑁 𝑴𝑴𝑡𝑡𝑮𝑮𝑡𝑡−1𝑯𝑯𝑡𝑡T𝒒𝒒𝑡𝑡 → 𝜆𝜆𝑡𝑡−1
𝑀𝑀 𝑴𝑴𝑡𝑡𝑮𝑮𝑡𝑡−1𝑴𝑴𝑡𝑡T𝒎𝒎𝑡𝑡−1 = 𝜆𝜆𝑡𝑡−1𝒎𝒎𝑡𝑡−1. 性質(c)(d)から、
上記を第一項に適用すると、
性質 (a) の証明 [3-4]
1
𝛿𝛿𝑁𝑁 𝑯𝑯𝑡𝑡T𝑸𝑸𝑡𝑡𝜷𝜷𝑡𝑡 𝑡𝑡′ = 1
𝛿𝛿𝑁𝑁 𝒉𝒉𝑡𝑡T′𝑸𝑸𝑡𝑡𝜷𝜷𝑡𝑡 = 1
𝛿𝛿𝑁𝑁 �𝜏𝜏=0
𝑡𝑡−1
𝛽𝛽𝜏𝜏𝒉𝒉𝑡𝑡T′𝒒𝒒𝜏𝜏 .
1
𝛿𝛿𝑁𝑁 𝑯𝑯𝑡𝑡T𝑸𝑸𝑡𝑡𝜷𝜷𝑡𝑡 𝑡𝑡′ → 1
𝑁𝑁 �𝜏𝜏=1
𝑡𝑡−1
𝛽𝛽𝜏𝜏𝜆𝜆𝜏𝜏−1𝒉𝒉𝑡𝑡T′𝒉𝒉𝜏𝜏−1 → 1
𝑀𝑀 �𝜏𝜏=1
𝑡𝑡−1
𝛽𝛽𝜏𝜏𝜆𝜆𝜏𝜏−1𝒎𝒎𝑡𝑡T′𝒎𝒎𝜏𝜏−1 .
1
𝛿𝛿𝑁𝑁 𝑴𝑴𝑡𝑡𝑮𝑮𝑡𝑡−1𝑯𝑯𝑡𝑡T𝑸𝑸𝑡𝑡𝛽𝛽𝑡𝑡 → 1
𝑀𝑀 �𝜏𝜏=0
𝑡𝑡−2
𝛽𝛽𝜏𝜏+1𝜆𝜆𝜏𝜏𝑴𝑴𝑡𝑡𝑮𝑮𝑡𝑡−1𝑴𝑴𝑡𝑡T𝒎𝒎𝜏𝜏 = �
𝜏𝜏=0 𝑡𝑡−2
𝛽𝛽𝜏𝜏+1𝜆𝜆𝜏𝜏𝒎𝒎𝜏𝜏 . 第二項に関して、
性質(c)(d)を使って、
これを第二項に適用すると、
性質 (a) の証明 [3-4]
𝒃𝒃𝑡𝑡 → 𝑩𝑩𝑡𝑡𝜷𝜷𝑡𝑡 + 𝚽𝚽𝑴𝑴⊥𝒕𝒕�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡. 以上の結果をまとめると、
𝚽𝚽𝑴𝑴⊥𝒕𝒕�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡は平均𝟎𝟎のガウス分布に従う。
大システム極限で第二項は無視できるので、補題４.１を使うと、
𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡 2 = 𝒒𝒒𝑡𝑡T𝑷𝑷𝑸𝑸⊥𝑡𝑡𝒒𝒒𝑡𝑡 = 𝒒𝒒𝑡𝑡⊥ 2から、
𝚽𝚽𝑴𝑴⊥𝒕𝒕�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡 ∼ 𝒩𝒩 𝟎𝟎, 𝑀𝑀−1 𝒒𝒒𝑡𝑡⊥ 2𝑰𝑰𝑀𝑀 . ∎ 𝚽𝚽𝑴𝑴⊥𝑡𝑡�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡 = 𝚽𝚽𝑴𝑴𝑡𝑡 �𝑨𝑨0
�𝑨𝑨 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡 − 𝚽𝚽𝑴𝑴∥ 𝑡𝑡�𝑨𝑨0 𝚽𝚽𝑸𝑸⊥ T𝑡𝑡 𝒒𝒒𝑡𝑡.
�𝑨𝑨0 ∈ ℝ𝑡𝑡×(𝑁𝑁−𝑡𝑡)を𝒩𝒩(0,1/𝑀𝑀)に従う独立な成分を持つ行列として、
