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 

その他の参考文献

編集