EMアルゴリズムのソースを表示

{{Pathnavbox|
* {{Pathnav|応用数学|統計学}}
* {{Pathnav|データサイエンス|機械学習}}
}}
{{Machine learning bar}}
'''EMアルゴリズム'''（{{lang-en-short|expectation–maximization algorithm}}）とは、[[統計学]]において、[[確率]][[数理モデル|モデル]]のパラメータを[[最尤推定]]する手法の一つであり、観測不可能な[[潜在変数]]に確率モデルが依存する場合に用いられる。'''EM法'''、'''期待値最大化法'''（きたいちさいだいかほう）{{sfn|計算統計I|p=130}}{{sfn|計算統計I|p=157}}とも呼ばれる。その一般性の高さから、[[機械学習]]、[[音声認識]]、[[因子分析]]など、広汎な応用がある{{sfn|計算統計I|p=130}}。

EMアルゴリズムは[[反復法 (数値計算)|反復法]]の一種であり、期待値（{{lang-en-short|expectation, E}}）ステップと最大化（{{lang-en-short|maximization, M}}）ステップを交互に繰り返すことで計算が進行する。Eステップでは、現在推定されている潜在変数の分布に基づいて、モデルの尤度の期待値を計算する。Mステップでは、E ステップで求まった尤度の期待値を最大化するようなパラメータを求める。M ステップで求まったパラメータは、次の E ステップで使われる潜在変数の分布を決定するために用いられる。 

== 概要 ==
=== セッティング・目標 ===
今、2値{{Math|''x''}}、{{Math|''z''}}を取る確率分布があり、その確率分布の確率密度関数<math>p(x,z|\theta)</math>が未知の母数<math>\theta\in\mathbb{R}^m</math>によりパラメトライズされているとする。ここで<math>\mathbb{R}</math>は実数全体の集合を表す。

そして<math>p(x,z|\theta)</math>に従って標本<math>(x_1,z_1),\ldots,(x_n,z_n)</math>を独立に抽出したものの、何らかの事情で<math>Z=(z_1,\ldots,z_n)</math>の値は観測できず、<math>X=(x_1,\ldots,x_n)</math>だけが観測できたとする。実応用上は例えば、<math>\theta=(\theta_1,\theta_2)</math>という形をしており、まず観測不能な<math>z_i\sim p_1(z|\theta_1)</math>が選ばれた後、<math>z_i</math>に依存して観測可能な<math>x_i\sim p_2(x|\theta_2,z_i)</math>が選ばれる、といったケースにEMアルゴリズムが使われる事が多いが、必ずしもこのケースにあてはまらなくてもよい。


簡単の為、記号を混用して{{Math|''X''}}、{{Math|''Z''}}の同時確率分布の確率密度関数も<math>p(X,Z|\theta)</math>と書く。以下では{{Math|''Z''}}が離散変数の場合について説明するが、{{Math|''Z''}}が連続変数の場合も総和を積分に置き換える以外は同様である<ref name=":02" />。

このような状況において母数{{Math|''θ''}}を最尤推定する事が我々の目標である。しかし{{Math|''Z''}}を知らない場合の<math>X=(x_1,\ldots,x_n)</math>に関する対数尤度

: <math>\ell(\theta|X):=\log p(X|\theta)=\log \sum_Zp(X,Z|\theta) </math>

を最大値を直接計算するのは一般には簡単ではない。

EMアルゴリズムは、反復法により、数列<math>\hat{\theta}^{(t)}</math>で対数尤度<math>\ell(\hat{\theta}^{(t)}|X) </math>が[[単調増加|単調非減少]]であるものを作るアルゴリズムである。最尤推定量を<math>\hat{\theta}_{\mathrm{MLE}}</math>とすると、

:<math>\ell(\hat{\theta}_{\mathrm{MLE}}|X)\ge \ell(\hat{\theta}^{(t)}|X) </math>

である事から、<math>\ell(\hat{\theta}_{\mathrm{MLE}}|X)</math>が有限であれば<math>\ell(\hat{\theta}^{(t)}|X) </math>の単調性より<math>\ell(\hat{\theta}^{(t)}|X) </math>は[[単調収束定理|必ず収束する]]。

=== アルゴリズム ===
EMアルゴリズムでは、以下の手順により数列<math>\hat{\theta}^{(0)},\hat{\theta}^{(1)},\ldots</math>を作る<ref name=":02" />。

* 初期値<math>\hat{\theta}^{(0)}</math>を（何らかの方法で）選ぶ。
* <math>t=0,1,\ldots</math>に対して以下を実行する
**'''E ステップ''': <math>p(Z|X,\hat{\theta}^{(t)})</math>を求める。
**'''M ステップ''': <math>\hat{\theta}^{(t+1)} = \underset{\theta} {\operatorname{arg\,max}} \ Q(\theta|\hat{\theta}^{(t)}) \, </math>を求める。

ここで''Q''は対数尤度関数<math> \log p (X,Z|\theta)</math>の{{Math|''Z''}}に関する条件付き[[期待値]]
:<math>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) \,</math>  　
である。実応用上は、<math>\hat{\theta}^{(t)}</math>の値が十分小さくなったと判定する何らかの条件を事前に定めておき、その条件を満たしたら上述のループを終了する。ループを終了する条件は、パラメータ値や対数尤度関数を使って定められる<ref name=":02">[[#PRML]] pp.156, 164-171</ref>。

=== 留意点 ===
'''EステップとMステップの切れ目は書籍により異なるので注意が必要である'''。本項では次節の議論と整合性をとる為に文献<ref name=":02" />の切れ目に従ったが、文献<ref name=":12">[[EMアルゴリズム#ESL|#ESL]] pp.316-317.</ref>では<math>Q(\theta|\hat{\theta}^{(t)})  </math>を計算する所までがEステップであり、<math>Q(\theta|\hat{\theta}^{(t)})  </math>の<math>\operatorname{arg\,max} </math>を取るところだけがMステップである。

ステップの名称「E」と「M」はそれぞれExpectation（期待値）、Maximization（最大化）の略であり<ref name=":12" />、文献<ref name=":12" />のようにEステップで<math>Q(\theta|\hat{\theta}^{(t)})  </math>を求める為に期待値を計算し、Mステップで<math>Q(\theta|\hat{\theta}^{(t)})  </math>の<math>\operatorname{arg\,max} </math>を取るところに名称の由来がある。

== 動作原理 ==
EMアルゴリズムで我々が求めたいのは、<math>X=(x_1,\ldots,x_n)</math>を観測した際における対数尤度

:<math>\ell(\theta|X):=\log p(X|\theta) </math>

を最大化する母数<math>\theta</math>であった。EMアルゴリズムの動作原理を説明する為、以下のような汎関数を考える：

: <math>\mathcal{L}(q,\theta)
:=\sum_Z q(Z) \log {p(X,Z|\theta)\over q(Z)} </math>　　...({{EquationRef|Eq.1}})

ここで<math>q(Z) </math>は任意の確率密度関数である。<math>p_{X,\theta}(Z):=p(Z|X,\theta) </math>とすると、<math>p(Z|X,\theta) p(X|\theta) = p(X,Z|\theta) </math>より、[[カルバック・ライブラー情報量]]

:<math>\mathrm{KL}(q||p_{X,\theta})=-\sum_Z q(Z)\log{p(Z|X,\theta) \over q(Z)} </math>　

を使って

:<math>\mathcal{L}(q,\theta)=\ell(\theta|X)-\mathrm{KL}(q||p_{X,\theta}) </math>　...({{EquationRef|Eq.2}})

と書ける事が分かる。カルバック・ライブラー情報量が常に非負である事（[[ギブスの不等式]]）から、

:<math>\ell(\theta|X)\ge\mathcal{L}(q,\theta) </math>　

であるので、<math>\mathcal{L}(q,\theta) </math>は<math>\ell(\theta|X) </math>の下限になっている。EMアルゴリズムはこの下限<math>\mathcal{L}(q,\theta) </math>を逐次的に改善していくことで、<math>\ell(\theta|X) </math>を可能な限り最大化するアルゴリズムである。すなわち、EステップとMステップは以下のように書き換えられる事を示す事ができる<ref name=":02" />：

*'''E ステップ''': <math>\hat{q}^{(t)} = \underset{q}{\operatorname{arg\,max}} \mathcal{L}(q,\hat{\theta}^{(t)})  </math>を求める。
*'''M ステップ''': <math>\hat{\theta}^{(t+1)} = \underset{\theta}{\operatorname{arg\,max}}\mathcal{L}(\hat{q}^{(t)},\theta)  </math>を求める。

この事実から対数尤度<math>\ell(\hat{\theta}^{(t)}|X) </math>の単調非減少性が明らかに従う。
（但し反復法の常として、初期値しだいでは尤度の最大点ではない極大点に到達してそこで停止する可能性がある。）

=== 証明 ===

本節ではEステップ、Mステップが上述のように書き換えられることを示す。本節の証明は文献<ref name=":02" />を参考にした。

==== Eステップの証明 ====
カルバック・ライブラー情報量<math>\mathrm{KL}(q||p_{X,\theta}) </math>が最小値0になるのは<math>q=p_{\theta,X}</math>の場合だけであった事から、({{EquationNote|Eq.2}})より<math>\mathcal{L}(q,\theta) </math>は

:<math>q(Z)=p(Z|X,\theta) </math>　

が満たされる場合に最大値を取る。すなわちEMアルゴリズムにおけるEステップは、<math>\theta=\hat{\theta}^{(t)} </math>を固定したままの状態で、<math>\mathcal{L}(q,\theta) </math>を最大化する<math>q</math>である

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

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

==== Mステップの証明 ====
<math>\mathcal{L}(q,\theta) </math>の定義式({{EquationNote|Eq.1}})に<math>\hat{q}^{(t)}=p_{X,\hat{\theta}^{(t)}}</math>を代入すると、

:<math>\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) </math>　

が成立し（ここで<math>H_{X,\theta^{(t)}}(Z)=\textstyle \sum_Z p(Z|X,\theta^{(t)}) \log p(Z|X,\theta^{(t)})</math>は[[情報量|条件付きエントロピー]]）、上式右辺第二項は{{Math|''θ''}}に依存しないので、

:<math>\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)  </math>　

が成立する。

== 一般化 ==
EMアルゴリズムは観測データの対数尤度を、E ステップとM ステップの繰り返しにより最大化するアルゴリズムであるので、正確にはlog-EMアルゴリズムというべきものである。log関数にはα-logとよばれる一般化された対数があるので、それを用いるとlog-EMを特例として含むアルゴリズムを作り上げることができる。ただし、この場合は尤度ではなくてα-log尤度比とαダイバージェンスを用いて基本等式を導くことになる。このようにして得られたものがα-EMアルゴリズム <ref>{{cite journal|last=Matsuyama|first=Yasuo|year=2003|title=The α-EM algorithm: Surrogate likelihood maximization using α-logarithmic information measures|journal=IEEE Transactions on Information Theory|volume=49|number=3|pages=692-706}}</ref> であり、log-EMアルゴリズムをサブクラスとして含んでいる。α-EMアルゴリズムは適切なαを選ぶことにより、log-EMアルゴリズムよりも高速になる。また、log-EMが隠れマルコフモデル推定アルゴリズム（Baum-Welchアルゴリズム）を含んでいるように、α-EMアルゴリズムから高速なα-HMMアルゴリズムを得ることができる。 <ref>{{cite journal|last=Matsuyama|first=Yasuo|year=2011|title=Hidden Markov model estimation based on alpha-EM algorithm: Discrete and continuous alpha-HMMs|journal=International Joint Conference on Neural Networks|pages=808-816}}</ref>

== 歴史 ==
EMアルゴリズムは、{{仮リンク|アーサー・デンプスター|en|Arthur P. Dempster}}、{{仮リンク|ナン・レアード|en|Nan Laird}}、[[ドナルド・ルービン]]による1977年の論文<ref>{{cite journal|author=Dempster, A.P., Laird, N.M., Rubin, D.B.,|year=1977|title=Maximum Likelihood from Incomplete Data via the EM Algorithm|journal=Journal of the [[王立統計学会|Royal Statistical Society]]. Series B (Methodological)|volume=39|issue=1|pages=1–38|id=[http://www.jstor.org/stable/2984875 JSTOR2984875]. {{MR|0501537}}}}</ref>で導入され、その名が付けられた。彼らは、EMアルゴリズムがほかの複数の著者によって「特殊な文脈でなんども提案されてきた」("proposed many times in special circumstances") ことを述べた上で、EMアルゴリズムの一般化を行い、その背後にある理論を追求した。

本来のEMアルゴリズムでは、期待値の評価において潜在変数のとりうる値すべてを列挙することが必要なため、効率的に扱える分布が限られていた。しかしその後、[[マルコフ連鎖モンテカルロ法]]や{{仮リンク|変分ベイズ法|en|Variational Bayesian methods}}が考案されたことにより、より一般の分布でも現実的な時間での計算が可能になった{{sfn|計算統計I|p=130}}{{sfn|計算統計I|p=163}}。 

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==

===引用文献===
* {{Cite book|title=統計的学習の基礎―データマイニング・推論・予測―|date=2014/6/25|publisher=[[共立出版]]|isbn=978-4-320-12362-5|author=Trevor Hastie|author2=Robert Tibshirani|author3=Jerome Friedman|author4=|author5=|author6=|author7=|author8=|author9=|ref=ESL|year=}}
* {{Cite book|title=パターン認識と機械学習 下 (ベイズ理論による統計的予測)|date=2012/2/29|publisher=丸善出版|author=C.M. ビショップ|isbn=978-4621061244|ref=PRML}}
* {{cite|和書|ref={{sfnref|計算統計I}}|author=汪金芳、手塚集、上田修功、田栗正章、[[樺島祥介]]、[[甘利俊一]]、[[竹村彰通]]、[[竹内啓]]、伊庭幸人|title=計算統計 I ―確率計算の新しい手法|series=統計科学のフロンティア|volume=11|year=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.
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ 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.
* [http://citeseer.ist.psu.edu/bilmes98gentle.html A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models], by [http://ssli.ee.washington.edu/people/bilmes/ Jeff Bilmes] includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
* [http://www.cse.buffalo.edu/faculty/mbeal/thesis/index.html ''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.
* [http://www.cc.gatech.edu/~dellaert/em-paper.pdf ''The Expectation Maximization Algorithm''], by Frank Dellaert, gives an easier explanation of EM algorithm in terms of lowerbound maximization.
* [http://www.seanborman.com/publications/EM_algorithm.pdf ''The Expectation Maximization Algorithm: A short tutorial''], A self contained derivation of the EM Algorithm by Sean Borman.
* [http://pages.cs.wisc.edu/~jerryzhu/cs838/EM.pdf ''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版。
* Kenneth Lange: ''MM Optimization Algorithms'', SIAM, {{ISBN2| 978-1-611974-39-3}} (2016). ※ "EM" アルゴリズムの一般化として　"[[MM algorithm]]" を提唱している．
和書
* 小西貞則 ・越智義道 ・大森裕浩:「計算統計学の方法 ―ブートストラップ，EMアルゴリズム，MCMC―」、朝倉書店(シリーズ：予測と発見の科学、5)、ISBN 978-4-254-12785-0　(2008年3月25日)。
* 関原謙介：「ベイズ信号処理」、共立出版、ISBN 978-4-320-08574-9 (2015年4月11日)。
* [http://signalanalysis.jp/pdfs/Bayes2019_0807.pdf 関原謙介：「ベイズ推論の基礎と信号処理への応用」]
* 黒田正博:「EMアルゴリズム」、共立出版(シリーズ：統計学One Point、18巻)、ISBN 978-4-320-11269-8、(2020年7月31日)。

{{Statistics-stub}}
{{デフォルトソート:いいえむあるこりすむ}}
[[Category:機械学習アルゴリズム]]
[[Category:クラスター分析アルゴリズム]]
[[Category:最適化アルゴリズム]]
[[Category:統計アルゴリズム]]
[[Category:統計学的方法]]
[[Category:数学に関する記事]]