狠狠撸

狠狠撸Share a Scribd company logo
GMM勉強会@森島研
Hayato OHYA
本日のお題
? EMアルゴリズムについて:大矢担当
? 多次元版GMMについて
– 資料は作る予定(15日現在)
– その場でPRML読みながらみんなで
? ノンパラ化
– 持橋さんの資料とか見る
– 増田君にアドバイスもらいつつみんなでがんばる
? プログラム実装
– できるのかね?
– まあやってみよう
参考図書
? Pattern Recognition and Machine Learning [Bishop]
– 言わずと知れたPRML
? 言語処理のための機械学習入門 [奥村?高村]
– 日本語でとってもわかりやすい本
? パターン認識と機械学習の学習 [光成]
– サイボウズラボが出しているPRMLの副読本
? 統計のための行列代数上?下 [ハーヴィル]
– 行列演算についてしっかり書かれた本
– 早稲田構内から原著はDL可
※もし私費で買う場合私のリンクから購入してくれるとうれしいです(アフィリエイト(笑))
http://8810008.web.fc2.com/research/books.html
注意
? 大矢がこの1週間で勉強したことを話すだけなので、
間違っている可能性があります
? 疑問点や間違っていそうな点がありましたら、
適宜つっこみを入れてください
– 答えられるとは限らない
? 基本的なことは結構飛ばして書いてます
EMアルゴリズム概要
? クラスタリングによく使われる
? EMアルゴリズムとは枠組みである
– EMアルゴリズムのライブラリは存在しない
? ある確率分布についてEMアルゴリズムを再現したもの
– GMMはEMアルゴリズムの一種
? たとえば
Expectation(E-step):クラスの期待値を求める
Maximization(M-step):ガウス函数のパラメータを求める
EMアルゴリズム
? 混合ガウス分布を使ったクラスタリングを考える
– K-meansとは違い、クラスに入る確率が計算できる
? 使うもの
なんかのデータ(たとえば特徴ベクトル) :?(?)
∈ ?
クラスタ(K個のうちのとあるクラスタc):? ∈ ?
分布のパラメータ(ポアソン分布の平均とか):?, ?′
なんかの確率分布:?(?|?)
対数尤度 ?(?)∈? log?(?, ? ? ; ?) を最尤推定で最大化したい
→ cが未知なのでできない
そこでまず、事前に計算した?′を利用して?(?|?(?); ?′)を計算
これを重みとして、
Σ ? ? ∈?log? ?, ?(?); ? → Σ ? ? ∈?Σ ? ?(?|?(?); ?′)log? ?, ?(?); ?
を最大化する
? ?; ?′
= Σ ? ? ∈?Σ ? ?(?|?(?)
; ?′)log? ?, ?(?)
; ?
?函数について
? ?; ?′
= Σ ? ? ∈?Σ ? ?(?|?(?)
; ?′)log? ?, ?(?)
; ?
? 変数:?
? 他はすべて定数
– ?(?|?(?); ?′)とか
EMアルゴリズム
入力:データ?
?の初期値をてきとーに決める
Until収束
E-step:??(?)
∈ ?, ??: ? ? ? ?
; ?′
ーデータがどの程度クラスタ?に所属しているか
M-step:? ??? = argmax ? ?(?|?′)
?′ = ? ???
End until
確率分布がガウス函数の場合
? ? ?
?; ? =
1
2??2 ?
exp(?
? ? ? ? ?
2
2?2
)
? ?について最大化すると、
?? ?; ?′
?? ?
=
?
?? ?
? ? ∈? ?
?(?|? ? ; ?′)log?(?)? ?(?)|?; ?
=
?
?? ?
? ? ∈?
?(?|? ?
; ?′)logexp ?
? ? ? ? ?
2
2?2
=
? ? ∈?
?(?|? ?
; ?′
)
? ?
? ? ?
?2
→ 0
∴ ? ? =
Σ ? ? ∈D ? ? ? ? ; ?′ ? ?
Σ ? ? ∈D ? ? ? ? ; ?′
→ これがM-stepの計算式
? ? はmarginal distributionを使って、
? ? =
1
?
? ? ∈D
?(?|??; ?′)
となる。
???はずなんだけど、証明ができないぞ(??ω?`)
? E-step
? ? ? ? ; ?′ =
? ? ? , ?; ?′
? ?(?); ?′
=
? ? ? , ?; ?′
? ? ∈?
? ?(?), ?; ?′
=
? ? ? |?; ?′ ?(?)
? ? ∈?
? ? ? |?; ?′ ?(?)
混合ガウス分布
? ガウス函数(多次元)
? = ? ? ?, Σ =
1
2?
? Σ ?
1
2exp ?
1
2
? ? ? ?Σ?1 ? ? ?
? 離散的な潜在変数を用いた混合ガウス分布の定式化
?次元2値変数?を考える(一つの成分のみが1で他は全て0)
?
? ? = 1
? ? ? = 1 = ? ? (0 ≤ ? ? ≤ 1)
? ? ? =
?
? ?
? ?
? ? ? ? = 1 = ?(?|? ?, Σk)
? ? ? ? =
?
? ?|? ?, Σ ?
? ?
以上より、
? ? =
?
?(?, ?) =
?
? ? ?(?|?)
z
x
なぜグラフィカルモデル使うの?
? 今回の場合は変数が単純だが、
(LDAなど)対応関係が複雑になった場合には、
変数の対応関係が見やすくなる
? 参考
http://www.slideshare.net/Kawamoto_Kazuhiko/ss-35483453
? ? =
? ?
? ? ?(?|?k, Σ ?) ? ?
? ?はどれか一つのみが1
?=
?
? ? ?(?|? ?, Σ ?)
? ?の条件付き確率? ? ? = 1|? ≡ γ zk を考える
? ? ? =
? ?, ? ? = 1
? ?
=
? ?, ? ? = 1
Σj ?(?, ? ? = 1)
=
? ? ? = 1 ? ? ? ? = 1
? ? ?? = 1 ?(?|? ? = 1)
=
? ? ? ? ? ?, Σ ?
? ? ? ? ? ? ?, Σ ?
→ 混合要素?が観測値?に対する負担率
EM Algorithm for Gaussian Mixture Model
データ集合:? ? = ?1, … , ? ? (? × ????)
対応する潜在変数:? ? = ?1, … , ? ? ? × ????
? 対数尤度函数の最大点の条件を求める
? = log ? ? ?, ?, Σ =
?=1
?
log(
?=1
?
?? ? ? ? ? ?, Σ?))
? ?について最大化
?
??
log? ? ?, Σ =
?
??
(?
1
2
? ? ? ?Σ?1(? ? ?))
= Σ?1 ? ? ?
∴
?
??
? = ? ?
?
?? ?
log? = ? ? Σ?1(? ? ?)
??? = ?(? ?|? ?, Σ ?)と置くと、
?
?? ?
? =
?
(
? ?
????
?? ?
? ?? ? ??
) =
?
? ? ? ??
? ?? ???
?
?? ?
log???
=
?
? ? ??
?
?? ?
log???
= Σ?1
(
?
?(? ??)(? ? ?)) → 0
∴
?
? ? ?? ? ? ?
?
? ? ?? ? ? = 0
?? = ? ?(? ??)と置くと、
? ? =
1
??
?
? ? ?? ? ?
? 次にΣ ?についての微分を考える
? = ?(?|?, Σ)と置くと、
log? = ?
?
2
log 2? ?
1
2
log Σ ?
1
2
tr(Σ?1
? ? ? ? ? ? ?
)
?
?Σ ?
log? = ?
1
2
Σ?1 +
1
2
Σ?1 ? ? ? ? ? ? ?Σ?1
?
?Σ ?
? =
?
? ? ??
?
?Σ ?
log? ??
=
?
? ? ?? ?
1
2
Σ?1 +
1
2
Σ?1 ? ? ? ? ? ? ?Σ?1 → 0
∴
?
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ?
?Σ ?
?1
= 0
? Σ ? =
1
??
?
? ? ?? ? ? ? ? ? ? ? ? ? ?
?
? ? ?に関する微分を考える
? ? ? = 1の制約があるので、
? = ? + ?(
?
? ? ? 1)
とすると、
?
?? ?
? =
?
? ??
? ?? ? ??
+ ? =
?
? ? ??
? ?
+ ? =
??
? ?
+ ? → 0
? ?? = ??? ?
? ? =
?
?? =
?
??? ? = ??
∴ ? ? =
??
??
=
??
?
EM for Gaussian Mixtures
1. テキトーに? ?, ? ?, ? ?を初期化
for
2. E-step:?(? ??)を計算
3. M-step: ? ?, ? ?, ? ?を計算
4. 対数尤度を計算
log? ? ?, ?, ? =
?=1
?
log{
?=1
?
? ? ? ? ? ? ?, ? ?)}
If flag == true:
break;
これをノンパラ化したい(??ω?缚)
EM for Gaussian Mixturesのんぱら!
1. テキトーに? ?, ? ?, ? ?を初期化;?をたくさん用意する
for
2. E-step:?(? ??)を計算
3. M-step: ? ?, ? ?, ? ?を計算
– 一定値以下の? ?を切り捨てる
4. 対数尤度を計算
log? ? ?, ?, ? =
?=1
?
log{
?=1
?
? ? ? ? ? ? ?, ? ?)}
If flag == true:
break;
のんぱらNMFの場合
? ?
?=1
?
? ?
> ?????. → ? ?生き残る
? ?
?=1
?
? ?
< ?????. → ?kを消す or 残して計算はしない
ガンマ分布を事前分布に与えて、
変分ベイズとか使って事後分布を近似を求める
参考
http://biometrics.cse.msu.edu/Publications/Clustering/Mallapra
gadaJinJain_NonparametricMixtureModels_SSSPR10.pdf
http://www.hua.edu.vn/khoa/fita/wp-
content/uploads/2013/08/Pattern-Recognition-and-Machine-
Learning-Christophe-M-Bishop.pdf

More Related Content

骋尘尘勉强会