EMアルゴリズム
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アルゴリズムでは、下記の二つのステップを反復することにより、最尤推定値をみつけようとする。
![Q(\theta|\theta^{(t)}) = \operatorname{E}_{Z|x,\theta^{(t)}}\big[ \log L (\theta;x,Z) \big] \,](http://upload.wikimedia.org/math/5/0/b/50b478aab80e4b7fa265b9c29b6a020a.png)
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]
[編集] 脚注
- ^ a b c 計算統計I, p. 130.
- ^ 計算統計I, p. 157.
- ^ 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.
- ^ 計算統計I, p. 163.
- ^ 計算統計I, p. 158.
- ^ Matsuyama, Yasuo (2003). “The α-EM algorithm: Surrogate likelihood maximization using α-logarithmic information measures”. IEEE Transactions on Information Theory 49 (3): 692-706.
- ^ 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.
[編集] 参考文献
- Robert Hogg, Joseph McKean and Allen Craig. Introduction to Mathematical Statistics. pp. 359-364. Upper Saddle River, NJ: Pearson Prentice Hall, 2005.
- The on-line textbook: Information Theory, Inference, and Learning Algorithms, 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.
- A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, by Jeff Bilmes includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
- Variational Algorithms for Approximate Bayesian Inference, by M. J. Beal includes comparisons of EM to Variational Bayesian EM and derivations of several models including Variational Bayesian HMMs.
- The Expectation Maximization Algorithm, by Frank Dellaert, gives an easier explanation of EM algorithm in terms of lowerbound maximization.
- The Expectation Maximization Algorithm: A short tutorial, A self contained derivation of the EM Algorithm by Sean Borman.
- The EM Algorithm, by Xiaojin Zhu.
- 汪金芳、手塚集、上田修功、田栗正章、樺島祥介、甘利俊一、竹村彰通、竹内啓、伊庭幸人 『計算統計 I ―確率計算の新しい手法』11巻〈統計科学のフロンティア〉、2003年。ISBN 4000068512。
