レポート課題 : 隠れマルコフモデル

最適化理論 2021年6月23日

レポート課題

隠れマルコフモデル

口頭試問は7月19日（月）までには終わらせるようにすること．コンピュータ・プログ ラムのバグがなかなか発見できず，課題解決が数日進まない場合がある．そういう場合を想 定して，はやめに課題に取り掛かること．

X3

X1 X2

Y3

Y1 Y2

図1: 確率変数の依存性を描いたグラフ

確率的生成モデルを用いたパターン認識について考えよう．ここでは与えられたデータ y からそのデータの表している内容x を当てるパターン認識を考える．x = (x1, x2, x3), y= (y1, y2, y3), xi, yi ∈ {0,1},i= 1,· · · ,3 ^{として，確率分布}p(x), p(y|x) ^{が以下のように} 与えられているとする．

p(x₁) = Prob(X₁ =x₁) = {

0.5 if x₁ = 0

0.5 if x1 = 1 (1)

p(x_i+1|x_i) =











0.9 if x_i = 0, x_i+1= 0 0.1 if x_i = 0, x_i+1= 1 0.7 if x_i = 1, x_i+1= 1 0.3 if xi = 1, xi+1= 0

(2)

p(y_i|x_i) = {

0.8 if x_i =y_i

0.2 if x_i ̸=y_i (3)

したがって

p(x) = p(x1, x2, x3) =p(x1)p(x2|x1)p(x3|x2) =p(x1)

∏2 i=1

p(xi+1|xi) (4)

p(y|x) = p(y₁, y₂, y₃|x₁, x₂, x₃) (5)

= p(y1|x1)p(y2|x2)p(y3|x3) (6)

=

∏3 i=1

p(yi|xi) (7)

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

とかける．これらの式は図1をイメージすると理解しやすい（各項が一本の枝に対応）．

1

確率分布p(x)について考えよう．ベクトルx= (x1, x2, x3)^の各要素 xiは0,1^の値をと る．したがってx^は8通りの状態を取り得る．それぞれの状態が出現する確率を足すと1^に なるため，確率分布p(x)は，7つのパラメータを決めれば完全に指定できる．しかし，こ こでは0.5,0.9,0.7という3つのパラメータ値を指定しただけであることに注意したい．音 や画像のような高次元データを扱う場合には，場合の数が大きくなり，一つ一つの状態の確 率を指定することは現実的にはできないため，このようなモデル化がよくおこなわれる．な おp(x)をモデルもしくは事前確率，p(y|x)をデータモデルとよぶ．

練習問題（手計算．理解度合いの確認用．提出する必要なし）

1. x= (0,0,0)^{とする．確率} p(x) ^{を求めよ．}

2. x= (0,1,0)^{とする．確率} p(x) ^{を求めよ．}

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

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

5. y= (0,1,0)^{であった．}x0= (0,0,0)^{とするとき事後確率}p(x0|y) ^{を求めよ．}

6. y= (0,1,0)^{であった．}x2= (0,1,0)^{とするとき事後確率}p(x2|y) ^{を求めよ．}

7. f(x) =−(x−1)^{2 とする} (a) max

x f(x)^{を求めよ．}

(b) argmax

x

f(x) ^{を求めよ．}

8. y= (0,1,0)であった．事後確率を最大にするxMAPを求めよ．

x_MAP = argmax

x

p(x|y) (9)

2

基本課題 （必須）

以下ではx,y^ともに，n= 200次元のベクトルとする．xi ∈ {0,1}, i= 0,· · · ,199^，yi は 実数とする．確率分布p(x)，確率密度関数p(y|x) が以下のように与えられているとする．

p(x₀) = Prob(X₀ =x₀) = {

0.5 if x₀ = 0

0.5 if x₀ = 1 (10)

p(x_i+1|x_i) =











0.99 if xi= 0, xi+1= 0 0.01 if xi= 0, xi+1= 1 0.97 if x_i= 1, x_i+1= 1 0.03 if x_i= 1, x_i+1= 0

(11)

p(yi|xi) = 1

√2πσ exp {

−(yi−xi)² 2σ²

}

(12) ここで以下の課題では，特に指定しない限りσ = 0.7とする．

1. ^確率分布p(x)^{にしたがう}x= (x0,· · ·, x199)^{を確率的に生成せよ．}10^{例を生成し，ま} とめて1枚の図に表示しなさい．一つ一つのグラフが重ならないように，α^番目のx は，縦軸の値をx_i+ 3α として表示せよ（α= 0,· · · ,9）．

2. 前問と同様にxを一つ生成し（これをx_orgとする），上記 p(y|x)を用い，y_obs を生 成せよ．xorgとしては，なるべく異なる状態に遷移する回数が多いものを用いること が望ましい．xorgは線で，yobsは点で，重ねて1^{枚の図に描きなさい．}

3. 事後確率を最大にするx_MAP = argmax

x

p(x|y_obs) を動的計画法を用いて求める方法 を，簡潔に説明できるようにしなさい．できるようになったら口頭試問を受けること．

4. ^{事後確率を最大にする}xMAP を動的計画法を用いて求め，xorg,y_obs,xMAP を重ねて 1枚の図に描きなさい．ここでxMAPについては，各要素の値に +2^{を加えたものを} 表示せよ．また x_orgとx_MAP のハミング距離d(x_org,x_MAP) を求めよ．ここで

d(a,b) =

∑199 i=0

|ai−bi| (13)

とする．最低 3例について図を作成せよ．

*** web上に，作成したプログラムが正しく作動しているかチェックする，テスト用のデー

タを用意している．

https://raw.githubusercontent.com/date333cs/courses/master/optimization theory/r20190702 20 test cases

3

応用課題 （できるところまででOK^）

5. 確率分布p(x,y)にしたがうx_org とy_obs を生成し，y_obsとモデルp(x), p(y|x) のみ を用いx_MAP^{を求め，ハミング距離}d(xorg,x_MAP) を計算せよ（ここまでは 4. ^と同 じ）．これを1000回繰り返し，ハミング距離のヒストグラムを描きなさい．また，ハ ミング距離の平均値と分散を求めよ．

6. σ ^の値を 0.3^から 2.0 ^の0.1刻みで変え，前問の実験をおこない，横軸にσ^，縦軸に ハミング距離の平均値±標準偏差をプロットした図を作成せよ．

7. xorgを生成したモデルと異なるモデルを用いてxMAPを求めた場合，認識性能が低下 することが期待される．どのくらい性能が低下するか調べてみよう．たとえば，x_org を生成したときのp(x)を使ってx_MAPを求めた場合と，それとは異なるモデル

q(xi+1|xi) =











θ if x_i = 0, x_i+1 = 0 1−θ if xi = 0, xi+1 = 1 θ if xi = 1, xi+1 = 1 1−θ if xi = 1, xi+1 = 0

(14)

を使ってxMAPを求めた場合を比較してみればよい．ここでは，σ = 0.7^{とし，デー} タモデルはp(y|x)は固定しておく．前問と同様に，同じ条件で1000回実験を繰り返 し，横軸にθを0.7< θ <1.0 において0.05きざみで，縦軸にハミング距離の平均値

±標準偏差をプロットした図などを描けばよい．

8. 一つのプログラミング言語でプログラムが書けたら，プログラムを美しく書き直した り，別のプログラミング言語で書き直したりしてみよ．GUI^{を作るのもよい．}

9. そのほか自分で考えた問題設定，講義で紹介した問題など．

レポートの最後には，感想，質問などを記述してほしい．理解しにくい点があった場合は，

このプリント中の，どこの部分が分かりにくかったか，具体的に，指摘してもらえれば大変 助かる（来年度向けに改善するため）．

レポート提出先： WebClass

「学籍番号＋名前」をファイル名にしたpdfファイル（例：7770770date.pdf）をアップロー ド．

4