Publication
Scaled CGEM: A Fast Accelerated EM
Jörg Fischer; Kristian Kersting
In: Nada Lavrac; Dragan Gamberger; Ljupco Todorovski; Hendrik Blockeel (Hrsg.). Machine Learning: ECML 2003, 14th European Conference on Machine Learning, Proceedings. European Conference on Machine Learning (ECML-2003), September 22-26, Cavtat-Dubrovnik, Croatia, Pages 133-144, Lecture Notes in Computer Science, Vol. 2837, Springer, 2003.
Abstract
The EM algorithm is a popular method for maximum likelihood estimation of Bayesian networks in the presence of missing data. Its simplicity and general convergence properties make it very attractive. However, it sometimes converges slowly. Several accelerated EM methods based on gradient-based optimization techniques have been proposed. In principle, they all employ a line search involving several NP-hard likelihood evaluations. We propose a novel acceleration called SCGEM based on scaled conjugate gradients (SCGs) well-known from learning neural networks. SCGEM avoids the line search by adopting the scaling mechanism of SCGs applied to the expected information matrix. This guarantees a single likelihood evaluation per iteration. We empirically compare SCGEM with EM and conventional conjugate gradient accelerated EM. The experiments show that SCGEM can significantly accelerate both of them and is equal in quality.