EMアルゴリズム Expectation and Minimization Algorithm 渡辺澄夫今日は、少し数式を使います・・・。 2015/9/30 Mathematical Learning Theory 1 混合正規分布 K ∑ ak = 1 w = (ak , bk ,σk) K p(x|w) = ∑ ak k=1 k=1 1 2 N/2 (2πσk ) exp( － || x – bk ||2 2σk 2 ) 2 平均 bk ,分散σk の正規分布 2015/9/30 Mathematical Learning Theory 2 EMアルゴリズム（簡単版） w = (bk ) ak =1/K , σk=1 山の大きさ形は同じで中心だけ最適化 (1) ●初期化 (2) ● 分類 (3) ●を●へ移動繰り返し 2015/9/30 Mathematical Learning Theory 3 隠れ変数（潜在変数） K p(x|w) = ∑ ak k=1 1 2 N/2 (2πσk ) exp( － || x – bk || 2σk 2 2 ) y について周辺化 K p(x,y|w) = Π [ ak k=1 1 (2πσk2) N/2 exp( － || x – bk ||2 2σk 2 )] yk y = (y1,y2,..,yK) は、どれかひとつだけ１で残りは０ 2015/9/30 Mathematical Learning Theory 4 隠れ変数 <= 確率競合 K p(x,y|w) = Π [ ak k=1 1 2 N/2 (2πσk ) exp( － || x – bk ||2 2σk 2 )] yk (定数項は省略） K 2 = exp[－Σ yk {||x-bk|| /2σk2 – Nlogσk+ log ak｝] k=1 ついたり消えたり ⇒平均すると混合分布 (y1,y2,..,yK) = (1,0,..,0), (0,1,0,..,0), ..,(0,0,..,1) 2015/9/30 Mathematical Learning Theory 5 準備任意の w1 , w2 について ∫ p(y| w1) log p(y|w2) dy≦∫ p(y| w1) log p(y|w1) dy なぜならカルバック情報量の性質 ∫ p(y| w1) log [p(y|w1)/ p(y|w2) ] dx ≧0 2015/9/30 Mathematical Learning Theory 6 EM法 n L(w)=Σ log p(xi|w) を最大にする w を求めたい i=1 方法 n G(w1,w2)=Σ Σy p(y| xi, w1) log p(xi,y | w2) i=1 (1) w1 初期化 (2) G(w1,w2)を w2 について最大化(w1 固定） (3) w１：＝w２として(2)に戻る。 2015/9/30 Mathematical Learning Theory 7 EM法の損失関数 n G*(w1,w2)= G(w1,w2)－ΣΣy p(y| xi, w1) log p(y|xi, w1) i=1 n ＝ΣΣy p(y| xi, w1) { log p(xi,y | w2)ー log p(y|xi, w1)｝ i=1 n =ΣΣy p(y| xi, w1) {log p(xi | w2) +log p(y|xi, w2) i=1 －log p(y|xi, w1) } n n i=1 i=1 2015/9/30 Mathematical Learning Theory =Σlog p(xi | w2) + ΣΣy p(y| xi, w1) log p(y|xi, w2) p(y|xi, w1) 8 EM法は何をしているか n G*(w1,w2)= G(w1,w2)－ΣΣy p(y| xi, w1) log p(y|xi, w1) i=1 n n =Σlog p(xi | w2) + ΣΣy p(y| xi, w1) log i=1 i=1 L(w2 ) w2=w1 p(y|xi, w2) p(y|xi, w1) のとき最大 L(w) がw*で最大⇔ G*(w1,w2)がw1=w2 =w*で最大 2015/9/30 Mathematical Learning Theory 9 EM法でなぜ尤度は大きくなるか n G*(w1,w2)= G(w1,w2)－ΣΣy p(y| xi, w1) log p(y|xi, w1) n i=1 n =Σlog p(xi | w2) + ΣΣy p(y| xi, w1) log i=1 i=1 p(y|xi, w2) p(y|xi, w1) (1) w1 初期化 (2) G(w1,w2)を w2 について最大化 G*(w1,w2)増加 G*(w1,w2)増加 (3) w１：＝w２として(2)に戻る。 G*(w1,w2)は増加L(w1) が大きくなっていく。 2015/9/30 Mathematical Learning Theory 10 EM法の実現 n G(w1,w2)=Σ Σy p(y| xi, w1) log p(xi,y | w2) i=1 K 2 log p(x,y|w) = －Σ yk {||x-bk|| /2σk2 – Nlogσk+ log ak｝ k=1 Σy yk p(y| xi, w) = Σy yk p(xi, y| w)/p(xi|w) 2 || x – b || k 1 i = ak exp( － 2σ 2 ) 2 N/2 = E[yk| xi , w] (2πσk ) k p(xi|w1) 2015/9/30 Mathematical Learning Theory とおく 11 EM法の実現 n G(w1,w2)=Σ Σy p(y| xi, w1) log p(xi,y | w2) i=1 n K 2 =－Σ Σ E[yk| xi , w1]{||x-bk|| /2σk2 – Nlogσk+ log ak｝ i=1 k=1 w1 が与えられたもとでこれを最大化 2015/9/30 Mathematical Learning Theory 12 EM法の実現 Σはすべてi=1,..,n の和を表す Σ E[yk| xi , w1] ak = bk= 2 σk = 2015/9/30 Σ1 w1 → w2 が計算できる Σ E[yk| xi , w1] xi Σ E[yk| xi , w1] Σ E[yk| xi , w1] || xi － bk || 2 NΣ E[yk| xi , w1] Mathematical Learning Theory 13 EM法の解釈 E[yk| xi , w] = ak || xi – bk ||2 1 2 N/2 (2πσk ) exp( － 2σ 2 k ) p(xi|w1) データ xi が k 番目のコンポーネントから出た確率面積 ak bk σk xi 2015/9/30 Mathematical Learning Theory 14 問題 EMアルゴリズムを1回動かすと各パラメータは、どのようになるか図示せよ。 b1 a1 面積 b2 σ1 a2 σ2 2015/9/30 Mathematical Learning Theory 15