EMアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

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

概要[編集]

セッティング・目標[編集]

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

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


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

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

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

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

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

アルゴリズム[編集]

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

  • 初期値を(何らかの方法で)選ぶ。
  • に対して以下を実行する
    • E ステップ: を求める。
    • M ステップ: を求める。

ここでQは対数尤度関数Zに関する条件付き期待値

 

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

留意点[編集]

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

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

動作原理[編集]

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

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

  ...(Eq.1)

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

 

を使って

 ...(Eq.2)

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

 

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

  • E ステップ: を求める。
  • M ステップ: を求める。

この事実から対数尤度の単調非減少性が明らかに従う。

証明[編集]

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

Eステップの証明[編集]

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

 

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

 

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

Mステップの証明[編集]

の定義式(Eq.1)にを代入すると、

 

が成立し(ここで条件付きエントロピー)、上式右辺第二項はθに依存しないので、

 

が成立する。

一般化[編集]

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

歴史[編集]

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

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

脚注[編集]

[脚注の使い方]
  1. ^ a b c 計算統計I, p. 130.
  2. ^ 計算統計I, p. 157.
  3. ^ a b c d e f #PRML pp.156, 164-171
  4. ^ a b c #ESL pp.316-317.
  5. ^ Matsuyama, Yasuo (2003). “The α-EM algorithm: Surrogate likelihood maximization using α-logarithmic information measures”. IEEE Transactions on Information Theory 49 (3): 692-706. 
  6. ^ Matsuyama, Yasuo (2011). “Hidden Markov model estimation based on alpha-EM algorithm: Discrete and continuous alpha-HMMs”. International Joint Conference on Neural Networks: 808-816. 
  7. ^ Dempster, A.P., Laird, N.M., Rubin, D.B., (1977). “Maximum Likelihood from Incomplete Data via the EM Algorithm”. Journal of the Royal Statistical Society. Series B (Methodological) 39 (1): 1–38. JSTOR2984875. MR0501537. 
  8. ^ 計算統計I, p. 163.

参考文献[編集]

引用文献[編集]

  • 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 

その他の参考文献[編集]