確率的生成モデル

(1)

確率的生成モデル

伊達章

宮崎大学工学部情報システム工学科

2020

年

6

月

30

日

(2)

観測データ（時系列）

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

seed: 20070919 σ=0.7

もとの信号は

0

^か

1

^{．復元したい！}

(3)

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

seed: 20070919 σ=0.7

もとの信号は

0

^か

1

^{．復元したい！}

(4)

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y

seed: 20070919 σ=0.7

もとの信号は

0

か

1

．復元したい！

(5)

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

seed: 20070919 σ=0.2

こちらのほうが復元しやすい

(6)

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y

seed: 20070919 σ=0.2

こちらのほうが復元しやすい

(7)

もとの信号

x _true

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

seed: 20070919 σ=0.7

マルコフ的情報源

(8)

マルコフ的情報源

0.99 0.97 0.01

0.03 0 1

000000001111111111000000000

(9)

0.99 0.97 0.01

0.03 0 1

000000001111111111000000000

(10)

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

seed: 20070919 σ=0.7

(11)

多段決定問題

多変数関数

f (x)

^の最大化

J = f (x ₁ , x ₂ , · · · , x _n ) → max

n = 10, x

_i

∈ { 0, 1 }

の場合

x J

0 0000000000 f(x

₀

) 1 0000000001 f(x

1

) 2 0000000010 f(x

₂

)

.. .

k 0011101011 f(x

_k

) ←

最大

.. .

1023 1111111111 f(x

₂ⁿ₋₁

) max

i

f (x

_i

) = f(x

_k

), argmax

i

f(x

_i

) = k

(12)

多変数関数

f (x)

^の最大化

J = f (x ₁ , x ₂ , · · · , x _n ) → max

n = 10, x

_i

∈ { 0, 1 }

の場合

x J

0 0000000000 f(x

₀

) 1 0000000001 f(x

1

) 2 0000000010 f(x

₂

)

.. .

k 0011101011 f(x

_k

) ←

最大

.. .

1023 1111111111 f(x

₂ⁿ₋₁

) max

i

f (x

_i

) = f(x

_k

), argmax

i

f (x

_i

) = k

(13)

多変数関数

f (x)

^の最大化

J = f (x ₁ , x ₂ , · · · , x _n ) → max

n = 100, x

_i

∈ { 0, 1 }

の場合．

2

¹⁰⁰

= (2

¹⁰

)

¹⁰

≈ (10

³

)

¹⁰

= 10

³⁰

x J

0 0000000000 f (x

₀

) 1 0000000001 f (x

₁

) 2 0000000010 f (x

₂

) 3 0000000011 f (x

₃

)

.. .

k 0011101011 f (x

_k

) ←

最大

.. .

≈ 10

³⁰

111 · · · 111 f(x

2ⁿ−1

)

(14)

課題

•

^例題：

n = 200, y = (y ₁ , · · · , y _n )

•

^目的：

x ^∗ = argmax

x

f (x), x _i ∈ { 0, 1 }

^の計算

•

まもとには計算できない．

•

動的計画法を使い，この問題を解決する．

•

仕組み理解し，コードを書き，問題を解く．

(15)

事後確率最大にする値

x _MAP

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y x

MAP

seed: 20070919 P (x_MAP| y ) = 0.03118

P (x_true| y ) = 0.00213 σ=0.7

(16)

多変数関数の最大化

J = p(x | y) → max

n = 200, x

_i

∈ { 0, 1 }

の場合．

2

²⁰⁰

= (2

¹⁰

)

²⁰

≈ (10

³

)

²⁰

= 10

⁶⁰

x J

0 0000000000 f (x

₀

) 1 0000000001 f (x

₁

) 2 0000000010 f (x

₂

) 3 0000000011 f (x

₃

)

.. .

k 0011101011 f (x

_k

) ←

最大

.. .

≈ 10

⁶⁰

111 · · · 111 f(x

2ⁿ−1

)

(17)

基本知識（確率・統計の復習）

•

^平均

µ

，分散

σ ²

，標準偏差

σ

•

確率分布：一様分布，正規分布

•

^{擬似乱数の生成}

•

^最尤推定

•

同時確率，条件付き確率

•

^{マルコフ的情報源}

•

ベイズの公式，事前確率・事後確率

•

^{事後確率最大化}

•

^{動的計画法}

(18)

確率，条件付き確率

B

₁ （風邪）

B

₂ （風邪なし）

p(A

_i

) A

₁ （熱あり）

0.55 0.05 0.60 A

₂ （熱なし）

0.10 0.30 0.40

p(B

_j

) 0.65 0.35

例

同時確率

p(A

₁

, B

₁

) = 0.55

周辺確率

p(A

₁

) = ∑

i

p(A

₁

, B

_i

) = p(A

₁

) = 0.6

条件付き確率

熱の有無を知る ⇒ 風邪であるかどうか検討がつく：

p(B

₁

| A

₁

) = p(B

₁

)p(A

₁

| B

₁

)

p(A

₁

) = p(A

₁

, B

₁

)

p(A

₁

) = 0.55

0.6 ≈ 0.92

(19)

ベイズの公式

•

ベイズの公式

熱があったとしよう．その時，風邪のあるなしの確率

p(B

₁

| A

₁

) = p(B

₁

)p(A

₁

| B

₁

)

p(A

1

) = p(A

₁

, B

₁

)

p(A

1

) = 0.55

0.6 ≈ 0.92 p(B

₂

| A

₁

) = p(B

₂

)p(A

₁

| B

₂

)

p(A

₁

) = p(A

₁

, B

₂

)

p(A

₁

) = 0.05

0.6 ≈ 0.08

•

事後確率最大化（ベイズ推定）

argmax

i

p(B

_i

| A

₁

) = 1

風邪であることの方が確率が大 ⇒ 風邪であると推定入力（観測値）：熱のあるなし

⇒ 出力（推定値）風邪かどうか

(20)

0.99 0.97 0.01

0.03 0 1

000000001111111111000000000

p(x) = 0.5 × 0.99 × 0.99 × 0.99 × 0.99 · · ·

p(x) = p(x 1 ) × p(x 2 | x 1 ) × p(x 3 | x 2 ) × p(x 4 | x 3 ) · · ·

(21)

0.99 0.97 0.01

0.03 0 1

000000001111111111000000000

p(x) = 0.5 × 0.99 × 0.99 × 0.99 × 0.99 · · ·

p(x) = p(x ₁ ) × p(x ₂ | x ₁ ) × p(x ₃ | x ₂ ) × p(x ₄ | x ₃ ) · · ·

(22)

x _MAP

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y x

MAP

seed: 20070919 P (x_MAP| y ) = 0.03118

P (x_true| y ) = 0.00213 σ=0.7

(23)

使って良い知識

データ（観測値）：

y = (y

1

, · · · , y

n

)

モデル：

p(x), p(y | x)

p(x

₁

) =

{ 0.5 if x

₁

= 0 0.5 if x

₁

= 1

p(x

_i+1

| x

_i

) =

 

 

 



0.99 if x

i

= 0, x

i+1

= 0 0.01 if x

_i

= 0, x

_i+1

= 1 0.97 if x

_i

= 1, x

_i+1

= 1 0.03 if x

_i

= 1, x

_i+1

= 0

p(y

_i

| x

_i

) = 1

√ 2πσ exp {

− (y

_i

− x

_i

)

²

2σ

²

}

以降，この課題では，特に指定しない限り

σ = 0.7

．

(24)

事後確率最大化

x ^∗ = argmax

x

p(x | y)

は知らない．

p(x), p(y | x)

は与えられている．

p(x | y) = p(x, y)

p(y)

^{（ベイズの公式）}

= p(x)p(y | x) p(y)

y

は観測値 ⇒

p(y) > 0

は定数

x ^∗ = argmax

x

p(x)p(y | x)

(25)

x ^∗ = argmax

x

p(x | y)

は知らない．

p(x), p(y | x)

は与えられている．

p(x | y) = p(x, y)

p(y)

^{（ベイズの公式）}

= p(x)p(y | x) p(y)

y

は観測値 ⇒

p(y) > 0

は定数

x ^∗ = argmax

x

p(x)p(y | x)

(26)

事後確率

p(x | y )

^の最大化

x

₁

x

₂

x

₃

x

_n-1

x

_n

y

₁

y

₂

y

₃

y

_n-1

y

_n

x

^∗

= argmax

x1,x2,···,xn

p(x

₁

, x

₂

, · · · , x

_n

, y

₁

, y

₂

, · · · , y

_n

)

x

^∗

= argmax

x1,x2,···,xn

p(x

₁

)

∏

n i=2

p(x

_i

| x

_i₋₁

)

∏

n i=1

p(y

_i

| x

_i

)

(27)

x _MAP

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y x

MAP

seed: 20070919 P (x_MAP| y ) = 0.03118

P (x_true| y ) = 0.00213 σ=0.7

(28)

事後確率

p(x | y )

^の最大化

x

₁

x

₂

x

₃

x

_n-1

x

_n

y

₁

y

₂

y

₃

y

_n-1

y

_n

x

^∗

= argmax

x1,x2,···,xn

p(x

₁

, x

₂

, · · · , x

_n

, y

₁

, y

₂

, · · · , y

_n

)

x

^∗

= argmax

x1,x2,···,xn

p(x

₁

)

∏

n i=2

p(x

_i

| x

_i₋₁

)

∏

n i=1

p(y

_i

| x

_i

)

(29)

演習問題

（プリント）

(30)

本日の課題

2020年6月30日最適化理論

学籍番号：671 0 0

名前：得点：

小テスト【マルコフ的情報源，ベイズの公式，事後確率最大化】

データy= (y1, y2, y3)が変数x= (x1, x2, x3)をもとに生成されている．yを観測し，最ももっともらしいxを推定する問題を考えよう．ここでx,yの要素は0,1の値をとり，確率分布p(x), p(y|x)が具体的に以下のとおり与えられている． ※以下，答だけでなく導出過程を記述せよ．以下には手計算が難しい問題が含まれている．

その場合は，計算できるところは計算し，計算できないところは，【（○通りの和）】などと記述せよ．

p(x1) = Prob(X1=x1)= (1

2if x1= 0 1 2if x1= 1

p(xi+1|xi)=









 9 10if xi= 0, xi+1= 0 1 10if xi= 0, xi+1= 1 7 10if xi= 1, xi+1= 1 3 10if xi= 1, xi+1= 0 p(yi|xi)=

(4 5if xi=yi 1 5if xi̸=yi

X3 X1 X2

Y3 Y1 Y2 確率変数の依存性を描いたグラフ

1.x= (0,0,0)とする．確率p(x)を求めよ． p(x) = 2.x= (0,1,0)とする．確率p(x)を求めよ． p(x) = 3.x= (0,0,0),y= (0,1,0)であった．同時確率p(x,y)を求めよ．

p(x,y) =

4.x= (0,1,0),y= (0,1,0)であった．同時確率p(x,y)を求めよ．

p(x,y) =

5.y= (0,1,0)であった．x0= (0,0,0)の場合の事後確率p(x0|y)を求めよ．

p(x0|y) =

6.y= (0,1,0)であった．x₂= (0,1,0)の場合の事後確率p(x₂|y)を求めよ．

p(x2|y) = 7.f(x) =−(x−1)²+ 3とする

(a) max_xf(x) =f(x^∗) = (b)x^∗= argmax

x f(x) =

8.事後確率p(x|y)をp(x), p(y|x)を用い表現せよ．必要であればP

˜

xp( ˜x)などの記号を用いよ．

p(x|y) =

9.y= (0,1,0)であった．事後確率を最大にするxを求めよ（それをx∗=xMAPと書く）．

xMAP= argmax

x p(x|y) =

•

プリント（小テスト）

1 ダウンロード

2 印刷

3 手で解く（手書き）

4 スキャン（撮影）

5

pdf

化

6

WebClass

で提出

（締切：6/30火

18:00）

•

使用できそうなツール

•

スマートフォン

検索：「数学者でもわかるスマホスキャナの使い方」

•

セブン

-

イレブン

https://www.sej.co.jp/services/multicopy.html

(31)

事後確率

p(x | y )

^の最大化

x

_i

, y

_i

= 0, 1

の場合を考える．

X

₃

X

₁

X

₂

Y

₃

Y

₁

Y

₂

(32)

使って良い知識

データ（観測値）：

y = (y

1

, y

2

, y

3

)

X

3

X

1

X

2

Y

3

Y

1

Y

2

モデル：

p(x), p(y | x) p(x

₁

) =

{

₁

2

if x

₁

= 0

1

2

if x

₁

= 1

p(x

_i+1

| x

_i

) =

 

 



 

 

9

10

if x

i

= 0, x

i+1

= 0

1

10

if x

i

= 0, x

i+1

= 1

7

10

if x

_i

= 1, x

_i+1

= 1

3

10

if x

_i

= 1, x

_i+1

= 0 p(y

i

| x

i

) =

{

₄

5

if x

i

= y

i 1

5

if x

i

̸ = y

i

x

^∗

= argmax

x1,x2,x3

p(x

1

, x

2

, x

3

, y

1

, y

2

, y

3

)

= argmax

x₁,x₂,x₃

p(x

₁

)p(x

₂

| x

₁

)p(x

₃

| x

₂

)p(y

₁

| x

₁

)p(y

₂

| x

₂

)p(y

₃

| x

₃

)

(33)

同時確率，事後確率

p(x₁) = { 1

2 if x₁= 0 1

2 if x₁= 1

p(x_i+1|x_i) =









 9

10 if x_i= 0, x_i+1= 0 1

10 if x_i= 0, x_i+1= 1 7

10 if x_i= 1, x_i+1= 1 3

10 if x_i= 1, x_i+1= 0 p(y_i|x_i) =

{ 4

5 if x_i=y_i 1

5 if x_i̸=y_i x^∗ = argmax

x1,x2,x3

p(x₁)p(x₂|x₁)p(x₃|x₂)p(y₁|x₁)p(y₂|x₂)p(y₃|x₃) X3

X1 X2

Y3

Y1 Y2

3. x = (0, 0, 0), y = (0, 1, 0)

であった．同時確率

p(x, y)

を求めよ．

p(x, y) =

₂₀₀⁸¹ ⁴₅¹₅⁴₅

=

⁸¹₅₀¹₅¹₅⁴₅

=

⁸¹₂₅¹₅¹₅²₅

=

¹⁶²₅5

=

₃₁₂₅¹⁶²

≈ 0.0518 5. y = (0, 1, 0)

であった．x₀

= (0, 0, 0)

の場合の事後確率

p(x

0

| y)

を求めよ．

p(x

0

| y) = p(x

0

, y)

p(y) = p(x

0

, y)

∑

x

p(x, y) = p(x

0

, y)

∑

x1

∑

x2

∑

x3

p(x

1

, x

2

, x

3

, y)

= p(x

₀

, y)

p(000010) + p(001010) + p(011010) + p(100010) + · · ·

= 162

3125 /(2

³

= 8

通りの和)

(34)

p(x₁) = { 1

2 if x₁= 0 1

2 if x₁= 1

p(x_i+1|x_i) =









 9

10 if x_i= 0, x_i+1= 0 1

10 if x_i= 0, x_i+1= 1 7

10 if x_i= 1, x_i+1= 1 3

10 if x_i= 1, x_i+1= 0 p(y_i|x_i) =

{ 4

5 if x_i=y_i 1

x1,x2,x3

X1 X2

Y3

Y1 Y2

3. x = (0, 0, 0), y = (0, 1, 0)

p(x, y)

を求めよ．

p(x, y) =

₂₀₀⁸¹ ⁴₅¹₅⁴₅

=

⁸¹₅₀¹₅¹₅⁴₅

=

⁸¹₂₅¹₅¹₅²₅

=

¹⁶²₅5

=

₃₁₂₅¹⁶²

≈ 0.0518

5. y = (0, 1, 0)

であった．x₀

= (0, 0, 0)

p(x

0

| y)

を求めよ．

p(x

0

| y) = p(x

0

, y)

p(y) = p(x

0

, y)

∑

x

p(x, y) = p(x

0

, y)

∑

x1

∑

x2

∑

x3

p(x

1

, x

2

, x

3

, y)

= p(x

₀

, y)

p(000010) + p(001010) + p(011010) + p(100010) + · · ·

= 162

3125 /(2

³

= 8

通りの和)

(35)

p(x₁) = { 1

2 if x₁= 0 1

2 if x₁= 1

p(x_i+1|x_i) =









 9

10 if x_i= 0, x_i+1= 0 1

10 if x_i= 0, x_i+1= 1 7

10 if x_i= 1, x_i+1= 1 3

10 if x_i= 1, x_i+1= 0 p(y_i|x_i) =

{ 4

5 if x_i=y_i 1

x1,x2,x3

X1 X2

Y3

Y1 Y2

3. x = (0, 0, 0), y = (0, 1, 0)

p(x, y)

を求めよ．

p(x, y) =

₂₀₀⁸¹ ⁴₅¹₅⁴₅

=

⁸¹₅₀¹₅¹₅⁴₅

=

⁸¹₂₅¹₅¹₅²₅

=

¹⁶²₅5

=

₃₁₂₅¹⁶²

≈ 0.0518 5. y = (0, 1, 0)

であった．x₀

= (0, 0, 0)

p(x

0

| y)

を求めよ．

p(x

0

| y) = p(x

0

, y)

p(y) = p(x

0

, y)

∑

x

p(x, y) = p(x

0

, y)

∑

x1

∑

x2

∑

x3

p(x

1

, x

2

, x

3

, y)

= p(x

₀

, y)

p(000010) + p(001010) + p(011010) + p(100010) + · · ·

= 162

3125 /(2

³

= 8

通りの和)

(36)

p(x₁) = { 1

2 if x₁= 0 1

2 if x₁= 1

p(x_i+1|x_i) =









 9

10 if x_i= 0, x_i+1= 0 1

10 if x_i= 0, x_i+1= 1 7

10 if x_i= 1, x_i+1= 1 3

10 if x_i= 1, x_i+1= 0 p(y_i|x_i) =

{ 4

5 if x_i=y_i 1

x1,x2,x3

X1 X2

Y3

Y1 Y2

3. x = (0, 0, 0), y = (0, 1, 0)

p(x, y)

を求めよ．

p(x, y) =

₂₀₀⁸¹ ⁴₅¹₅⁴₅

=

⁸¹₅₀¹₅¹₅⁴₅

=

⁸¹₂₅¹₅¹₅²₅

=

¹⁶²₅5

=

₃₁₂₅¹⁶²

≈ 0.0518 5. y = (0, 1, 0)

であった．x₀

= (0, 0, 0)

p(x

0

| y)

を求めよ．

p(x

0

| y) = p(x

0

, y)

p(y) = p(x

0

, y)

∑

x

p(x, y) = p(x

0

, y)

∑

x1

∑

x2

∑

x3

p(x

1

, x

2

, x

3

, y)

= p(x

₀

, y)

p(000010) + p(001010) + p(011010) + p(100010) + · · ·

= 162

3125 /(2

³

= 8

通りの和)

(37)

演習問題おわり

(38)

x3

x1 x2 xn-1 xn

y3

y1 y2 yn-1 yn

x

^∗

= argmax

x

p(x)p(y | x)

= argmax

x

p(x

1

)

∏

n i=2

p(x

i

| x

i−1

)

∏

n i=1

p(y

i

| x

i

)

= argmax

x

log p(x

1

) +

∑

n i=2

log p(x

i

| x

i−1

) +

∑

n i=1

log p(y

i

| x

i

)

(39)

x₃

x₁ x₂ x_n-1 x_n

y3

y1 y2 yn-1 yn

J = log p(x

1

) +

∑

n i=2

log p(x

i

| x

i−1

) +

∑

n i=1

log p(y

i

| x

i

)

= log p(x

1

) + log p(y

1

| x

1

) +

n−1

∑

i=1

{

log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

) }

y

iは定数

= f

1

(x

1

) + h

1

(x

1

, x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

• f

₁

(x

₁

) = log p(x

₁

) + log p(y

₁

| x

₁

)

• h

_i

(x

_i

, x

_i+1

) = log p(x

_i+1

| x

_i

) + log p(y

_i+1

| x

_i+1

)

(40)

x₃

x₁ x₂ x_n-1 x_n

y3

y1 y2 yn-1 yn

J = log p(x

1

) +

∑

n i=2

log p(x

i

| x

i−1

) +

∑

n i=1

log p(y

i

| x

i

)

= log p(x

1

) + log p(y

1

| x

1

) +

n−1

∑

i=1

{

log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

) }

y

iは定数

= f

1

(x

1

) + h

1

(x

1

, x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

• f

₁

(x

₁

) = log p(x

₁

) + log p(y

₁

| x

₁

)

• h

_i

(x

_i

, x

_i+1

) = log p(x

_i+1

| x

_i

) + log p(y

_i+1

| x

_i+1

)

(41)

基本知識（確率・統計の復習）

•

^平均

µ

，分散

σ ²

，標準偏差

σ

•

確率分布：一様分布，正規分布

•

^{擬似乱数の生成}

•

^最尤推定

•

同時確率，条件付き確率

•

^{マルコフ的情報源}

•

ベイズの公式，事前確率・事後確率

•

^{事後確率最大化}

•

^{動的計画法}

(42)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = log p(x

1

) + log p(y

1

| x

1

) +

n−1

∑

i=1

{

log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

) }

= f

1

(x

1

) + h

1

(x

1

, x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

• x

₁ に着目 ⇒

f

₁

(x

₁

), h

₁

(x

₁

, x

₂

)

にしか関係しない

• f

₁

(x

₁

) + h

₁

(x

₁

, x

₂

)

を最大にするよう

x

₁ を選ぶ

•

↑

x

₂の値がわかっていないければ選べない

•

そこで，x₂の可能なすべての値（0,

1）に対して，以下を計算

• f

2

(x

2

) = max

x₁

{ f

1

(x

1

) + h

1

(x

1

, x

2

) } ˆ

x

1

(x

2

) = argmax

x1

{ f

1

(x

1

) + h

1

(x

1

, x

2

) }

J = f

₂

(x

₂

) + h

₂

(x

₂

, x

₃

) + · · · + h

_n₋₁

(x

_n₋₁

, x

_n

)

(43)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = log p(x

1

) + log p(y

1

| x

1

) +

n−1

∑

i=1

{

log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

) }

= f

1

(x

1

) + h

1

(x

1

, x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

• x

₁ に着目 ⇒

f

₁

(x

₁

), h

₁

(x

₁

, x

₂

)

• f

₁

(x

₁

) + h

₁

(x

₁

, x

₂

)

x

₁ を選ぶ

•

↑

x

• 1）に対して，以下を計算

• f

2

(x

2

) = max

x₁

{ f

1

(x

1

) + h

1

(x

1

, x

2

) } ˆ

x

1

(x

2

) = argmax

x1

{ f

1

(x

1

) + h

1

(x

1

, x

2

) }

J = f

₂

(x

₂

) + h

₂

(x

₂

, x

₃

) + · · · + h

_n₋₁

(x

_n₋₁

, x

_n

)

(44)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = log p(x

1

) + log p(y

1

| x

1

) +

n−1

∑

i=1

{

log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

) }

= f

1

(x

1

) + h

1

(x

1

, x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

• x

₁ に着目 ⇒

f

₁

(x

₁

), h

₁

(x

₁

, x

₂

)

• f

₁

(x

₁

) + h

₁

(x

₁

, x

₂

)

x

₁ を選ぶ

•

↑

x

• 1）に対して，以下を計算

• f

2

(x

2

) = max

x₁

{ f

1

(x

1

) + h

1

(x

1

, x

2

) } ˆ

x

1

(x

2

) = argmax

x1

{ f

1

(x

1

) + h

1

(x

1

, x

2

) }

J = f

₂

(x

₂

) + h

₂

(x

₂

, x

₃

) + · · · + h

_n₋₁

(x

_n₋₁

, x

_n

)

(45)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = log p(x

1

) + log p(y

1

| x

1

) +

n−1

∑

i=1

{

log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

) }

= f

1

(x

1

) + h

1

(x

1

, x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

• x

₁ に着目 ⇒

f

₁

(x

₁

), h

₁

(x

₁

, x

₂

)

• f

₁

(x

₁

) + h

₁

(x

₁

, x

₂

)

x

₁ を選ぶ

•

↑

x

• 1）に対して，以下を計算

• f

2

(x

2

) = max

x₁

{ f

1

(x

1

) + h

1

(x

1

, x

2

) } ˆ

x

1

(x

2

) = argmax

x1

{ f

1

(x

1

) + h

1

(x

1

, x

2

) }

J = f

₂

(x

₂

) + h

₂

(x

₂

, x

₃

) + · · · + h

_n₋₁

(x

_n₋₁

, x

_n

)

(46)

動的計画法

x3

x1 x2 xn-1 xn

y₃

y₁ y₂ y_n-1 y_n

J = f

2

(x

2

) + h

2

(x

2

, x

3

) + · · · + h

n−1

(x

n−1

, x

n

)

•

変数の数が

1

つ減った．これを続けていけばよい．

• x

2 に着目 ⇒

f

2

(x

2

), h

2

(x

2

, x

3

)

• f

2

(x

2

) + h

2

(x

2

, x

3

)

x

2 を選ぶ

•

↑

x

₃の値がわかっていないければ選べない

•

そこで，x₃の可能なすべての値（0,

1）に対して，以下を計算

• f

3

(x

3

) = max

x2

{ f

2

(x

2

) + h

2

(x

2

, x

3

) } ˆ

x

2

(x

3

) = argmax

x2

{ f

2

(x

2

) + h

2

(x

2

, x

3

) }

(47)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = f

_n₋₁

(x

_n₋₁

) + h

_n₋₁

(x

_n₋₁

, x

_n

)

• x

nの可能なすべての値（0,

1）に対して，以下を計算

• f

n

(x

n

) = max

x_n−1

{ f

n−1

(x

n−1

) + h

n−1

(x

n−1

, x

n

) } ˆ

x

_n₋₁

(x

_n

) = argmax

x_n−1

{ f

_n₋₁

(x

_n₋₁

) + h

_n₋₁

(x

_n₋₁

, x

_n

) }

• x

^∗_n

= argmax

x_n

f

_n

(x

_n

)

(48)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

• x

^∗_n

= argmax

x_n

f

n

(x

n

)

• x

^∗_n₋₁

= ˆ x

_n₋₁

(x

^∗_n

)

• x

^∗_n₋₂

= ˆ x

_n₋₂

(x

^∗_n₋₁

)

• · · · → x

^∗₁

= ˆ x

₁

(x

^∗₂

)

(49)

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

• x

^∗_n

= argmax

x_n

f

n

(x

n

)

• x

^∗_n₋₁

= ˆ x

n−1

(x

^∗_n

)

• x

^∗_n₋₂

= ˆ x

_n₋₂

(x

^∗_n₋₁

)

• · · · → x

^∗₁

= ˆ x

₁

(x

^∗₂

)

確率的生成モデル

2020

6

30

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

0

1

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

0

1

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

, y

0

1

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

, y

x true

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

0.99

0.97 0.01

0.03

0 1

000000001111111111000000000

0.99

0.97 0.01

0.03

0 1

000000001111111111000000000

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

f (x)

J = f (x 1 , x 2 , · · · , x n ) → max

n = 10, x

∈ { 0, 1 }

x J

0 0000000000 f(x

) 1 0000000001 f(x

) 2 0000000010 f(x

)

.. .

k 0011101011 f(x

) ←

.. .

1023 1111111111 f(x

) max

f (x

) = f(x

), argmax

f(x

) = k

f (x)

J = f (x 1 , x 2 , · · · , x n ) → max

n = 10, x

∈ { 0, 1 }

x J

0 0000000000 f(x

) 1 0000000001 f(x

) 2 0000000010 f(x

)

.. .

k 0011101011 f(x

) ←

x _true

J = f (x ₁ , x ₂ , · · · , x _n ) → max

J = f (x ₁ , x ₂ , · · · , x _n ) → max

J = f (x ₁ , x ₂ , · · · , x _n ) → max

n = 200, y = (y ₁ , · · · , y _n )

x ^∗ = argmax

f (x), x _i ∈ { 0, 1 }

x _MAP

σ ²