パターン認識論 #4

パターン認識論 第４回 伊藤彰則 1

ガウス混合モデル(GMM) もくじ ◦GMMとは何か ◦GMMはどうして必要か ◦EMアルゴリズム ◦GMMの推定アルゴリズム 2

GMMとは何か 混合ガウス分布（混合正規分布） 𝐾 σ ◦𝑝 𝑥 = 𝑘=1 𝜆𝑘 𝑁(𝑥; 𝜇𝑘 , 𝛴𝑘 ) 𝑥 − 𝜇 𝑡 𝛴 −1 (𝑥 − 𝜇) 𝑁 𝑥; 𝜇, 𝛴 = exp − 𝑑/2 1/2 2 2𝜋 𝛴 1 3

GMMでサンプルが生成さ れる仕組み ◦GMMは生成モデル ◦ ある確率分布にしたがってサンプルが生成 されることを仮定する ◦𝑝 𝑥 = 𝜆1 𝑁 𝑥; 𝜇1 , Σ1 + 𝜆2 𝑁(𝑥; 𝜇2 , Σ2 )の 場合 ◦ 確率𝜆𝑘 で𝑘番目の分布が選ばれる ◦ 確率密度𝑁 𝑥; 𝜇𝑘 , Σ𝑘 でサンプル生成 4

さまざまな分布 5

GMMはどうして必要か パラメトリックな認識では 1. 認識すべきクラスのサンプルが従う 確率分布を仮定 2. 学習データから各クラスの確率分布 のパラメータを推定 3. 未知サンプルが与えられたら各クラ スの確率密度を推定 4. 一番確率密度が高いクラスに分類 6

GMMはどうして必要か 何が識別性能を決めるのか ◦推定された確率分布が「真の分布」に 近いほど高性能 ◦それぞれのクラスを多次元正規分布で 近似するだけでは限界がある ◦ もっと複雑でパラメータの多い分布が使え ればよいのでは？ 7

分布の例 8

分布の例 2次元ガウス分布で近似 9

分布の例 各クラスを2つのガウス分布で近似 10

GMMはどうして必要か パラメータを「減らす」ために GMMを使うことがある ◦d次元ガウス分布のパラメータ数は 𝑑 𝑑+1 1 2 3 𝑑+ = 𝑑 + 𝑑 2 2 2 ◦次元が高い場合には推定が難しい 11

GMMはどうして必要か ◦ここで共分散が対角行列と仮定 𝜎12 ⋯ 0 ◦𝛴 = ⋮ ⋱ ⋮ 0 ⋯ 𝜎𝑑2 ◦ 分布を表す楕円の軸が座標軸に平行 ◦ 1つのガウス分布を表現するパラメータ数は 𝑑 + 𝑑 = 2𝑑 ◦ 𝑀個の分布を混合してもパラメータは 2𝑀𝑑 12

対角共分散GMM 13

GMMのパラメータ推定 2混合の場合 ◦𝑝 𝑥 = 𝜆1 𝑁 𝑥; 𝜇1 , Σ1 + 𝜆2 𝑁 𝑥; 𝜇2 , Σ2 ◦パラメータは 𝜆1 , 𝜆2 , 𝜇1 , 𝜇2 , Σ1 , Σ2 ◦どうやってこれらを推定するか？ ◦ 学習データ中で，2つの分布に属している サンプルがあらかじめわかっていれば，そ れぞれから最尤推定 14

GMMのパラメータ推定 2分布でそれぞれに属するサンプル が既知の場合 (1) (2) 1 2 ◦𝑋1 = 𝑥1 , … , 𝑥𝑁1 , 𝑋2 = 𝑥1 , … , 𝑥𝑁2 1 𝑁𝑘 (𝑘) ◦𝜇𝑘 = σ𝑖=1 𝑥𝑖 𝑁𝑘 𝑡 1 (𝑘) 𝑁𝑘 𝑘 ◦𝛴𝑘 = σ𝑖=1 𝑥𝑖 − 𝜇𝑘 𝑥𝑖 − 𝜇𝑘 𝑁𝑘 ◦𝜆𝑘 = 𝑁𝑘 /(𝑁1 + 𝑁2 ) 15

GMMのパラメータ推定 それぞれの分布に属するサンプルが 不明な場合は？ ◦繰り返し処理による推定 ◦仮に分布を設定し，各サンプルの各分 布に対する確率密度で出現回数を按分 する ◦EMアルゴリズム 16

EM (ExpectationMaximization) アルゴリズム 観測データから決定することのでき ない内部状態（隠れ変数）を持つ確 率モデルのパラメータ推定法 ◦GMMの場合「分布」 ◦最初にもっと簡単な例で説明 17

EMアルゴリズム 箱の中に赤玉と白玉 ◦箱から取り出して玉を観測できるが，ど ちらの箱から取り出したかわからない 18

EMアルゴリズム どの箱から玉が出たかわからない状 態で，それぞれの箱の選択比率がわ かるか？ ◦玉を取り出しては戻す操作をN 回 ◦箱 𝐵1 , 𝐵2 それぞれを選ぶ確率 𝑃(𝐵𝑘 ) ◦箱𝐵𝑘 から𝑖番目の色の玉を取り出す確率 𝑃(𝑐𝑖 |𝐵𝑘 ) ◦𝑃(𝑐𝑖 |𝐵𝑘 )が既知だとして𝑃(𝐵𝑘 )を推定 19

EMアルゴリズム ◦どちらかの箱から取り出した玉が𝑐𝑖 で ある確率は 𝑃 𝑐𝑖 = 𝑃 𝑐𝑖 𝐵1 𝑃 𝐵1 + 𝑃 𝑐𝑖 𝐵2 𝑃(𝐵2 ) ◦取り出した玉が𝑐𝑖 であるとき，それが 𝐵𝑘 から取り出されていた確率（事後確 率）は 𝑃 𝑐𝑖 𝐵𝑘 𝑃 𝐵𝑘 𝑃 𝐵𝑘 𝑐𝑖 = 𝑃(𝑐𝑖 ) k番目の箱の「按分された出現回数」 20

EMアルゴリズム ◦ 按分された出現回数を使って箱の選択確率の 期待値を計算する 1 = ෍ 𝑃(𝐵𝑘 |𝑐𝑖 ) 𝑁 𝑃′ 𝐵𝑘 𝑖 1 𝑃 𝑐𝑖 𝐵𝑘 𝑃(𝐵𝑘 ) = ෍ 𝑁 σ𝑗 𝑃( 𝑐𝑖 𝐵𝑗 𝑃(𝐵𝑗 ) 𝑖 21

EMアルゴリズム  t +1 k  P(ci | Bk ) 1 =  t N i   j P (ci | B j ) t k j 22

推定例 ◦ 𝑃 𝐵1 = 0.6, 𝑃 𝐵2 = 0.4 𝑃 𝑟𝑒𝑑 𝐵1 = 0.3, 𝑃 𝑤ℎ𝑖𝑡𝑒 𝐵1 = 0.7 𝑃 𝑟𝑒𝑑 𝐵1 = 0.7, 𝑃 𝑤ℎ𝑖𝑡𝑒 𝐵2 = 0.3 ◦ サンプル数1000 23

EMアルゴリズムの原理 ◦ 推定すべきパラメータ𝜃 （先程の例では𝜃 = {𝜆1 , 𝜆2 }） ◦ 観測データ𝑥𝑖 ◦ 「隠れ変数」のデータ（観測できない） 𝑦𝑖 (∈ 𝐵1 , 𝐵2 ) ◦ 箱𝑦𝑖 から玉𝑥𝑖 が取り出される確率 𝑃(𝑥𝑖 , 𝑦𝑖 |𝜃) ◦ 玉𝑥𝑖 が取り出されたとき，元の箱が𝑦𝑖 であっ た確率 𝑃(𝑦𝑖 |𝑥𝑖 , 𝜃) 24

EMアルゴリズムの原理 ◦Q関数 𝑄 𝜃 𝜃0 = ෍ ෍ 𝑃 𝑦 𝑥𝑖 , 𝜃0 log 𝑃(𝑥𝑖 , 𝑦|𝜃) 𝑖 𝑦 ◦これを最大にする𝜃を求める 𝜃෨ = arg max 𝑄(𝜃|𝜃0 ) 𝜃 ෨ ◦求めた𝜃を𝜃 0 とおいて推定を繰り返す 25

「箱と玉」の場合の例 ◦𝜃 = 𝜆1 , 𝜆2 , 𝜃0 = 𝜆10 , 𝜆02 ◦ 𝑄 𝜃 𝜃0 = σ𝑖 σ𝑘 𝑃 𝑘 𝑥𝑖 , 𝜃0 log 𝑃(𝑘, 𝑥𝑖 |𝜃) 𝜆0𝑘 𝑃(𝑥𝑖 |𝐵𝑘 ) ◦= σ𝑖 σ𝑘 σ 0 log 𝜆𝑘 𝑃(𝑥𝑖 |𝐵𝑘 ) 𝑗 𝜆𝑗 𝑃(𝑥𝑖 |𝐵𝑗 ) ◦制約条件 𝜆1 + 𝜆2 = 1 ◦𝐿 = 𝑄 𝜃 𝜃0 − 𝛾(1 − σ𝑘 𝜆𝑘 ) 𝜕𝐿 ◦ = 0を解く 𝜕𝜆𝑘 26

演習 前のページの式を解いて、答えが 21ページの式になることを確かめな さい。 ◦λk0とλkは違うものであることに注意 （λk0は単なる定数） ◦Lをλkで微分して0とおき、λkについて 解く ◦ このときのλkがλk1になる 27

GMMのパラメータ推定 ◦𝜃 = 𝜇1 , … , 𝜇𝐾 , 𝜎12 , … , 𝜎𝐾2 , 𝜆1 , … , 𝜆𝐾 2 σ ◦𝑝 𝑥 𝜃 = 𝑘 𝜆𝑘 𝑁(𝑥 ; 𝜇𝑘 , 𝜎𝑘 ) ◦𝑝 𝑥, 𝑘 𝜃 = 𝜆𝑘 𝑁(𝑥; 𝜇𝑘 , 𝜎𝑘2 ) ◦𝑝 𝑘 𝑥, 𝜃 𝜆𝑘 𝑁(𝑥;𝜇𝑘 ,𝜎𝑘2 ) =σ 2 𝜆 𝑁(𝑥;𝜇 ,𝜎 𝑘 𝑘 𝑘 𝑘) ◦𝑄 𝜃 𝜃0 = σ𝑖 𝑝 𝑘 𝑥𝑖 , 𝜃0 log 𝑝(𝑥𝑖 , 𝑘|𝜃) ◦制約 σ𝑗 𝜆𝑗 = 1 28

GMMのパラメータ推定 ◦ 𝐿 = 𝑄 𝜃 𝜃0 + 𝜉 1 − σ𝑗 𝜆𝑗 →max ◦ 注意： 𝑥−𝜇𝑘 2 1 2 2 log 𝜆𝑘 𝑁 𝑥; 𝜇𝑘 , 𝜎𝑘 = log 𝜆𝑘 − − log(2𝜋𝜎 2 𝑘) 2𝜎𝑘 ◦ 𝛾𝑖𝑘 = 𝑝 𝑘 𝑥𝑖 , 𝜃0 = 0 𝜆0𝑘 𝑁 𝑥𝑖 ;𝜇𝑘 , 𝜎𝑘0 2 2 σ𝑗 𝜆0𝑗 𝑁 𝑥𝑖 ;𝜇𝑗0 , 𝜎𝑗0 2 とおく 𝛾𝑖𝑘 は𝑥𝑖 のk 番目の分布への「帰属度」 29

GMMのパラメータ推定 𝜕𝐿 ◦ = 0 より 𝜕𝜇𝑘 𝑥𝑖 − 𝜇𝑘 ෍ 𝛾𝑖𝑘 =0 𝜎𝑘 𝑖 σ𝑖 𝛾𝑖𝑘 𝑥𝑖 𝜇𝑘 = σ𝑖 𝛾𝑖𝑘 30

GMMのパラメータ推定 𝜕𝐿 ◦ 2 = 0より 𝜕𝜎𝑘 𝑥𝑖 − 𝜇𝑘 2 − 𝜎𝑘2 ෍ 𝛾𝑖𝑘 =0 2 2𝜎𝑘 𝑖 2 σ 𝛾 𝑥 − 𝜇 𝑘 𝑖 𝑖𝑘 𝑖 2 𝜎𝑘 = σ𝑖 𝛾𝑖𝑘 31

GMMのパラメータ推定 𝜕𝐿 ◦ = 0 より 𝜕𝜆𝑘 𝛾𝑖𝑘 ෍ −𝜉 =0 𝜆𝑘 𝑖 1 1 𝜆𝑘 = ෍ 𝛾𝑖𝑘 = ෍ 𝛾𝑖𝑘 𝜉 𝑁 𝑖 𝑖 32

実施例 33

実施例 34

実施例 35