EMアルゴリズム

EMアルゴリズムとは、統計学において、確率モデルのパラメータを最尤推定する手法の一つであり、観測不可能な潜在変数に確率モデルが依存する場合に用いられる。EM法、期待値最大化法計算統計I計算統計Iとも呼ばれる。その一般性の高さから、機械学習、音声認識、因子分析など、広汎な応用がある計算統計I。

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

1. 概要
-----

1.1. セッティング・目標
--------------

今、2値//x//}}、//z//}}を取る確率分布があり、その確率分布の確率密度関数が未知の母数によりパラメトライズされているとする。ここでは実数全体の集合を表す。

そしてに従って標本を独立に抽出したものの、何らかの事情での値は観測できず、だけが観測できたとする。実応用上は例えば、という形をしており、まず観測不能なが選ばれた後、に依存して観測可能なが選ばれる、といったケースにEMアルゴリズムが使われる事が多いが、必ずしもこのケースにあてはまらなくてもよい。

簡単の為、記号を混用して//X//}}、//Z//}}の同時確率分布の確率密度関数もと書く。以下では//Z//}}が離散変数の場合について説明するが、//Z//}}が連続変数の場合も総和を積分に置き換える以外は同様である。

このような状況において母数//θ//}}を最尤推定する事が我々の目標である。しかし//Z//}}を知らない場合のに関する対数尤度

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

EMアルゴリズムは、反復法により、数列で対数尤度が単調非減少であるものを作るアルゴリズムである。最尤推定量をとすると、

である事から、が有限であればの単調性よりは必ず収束する。

1.2. アルゴリズム
-----------

EMアルゴリズムでは、以下の手順により数列を作る。

初期値を選ぶ。
に対して以下を実行する
E ステップ: を求める。
M ステップ: を求める。ここで//Q//は対数尤度関数の//Z//}}に関する条件付き期待値

　 である。実応用上は、の値が十分小さくなったと判定する何らかの条件を事前に定めておき、その条件を満たしたら上述のループを終了する。ループを終了する条件は、パラメータ値や対数尤度関数を使って定められる。

1.3. 留意点
--------

EステップとMステップの切れ目は書籍により異なるので注意が必要である。本項では次節の議論と整合性をとる為に文献の切れ目に従ったが、文献ではを計算する所までがEステップであり、のを取るところだけがMステップである。

ステップの名称「E」と「M」はそれぞれExpectation、Maximizationの略であり、文献のようにEステップでを求める為に期待値を計算し、Mステップでのを取るところに名称の由来がある。

2. 動作原理
-------

EMアルゴリズムで我々が求めたいのは、を観測した際における対数尤度

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

　　...ここでは任意の確率密度関数である。とすると、より、カルバック・ライブラー情報量

　 を使って

　...と書ける事が分かる。カルバック・ライブラー情報量が常に非負である事から、

　 であるので、はの下限になっている。EMアルゴリズムはこの下限を逐次的に改善していくことで、を可能な限り最大化するアルゴリズムである。すなわち、EステップとMステップは以下のように書き換えられる事を示す事ができる：

E ステップ: を求める。
M ステップ: を求める。この事実から対数尤度の単調非減少性が明らかに従う。

2.1. 証明
-------

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

2.1.1. Eステップの証明
---------------

カルバック・ライブラー情報量が最小値0になるのはの場合だけであった事から、よりは

　 が満たされる場合に最大値を取る。すなわちEMアルゴリズムにおけるEステップは、を固定したままの状態で、を最大化するである

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

2.1.2. Mステップの証明
---------------

の定義式にを代入すると、

　 が成立し、上式右辺第二項は//θ//}}に依存しないので、

　 が成立する。

3. 一般化
------

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

4. 歴史
-----

EMアルゴリズムは、アーサー・デンプスター、ナン・レアード、ドナルド・ルービンによる1977年の論文で導入され、その名が付けられた。彼らは、EMアルゴリズムがほかの複数の著者によって「特殊な文脈でなんども提案されてきた」 ことを述べた上で、EMアルゴリズムの一般化を行い、その背後にある理論を追求した。

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

5. 脚注
-----

6. 参考文献
-------

6.1. 引用文献
---------

6.2. その他の参考文献
-------------

Robert Hogg, Joseph McKean and Allen Craig. //Introduction to Mathematical Statistics//. pp. 359-364. Upper Saddle River, NJ: Pearson Prentice Hall, 2005.
[1], 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.
[2], by [3] includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
[4], by M. J. Beal includes comparisons of EM to Variational Bayesian EM and derivations of several models including Variational Bayesian HMMs.
[5], by Frank Dellaert, gives an easier explanation of EM algorithm in terms of lowerbound maximization.
[6], A self contained derivation of the EM Algorithm by Sean Borman.
[7], 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 .
Geoffrey J. McLachlan and Thriyambakam Krishnan:"The EM Algorithm and Extensions", 2nd Edition, Wiley & Sons Inc., ISBN 978-0-471-20170-0 .　上記の改訂第2版。
小西貞則 ・越智義道 ・大森裕浩:「計算統計学の方法 ―ブートストラップ，EMアルゴリズム，MCMC―」、朝倉書店、ISBN 978-4-254-12785-0、2008年3月25日。
関原謙介：「ベイズ信号処理」、共立出版、ISBN 978-4-320-08574-9、2015年4月。
[8]
Kenneth Lange: "MM Optimization Algorithms", SIAM, 978-1-611974-39-3}} . ※ "MM algorithm" は "EM" アルゴリズムの一般化として提唱されている．
黒田正博:「EMアルゴリズム」、共立出版、ISBN 978-4-320-11269-8、2020年07月31日。