Abstract
The EM algorithm is a popular method for parameter estimation in situations where the data can be viewed as being incomplete. As each E-step visits each data point on a given iteration, the EM algorithm requires considerable computation time in its application to large data sets. Two versions, the incremental EM (IEM) algorithm and a sparse version of the EM algorithm, were proposed recently by Neal R.M. and Hinton G.E. in Jordan M.I. (Ed.), Learning in Graphical Models, Kluwer, Dordrecht, 1998, pp. 355–368 to reduce the computational cost of applying the EM algorithm. With the IEM algorithm, the available n observations are divided into B (B ≤ n) blocks and the E-step is implemented for only a block of observations at a time before the next M-step is performed. With the sparse version of the EM algorithm for the fitting of mixture models, only those posterior probabilities of component membership of the mixture that are above a specified threshold are updated; the remaining component-posterior probabilities are held fixed. In this paper, simulations are performed to assess the relative performances of the IEM algorithm with various number of blocks and the standard EM algorithm. In particular, we propose a simple rule for choosing the number of blocks with the IEM algorithm. For the IEM algorithm in the extreme case of one observation per block, we provide efficient updating formulas, which avoid the direct calculation of the inverses and determinants of the component-covariance matrices. Moreover, a sparse version of the IEM algorithm (SPIEM) is formulated by combining the sparse E-step of the EM algorithm and the partial E-step of the IEM algorithm. This SPIEM algorithm can further reduce the computation time of the IEM algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bradley P.S., Fayyad U.M., and Reina C.A. 1998. Scaling EM (expectation-maximization) clustering to large databases. Technical Report No. MSR-TR-98-35 (revised February, 1999), Microsoft Research, Seattle.
Dempster A.P., Laird N.M., and Rubin D.B. 1977. Maximum likelihood from incomplete data via the EM algorithm (with discussion). Journal of the Royal Statistical Society Series B 39: 1–38.
Friedman J.H. 1989. Regularized discriminant analysis. Journal of the American Statistical Association 84: 165–175.
Fukunaga K. 1990. Statistical Pattern Recognition, 2nd edn. Academic Press, New York.
Jamshidian M. and Jennrich R.I. 1993. Conjugate gradient acceleration of the EM algorithm. Journal of the American Statistical Association 88: 221–228.
Jamshidian M. and Jennrich R.I. 1997. Acceleration of the EM algorithm by using quasi-Newton methods. Journal of the Royal Statistical Society Series B 59: 569–587.
Liang Z., MacFall J.R., and Harrington D.P. 1994. Parameter estimation and tissue segmentation from multispectral MR images. IEEE Transactions on Medical Imaging 13: 441–449.
McCallum A., Nigam K., and Ungar L.H. 2000. Efficient clustering of high-dimensional data sets with application to reference matching. In: Proceeding of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, New York, pp. 169–178.
McLachlan G.J. and Krishnan T. 1997. The EM Algorithm and Extensions. Wiley, New York.
McLachlan G.J. and Ng S.K. 2000. A sparse version of the incremental EM algorithm for large databases. Technical Report, Centre of Statistics, University of Queensland.
McLachlan G.J. and Peel D. 2000. Finite Mixture Models. Wiley, New York.
McLachlan G.J., Peel D., Basford K.E., and Adams P. 1999. The EMMIX software for the fitting of mixtures of normal and tcomponents. Journal of Statistical Software 4(2).
Meilijson I. 1989. A fast improvement to the ECM algorithm on its own terms. Journal of the Royal Statistical Society Series B 51: 127–138.
Meng X.L. 1994. On the rate of convergence of the ECM algorithm. Annals of Statistics 22: 326–339.
Meng X.L. and Rubin D.B. 1993. Maximum likelihood estimation via the ECM algorithm: A general framework. Biometrika 80: 267–278.
Meng X.L. and van Dyk D. (1997). The EM algorithm-An old folksong sung to a fast newtune (with discussion). Journal of the Royal Statistical Society Series B 59: 511–567.
Moore A.W. 1999. Very fast EM-based mixture model clustering using multiresolution kd-trees. In: Kearns M.S., Solla S.A., and Cohn D.A. (Eds.), Advances in Neural Information Processing Systems 11. MIT Press, Cambridge, MA, pp. 543–549.
Neal R.M. and Hinton G.E. 1998. A view of the EM algorithm that justifies incremental, sparse, and other variants. In: Jordan M.I. (Ed.), Learning in Graphical Models. Kluwer, Dordrecht, pp. 355–368.
Thiesson B. 1995. Accelerated quantification of Bayesian networks with incomplete data. In: Fayyad U.M. and Uthurusamy R. (Eds.), Proceedings of First International Conference on Knowledge Discovery and Data Mining. AAAI Press, pp. 306–311.
Thiesson B., Meek C., and Heckerman D. 2001. Accelerating EM for large databases. Machine Learning 45: 279–299.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ng, S.K., McLachlan, G.J. On the choice of the number of blocks with the incremental EM algorithm for the fitting of normal mixtures. Statistics and Computing 13, 45–55 (2003). https://doi.org/10.1023/A:1021987710829
Issue Date:
DOI: https://doi.org/10.1023/A:1021987710829