確率的生成モデル

(1)

確率的生成モデル

伊達章

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

2020

^年

7

^月

7

^{日（}

11/15

^）

(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)

もとの信号

x _true

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

seed: 20070919 σ=0.7

マルコフ的情報源

(6)

マルコフ的情報源

0.99 0.97 0.01

0.03 0 1

000000001111111111000000000

(7)

0.99 0.97 0.01

0.03 0 1

000000001111111111000000000

(8)

観測データ

y

^{（時系列）}

-2 -1 0 1 2 3 4

0 50 100 150 200

t

y

seed: 20070919 σ=0.7

(9)

多段決定問題

多変数関数

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

(10)

多変数関数

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

(11)

多変数関数

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

)

(12)

課題

•

^例題：

n = 200, y = (y 1 , · · · , y n )

•

^目的：

x ^∗ = argmax

x

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

^の計算

•

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

•

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

•

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

(13)

事後確率最大にする値

x _MAP

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y x

MAP

seed: 20070919 P (xMAP| y ) = 0.03118

P (x_true| y ) = 0.00213 σ=0.7

(14)

多変数関数の最大化

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

)

(15)

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

•

^平均

µ

，分散

σ ²

，標準偏差

σ

•

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

•

^{擬似乱数の生成}

•

^最尤推定

•

同時確率，条件付き確率

•

^{マルコフ的情報源}

•

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

•

^{事後確率最大化}

•

^{動的計画法}

(16)

確率，条件付き確率

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

(17)

ベイズの公式

•

ベイズの公式

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

p(B

₁

| A

₁

) = p(B

₁

)p(A

₁

| B

₁

)

p(A

₁

) = p(A

₁

, B

₁

)

p(A

₁

) = 0.55

0.6 ≈ 0.92

p(B

₂

| A

₁

) = p(B

₂

)p(A

₁

| B

₂

)

p(A

1

) = p(A

₁

, B

₂

)

p(A

1

) = 0.05

0.6 ≈ 0.08

•

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

argmax

i

p(B

_i

| A

₁

) = 1

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

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

(18)

ここから

(19)

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 ₃ ) · · ·

(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 ₁ ) × p(x ₂ | x ₁ ) × p(x ₃ | x ₂ ) × p(x ₄ | x ₃ ) · · ·

(21)

x _MAP

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y x

MAP

seed: 20070919 P (xMAP| y ) = 0.03118

P (x_true| y ) = 0.00213 σ=0.7

(22)

使って良い知識

データ（観測値）：

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

．

(23)

事後確率最大化

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)

(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)

事後確率

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

)

(26)

x _MAP

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y x

MAP

seed: 20070919 P (xMAP| y ) = 0.03118

P (x_true| y ) = 0.00213 σ=0.7

(27)

事後確率

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

)

この絵と式だけで解ける仕組みが理解できる！

(28)

これ以降，しばらくは補足．

式を使って説明すればこうなる というだけの話．

(29)

x

₁

x

₂

x

₃

x

_n-1

x

_n

y

₁

y

₂

y

₃

y

_n-1

y

_n

x

^∗

= argmax

x

p(x)p(y | x)

= argmax

x

p(x

₁

)

∏

n i=2

p(x

_i

| x

_i₋₁

)

∏

n i=1

p(y

_i

| x

_i

)

= argmax

x

log p(x

₁

) +

∑

n i=2

log p(x

_i

| x

_i₋₁

) +

∑

n i=1

log p(y

_i

| x

_i

)

(30)

x

₁

x

₂

x

₃

x

_n-1

x

_n

y

₁

y

₂

y

₃

y

_n-1

y

_n

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

1

(x

1

) = log p(x

1

) + log p(y

1

| x

1

)

• h

i

(x

i

, x

i+1

) = log p(x

i+1

| x

i

) + log p(y

i+1

| x

i+1

)

(31)

x

₁

x

₂

x

₃

x

_n-1

x

_n

y

₁

y

₂

y

₃

y

_n-1

y

_n

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 (x , x ) = log p(x | x ) + log p(y | x )

(32)

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

•

^平均

µ

^，分散

σ ²

^{，標準偏差}

σ

•

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

•

^{擬似乱数の生成}

•

^最尤推定

•

同時確率，条件付き確率

•

^{マルコフ的情報源}

•

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

•

^{事後確率最大化}

•

^{動的計画法}

(33)

動的計画法

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

)

(34)

動的計画法

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

)

(35)

動的計画法

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

)

(36)

動的計画法

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

₋

(x

₋

, x )

(37)

動的計画法

x₁ x₂ x₃ x_n-1 x_n

y1 y₂ y₃ y_n-1 y_n

J = f

₂

(x

₂

) + h

₂

(x

₂

, x

₃

) + · · · + h

_n₋₁

(x

_n₋₁

, x

_n

)

•

変数の数が

1

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

• x

2 に着目 ⇒

f

2

(x

2

), h

2

(x

2

, x

3

)

• f

₂

(x

₂

) + h

₂

(x

₂

, x

₃

)

x

₂ を選ぶ

•

↑

x

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

•

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

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

• f

3

(x

3

) = max

x₂

{ 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

) }

(38)

動的計画法

x₁ x₂ x₃ x_n-1 x_n

y₁ y₂ y₃ y_n-1 y_n

J = f

n−1

(x

n−1

) + h

n−1

(x

n−1

, 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−1

(x

n

) = argmax

x_n−1

{ f

n−1

(x

n−1

) + h

n−1

(x

n−1

, x

n

) }

• x

^∗_n

= argmax

xn

f

n

(x

n

)

(39)

動的計画法

x₁ x₂ x₃ x_n-1 x_n

y₁ y₂ y₃ y_n-1 y_n

• x

^∗_n

= argmax

xn

f

n

(x

n

)

• x

^∗_n₋₁

= ˆ x

n−1

(x

^∗_n

)

• x

^∗_n₋₂

= ˆ x

n−2

(x

^∗_n₋₁

)

• · · · → x

^∗₁

= ˆ x

1

(x

^∗₂

)

(40)

動的計画法

x₁ x₂ x₃ x_n-1 x_n

y₁ y₂ y₃ y_n-1 y_n

• x

^∗_n

= argmax

xn

f

n

(x

n

)

• x

^∗_n₋₁

= ˆ x

n−1

(x

^∗_n

)

• x

^∗_n₋₂

= ˆ x

n−2

(x

^∗_n₋₁

)

• · · · → x

^∗₁

= ˆ x

1

(x

^∗₂

)

(41)

動的計画法

x₁ x₂ x₃ x_n-1 x_n

y₁ y₂ y₃ y_n-1 y_n

• x

^∗_n

= argmax

xn

f

n

(x

n

)

• x

^∗_n₋₁

= ˆ x

n−1

(x

^∗_n

)

• x

^∗_n₋₂

= ˆ x

n−2

(x

^∗_n₋₁

)

• · · · → x

^∗₁

= ˆ x

1

(x

^∗₂

)

(42)

口頭試問について

(43)

口頭試問について

x

₁

x

₂

x

₃

x

_n-1

x

_n

y

₁

y

₂

y

₃

y

_n-1

y

_n

•

上記の絵を使い，「問題設定 ↓」から説明をはじめる．

•

線を結ぶ両端の○に値が入ると，棒に値が付く

•

それを全部掛け算した値を最大にしたい

•

下の○の値は与えられている．

•

上の○には

0,1

が入る．全部で

2

²⁰⁰通り

•

どうする？

→

（以降，自分の言葉で説明）

•

解ける仕組みを「本当に分かった！」ことをアピールせよ．

•

怪しい点があれば，途中で何度も止めて，質問します．

•

最速

3

分以内に終了

(44)

コードを書く際に

「データ構造」と「アルゴリズム」

(45)

データ構造

• i = 0, · · · , 199, a = 0, 1

• x

_i

· · · int x[i]

真の値

• y

_i

· · · double y[i]

観測データ

• x ˆ

_i

· · · int xhat[i]

推定値

• f

_i

(x

_i

) · · · double C[i][a]

i

番目の変数の値が

x

_i

= a

のとき，そこまでに至る最適経路の尤もらしさ．

• x ˆ

_i

(x

_i+1

) · · · int S[i][a]

x

i+1

= a

のとき，

x

i が取るべき値

(46)

データ構造

Y₀ Y₁

X₀ X₁ X₁₉₉

Y₁₉₉ C[3][1]

X₄ 1

• f

i

(x

i

) · · · double C[i][a]

i

番目の変数の値が

x

_i

= a

のとき，そこまでに至る最適経路の尤もらしさ．

Y₀ Y₁

X₀ X₁ X₁₉₉

Y₁₉₉ S[3][1]

1 X₄

• x ˆ

i

(x

i+1

) · · · int S[i][a]

x

i+1

= a

のとき，

x

i が取るべき値

(47)

もとの信号

x _true

^と観測値

y

^の生成

-2 -1 0 1 2 3 4

0 50 100 150 200

t x

true

, y

seed: 20070919 σ=0.7

まずは，こんな図を自分で作ることからはじめる平均

x

標準偏差

σ

の正規分布にしたがう乱数の生成

(48)

最大化のコードを書く際に

•

^{対数尤度の計算}

log

をとるのはコンピュータにはさせない．

p(y _i | x _i ) = 1

√ 2πσ exp {

− (y _i − x _i ) ² 2σ ²

}

, σ = 0.7 log p(y _i | x _i ) = · · · ·

C[0][0] = -(y[0]-0.0)(y[0]-0.0)/(2.0SIGMASIGMA) C[0][1] = -(y[0]-1.0)(y[0]-1.0)/(2.0SIGMASIGMA)

•

なるべくムダな計算はしない

（最大化に関係ない定数は省略できる）

(49)

終

確率的生成モデル

2020

7

7

11/15

-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

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

y

-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

) ←

.. .

1023 1111111111 f(x

) max

f (x

) = f(x

), argmax

x _true

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

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

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

x ^∗ = argmax

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

x _MAP

σ ²