通信符号理論 12

1 通信符号理論 第12回 伊藤彰則

2 シンボルMAP復号に向けて ෝ = arg max 𝑃 𝒚 𝒙 𝑃(𝒙) • ブロックMAP復号 𝒙 𝒙 • ブロックMAP復号は「全体として」確率最大のシンボル系列 ෝ = (𝑥ො1 , … , 𝑥ො𝑛 ) 𝒙 を計算する • それぞれの𝑥ො𝑖 が確率的な意味で最適であることを必ずしも意味しない • ある𝑖番目のシンボルについて、確率的な意味で最も良い復号結 果を得るためにはどうしたらいいのか？

3 特定のシンボルを復号する • 𝑖番目のシンボルについて最適な結果を得るには？ • 𝑥ො𝑖 = arg max𝑥𝑖 σ𝒙∖𝑥𝑖 𝑃(𝒚| … , 𝑥𝑖 , … ) 𝑃( … , 𝑥𝑖 , … ) • 𝒙 ∖ 𝑥𝑖 は「𝒙から𝑥𝑖 を除いたもの」つまり(𝑥1 , … , 𝑥𝑖−1 , 𝑥𝑖+1 , … , 𝑥𝑛 ) • 省略しているが、実際にはσ𝒙∖𝑥𝑖 𝑃(… )は、「変数𝒙 ∖ 𝑥𝑖 について、すべ ての可能な値に関する総和をとる」ことを意味する • 関数の周辺化(marginalization)とは • 関数𝑓 𝒙 = 𝑓(𝑥1 , … , 𝑥𝑛 ) • 変数𝑥𝑖 以外を周辺化した関数𝑔𝑖 𝑥𝑖 = σ𝒙∖𝑥𝑖 𝑓(𝒙)

4 周辺化の例 • 関数𝑓 𝑥1 , 𝑥2 , 𝑥1 , 𝑥2 ∈ 𝐺𝐹(2)について • 𝑔1 𝑥1 = 𝑓 𝑥1 , 0 + 𝑓(𝑥1 , 1) • 𝑔2 𝑥2 = 𝑓 0, 𝑥2 + 𝑓(1, 𝑥2 ) • 関数𝑓 𝑥1 , 𝑥2 , 𝑥3 , 𝑥1 , 𝑥2 , 𝑥3 ∈ 𝐺𝐹(2)について • 𝑔1 𝑥1 = 𝑓 𝑥1 , 0, 0 + 𝑓 𝑥1 , 0, 1 + 𝑓 𝑥1 , 1, 0 + 𝑓(𝑥1 , 1, 1) • 𝑔2 𝑥2 = 𝑓 0, 𝑥2 , 0 + 𝑓 0, 𝑥2 , 1 + 𝑓 1, 𝑥2 , 0 + 𝑓(1, 𝑥2 , 1) • 𝑔3 𝑥3 = 𝑓 0, 0, 𝑥3 + 𝑓 0, 1, 𝑥3 + 𝑓 1, 0, 𝑥3 + 𝑓(1, 1, 𝑥3 )

5 周辺化の難しさ • n変数関数を周辺化して1変数関数にしようとした場合 • すべての𝒙 ∖ 𝑥𝑖 について関数の加算が必要 • 変数が２値であれば、𝒙 ∖ 𝑥𝑖 は全部で2𝑛−1 通りある • 𝑛が大きい場合（~1000）計算不可能になる

6 周辺化の難しさ • 全部計算しなくて済む方法はないのか • 例：𝑓(𝑥1 , 𝑥2 , 𝑥3 )を𝑥3 以外について周辺化する場合 • もし𝑓 𝑥1 , 𝑥2 , 𝑥3 = 𝑓1 𝑥1 , 𝑥3 𝑓2 (𝑥2 , 𝑥3 )と分解できたとしたら？ • 𝑔3 𝑥3 = σ𝑥1 ,𝑥2 𝑓 𝑥1 , 𝑥2 , 𝑥3 = σ𝑥1 ,𝑥2 𝑓1 𝑥1 , 𝑥3 𝑓2 𝑥2 , 𝑥3 = σ𝑥1 𝑓1 (𝑥1 , 𝑥3 ) σ𝑥2 𝑓2 (𝑥2 , 𝑥3 ) • 加算回数は（𝑥1 の種類×𝑥2 の種類）から（𝑥1 の種類＋𝑥2 の種類）へ

7 関数の分解と周辺化 • 𝑓 𝑥1 , 𝑥2 , 𝑥3 = 𝑓1 𝑥1 , 𝑥3 𝑓2 (𝑥2 , 𝑥3 )と分解できる場合の例 • 𝑔3 𝑥3 = σ𝑥1 ,𝑥2 ∈{0,1} 𝑓(𝑥1 , 𝑥2 , 𝑥3 ) = 𝑓 0,0, 𝑥3 + 𝑓 0,1, 𝑥3 + 𝑓 1,0, 𝑥3 + 𝑓 1,1, 𝑥3 = 𝑓1 0, 𝑥3 𝑓2 0, 𝑥3 + 𝑓1 0, 𝑥3 𝑓2 1, 𝑥3 +𝑓1 1, 𝑥3 𝑓2 0, 𝑥3 + 𝑓1 1, 𝑥3 𝑓2 1, 𝑥3 = (𝑓1 0, 𝑥3 + 𝑓1 1, 𝑥3 )(𝑓2 0, 𝑥3 + 𝑓2 1, 𝑥3 ) • 一般に 𝑓 𝒙 = 𝑓1 𝐴1 ⋯ 𝑓𝑛 (𝐴𝑛 )と分解できる場合を考える

8 関数の周辺化とファクターグラフ • ファクターグラフとは • 関数と変数の依存関係をグラフで表現したもの • 「関数ノード」と「変数（因子）ノード」を結んだ無向グラフ • 例：𝑓 𝑥1 , 𝑥2 , 𝑥3 = 𝑓1 𝑥1 , 𝑥3 𝑓2 (𝑥2 , 𝑥3 )の場合 𝑥1 𝑓1 (𝑥1 , 𝑥3 ) 𝑥3 𝑥2 𝑓2 (𝑥2 , 𝑥3 )

9 関数の周辺化とファクターグラフ この変数以外の周辺化をする 場合 𝑥1 𝑥3 𝒙∖𝑥3 𝑥2 ෍ 𝑓1 (𝑥1 , 𝑥3 ) 𝑥1 ෍ 𝑓(𝑥1 , 𝑥2 , 𝑥3 ) ෍ 𝑓2 (𝑥2 , 𝑥3 ) 𝑓1 (𝑥1 , 𝑥3 ) 𝑓2 (𝑥2 , 𝑥3 ) この２つの関数の周辺化の結果の積を計算 𝑥2

10 関数の周辺化とファクターグラフ この変数について総和をとる 𝑥1 𝑥3 𝑥2 ෍ 𝑓2 (𝑥2 , 𝑥3 ) 𝑓1 (𝑥1 , 𝑥3 ) 𝑓2 (𝑥2 , 𝑥3 ) 𝑥2 この関数を（𝑥3 以外について） 周辺化する場合

11 関数の周辺化とファクターグラフ この変数以外の周辺化をする 場合 𝑥1 𝑥3 ෍ 𝑓(𝑥1 , 𝑥2 , 𝑥3 ) 𝒙∖𝑥1 𝑥2 ෍ 𝑓1 (𝑥1 , 𝑥3 ) ෍ 𝑓2 (𝑥2 , 𝑥3 ) 𝑥3 𝑓1 (𝑥1 , 𝑥3 ) 𝑓2 (𝑥2 , 𝑥3 ) この関数と「𝑓2 を𝑥3 以外について周辺化した関 数」の積を𝑥3 について総和 𝑥2

12 関数の周辺化とファクターグラフ この変数以外を周辺化 𝑥1 𝑥3 𝑥2 ෍ 𝑓2 (𝑥2 , 𝑥3 ) 𝑥2 𝑓1 (𝑥1 , 𝑥3 ) 𝑓2 (𝑥2 , 𝑥3 ) 𝑥2 について周辺化

13 もっと複雑なファクターグラフ 𝑓𝐴 (𝑥1 ) 𝑥1 𝑓 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 = 𝑓𝐴 𝑥1 𝑓𝐵 𝑥1 , 𝑥4 𝑓𝐶 𝑥1 , 𝑥2 , 𝑥3 𝑓𝐷 𝑥4 𝑓𝐸 (𝑥4 , 𝑥5 ) 𝑓𝐶 (𝑥1 , 𝑥2 , 𝑥3 ) 𝑓𝐷 (𝑥4 ) 𝑥2 𝑓𝐵 (𝑥1 , 𝑥4 ) 𝑥3 𝑥4 𝑓𝐸 (𝑥4 , 𝑥5 ) 𝑥5 こういう関数の周辺化は どうすればいいのか？

14 Sum-Product（和積）アルゴリズム • ファクターグラフで表現された関数を周辺化するアルゴリズム • 変数ノードと関数ノードそれぞれについて処理する • 残す変数を根とする木を作る 𝑓𝐴 (𝑥1 ) • 例：𝑥 を残す場合 4 𝑓𝐷 (𝑥4 ) 𝑥1 𝑓𝐶 (𝑥1 , 𝑥2 , 𝑥3 ) こっち方向 に見る 𝑓𝐵 (𝑥1 , 𝑥4 ) 𝑥4 𝑥2 𝑓𝐸 (𝑥4 , 𝑥5 ) 𝑥5 𝑥3

15 Sum-Product（和積）アルゴリズム • 木の葉から順番に根に向かって計 算結果を送る （メッセージパッシング） 𝑓𝐸 (𝑥4 , 𝑥5 ) • 最終的に木の根にあたるノード （目的の変数のノード）で周辺化 した関数が得られる 𝑥5 𝑥4 𝑓𝐷 (𝑥4 ) 𝑓𝐵 (𝑥1 , 𝑥4 ) 𝑥1

16 Sum-Product（和積）アルゴリズム • 木の葉から根に向かって処理をする • 変数ノードの場合 𝑀𝑥𝑘→⋅ 𝑥𝑘 , … = 𝑀𝑓𝑘→𝑥𝑘 𝑥𝑘 𝑀𝑓𝑗→𝑥𝑘 (𝑥𝑘 , … ) 𝑥𝑘 𝑀𝑓𝑖→𝑥𝑘 (𝑥𝑘 , … ) 𝑀𝑓𝑗→𝑥𝑘 (𝑥𝑘 , … ) 𝑓𝑖 (𝑥𝑘 , … ) 𝑓𝑗 (𝑥𝑘 , … )

17 Sum-Product（和積）アルゴリズム • 木の葉から根に向かって処理をする • 関数ノードの場合 ෍ 𝑓𝑘 𝑥𝑖 , 𝑥𝑗 , … 𝑀𝑥𝑖→𝑓𝑘 𝑥𝑖 𝑀𝑥𝑗→𝑓𝑘 (𝑥𝑗 ) 𝑥𝑖 ,𝑥𝑗 ෍ 𝑓𝑘 (𝑥𝑖 , 𝑥𝑗 , . . . ) 𝑥𝑖 ,𝑥𝑗 𝑓𝑘 (𝑥𝑖 , 𝑥𝑗 , . . . ) 1 𝑓𝑘 (𝑥𝑖 , 𝑥𝑗 , . . . ) 1 葉の場合 𝑥𝑖 𝑥𝑗 𝑀𝑥𝑖→𝑓𝑘 (𝑥𝑖 ) 葉でない 場合 𝑥𝑖 𝑀𝑥𝑗→𝑓𝑘 (𝑥𝑗 ) 𝑥𝑗

18 適用例 ෍ 𝑥1 ,𝑥2 𝑥3 𝑥5 𝑓(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) 𝑥4 𝑓𝐷 (𝑥4 ) 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) 𝑥3 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥2 𝑓 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 = 𝑓𝐴 𝑥2 , 𝑥3 𝑓𝐵 𝑥1 , 𝑥4 × 𝑓𝐶 𝑥3 , 𝑥4 , 𝑥5 𝑓𝐷 (𝑥4 ) 𝑥5 𝑥1

19 適用例 𝑥4 𝑓𝐷 (𝑥4 ) 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) 𝑥3 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥5 𝑥1 𝑥2 1

20 適用例 𝑥4 𝑓𝐷 (𝑥4 ) 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) 𝑥3 𝑓𝐴 (𝑥2 , 𝑥3 ) ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥2 𝑥2 1 𝑥5 𝑥1

21 適用例 𝑥4 𝑓𝐷 (𝑥4 ) 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) 1 ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥3 𝑥2 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥2 1 𝑥5 ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 1 𝑥2 𝑥1

22 適用例 ෍ 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥3 ,𝑥5 𝑥4 𝑓𝐷 (𝑥4 ) 𝑥2 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) 1 ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥1 𝑥3 𝑥2 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥2 1 ෍ 𝑓𝐵 (𝑥1 , 𝑥4 ) 𝑥5 ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 1 𝑥2 𝑥1 𝑓𝐷 (𝑥4 )

23 適用例 𝑓𝐷 (𝑥4 ) ෍ 𝑓𝐵 (𝑥1 , 𝑥4 ) 𝑥1 ෍ 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥3 ,𝑥5 ෍ 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥3 ,𝑥5 𝑥4 𝑓𝐷 (𝑥4 ) 𝑥2 𝑓𝐶 (𝑥3 , 𝑥4 , 𝑥5 ) 1 ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥1 𝑥3 𝑥2 𝑓𝐴 (𝑥2 , 𝑥3 ) 𝑥2 1 ෍ 𝑓𝐵 (𝑥1 , 𝑥4 ) 𝑥5 ෍ 𝑓𝐴 (𝑥2 , 𝑥3 ) 1 𝑥2 𝑥1 𝑥2 𝑓𝐷 (𝑥4 )

24 適用例の計算量 • 各変数の取りうる値を𝑁種類とする ෍ 𝑂(𝑁 4 ) 𝑓(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) 𝑥1 ,𝑥2 𝑥3 𝑥5 𝑓𝐷 𝑥4 = 𝑓𝐷 𝑥4 ෍ 𝑓𝐵 𝑥1 , 𝑥4 ෍ 𝑓𝐶 𝑥3 , 𝑥4 , 𝑥5 ෍ 𝑓𝐴 𝑥2 , 𝑥3 𝑥1 𝑥3 ,𝑥5 𝑥2 ෍ 𝑓𝐵 𝑥1 , 𝑥4 ෍ ෍ 𝑓𝐴 𝑥2 , 𝑥3 ෍ 𝑓𝐶 𝑥3 , 𝑥4 , 𝑥5 𝑥1 𝑥3 𝑥5 𝑥2 𝑂 𝑁+𝑁 𝑁+𝑁 = 𝑂(𝑁 2 )

25 マルコフ連鎖 • あるシンボルの生成確率が直前のシンボルのみに依存する場合 • 単純マルコフ過程 • 𝑃 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = 𝑃 𝑥1 𝑃 𝑥2 𝑥1 𝑃 𝑥3 𝑥2 𝑃(𝑥4 |𝑥3 ) • 確率を関数（みたいなもの）とみなせば、sum-productアルゴリズム が使える 𝑥1 𝑥2 𝑥3 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) 𝑥4

26 マルコフ連鎖 • 例：𝑃 𝑥3 = 0 = σ𝑥1 ,𝑥2 ,𝑥4 𝑃(𝑥1 , 𝑥2 , 0, 𝑥4 ) • Sum-Productアルゴリズムを使って計算してみよう 𝑥1 𝑥2 𝑥3 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) 𝑥4

27 マルコフ連鎖 • 例：𝑃 𝑥3 = 0 = σ𝑥1,𝑥2,𝑥4 𝑃(𝑥1 , 𝑥2 , 0, 𝑥4 ) • Sum-Productアルゴリズムを使って計算してみよう ෍ 𝑃 𝑥2 𝑥1 𝑃(𝑥1 ) ෍ 𝑃 𝑥2 𝑥1 𝑃(𝑥1 ) 𝑥1 𝑥1 𝑥1 𝑥2 ෍ 𝑃 𝑥4 𝑥3 = 1 𝑥4 𝑥3 𝑥4 𝑃(𝑥1 ) 1 𝑃(𝑥1 ) 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) ෍ 𝑃(𝑥3 |𝑥2 ) ෍ 𝑃 𝑥2 𝑥1 𝑃(𝑥1 ) 𝑥2 𝑥1

28 関数を表であらわす • ファクターグラフの中の関数が離散確率である場合 • 𝑃(𝑥)とか𝑃(𝑥|𝑦)の𝑥, 𝑦は有限の組み合わせしかない • 典型的には0または1 • 𝑃 0 = 𝑝0 , 𝑃 1 = 𝑝1 の場合、𝑃(𝑥)を(𝑝0 , 𝑝1 )のようなベクトルで表せる • 𝑃(𝑥|𝑦)は(𝑝0|0 , 𝑝1|0 , 𝑝0|1 , 𝑝1|1 )のような感じ • 「関数のメッセージパッシング」は「表の値を加算乗算して新 たな表を作る」という形になる 𝑝0 • 𝑃 𝑥 = 𝑝 1 𝑃0|0 • 𝑃 𝑦𝑥 𝑃 𝑥 = 𝑝 1|0 𝑝0|1 𝑝1|1 𝑝0 𝑝0|0 + 𝑝1 𝑝0|1 𝑝0 𝑝1 = 𝑝0 𝑝1|0 + 𝑝1 𝑝1|1

29 もう一度マルコフ連鎖 • 初期確率を(𝑝01 , 𝑝11 )とする(𝑝01 + 𝑝11 = 1) • 連鎖確率を 𝑝0|0 , 𝑝1|0 , 𝑝0|1 , 𝑝1|1 とする 𝑥1 𝑥2 𝑥3 𝑝01 𝑝11 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) 𝑝01 𝑝11 𝑥4

30 もう一度マルコフ連鎖 (1) (1) (1) (1) • 初期確率を(𝑝0 , 𝑝1 )とする(𝑝0 + 𝑝1 = 1) • 連鎖確率を 𝑝0|0 , 𝑝1|0 , 𝑝0|1 , 𝑝1|1 とする (1) 𝑝0 (1) 𝑝1 𝑥1 𝑥2 (1) 𝑝0 (1) 𝑝1 𝑥3 𝑥4 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) (1) 𝑝0 (1) 𝑝1 (1) ෍ 𝑃 𝑥1 𝑃 𝑥2 𝑥1 = 𝑥1 (1) 𝑝0 𝑝0|0 + 𝑝1 𝑝0|1 (1) (1) 𝑝0 𝑝1|0 + 𝑝1 𝑝1|1 (2) = 𝑝0 (2) 𝑝1

31 もう一度マルコフ連鎖 • 初期確率を(𝑝01 , 𝑝11 )とする(𝑝01 + 𝑝11 = 1) • 連鎖確率を 𝑝0|0 , 𝑝1|0 , 𝑝0|1 , 𝑝1|1 とする 𝑥1 𝑥2 (2) 𝑥3 𝑝0 (2) 𝑝1 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) (2) 𝑝0 (2) 𝑝1 𝑥4

32 もう一度マルコフ連鎖 • 初期確率を(𝑝01 , 𝑝11 )とする(𝑝01 + 𝑝11 = 1) • 連鎖確率を 𝑝0|0 , 𝑝1|0 , 𝑝0|1 , 𝑝1|1 とする 𝑥1 𝑥2 (2) 𝑝0 (2) 𝑝1 𝑥3 𝑥4 𝑃(𝑥1 ) 𝑃(𝑥2 |𝑥1 ) 𝑃(𝑥3 |𝑥2 ) 𝑃(𝑥4 |𝑥3 ) (2) (2) ෍ 𝑃 𝑥3 𝑥2 𝑥2 𝑝0 (2) 𝑝1 = (2) 𝑝0 𝑝0|0 + 𝑝1 𝑝0|1 (2) (2) 𝑝0 𝑝1|0 + 𝑝1 𝑝1|1 (3) = 𝑝0 (3) 𝑝1

33 演習 • 関数𝑓 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = 𝑓1 𝑥1 , 𝑥2 𝑓2 𝑥1 , 𝑥3 𝑓3 (𝑥1 , 𝑥4 )のとき、次の 問いに答えよ。 1. 関数𝑓のファクターグラフを描け。 2. Sum-Productアルゴリズムを使い、𝑔2 𝑥2 = σ𝑥1 ,𝑥3 ,𝑥4 𝑓(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ) を𝑓1 , 𝑓2 , 𝑓3 で表せ。