プログラミング メモ

プログラミング メモ

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

伊達 章

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

2017年6月16日

1 / 22

概要

1. データ構造とアルゴリズムについて

2. ともかく書く．わからなければ日本語で書く 3. ^{おまじないについて．}

4. ^{空関数を作る．}

5. ^{デバグ・テスト}

2 / 22

目標

ともかく

• 動くコードを

• 自分一人で

作ることができるように！

3 / 22

データ構造とアルゴリズムについて

• アルゴリズム

前々回の資料と，教科書 8.2，8.3 分かるまで何度も読む．

• データ構造

f_i(x_i) とxˆ_i(x_i+1) を表現する2次元配列

4 / 22

データ構造

i= 0,· · · ,199, a = 0,1として，

• x_i · · · int x[i] 真の値

• yi · · · double y[i] 観測データ

• xˆ_i · · · int xmap[i] 推定値

• f_i(x_i) · · · double f[i][a]

i番目の変数の値がx_i =aのとき，そこに至る最適経 路の尤もらしさを保持．

• xˆi(xi+1) · · · int xhat[i][a]

xi+1 =a のとき，xi が取るべき値を保持．

5 / 22

C^{言語 チュートリアル}

とにかく書きはじめる！

1 # i n c l u d e < s t d i o . h > // おまじない 2 # i n c l u d e < s t d l i b . h >

3 # i n c l u d e < m a t h . h >

4 5

6 int

7 m a i n (int argc , c h a r * a r g v [])

8 {

9

10 r e t u r n 0;

11 }

↑ C言語のテンプレート．さっそくコンパイル！

7 / 22

わからなければ日本語で書く！

1 # i n c l u d e < s t d i o . h > // おまじない 2 # i n c l u d e < s t d l i b . h >

3 # i n c l u d e < m a t h . h >

4

5 int

6 m a i n (int argc , c h a r * a r g v [])

7 {

8

9 // 問題を作る（200 個のデータ生成）

10

11 // 復元する

12

13 // 結果を表示する 14

15 r e t u r n 0;

16 }

https://github.com/date333cs/optimization/blob/master/hmm001.c

8 / 22

空の関数を作る！

1 # i n c l u d e < s t d i o . h > // おまじない 2 # i n c l u d e < s t d l i b . h >

3 # i n c l u d e < m a t h . h >

4

5 v o i d g e n e r a t e _ x () { 6

7 }

8 v o i d g e n e r a t e _ y () { 9

10 } 11

12 int m a i n (int argc , c h a r * a r g v []) { 13

14 g e n e r a t e _ x () ; // 問題を作る 15 g e n e r a t e _ y () ;

16 c o m p u t e _ x m a p () ; // 復元する 17 // 結果を表示する

18

19 r e t u r n 0;

20 } 9 / 22

データ構造

1 int x [ N _ D A T A ]; // もともとの信号． 0 か 1

2 int x m a p [ N _ D A T A ]; // 推定値． 0 か 1 3 d o u b l e y [ N _ D A T A ]; // 観測データ 4

5 int x h a t [ N _ D A T A ] [ 2 ] ;

6 // x h a t [ 2 ] [ b ] = a r g m a x _ a { ( f [ 2 ] [ a ] + h ( a , b ) } 7 // 教科書 p . 2 1 8 参照

8 d o u b l e f [ N _ D A T A ] [ 2 ] ;

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

• f_i(x_i) · · · double f[i][a]

i番目の変数の値がx_i =aのとき，そこに至る最適経 路の尤もらしさ．

• xˆi(xi+1) · · · int xhat[i][a]

xi+1 =a のとき，xi が取るべき値

10 / 22

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

• nrnd() という関数を用意しているので，それを使う．

1 v o i d t e s t _ n r n d () { 2

3 int i ;

4 for ( i =0; i < 1 0 ; i ++) {

5 p r i n t f (" %.8 lf \ n ", n r n d () ) ;

6 }

7 }

σ * nrnd() とすれば，標準偏差 σ のデータを生成できる．

平均 µ，標準偏差 σ にしたければ，σ * nrnd() + µ 0.97430744

-0.18328546 -0.20470468 -0.26548298 ...

11 / 22

使って良い知識

データ（観測値）： y= (y1,· · · , yn) モデル：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 xi = 0, xi+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．

12 / 22

事後確率最大化

x₃

x₁ x₂ x_n-1 x_n

y3

y1 y2 yn-1 yn

J = logp(x1) +

∑n

i=2

logp(xi|xi−1) +

∑n

i=1

logp(yi|xi)

= logp(x1) + logp(y1|x1) +

n−1

∑

i=1

{

logp(xi+1|xi) + logp(yi+1|xi+1) }

yiは定数 ⇒ 教科書p.216 (8.2)式と同じ形

= f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

• ^f1(x₁) = logp(x₁) + logp(y₁|x₁)

• ^hi(x_i, x_i+1) = logp(x_i+1|x_i) + logp(y_i+1|x_i+1)

13 / 22

事後確率最大化

x₃

x₁ x₂ x_n-1 x_n

y3

y1 y2 yn-1 yn

J = logp(x1) +

∑n

i=2

logp(xi|xi−1) +

∑n

i=1

logp(yi|xi)

= logp(x1) + logp(y1|x1) +

n−1

∑

i=1

{

logp(xi+1|xi) + logp(yi+1|xi+1) }

yiは定数 ⇒ 教科書p.216 (8.2)式と同じ形

= f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

• ^f1(x₁) = logp(x₁) + logp(y₁|x₁)

• ^hi(x_i, x_i+1) = logp(x_i+1|x_i) + logp(y_i+1|x_i+1)

14 / 22

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = logp(x1) + logp(y1|x1) +

n−1

∑

i=1

{

logp(xi+1|xi) + logp(yi+1|xi+1) }

= f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

• ^x1 に着目 ⇒f₁(x₁), h₁(x₁, x₂)にしか関係しない

• ^f1(x₁) +h₁(x₁, x₂)を最大にするようx₁ を選ぶ

• ^↑x2の値がわかっていないければ選べない

• ^{そこで，x2}の可能なすべての値（0,1）に対して，以下を計算

• ^{f2(x2) = max}_x

1

{f1(x1) +h1(x1, x2)} ˆ

x1(x2) = argmax

x1

{f1(x1) +h1(x1, x2)}

J =f₂(x₂) +h₂(x₂, x₃) +· · ·+h_n−1(x_n−1, x_n)

15 / 22

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = logp(x1) + logp(y1|x1) +

n−1

∑

i=1

{

logp(xi+1|xi) + logp(yi+1|xi+1) }

= f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

• ^x1 に着目 ⇒f₁(x₁), h₁(x₁, x₂)にしか関係しない

• ^f1(x₁) +h₁(x₁, x₂)を最大にするようx₁ を選ぶ

• ^↑x2の値がわかっていないければ選べない

• ^{そこで，x2}の可能なすべての値（0,1）に対して，以下を計算

• ^{f2(x2) = max}_x

1

{f1(x1) +h1(x1, x2)} ˆ

x1(x2) = argmax

x1

{f1(x1) +h1(x1, x2)}

J =f₂(x₂) +h₂(x₂, x₃) +· · ·+h_n−1(x_n−1, x_n)

16 / 22

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = logp(x1) + logp(y1|x1) +

n−1

∑

i=1

{

logp(xi+1|xi) + logp(yi+1|xi+1) }

= f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

• ^x1 に着目 ⇒f₁(x₁), h₁(x₁, x₂)にしか関係しない

• ^f1(x₁) +h₁(x₁, x₂)を最大にするようx₁ を選ぶ

• ^↑x2の値がわかっていないければ選べない

• ^{そこで，x2}の可能なすべての値（0,1）に対して，以下を計算

• ^{f2(x2) = max}_x

1

{f1(x1) +h1(x1, x2)} ˆ

x1(x2) = argmax

x1

{f1(x1) +h1(x1, x2)}

J =f₂(x₂) +h₂(x₂, x₃) +· · ·+h_n−1(x_n−1, x_n)

17 / 22

動的計画法

x₃

x₁ x₂ x_n-1 x_n

y₃

y₁ y₂ y_n-1 y_n

J = logp(x1) + logp(y1|x1) +

n−1

∑

i=1

{

logp(xi+1|xi) + logp(yi+1|xi+1) }

= f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

• ^x1 に着目 ⇒f₁(x₁), h₁(x₁, x₂)にしか関係しない

• ^f1(x₁) +h₁(x₁, x₂)を最大にするようx₁ を選ぶ

• ^↑x2の値がわかっていないければ選べない

• ^{そこで，x}2の可能なすべての値（0,1）に対して，以下を計算

• ^{f2(x2) = max}_x

1

{f1(x1) +h1(x1, x2)} ˆ

x1(x2) = argmax

x1

{f1(x1) +h1(x1, x2)}

J =f₂(x₂) +h₂(x₂, x₃) +· · ·+h_n−1(x_n−1, x_n) 18 / 22

ここまで

x3

x1 x2 xn-1 xn

y3

y1 y2 yn-1 yn

• ^f1(x1) = logp(x1) + logp(y1|x1)

p(x1)はx1= 0, x1= 1どちらの場合も0.5．

• ^{hi(xi, xi+1) = logp(xi+1}|xi) + logp(yi+1|xi+1)

上の図では，p(x_i+1|xi)が横棒，p(y_i+1|xi+1)が縦棒に対応．

• ^f2(x₂) = max

x₁ {f₁(x₁) +h₁(x₁, x₂)} ˆ

x₁(x₂) = argmax

x₁ {f₁(x₁) +h₁(x₁, x₂)}

J =f1(x1) +h1(x1, x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn) J =f2(x2) +h2(x2, x3) +· · ·+hn−1(xn−1, xn)

J =fn(xn)

19 / 22

縦棒 logp(y_i|x_i)^について

x3

x1 x2 xn-1 xn

y3

y1 y2 yn-1 yn

• ^logをとるのはコンピュータにはさせない． 手計算で！

p(yi|xi) = 1

√2πσexp {

−(yi−xi)² 2σ²

}

logp(y_i|x_i) =−log(√

2πσ)−(y_i−x_i)² 2σ²

• ^{上式，右辺第1項は，xi}の値に依存しない．最大化には関係ない．

20 / 22

チュートリアル 【終わり】

終

22 / 22