EMアルゴリズム

EMアルゴリズム（）とは、統計学において、確率モデルのパラメータを最尤推定する手法の一つであり、観測不可能な潜在変数に確率モデルが依存する場合に用いられる。EM法、期待値最大化法（きたいちさいだいかほう）とも呼ばれる。その一般性の高さから、機械学習、音声認識、因子分析など、広汎な応用がある。
EMアルゴリズムは反復法の一種であり、期待値() ステップと最大化 ()ステップを交互に繰り返すことで計算が進行する。Eステップでは、現在推定されている潜在変数の分布に基づいて、モデルの尤度の期待値を計算する。Mステップでは、E ステップで求まった尤度の期待値を最大化するようなパラメータを求める。M ステップで求まったパラメータは、次の E ステップで使われる潜在変数の分布を決定するために用いられる。 
概要.
セッティング・目標.
今、2値、を取る確率分布があり、その確率分布の確率密度関数formula_1が未知の母数formula_2によりパラメトライズされているとする。ここでformula_3は実数全体の集合を表す。
そしてformula_1に従って標本formula_5を独立に抽出したものの、何らかの事情でformula_6の値は観測できず、formula_7だけが観測できたとする。実応用上は例えば、formula_8という形をしており、まず観測不能なformula_9が選ばれた後、formula_10に依存して観測可能なformula_11が選ばれる、といったケースにEMアルゴリズムが使われる事が多いが、必ずしもこのケースにあてはまらなくてもよい。
簡単の為、記号を混用して、の同時確率分布の確率密度関数もformula_12と書く。以下ではが離散変数の場合について説明するが、が連続変数の場合も総和を積分に置き換える以外は同様である。
このような状況において母数を最尤推定する事が我々の目標である。しかしを知らない場合のformula_7に関する対数尤度
を最大値を直接計算するのは一般には簡単ではない。
EMアルゴリズムは、反復法により、数列formula_15で対数尤度formula_16が単調非減少であるものを作るアルゴリズムである。最尤推定量をformula_17とすると、
である事から、formula_19が有限であればformula_16の単調性よりformula_16は必ず収束する。
アルゴリズム.
EMアルゴリズムでは、以下の手順により数列formula_22を作る。
ここで"Q"は対数尤度関数formula_27のに関する条件付き期待値
である。実応用上は、formula_15の値が十分小さくなったと判定する何らかの条件を事前に定めておき、その条件を満たしたら上述のループを終了する。ループを終了する条件は、パラメータ値や対数尤度関数を使って定められる。
留意点.
EステップとMステップの切れ目は書籍により異なるので注意が必要である。本項では次節の議論と整合性をとる為に文献の切れ目に従ったが、文献ではformula_30を計算する所までがEステップであり、formula_30のformula_32を取るところだけがMステップである。
ステップの名称「E」と「M」はそれぞれExpectation(期待値)、Maximization（最大化）の略であり、文献のようにEステップでformula_30を求める為に期待値を計算し、Mステップでformula_30のformula_32を取るところに名称の由来がある。
動作原理.
EMアルゴリズムで我々が求めたいのは、formula_7を観測した際における対数尤度
を最大化する母数formula_38であった。EMアルゴリズムの動作原理を説明する為、以下のような汎関数を考える：
ここでformula_40は任意の確率密度関数である。formula_41とすると、formula_42より、カルバック・ライブラー情報量
を使って
と書ける事が分かる。カルバック・ライブラー情報量が常に非負である事（ギブスの不等式）から、
であるので、formula_46はformula_47の下限になっている。EMアルゴリズムはこの下限formula_46を逐次的に改善していくことで、formula_47を可能な限り最大化するアルゴリズムである。すなわち、EステップとMステップは以下のように書き換えられる事を示す事ができる：
この事実から対数尤度formula_16の単調非減少性が明らかに従う。
（但し反復法の常として、初期値しだいでは尤度の最大点ではない極大点に到達してそこで停止する可能性がある。）
証明.
本節ではEステップ、Mステップが上述のように書き換えられることを示す。本節の証明は文献を参考にした。
Eステップの証明.
カルバック・ライブラー情報量formula_53が最小値0になるのはformula_54の場合だけであった事から、()よりformula_46は
が満たされる場合に最大値を取る。すなわちEMアルゴリズムにおけるEステップは、formula_57を固定したままの状態で、formula_46を最大化するformula_59である
を求めるステップである。
Mステップの証明.
formula_46の定義式()にformula_62を代入すると、
が成立し（ここでformula_64は条件付きエントロピー）、上式右辺第二項はに依存しないので、
が成立する。
一般化.
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アルゴリズムでは、期待値の評価において潜在変数のとりうる値すべてを列挙することが必要なため、効率的に扱える分布が限られていた。しかしその後、マルコフ連鎖モンテカルロ法やが考案されたことにより、より一般の分布でも現実的な時間での計算が可能になった。