---
title: 通信符号理論 12
tags: 
author: [Akinori Ito](https://docswell.com/user/akinori-ito)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/DJY4RP547M.jpg?width=480
description: シンボルMAP復号 ファクターグラフ
published: July 02, 26
canonical: https://docswell.com/s/akinori-ito/KL33Y3-2026-07-02-162015
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/DJY4RP547M.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/V7NYD5N6E8.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/YJ9PGYRR73.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/GJ8DV6WGJD.jpg)

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 )


# Page. 5

![Page Image](https://bcdn.docswell.com/page/LJLM59NXER.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/47MY3ZX37W.jpg)

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 の種類）へ


# Page. 7

![Page Image](https://bcdn.docswell.com/page/P7R9Q6NRE9.jpg)

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 ⋯ 𝑓𝑛 (𝐴𝑛 )と分解できる場合を考える


# Page. 8

![Page Image](https://bcdn.docswell.com/page/PJXQ5MNY7X.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/3JK96GN4JD.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LE3W6NVDE5.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/8EDKVW827G.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/V7PKV98LJ8.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/2JVVZMN6JQ.jpg)

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
こういう関数の周辺化は
どうすればいいのか？


# Page. 14

![Page Image](https://bcdn.docswell.com/page/5EGL4GK2JL.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/4JQYGXN97P.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/K74W563RE1.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/LJ1YWV1VEG.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/GJWG6L8372.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/4EZLYM8G73.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/Y76WDNPQ7V.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/G75M35K274.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/9J29ZNW1ER.jpg)

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 )


# Page. 23

![Page Image](https://bcdn.docswell.com/page/DEY4RPL4JM.jpg)

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 )


# Page. 24

![Page Image](https://bcdn.docswell.com/page/VJNYD54678.jpg)

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 )


# Page. 25

![Page Image](https://bcdn.docswell.com/page/YE9PGYQRJ3.jpg)

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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/GE8DV6GGED.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/LELM59GX7R.jpg)

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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/4JMY3ZQ3JW.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/PJR9Q68R79.jpg)

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


# Page. 30

![Page Image](https://bcdn.docswell.com/page/PEXQ5M8YJX.jpg)

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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/3EK96GK4ED.jpg)

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


# Page. 32

![Page Image](https://bcdn.docswell.com/page/L73W6NZD75.jpg)

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


# Page. 33

![Page Image](https://bcdn.docswell.com/page/87DKVWR2JG.jpg)

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 で表せ。