EMアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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


歴史[編集]

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

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

概要[編集]

観測データを x、パラメータを θ、潜在データあるいは欠損値z尤度関数 L(θ;x,z)とするとき、パラメータの最尤推定値は、観測データに対する周辺尤度英語版を最大化することで求められる。しかしその最大化問題は解析的に解けず[5]計算量intractableであり、繰り返しにより解を求めることになる。

EMアルゴリズムでは、下記の二つのステップを反復することにより、最尤推定値をみつけようとする。

E ステップ: 現在推定されているパラメータの分布θ(t)のもとで、尤度関数の、条件付き確率 P(z|x) に関する期待値を計算する:
Q(\theta|\theta^{(t)}) = \operatorname{E}_{Z|x,\theta^{(t)}}\big[ \log L (\theta;x,Z)  \big] \,
M ステップ: 下記の量Qを最大化するパラメータを求める。
\theta^{(t+1)} = \underset{\theta} {\operatorname{arg\,max}} \ Q(\theta|\theta^{(t)}) \,

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

脚注[編集]

  1. ^ a b c 計算統計I, p. 130.
  2. ^ 計算統計I, p. 157.
  3. ^ 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. MR:0501537. 
  4. ^ 計算統計I, p. 163.
  5. ^ 計算統計I, p. 158.
  6. ^ Matsuyama, Yasuo (2003). “The α-EM algorithm: Surrogate likelihood maximization using α-logarithmic information measures”. IEEE Transactions on Information Theory 49 (3): 692-706. 
  7. ^ 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. 

参考文献[編集]