1. No category

第９章
混合モデルとEM
Lab seminer 10/17
MASANORI MIZUGUCHI
K-meansアルゴリズム
データ集合 𝑋1 , … , 𝑋𝑁 をK個のクラスターに分割することが目的
• K個のD次元ベクトル𝜇𝑘 （プロトタイプ）を導入する
（𝜇𝑘 ：クラスターの中心を表す）
• 𝑋𝑛 がクラスターｋに分類されるとき𝑟𝑛𝑘 = 1, 𝑗 ≠ 𝑘では𝑟𝑛𝑗 = 0
（1-of-K符号化法）
データ点からそれが割り当てられたベクトル𝜇𝑘 までの二乗距離は、
𝑁
𝐾
𝐽=
𝑟𝑛𝑘 𝑋𝑛 − 𝜇𝑘
2
(9.1)
𝑛=1 𝑘=1
2
K-meansアルゴリズム
Jを最小にする 𝑟𝑛𝑘 と 𝜇𝑘 を求めればよい
𝜇𝑘 の初期値を選ぶ → 𝜇𝑘 を固定し、𝑟𝑛𝑘 についてJを最小化
↓収束まで繰り返し↑
𝑟𝑛𝑘 を固定し、𝜇𝑘 についてJを最小化
最初のステップ：E(expectation)ステップ
次のステップ：M(maximization)ステップ と呼ばれる
3
K-meansアルゴリズム
𝑁
𝐽=
𝐾
𝑟𝑛𝑘 𝑋𝑛 − 𝜇𝑘
2
初めに𝑟𝑛𝑘 を考える
𝑛=1 𝑘=1
• 異なるｎを含む項は互いに独立
→ｎ番目のデータ点を、中心がそれに最も近いクラスター中心
に割り当てる
𝑟𝑛𝑘
1 𝑘 = argmin𝑗 𝑋𝑛 − 𝜇𝑘
=
0 それ以外
2
4
K-meansアルゴリズム
次に𝑟𝑛𝑘 を固定した下での𝜇𝑘 の最適化を考える
• Jは𝜇𝑘 の二次関数で、𝜇𝑘 に関する偏微分を０と置き最適化出来る
𝑁
𝜕𝐽
=2
𝑟𝑛𝑘 (𝑋𝑛 − 𝜇𝑘 ) = 0
𝜕𝜇𝑘
𝑛=1
𝜇𝑘 について解くと、
𝜇𝑘 =
𝑛 𝑟n𝑘 𝑋n
𝑛 𝑟n𝑘
⇒𝜇𝑘 はｋ番目のクラスターに割り当てられたデータの平均値
5
K-meansアルゴリズム
2クラスターに分割する例
(a)×印はμ1とμ2の初期選択を表す
(b)各データを近いクラスターに割り当てる（垂直２等分性）
(c)割り当てられたデータの平均値をクラスターの中心とする（×印）
(d)～(ｇ)収束するまで繰り返す
Old Faithful間欠泉データ集合を用いたK-meansアルゴリズムの説明
6
K-meansアルゴリズム
K-meansアルゴリズムをそのまま実装すると、比較的速度が遅いこと
がある
• 近くにあるデータ点同士が、同一の木に属する木構造を利用して、
データ構造をあらかじめ計算する
• 距離の三角不等式を利用して不必要な距離計算を省く
などの方法が提案されている
7
画像分割と画像圧縮
• 画像分割の目的は、一つの画像を複数の領域に分割すること
• 画像の画素は、赤,青,緑の３原色からなる３次元空間の１点
下図は、K色のパレットを用いた画像であり、各画素ベクトルを、それ
が割り当てられたクラスターの色に置き換えている
K-meansクラスタリングアルゴリズムを画像分割に適用した例
8
画像分割と画像圧縮
• N個のデータ点の、クラスターのインデックスｋのみを保存する
→各データ点を最も近い中心𝜇𝑘 で近似する
• ベクトル量子化と呼ばれる
歪みはあるが、高レベルの圧縮が可能
9
混合ガウス分布
離散的な潜在変数を用いた混合ガウス分布の定式化を行う
K
p(x)    k N(x  k ,k )
k1
• K次元の2値確率変数zを導入 𝑧𝑘 ∈ 0,1 かつ
1つのZkだけ1、他は0の1-of-K符号化法
𝑘 𝑧𝑘
=1
• ｚの周辺分布は、混合係数  kによって定められる

ただし、  k は 0   k  1,
p(zk 1)   k
K

k
 1 を満たす
k1
10
混合ガウス分布
• ｚには1-of-K符号化法を用いるので、次のようにも書ける
K
p(z)    kzk
k1
• ｚが与えられたときのｘの条件付き分布は次のガウス分布
p(x zk 1)  N(x k ,k )

• これは、上と同様に次のように書き換えられる
K

p(x z)   N(x k ,k ) zk
k1
11
混合ガウス分布
• 同時分布は、 p( z ) p( x z ) で与えられる
• Xの周辺分布は、zの取り得る状態全ての総和を取り、次のようになる
K
p(x)   p(z) p(x z)    k N(x k ,k )
z
k1
これは，混合ガウス分布と同じ形
潜在変数z

nを含む別な混合ガウス分布の表現をした
12
混合ガウス分布
Xが与えられた下でのzの条件付き確率γ(zk)について考える
• ベイズの定理を用いて、
 (zk )  p(zk  1 x) 
p(x zk  1) p(zk  1)

p(x)
p(zk  1) p(x zk  1)
K
 p(z
j1

j
 1) p(x z j  1)

 k N(x k ,k )
K

j
N(x  j , j )
j1
• πkはzk=1なる事象の事前確率、γ(zk)はxを観測したときの事後確率
• γ(zk)は，混合要素kがxの観測を説明する度合いを表す負荷率
13
混合ガウス分布
混合ガウスモデルに従うランダムサンプルを生成する
(a) 同時分布p(z)p(x|z)からのサンプル
• 混合要素に対応するZの状態を赤,緑,青で描写
(b) 同サンプルを周辺分布(x)から生成
• Zの値を無視し、xの値のみ描写
(c) 同サンプルの負担率γ(znk)を表現
• γ(znk)(k=1,2,3)に比例する量の赤,青,緑のインクでプロット
３つのガウス分布の混合から生成した５００点の例
14
最尤推定
観測したデータ集合{x1,…xN}に混合ガウス分布を当てはめる
• 混合ガウス分布 p(x) 
K
 N(x  , ) なので、対数尤度関数は
k
k
k
k1
 K

ln p(X  , ,)   ln  k N(x n k ,k )

n1 k1
N


15
混合ガウス分布のEMアルゴリズム
EMアルゴリズム
：潜在変数を持つモデルの最尤解を求めるための強力な方法
ここでは、混合ガウスモデルにおいてEMアルゴリズムの意義を説明
• 尤度関数の最大点において満たされるべき条件を書く
• 対数尤度lnp(X|π,μ,Σ)をガウス要素の平均μkに関して微分し、0とおく
1
 k N(x n k ,k )
0
(x n  k )

k
n1  j  j N(x n  j , j )
N
 (znk )
16
混合ガウス分布のEMアルゴリズム
• 負担率γ(znk)が右辺に現れている
• 両辺にΣkを掛けて整理すると
N
1 N
k    (znk )x n , N k   (znk )
N k n1
n1
（Nk：k番目クラスターに割り当てられたデータの実効的な数）
• ｋ番目の要素の平均μkはデータ集合各点の重み付き平均とわかる

重み因子はｋ番目のガウス要素がxnを生成を負担した事後確率γ(znk)
17
混合ガウス分布のEMアルゴリズム
• 対数尤度lnp(X|π,μ,Σ)をΣkに関して微分して0とおき，整理すると
1 N
T
k 

(z
)(x


)(x


)

nk
n
k
n
k
N k n1
共分散でも
•
•
各データ点は対応する事後確率γ(znk)で重み付けられており、

分母はk番目要素に割り当てられたデータの実効的な数
であるとわかる
18
混合ガウス分布のEMアルゴリズム
最後に、対数尤度lnp(X|π,μ,Σ)を混合係数πkについて最大化する
• 各パラメータの総和が1であるという制約条件(P.10)がある
→ラグランジュ未定係数法を用いる
 K

ln p(X  , ,)    k 1
k1

• 上式をπk(k=1,…K)で微分し0とおくと
N
N(x n k ,k )
0


n1  j  j N(x n  j , j )
19
混合ガウス分布のEMアルゴリズム
• 両辺にπkを掛けてkについて和を取り、制約条件k1 k  1を用いると、
λ=−Nが得られる
• これを用いてλを消去し、変形すると

Nk
k 
N
K
• k番目要素の混合係数は、全データ点に対する負担率の平均である

20
混合ガウス分布のEMアルゴリズム
これまでに求めたμk,Σk,πkによって、最尤推定問題の解を、単純な手続
きで求められる（EMアルゴリズム）
μk,Σk,πkの
適当な初期値を選ぶ
→
初期値を用いて
事後確率（負担率）を計算
Eステップ
→
←
事後確率に基づき
μk,Σk,πkを再計算
Mステップ
対数尤度、またはパラメータの変化量が閾値より小さくなったとき
収束したとする
21
混合ガウス分布のEMアルゴリズム
混合ガウス分布についてのEMアルゴリズムを、Old Faithful間欠泉
データ集合に適用した例を示す
(a)緑はデータ点 青と赤の円は、ガウス分布の標準偏差の等高線
(b)青と赤の両クラスターの負担率に比例した量のインクで描写
(c)青のガウス分布の平均は，各データ点が持つ青インクの重み付き平均(重心)
共分散は、インクの共分散である
22
混合ガウス分布のEMアルゴリズム
• EMアルゴリズムは、K-meansアルゴリズムに比べ、
• 収束までに必要な繰り返し回数が多い
• １度の繰り返しの計算量が多い
⇒混合ガウスモデルの初期値を発見するために，K-meansを実行し
た後，EMアルゴリズムを行う
• 共分散Σkの初期値 K-meansアルゴリズムによるクラスターのサンプル分散
• 混合係数πkの初期値 各クラスターに属する点の割合
23
EMアルゴリズムのもう一つの解釈
EMアルゴリズムの目的は、潜在変数を持つモデルについて最尤解を
見つけること
• 観測データの集合をX、潜在変数の集合をZ、パラメータをθとする
• 対数尤度は次のようになる


ln p(X  )  ln p(X,Z  )
 z

• Xの各観測において、実際には見えない潜在変数Zの値がもらえると
すると（完全データ）、対数尤度は単純に ln p( X , Z  ) という形を取り、
簡単に最大化できる

24
EMアルゴリズムのもう一つの解釈
完全データ尤度関数が使えないので、潜在変数の事後確率に関する
期待値を考える（Eステップ）
• 潜在変数の事後分布p(Z|X,θold)の計算に現在のパラメーターをθold用いる
• この事後分布を、完全データ対数尤度lnp(X,Z|θ)の期待値Q(θ,θold)を計
算するのに用いる
Q(, old )   p(Z X, old )ln p(X,Z  )
z
Mステップ
• Q(θ,θold)をθについて最大化し、新たな推定値θnewを得る

 new  arg max Q(, old )

25