research-article

Estimating local optimums in EM algorithm over Gaussian mixture model

Authors:

Zhenjie Zhang,

Bing Tian Dai,

Anthony K. H. TungAuthors Info & Claims

ICML '08: Proceedings of the 25th international conference on Machine learning

Pages 1240 - 1247

https://doi.org/10.1145/1390156.1390312

Published: 05 July 2008 Publication History

Get Access

Abstract

EM algorithm is a very popular iteration-based method to estimate the parameters of Gaussian Mixture Model from a large observation set. However, in most cases, EM algorithm is not guaranteed to converge to the global optimum. Instead, it stops at some local optimums, which can be much worse than the global optimum. Therefore, it is usually required to run multiple procedures of EM algorithm with different initial configurations and return the best solution. To improve the efficiency of this scheme, we propose a new method which can estimate an upper bound on the logarithm likelihood of the local optimum, based on the current configuration after the latest EM iteration. This is accomplished by first deriving some region bounding the possible locations of local optimum, followed by some upper bound estimation on the maximum likelihood. With this estimation, we can terminate an EM algorithm procedure if the estimated local optimum is definitely worse than the best solution seen so far. Extensive experiments show that our method can effectively and efficiently accelerate conventional multiple restart EM algorithm.

References

[1]

Dempster, A. P., Laird, N. M., & Robin, D. B. (1977). Maximum likelihood from incomplete data via the em algorithm (with discussion). Journal of Royal Statistical Society B, 39, 1--38.

Crossref

Google Scholar

[2]

Elkan, C. (2003). Using the triangle inequality to accelerate k-means. ICML (pp. 147--153).

Google Scholar

[3]

Jordan, M. I., & Xu, L. (1995). Convergence results for the em approach to mixtures of experts architectures. Neural Networks, 8, 1409--1431.

Digital Library

Google Scholar

[4]

Kanungo, T., Mount, D., Netanyahu, N., Piatko, C., Silverman, R., & Wu, A. (2002). An efficient k-means clustering algorithm: analysis and implementation.

Google Scholar

[5]

Lutkepohl, H. (1996). Handbook of matrices. John Wiley & Sons Ltd.

Google Scholar

[6]

Ma, J., Xu, L., & Jordan, M. I. (2001). Asymptotic convergence rate of the em algorithm for gaussian mixtures. Neural Computation, 12, 2881--2907.

Digital Library

Google Scholar

[7]

McLachlan, G., & Krishnan, T. (1996). The em algorithm and extensions. Wiley-Interscience.

Google Scholar

[8]

McLachlan, G., & Peel, D. (2000). Finite mixture models. Wiley-Interscience.

Google Scholar

[9]

Xu, L., & Jordan, M. I. (1996). On convergence properties of the em algorithm for gaussian mixtures. Neural Computation, 8, 129--151.

Digital Library

Google Scholar

[10]

Zhang, Z., Dai, B. T., & Tung, A. K. H. (2006). On the lower bound of local optimums in k-means algorithm. ICDM (pp. 775--786).

Digital Library

Google Scholar

[11]

Zhang, Z., Dai, B. T., & Tung, A. K. H. (2008). Estimating local optimums in em algorithm over gaussian mixture model. http://www.comp.nus.edu.sg/~zhangzh2/papers/em.pdf.

Google Scholar

Cited By

View all

Benabdellah ABenghabrit ABouhaddou IBenghabrit O(2020)Design for relevance concurrent engineering approach: integration of IATF 16949 requirements and design for X techniquesResearch in Engineering Design10.1007/s00163-020-00339-4Online publication date: 18-Apr-2020
https://doi.org/10.1007/s00163-020-00339-4
Benabdellah ABenghabrit ABouhaddou I(2019)A survey of clustering algorithms for an industrial contextProcedia Computer Science10.1016/j.procs.2019.01.022148(291-302)Online publication date: 2019
https://doi.org/10.1016/j.procs.2019.01.022
Xu YZhu YZhang ZZhang YYu P(2015)Convex Approximation to the Integral Mixture Models Using Step FunctionsProceedings of the 2015 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM.2015.48(479-488)Online publication date: 14-Nov-2015
https://dl.acm.org/doi/10.1109/ICDM.2015.48
Show More Cited By

Index Terms

Estimating local optimums in EM algorithm over Gaussian mixture model

Recommendations

A BYY Split-and-Merge EM Algorithm for Gaussian Mixture Learning
ISNN '08: Proceedings of the 5th international symposium on Neural Networks: Advances in Neural Networks

Gaussian mixture is a powerful statistic tool and has been widely used in the fields of information processing and data analysis. However, its model selection, i.e., the selection of number of Gaussians in the mixture, is still a difficult problem. ...
A Novel Split and Merge EM Algorithm for Gaussian Mixture Model
ICNC '09: Proceedings of the 2009 Fifth International Conference on Natural Computation - Volume 06

As an extremely powerful probability model, Gaussian mixture model (GMM) has been widely used in fields of pattern recognition, information processing and data mining. If the number of the Gaussians in the mixture is pre-known, the well-known ...
A Greedy EM Algorithm for Gaussian Mixture Learning

Learning a Gaussian mixture with a local algorithm like EM can be difficult because (i) the true number of mixing components is usually unknown, (ii) there is no generally accepted method for parameter initialization, and (iii) the algorithm can get ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICML '08: Proceedings of the 25th international conference on Machine learning

July 2008

1310 pages

ISBN:9781605582054

DOI:10.1145/1390156

General Chair:
William Cohen
Carnegie Mellon University
,
Program Chairs:
Andrew McCallum
University of Massachusetts Amherst
,
Sam Roweis
University of Toronto and Google

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICML '08

Sponsor:

Microsoft Research
Intel
IBM

ICML '08: The 25th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

July 5 - 9, 2008

Helsinki, Finland

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
315
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Benabdellah ABenghabrit ABouhaddou IBenghabrit O(2020)Design for relevance concurrent engineering approach: integration of IATF 16949 requirements and design for X techniquesResearch in Engineering Design10.1007/s00163-020-00339-4Online publication date: 18-Apr-2020
https://doi.org/10.1007/s00163-020-00339-4
Benabdellah ABenghabrit ABouhaddou I(2019)A survey of clustering algorithms for an industrial contextProcedia Computer Science10.1016/j.procs.2019.01.022148(291-302)Online publication date: 2019
https://doi.org/10.1016/j.procs.2019.01.022
Xu YZhu YZhang ZZhang YYu P(2015)Convex Approximation to the Integral Mixture Models Using Step FunctionsProceedings of the 2015 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM.2015.48(479-488)Online publication date: 14-Nov-2015
https://dl.acm.org/doi/10.1109/ICDM.2015.48
Reed EMengshoel O(2014)Bayesian network parameter learning using EM with parameter sharingProceedings of the Eleventh UAI Conference on Bayesian Modeling Applications Workshop - Volume 121810.5555/3020299.3020305(48-59)Online publication date: 27-Jul-2014
https://dl.acm.org/doi/10.5555/3020299.3020305
Matsubara YSakurai YFaloutsos CIwata TYoshikawa MYang QAgarwal DPei J(2012)Fast mining and forecasting of complex time-stamped eventsProceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2339530.2339577(271-279)Online publication date: 12-Aug-2012
https://dl.acm.org/doi/10.1145/2339530.2339577
Bubeck SMeilă Mvon Luxburg U(2012)How the initialization affects the stability of the қ-means algorithmESAIM: Probability and Statistics10.1051/ps/201201316(436-452)Online publication date: 4-Sep-2012
https://doi.org/10.1051/ps/2012013
Karabacak MCirpan HArslan H(2011)An efficient modulation identification algorithm without constellation map knowledge2011 IEEE Radio and Wireless Symposium10.1109/RWS.2011.5725472(146-149)Online publication date: Jan-2011
https://doi.org/10.1109/RWS.2011.5725472
Zhao QHautamaki VFranti P(2011)RSEMProceedings of the 2011 Sixth International Conference on Image and Graphics10.1109/ICIG.2011.110(135-140)Online publication date: 12-Aug-2011
https://dl.acm.org/doi/10.1109/ICIG.2011.110
Matsubara YSakurai YYoshikawa M(2011)D-Search: an efficient and exact search algorithm for large distribution setsKnowledge and Information Systems10.1007/s10115-010-0336-629:1(131-157)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s10115-010-0336-6
Tran KJin H(2010)Detecting Network Anomalies in Mixed-Attribute Data SetsProceedings of the 2010 Third International Conference on Knowledge Discovery and Data Mining10.1109/WKDD.2010.96(383-386)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1109/WKDD.2010.96
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A BYY Split-and-Merge EM Algorithm for Gaussian Mixture Learning

A Novel Split and Merge EM Algorithm for Gaussian Mixture Model

A Greedy EM Algorithm for Gaussian Mixture Learning