Estimating local optimums in EM algorithm over Gaussian mixture model

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.
• 2: Elkan, C. (2003). Using the triangle inequality to accelerate k-means. ICML (pp. 147--153).
• 3: Michael I. Jordan , Lei Xu, Convergence results for the EM approach to mixtures of experts architectures, Neural Networks, v.8 n.9, p.1409-1431, 1995 [doi>10.1016/0893-6080(95)00014-3]
• 4: Kanungo, T., Mount, D., Netanyahu, N., Piatko, C., Silverman, R., & Wu, A. (2002). An efficient k-means clustering algorithm: analysis and implementation.
• 5: Lutkepohl, H. (1996). Handbook of matrices. John Wiley & Sons Ltd.
• 6: Jinwen Ma , Lei Xu , Michael I. Jordan, Asymptotic Convergence Rate of the EM Algorithm for Gaussian Mixtures, Neural Computation, v.12 n.12, p.2881-2907, December 2000 [doi>10.1162/089976600300014764]
• 7: McLachlan, G., & Krishnan, T. (1996). The em algorithm and extensions. Wiley-Interscience.
• 8: McLachlan, G., & Peel, D. (2000). Finite mixture models. Wiley-Interscience.
• 9: Lei Xu , Michael I. Jordan, On convergence properties of the em algorithm for gaussian mixtures, Neural Computation, v.8 n.1, p.129-151, January 1996 [doi>10.1162/neco.1996.8.1.129]
• 10: Zhenjie Zhang , Bing Tian Dai , Anthony K. H. Tung, On the Lower Bound of Local Optimums in K-Means Algorithm, Proceedings of the Sixth International Conference on Data Mining, p.775-786, December 18-22, 2006 [doi>10.1109/ICDM.2006.118]
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
      G.1.7 Ordinary Differential Equations
          Subjects: Convergence and stability

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory