最適化理論確率・統計の復習

(1)

最適化理論 確率・統計の復習

http://www.cs.miyazaki-u.ac.jp/~date/lectures/optimization/

伊達章

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

2020

^年

6

^月

23

^日

(2)

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

•

^平均

µ

，分散

σ ²

，標準偏差

σ

•

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

•

^{擬似乱数の生成}

•

^最尤推定

•

同時確率，条件付き確率

•

^{マルコフ的情報源}

•

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

•

^{事後確率最大化}

•

^{動的計画法}

(3)

•

^平均

µ

，分散

σ ²

，標準偏差

σ

•

^最尤推定

•

^{動的計画法}

(4)

確率：基本中の基本（全部をたすと

1

^）

•

確率変数が離散値の場合

0 ≦ p(x _i ) ≦ 1

∑ n i=1

p(x _i ) = 1

•

確率変数が連続値の場合

p(x)

は確率密度関数

0 ≦ ∫ p(x _∞ _i ) < ∞

−∞

p(x)dx = 1

∫ b a

p(x)dx =

確率

(5)

平均，分散

•

^平均

µ

，期待値

E[x]

µ = E[x] =

∑ n i=1

x _i p(x _i ),

∫ _∞

−∞

xp(x)dx

平均は分かった．例：数学のテストの平均

70

点その周りにどの程度ばらついているかも知りたい！

•

^分散

σ ²

^{，標準偏差}

σ

^： ^{【一つの指標】}

σ ² = E[(x − µ) ² ]

(6)

平均，分散

•

^平均

µ

，期待値

E[x]

µ = E[x] =

∑ n i=1

x _i p(x _i ),

∫ _∞

−∞

xp(x)dx

70

•

^分散

σ ²

^{，標準偏差}

σ

^： ^{【一つの指標】}

σ ² = E[(x − µ) ² ]

(7)

平均，分散

•

^平均

µ

，期待値

E[x]

µ = E[x] =

∑ n i=1

x _i p(x _i ),

∫ _∞

−∞

xp(x)dx

70

•

^分散

σ ²

^{，標準偏差}

σ

^： ^{【一つの指標】}

σ ² = E[(x − µ) ² ]

(8)

共分散（

covariance

^）

• N {

^{人の数学と英語の点数}

x ₁ , x ₂ , · · · , x _N

y ₁ , y ₂ , · · · , y _N

数学と英語の点数に，どんな関係があるか

•

^共分散

σ _XY = E[(x − µ _x )(y − µ _y )]

•

分散・共分散行列

V =

( σ

_X²

σ

_XY

σ

_XY

σ

_Y²

)

(1)

=



 

 1 N

∑

N i=1

(x

i

− µ

x

)

²

1 N

∑

N i=1

(x

i

− µ

x

)(y

i

− µ

y

) 1

N

∑

N i=1

(x

_i

− µ

_x

)(y

_i

− µ

_y

) 1 N

∑

N i=1

(y

_i

− µ

_x

)

²



 



(9)

共分散（

covariance

^）

• N {

x ₁ , x ₂ , · · · , x _N

y ₁ , y ₂ , · · · , y _N

•

^共分散

σ _XY = E[(x − µ _x )(y − µ _y )]

• V =

( σ

_X²

σ

_XY

σ

_XY

σ

_Y²

)

(1)

=



 

 1 N

∑

N i=1

(x

i

− µ

x

)

²

1 N

∑

N i=1

(x

i

− µ

x

)(y

i

− µ

y

) 1

N

∑

N i=1

(x

_i

− µ

_x

)(y

_i

− µ

_y

) 1 N

∑

N i=1

(y

_i

− µ

_x

)

²



 



(10)

共分散（

covariance

^）

• N {

x ₁ , x ₂ , · · · , x _N

y ₁ , y ₂ , · · · , y _N

•

^共分散

σ _XY = E[(x − µ _x )(y − µ _y )]

• V =

( σ

_X²

σ

_XY

σ

_XY

σ

_Y²

)

(1)

=



 

 1 N

∑

N i=1

(x

i

− µ

x

)

²

1 N

∑

N i=1

(x

i

− µ

x

)(y

i

− µ

y

) 1

N

∑

N i=1

(x

i

− µ

x

)(y

i

− µ

y

) 1 N

∑

N i=1

(y

i

− µ

x

)

²



 



(11)

(12)

正規分布，ガウス分布

0.5

-3 -2 -1 0 1 2 3

x p(x)

σ

「

x 1 , x 2 , · · · .x 100

を平均

µ,

^分散

σ ²

^{の互いに独立} なガウス分布に従う確率変数とする」

(13)

N (µ, σ ² )

0.5

-3 -2 -1 0 1 2 3

x p(x)

σ

p(x; θ, σ ² ) = 1

√ 2πσ ² e ⁻

^(x^2σ⁻^µ)2²

, p(x; 0, 1) = 1

√ 2π e ⁻

^x

2 2

∫ _∞

−∞

p(x)dx = 1

(14)

0.5

-3 -2 -1 0 1 2 3

x p(x)

σ

p(x; 0, 1) = 1

√ 2π e ⁻

^x

2 2

x i , i = 1, · · · , 1000

^のうち約

68.26%

^が

− 1 < x _i < 1

に含まれている．その根拠：

∫ 1

− 1

p(x)dx = 0.6826

(15)

0.5

-3 -2 -1 0 1 2 3

x p(x)

σ

∫ 2

− 2

p(x)dx = 0.9544,

∫ 3

− 3

p(x)dx = 0.9974

(16)

(17)

•

^平均

µ

，分散

σ ²

，標準偏差

σ

•

^最尤推定

•

^{動的計画法}

(18)

ss002.py

1 i m p o r t r a n d o m 2

3 T = 200;

4 S i g m a = 0.7

5 r a n d o m . seed ( 2 0 1 3 1 1 0 7 ) 6

7 for i in r a n g e ( T ) :

8 p r i n t r a n d o m . g a u s s (0 , S i g m a )

•

^平均

µ = 0,

標準偏差

σ = 0.7

の正規分布にしたがうデータを

200

個生成

•

^{正規分布（＝}

Gauss

^{分布）とは？}

(19)

擬似乱数

•

^{おなじない：}

import random

^{という行が必要}

•

^一様分布

for i in range(100):

print random.randint (2,9)

# 2

から

9

までの整数が等確率で出力される

•

正規分布（ガウス分布）

for i in range(100):

print random.gauss(72.0, 5.0)

#

平均 μ

=72,

標準偏差σ

=5

の正規分布にしたがうデータが出力される．

•

^標準偏差

σ

^{の意味？！}

• random.seed(20131107)

^とは？

(20)

擬似乱数

• import random

•

^一様分布

for i in range(100):

print random.randint (2,9)

# 2

から

9

• for i in range(100):

print random.gauss(72.0, 5.0)

#

平均 μ

=72,

標準偏差σ

=5

•

^標準偏差

σ

^{の意味？！}

• random.seed(20131107)

^とは？

(21)

擬似乱数

• import random

•

^一様分布

for i in range(100):

print random.randint (2,9)

# 2

から

9

• for i in range(100):

print random.gauss(72.0, 5.0)

#

平均 μ

=72,

標準偏差σ

=5

•

^標準偏差

σ

^{の意味？！}

• random.seed(20131107)

^とは？

(22)

正規分布（ガウス分布）

ss105.py

−4 −2 0 2 4

0 50 100 150 200 250 300 350 400 450

• N (µ, σ ² ) = N (0, 1)

にしたがう

1

万のデータ

• [ − 1 : 1]

にあるデータは何

%

？

[ − 3 : 3]

は？

(23)

擬似乱数

•

真の乱数は人工的には作れない．

コンピュータは，どう乱数を作っているか

•

次の数列を考えよう．

線形合同法（

Linear congruential generators, LCGs

）

X

_n+1

= (3X

_n

+ 7) mod 20, X

₀

= 5

• 5, 2, 13, 6, · · ·

（乱数ぽい）

• 5, 2, 13, 6, 5, 2, 13, 6, 5 · · ·

（周期

5）

• X

_n+1

= 48271 X

_n

mod (2

³¹

− 1)

Park, S.K. & Miller, K.W. Random numbergenerators: Good ones

are hard to ﬁnd. Communications of the ACM 31, 1192-1201

(1988).

(24)

擬似乱数

•

真の乱数は人工的には作れない．

コンピュータは，どう乱数を作っているか

•

次の数列を考えよう．

線形合同法（

Linear congruential generators, LCGs

）

X

_n+1

= (3X

_n

+ 7) mod 20, X

₀

= 5

• 5, 2, 13, 6, · · ·

（乱数ぽい）

• 5, 2, 13, 6, 5, 2, 13, 6, 5 · · ·

（周期

5）

• X

_n+1

= 48271 X

_n

mod (2

³¹

− 1)

Park, S.K. & Miller, K.W. Random numbergenerators: Good ones

are hard to ﬁnd. Communications of the ACM 31, 1192-1201

(1988).

(25)

擬似乱数：乱数の種とは

• random.seed(20131107)

とは？

X

_n+1

= 48271 X

_n

mod (2

³¹

− 1), X

₀

X

0 のこと

•

式と種

(seed)

から乱数系列を再現できる．

(26)

(27)

最尤推定

•

確率分布の形を仮定：

x ∼ p(x; θ)

，

•

目的：パラメータ

θ

の値を知りたい！

例：

p(x; µ, σ) = 1

√ 2πσ

²

e

⁻^(x^2σ⁻^µ)2²

•

与えられているデータ：

x = (x

₁

, x

₂

, · · · , x

_N

)

•

アイデア：データ

x

を固定して

l(θ) = f(x, θ) =

∏

N

i=1

p(x

_i

; θ)

を最大にする

θ

の値を真の

θ

の推定値にしよう！

θ ˆ = argmax

θ

l(θ)

(28)

対数尤度

•

アイデア：データ

x

を固定して

l(θ) = f(x, θ) =

∏

N

i=1

p(x

_i

; θ)

を最大にする

θ

の値を真の

θ

の推定値にしよう！

θ ˆ = argmax

θ

l(θ)

•

対数関数は単調増加関数．

L(θ) = log l(θ)

として

θ ˆ = argmax

θ

L(θ)

を求めても同じ．

•

用語：対数尤度

L(θ)

，最尤推定量

θ ˆ

(29)

問題：最尤推定

*******

・

n

^{個のデータ}

x 1 , x 2 , · · · , x n

を観測した．

・このデータは，互いに独立であると仮定する．

・正規分布

N (µ, 1)

から生成されたと仮定する．

x _i ∼ N (µ, 1), i = 1, · · · , n

・このとき，

µ

の最尤推定量

µ ˆ

を求めよ．

(30)

最尤推定：正規分布

θ ˆ = argmax

θ

L(θ) (2)

L(θ) = log

∏

N i=1

p(x

i

; θ) =

∑

N i=1

log p(x

i

; θ) (3)

L(µ, σ

²

) =

∑

N i=1

log p(x

i

; µ, σ

²

) =

∑

N i=1

log( 1

√ 2πσ

²

e

⁻⁽^xi−µ)2^2σ²

)

=

∑

N i=1

{

− 1

2 log(2πσ

²

) − (x

_i

− µ)

²

2σ

²

}

(4)

= − N

2 log(2πσ

²

) −

∑

N i=1

(x

i

− µ)

²

2σ

²

∂

∂µ L = −

∑

N i=1

1 2σ

²

2(x

_i

− µ)( − 1) =

∑

N i=1

x

_i

− µ

σ

²

= 0 (5) ˆ

µ = 1 N

∑

N

x

i

(6)

30 / 38

(31)

最尤推定：正規分布

L(µ, σ

²

) = − N

2 log(2πσ

²

) −

∑

N i=1

(x

i

− µ)

²

2σ

²

(7)

= − N

2 log(2π) − N

2 log(σ

²

) −

∑

N i=1

(x

_i

− µ)

²

2σ

²

(8)

∂

∂σ

²

L = − N 2σ

²

−

∑

N i=1

(x

i

− µ)

²

2 ∂

∂σ

²

1 σ

²

(9)

= − N 2σ

²

−

∑

N i=1

(x

_i

− µ)

²

2 ( − 1) 1

σ

⁴

(10)

= − N 2σ

²

+

∑

N i=1

(x

i

− µ)

²

2

1 σ

⁴

= 0 (11)

ˆ

σ

²

= 1 N

∑

N i=1

(x

i

− µ)

²

(12)

(32)

問題：最尤推定

*******

・

n

個のデータ

x ₁ , x ₂ , · · · , x _n

を観測した．

・このデータは，互いに独立であると仮定する．

・指数分布

p(x; λ) = 1 λ e ⁻

^x^λ

から生成されたと仮定する（

x ≧ 0

）．

・このとき，

µ

の最尤推定量

µ ˆ

を求めよ．

(33)

最尤推定：指数分布

θ ˆ = argmax

θ

L(θ) (13)

L(θ) = log

∏

N i=1

p(x

_i

; θ) =

∑

N i=1

log p(x

_i

; θ) (14)

L(λ) =

∑

N i=1

log p(x

i

; λ) =

∑

N i=1

log( 1 λ e

⁻^x^λ

)

=

∑

N i=1

{ − log λ − x

_i

λ

}

= − N log λ −

∑

N i=1

x

_i

λ (15)

∂

∂λ L = − N λ +

∑

N i=1

x

i

λ

²

= 0 (16)

λ ˆ = 1 N

∑

N i=1

x

_i

(17)

(34)

Fisher

^情報量

• Fisher

^情報量

I(θ) = E [( d

dθ log p(x; θ) )

2

]

=

∫

p(x; θ) ( d

dθ log p(x; θ) )

2

dx

• Cramer-Rao

の不等式（推定精度の限界）

E[(ˆ θ − θ)

²

] ≧ 1 N I(θ)

右辺は，モデルとデータ数

N

だけに依存

(35)

Fisher

^情報量

•

^平均

µ

，分散

1

の正規分布の場合

log p(x; µ) = − 1

2 log(2π) − (x − µ)

²

2 (18)

• Fisher

情報量

I(µ) = E [( d

dµ log p(x; µ) )

2

]

=

∫

p(x; µ)(x − µ)

²

dx = σ

²

= 1

• Cramer-Rao

の不等式（推定精度の限界）

E[(ˆ µ − µ)

²

] ≧ 1 N

右辺は，モデル

p(x; µ)

とデータ数

N

だけに依存平均値の推定がどのくらいの精度でできるか

−

^√¹_N

< µ ˆ − µ <

^√¹

N

(36)

(37)

本日の課題

2020年6月23日最適化理論

学籍番号：671 0 0

名前：得点：

小テスト【正規分布，最尤推定】

1.平均µ，分散σ²の正規分布の確率密度関数p(x;µ, σ2)を記述せよ．

2.n個のデータx1, x2,· · ·, xnが観測されている．このデータの平均mと分散s2を求めよ．s2を表現

する際に文字mを使ってよい．

m= s²=

3.平均µ，分散σ2の正規分布から独立に生成された1000個のデータx1, x2,· · ·が観測されている．そのうち値がµ−σ < xi< µ+σの範囲．およびµ−3σ < xi< µ+ 3σの範囲にあるデータのおおよその割合（%）を求めよ（i= 1,· · ·,1000）．

µ−σ < xi< µ+σ： µ−3σ < xi< µ+ 3σ：

4.x1, x2,· · ·, xnを平均µ，分散σ2の正規分布から独立に生成されたデータとする．尤度L(µ, σ2)を求めよ．

L(µ, σ²) =

5. 4.の対数尤度を求めよ．

logL(µ, σ²) =

6.N人の学生について数学の点数x1, x2,· · ·xNと英語の点数y1, y2,· · ·yNのデータがある（xi, yiはi 番目の人の得点）．このデータについて，数学と英語に関する分散・共分散行列Vを求めよ．数学と英語の得点の平均はそれぞれmx, myとしてよい．

•

プリント（小テスト）

1 ダウンロード

2 印刷

3 手で解く（手書き）

4 スキャン（撮影）

5

pdf

化

6

WebClass

で提出

（締切：6/25木

18:00）

•

使用できそうなツール

•

スマートフォン

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

•

セブン

-

イレブン

(38)

終

最適化理論 確率・統計の復習

http://www.cs.miyazaki-u.ac.jp/~date/lectures/optimization/

2020

6

23

•

µ

σ 2

σ

•

•

•

•

•

•

•

•

•

µ

σ 2

σ

•

•

•

•

•

•

•

•

1

•

0 ≦ p(x i ) ≦ 1

∑ n i=1

p(x i ) = 1

•

p(x)

0 ≦ ∫ p(x ∞ i ) < ∞

−∞

p(x)dx = 1

∫ b a

p(x)dx =

•

µ

E[x]

µ = E[x] =

∑ n i=1

x i p(x i ),

∫ ∞

−∞

xp(x)dx

70

•

σ 2

σ

σ 2 = E[(x − µ) 2 ]

•

µ

E[x]

µ = E[x] =

∑ n i=1

x i p(x i ),

∫ ∞

−∞

xp(x)dx

70

•

σ 2

σ

σ 2 = E[(x − µ) 2 ]

•

µ

E[x]

µ = E[x] =

∑ n i=1

x i p(x i ),

∫ ∞

−∞

xp(x)dx

70

•

最適化理論確率・統計の復習

σ ²

σ ²

0 ≦ p(x _i ) ≦ 1

p(x _i ) = 1

0 ≦ ∫ p(x _∞ _i ) < ∞

x _i p(x _i ),

∫ _∞

σ ²

σ ² = E[(x − µ) ² ]

x _i p(x _i ),

∫ _∞

σ ²

σ ² = E[(x − µ) ² ]

x _i p(x _i ),

∫ _∞

σ ²

σ ² = E[(x − µ) ² ]

x ₁ , x ₂ , · · · , x _N

y ₁ , y ₂ , · · · , y _N

σ _XY = E[(x − µ _x )(y − µ _y )]

x ₁ , x ₂ , · · · , x _N

y ₁ , y ₂ , · · · , y _N

σ _XY = E[(x − µ _x )(y − µ _y )]