EMアルゴリズム

• 応用おうよう数学すうがく > 統計とうけい学がく > EMアルゴリズム
• データサイエンス > 機械きかい学習がくしゅう > EMアルゴリズム

EMアルゴリズム（英えい: expectation–maximization algorithm）とは、統計とうけい学がくにおいて、確かく率りつモデルのパラメータを最さい尤ゆう推定すいていする手法しゅほうの一ひとつであり、観測かんそく不可能ふかのうな潜在せんざい変数へんすうに確かく率りつモデルが依存いぞんする場合ばあいに用もちいられる。EM法ほう、期待きたい値ち最大さいだい化か法ほう（きたいちさいだいかほう）とも呼よばれる。その一般いっぱん性せいの高たかさから、機械きかい学習がくしゅう、音声おんせい認識にんしき、因子いんし分析ぶんせきなど、広汎こうはんな応用おうようがある。

EMアルゴリズムは反復はんぷく法ほうの一種いっしゅであり、期待きたい値ち(英えい: expectation, E) ステップと最大さいだい化か (英えい: maximization, M)ステップを交互こうごに繰くり返かえすことで計算けいさんが進行しんこうする。Eステップでは、現在げんざい推定すいていされている潜在せんざい変数へんすうの分布ぶんぷに基もとづいて、モデルの尤ゆう度どの期待きたい値ちを計算けいさんする。Mステップでは、E ステップで求もとまった尤ゆう度どの期待きたい値ちを最大さいだい化かするようなパラメータを求もとめる。M ステップで求もとまったパラメータは、次つぎの E ステップで使つかわれる潜在せんざい変数へんすうの分布ぶんぷを決定けっていするために用もちいられる。

概要がいよう

セッティング・目標もくひょう

今いま、2値ちx、zを取とる確かく率りつ分布ぶんぷがあり、その確かく率りつ分布ぶんぷの確かく率りつ密度みつど関数かんすう$p(x,z|\theta )$が未知みちの母はは数すう$\theta \in \mathbb {R} ^{m}$によりパラメトライズされているとする。ここで$\mathbb {R}$は実数じっすう全体ぜんたいの集合しゅうごうを表あらわす。

そして$p(x,z|\theta )$に従したがって標本ひょうほん$(x_{1},z_{1}),\ldots ,(x_{n},z_{n})$を独立どくりつに抽出ちゅうしゅつしたものの、何なんらかの事情じじょうで$Z=(z_{1},\ldots ,z_{n})$の値ねは観測かんそくできず、$X=(x_{1},\ldots ,x_{n})$だけが観測かんそくできたとする。実じつ応用おうよう上じょうは例たとえば、$\theta =(\theta _{1},\theta _{2})$という形かたちをしており、まず観測かんそく不能ふのうな$z_{i}\sim p_{1}(z|\theta _{1})$が選えらばれた後のち、$z_{i}$に依存いぞんして観測かんそく可能かのうな$x_{i}\sim p_{2}(x|\theta _{2},z_{i})$が選えらばれる、といったケースにEMアルゴリズムが使つかわれる事ことが多おおいが、必かならずしもこのケースにあてはまらなくてもよい。

簡単かんたんの為ため、記号きごうを混用こんようしてX、Zの同時どうじ確かく率りつ分布ぶんぷの確かく率りつ密度みつど関数かんすうも$p(X,Z|\theta )$と書かく。以下いかではZが離散りさん変数へんすうの場合ばあいについて説明せつめいするが、Zが連続れんぞく変数へんすうの場合ばあいも総和そうわを積分せきぶんに置おき換かえる以外いがいは同様どうようである。

このような状況じょうきょうにおいて母はは数すうθしーたを最さい尤ゆう推定すいていする事ことが我々われわれの目標もくひょうである。しかしZを知しらない場合ばあいの$X=(x_{1},\ldots ,x_{n})$に関かんする対数たいすう尤ゆう度ど

$\ell (\theta |X):=\log p(X|\theta )=\log \sum _{Z}p(X,Z|\theta )$

を最大さいだい値ちを直接ちょくせつ計算けいさんするのは一般いっぱんには簡単かんたんではない。

EMアルゴリズムは、反復はんぷく法ほうにより、数列すうれつ${\hat {\theta }}^{(t)}$で対数たいすう尤ゆう度ど$\ell ({\hat {\theta }}^{(t)}|X)$が単調たんちょう非ひ減少げんしょうであるものを作つくるアルゴリズムである。最さい尤ゆう推定すいてい量りょうを${\hat {\theta }}_{\mathrm {MLE} }$とすると、

$\ell ({\hat {\theta }}_{\mathrm {MLE} }|X)\geq \ell ({\hat {\theta }}^{(t)}|X)$

である事ことから、$\ell ({\hat {\theta }}_{\mathrm {MLE} }|X)$が有限ゆうげんであれば$\ell ({\hat {\theta }}^{(t)}|X)$の単調たんちょう性せいより$\ell ({\hat {\theta }}^{(t)}|X)$は必かならず収束しゅうそくする。

アルゴリズム

EMアルゴリズムでは、以下いかの手順てじゅんにより数列すうれつ${\hat {\theta }}^{(0)},{\hat {\theta }}^{(1)},\ldots$を作つくる。

• 初期しょき値ち${\hat {\theta }}^{(0)}$を（何なんらかの方法ほうほうで）選えらぶ。
• $t=0,1,\ldots$に対たいして以下いかを実行じっこうする
  • E ステップ: $p(Z|X,{\hat {\theta }}^{(t)})$を求もとめる。
  • M ステップ: ${\hat {\theta }}^{(t+1)}={\underset {\theta }{\operatorname {arg\,max} }}\ Q(\theta |{\hat {\theta }}^{(t)})\,$を求もとめる。

ここでQは対数たいすう尤ゆう度ど関数かんすう$\log p(X,Z|\theta )$のZに関かんする条件じょうけん付つき期待きたい値ち

$Q(\theta |\theta ^{(t)}):=\operatorname {E} _{Z|X,{\hat {\theta }}^{(t)}}{\big [}\log p(X,Z|\theta ){\big ]}=\sum _{Z}p(Z|X,{\hat {\theta }}^{(t)})\log p(X,Z|\theta )\,$ 　

である。実じつ応用おうよう上じょうは、${\hat {\theta }}^{(t)}$の値ねが十分じゅうぶん小ちいさくなったと判定はんていする何なんらかの条件じょうけんを事前じぜんに定さだめておき、その条件じょうけんを満みたしたら上述じょうじゅつのループを終了しゅうりょうする。ループを終了しゅうりょうする条件じょうけんは、パラメータ値ちや対数たいすう尤ゆう度ど関数かんすうを使つかって定さだめられる。

留意りゅうい点てん

EステップとMステップの切きれ目めは書籍しょせきにより異ことなるので注意ちゅういが必要ひつようである。本ほん項こうでは次節じせつの議論ぎろんと整合せいごう性せいをとる為ために文献ぶんけんの切きれ目めに従したがったが、文献ぶんけんでは$Q(\theta |{\hat {\theta }}^{(t)})$を計算けいさんする所ところまでがEステップであり、$Q(\theta |{\hat {\theta }}^{(t)})$の$\operatorname {arg\,max}$を取とるところだけがMステップである。

ステップの名称めいしょう「E」と「M」はそれぞれExpectation(期待きたい値ち)、Maximization（最大さいだい化か）の略りゃくであり、文献ぶんけんのようにEステップで$Q(\theta |{\hat {\theta }}^{(t)})$を求もとめる為ために期待きたい値ちを計算けいさんし、Mステップで$Q(\theta |{\hat {\theta }}^{(t)})$の$\operatorname {arg\,max}$を取とるところに名称めいしょうの由来ゆらいがある。

動作どうさ原理げんり

EMアルゴリズムで我々われわれが求もとめたいのは、$X=(x_{1},\ldots ,x_{n})$を観測かんそくした際さいにおける対数たいすう尤ゆう度ど

$\ell (\theta |X):=\log p(X|\theta )$

を最大さいだい化かする母はは数すう$\theta$であった。EMアルゴリズムの動作どうさ原理げんりを説明せつめいする為ため、以下いかのような汎ひろし関数かんすうを考かんがえる：

${\mathcal {L}}(q,\theta ):=\sum _{Z}q(Z)\log {p(X,Z|\theta ) \over q(Z)}$　　...(Eq.1)

ここで$q(Z)$は任意にんいの確かく率りつ密度みつど関数かんすうである。$p_{X,\theta }(Z):=p(Z|X,\theta )$とすると、$p(Z|X,\theta )p(X|\theta )=p(X,Z|\theta )$より、カルバック・ライブラー情報じょうほう量りょう

$\mathrm {KL} (q||p_{X,\theta })=-\sum _{Z}q(Z)\log {p(Z|X,\theta ) \over q(Z)}$　

を使つかって

${\mathcal {L}}(q,\theta )=\ell (\theta |X)-\mathrm {KL} (q||p_{X,\theta })$　...(Eq.2)

と書かける事ことが分わかる。カルバック・ライブラー情報じょうほう量りょうが常つねに非負ひふである事こと（ギブスの不等式ふとうしき）から、

$\ell (\theta |X)\geq {\mathcal {L}}(q,\theta )$　

であるので、${\mathcal {L}}(q,\theta )$は$\ell (\theta |X)$の下限かげんになっている。EMアルゴリズムはこの下限かげん${\mathcal {L}}(q,\theta )$を逐次ちくじ的てきに改善かいぜんしていくことで、$\ell (\theta |X)$を可能かのうな限かぎり最大さいだい化かするアルゴリズムである。すなわち、EステップとMステップは以下いかのように書かき換かえられる事ことを示しめす事ことができる：

• E ステップ: ${\hat {q}}^{(t)}={\underset {q}{\operatorname {arg\,max} }}{\mathcal {L}}(q,{\hat {\theta }}^{(t)})$を求もとめる。
• M ステップ: ${\hat {\theta }}^{(t+1)}={\underset {\theta }{\operatorname {arg\,max} }}{\mathcal {L}}({\hat {q}}^{(t)},\theta )$を求もとめる。

この事実じじつから対数たいすう尤ゆう度ど$\ell ({\hat {\theta }}^{(t)}|X)$の単調たんちょう非ひ減少げんしょう性せいが明あきらかに従したがう。 （但ただし反復はんぷく法ほうの常つねとして、初期しょき値ちしだいでは尤ゆう度どの最大さいだい点てんではない極大きょくだい点てんに到達とうたつしてそこで停止ていしする可能かのう性せいがある。）

証明しょうめい

本節ほんぶしではEステップ、Mステップが上述じょうじゅつのように書かき換かえられることを示しめす。本節ほんぶしの証明しょうめいは文献ぶんけんを参考さんこうにした。

Eステップの証明しょうめい

カルバック・ライブラー情報じょうほう量りょう$\mathrm {KL} (q||p_{X,\theta })$が最小さいしょう値ち0になるのは$q=p_{\theta ,X}$の場合ばあいだけであった事ことから、(Eq.2)より${\mathcal {L}}(q,\theta )$は

$q(Z)=p(Z|X,\theta )$　

が満みたされる場合ばあいに最大さいだい値ちを取とる。すなわちEMアルゴリズムにおけるEステップは、$\theta ={\hat {\theta }}^{(t)}$を固定こていしたままの状態じょうたいで、${\mathcal {L}}(q,\theta )$を最大さいだい化かする$q$である

${\hat {q}}^{(t)}:=p_{X,{\hat {\theta }}^{(t)}}={\underset {q}{\operatorname {arg\,max} }}{\mathcal {L}}(q,{\hat {\theta }}^{(t)})$　

を求もとめるステップである。

Mステップの証明しょうめい

${\mathcal {L}}(q,\theta )$の定義ていぎ式しき(Eq.1)に${\hat {q}}^{(t)}=p_{X,{\hat {\theta }}^{(t)}}$を代入だいにゅうすると、

${\mathcal {L}}({\hat {q}}^{(t)},\theta )=\sum _{Z}p(Z|X,\theta ^{(t)})\log {p(X,Z|\theta ) \over p(Z|X,\theta ^{(t)})}=Q(\theta |\theta ^{(t)})-H_{X,\theta ^{(t)}}(Z)$　

が成立せいりつし（ここで$H_{X,\theta ^{(t)}}(Z)=\textstyle \sum _{Z}p(Z|X,\theta ^{(t)})\log p(Z|X,\theta ^{(t)})$は条件じょうけん付つきエントロピー）、上うえ式しき右辺うへん第だい二に項こうはθしーたに依存いぞんしないので、

${\hat {\theta }}^{(t+1)}={\underset {\theta }{\operatorname {arg\,max} }}Q(\theta |{\hat {\theta }}^{(t)})={\underset {\theta }{\operatorname {arg\,max} }}{\mathcal {L}}(p_{X,{\hat {\theta }}^{(t)}},\theta )$　

が成立せいりつする。

一般いっぱん化か

EMアルゴリズムは観測かんそくデータの対数たいすう尤ゆう度どを、E ステップとM ステップの繰くり返かえしにより最大さいだい化かするアルゴリズムであるので、正確せいかくにはlog-EMアルゴリズムというべきものである。log関数かんすうにはαあるふぁ-logとよばれる一般いっぱん化かされた対数たいすうがあるので、それを用もちいるとlog-EMを特例とくれいとして含ふくむアルゴリズムを作つくり上あげることができる。ただし、この場合ばあいは尤ゆう度どではなくてαあるふぁ-log尤ゆう度ど比ひとαあるふぁダイバージェンスを用もちいて基本きほん等式とうしきを導みちびくことになる。このようにして得えられたものがαあるふぁ-EMアルゴリズム であり、log-EMアルゴリズムをサブクラスとして含ふくんでいる。αあるふぁ-EMアルゴリズムは適切てきせつなαあるふぁを選えらぶことにより、log-EMアルゴリズムよりも高速こうそくになる。また、log-EMが隠かくれマルコフモデル推定すいていアルゴリズム（Baum-Welchアルゴリズム）を含ふくんでいるように、αあるふぁ-EMアルゴリズムから高速こうそくなαあるふぁ-HMMアルゴリズムを得えることができる。

歴史れきし

EMアルゴリズムは、アーサー・デンプスター、ナン・レアード、ドナルド・ルービンによる1977年ねんの論文ろんぶんで導入どうにゅうされ、その名なが付つけられた。彼かれらは、EMアルゴリズムがほかの複数ふくすうの著者ちょしゃによって「特殊とくしゅな文脈ぶんみゃくでなんども提案ていあんされてきた」("proposed many times in special circumstances") ことを述のべた上うえで、EMアルゴリズムの一般いっぱん化かを行おこない、その背後はいごにある理論りろんを追求ついきゅうした。

本来ほんらいのEMアルゴリズムでは、期待きたい値ちの評価ひょうかにおいて潜在せんざい変数へんすうのとりうる値ねすべてを列挙れっきょすることが必要ひつようなため、効率こうりつ的てきに扱あつかえる分布ぶんぷが限かぎられていた。しかしその後ご、マルコフ連鎖れんさモンテカルロ法ほうや変へん分ぶんベイズ法ほうが考案こうあんされたことにより、より一般いっぱんの分布ぶんぷでも現実げんじつ的てきな時間じかんでの計算けいさんが可能かのうになった。

参考さんこう文献ぶんけん

引用いんよう文献ぶんけん

• Trevor Hastie; Robert Tibshirani; Jerome Friedman (2014/6/25). 統計とうけい的てき学習がくしゅうの基礎きそ―データマイニング・推論すいろん・予測よそく―. 共立きょうりつ出版しゅっぱん. ISBN 978-4-320-12362-5 
• C.M. ビショップ (2012/2/29). パターン認識にんしきと機械きかい学習がくしゅう 下か (ベイズ理論りろんによる統計とうけい的てき予測よそく). 丸善まるぜん出版しゅっぱん. ISBN 978-4621061244 
• 汪ひろし金きむ芳かおる、手塚てづか集しゅう、上田うえだ修おさむ功こう、田栗たぐり正章まさあき、樺島かばしま祥さち介かい、甘利あまり俊一しゅんいち、竹村たけむら彰あきら通どおり、竹内たけうち啓あきら、伊庭いば幸人ゆきと『計算けいさん統計とうけい I ―確かく率りつ計算けいさんの新あたらしい手法しゅほう』 11巻かん〈統計とうけい科学かがくのフロンティア〉、2003年ねん。ISBN 4000068512。 

その他たの参考さんこう文献ぶんけん

• Robert Hogg, Joseph McKean and Allen Craig. Introduction to Mathematical Statistics. pp. 359-364. Upper Saddle River, NJ: Pearson Prentice Hall, 2005.
• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay includes simple examples of the E-M algorithm such as clustering using the soft K-means algorithm, and emphasizes the variational view of the E-M algorithm.
• A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, by Jeff Bilmes includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
• Variational Algorithms for Approximate Bayesian Inference, by M. J. Beal includes comparisons of EM to Variational Bayesian EM and derivations of several models including Variational Bayesian HMMs.
• The Expectation Maximization Algorithm, by Frank Dellaert, gives an easier explanation of EM algorithm in terms of lowerbound maximization.
• The Expectation Maximization Algorithm: A short tutorial, A self contained derivation of the EM Algorithm by Sean Borman.
• The EM Algorithm, by Xiaojin Zhu.
• Geoffrey J. McLachlan and Thriyambakam Krishnan: "The EM Algorithm and Extensions", Wiley series in probability and statistics, John Wiley & Sons, Inc., ISBN 0-471-12358-7 (1997).
• Geoffrey J. McLachlan and Thriyambakam Krishnan:"The EM Algorithm and Extensions", 2nd Edition, Wiley & Sons Inc., ISBN 978-0-471-20170-0 (February 2008).　上記じょうきの改訂かいてい第だい2版はん。
• 小西こにし貞さだ則そく ・越智おち義道よしみち ・大森おおもり裕ひろし浩ひろし:「計算けいさん統計とうけい学がくの方法ほうほう ―ブートストラップ，EMアルゴリズム，MCMC―」、朝倉書店あさくらしょてん(シリーズ：予測よそくと発見はっけんの科学かがく、5)、ISBN 978-4-254-12785-0、2008年ねん3月がつ25日にち。
• 関原せきはら謙介けんすけ：「ベイズ信号しんごう処理しょり」、共立きょうりつ出版しゅっぱん、ISBN 978-4-320-08574-9、2015年ねん4月がつ。
• 関原せきはら謙介けんすけ：「ベイズ推論すいろんの基礎きそと信号しんごう処理しょりへの応用おうよう」
• Kenneth Lange: "MM Optimization Algorithms", SIAM, ISBN 978-1-611974-39-3 (2016). ※ "MM algorithm" は "EM" アルゴリズムの一般いっぱん化かとして提唱ていしょうされている．
• 黒田くろだ正博まさひろ:「EMアルゴリズム」、共立きょうりつ出版しゅっぱん(シリーズ：統計とうけい学がくOne Point、18巻かん)、ISBN 978-4-320-11269-8、2020年ねん07月がつ31日にち。