On convergence and parameter selection of the EM and DA-EM algorithms for Gaussian mixtures. (May 2018)

• Record Type: Journal Article
• Authors: Yu, Jian; Chaomurilige, Chaomu; Yang, Miin-Shen
• Is Part Of: Pattern recognition. Volume 77(2018:May)
• Page Start: 188
• Page End: 203
• Publication Date: 2018-05
• Subjects: Expectation & maximization (EM) algorithm -- Deterministic annealing EM (DA-EM) -- GAUSSIAN mixtures -- Self-annealing -- Convergence -- Parameter selection; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.12.014
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We investigate theoretical behaviors of the EM and DA-EM algorithms. We propose a theoretical lower bound for initialization of the annealing parameter in the DA-EM algorithm. We theoretically prove that, the EM algorithm for Gaussian mixtures actually exhibits the self-annealing behavior. Experimental results actually indicate that our theoretical results are applicable in practice. Abstract: The expectation & maximization (EM) for Gaussian mixtures is popular as a clustering algorithm. However, the EM algorithm is sensitive to initial values, and so Ueda and Nakano [4] proposed the deterministic annealing EM (DA-EM) algorithm to improve it. In this paper, we investigate theoretical behaviors of the EM and DA-EM algorithms. We first derive a general Jacobian matrix of the DA-EM algorithm with respect to posterior probabilities. We then propose a theoretical lower bound for initialization of the annealing parameter in the DA-EM algorithm. On the other hand, some researches mentioned that the EM algorithm exhibits a self-annealing behavior, that is, the equal posterior probability with small random perturbations can avoid the EM algorithm to output the mass center for Gaussian mixtures. However, there is no theoretical analysis on this self-annealing property. Since the DA-EM will become the EM when the annealing parameter is 1, according to the Jacobian matrix of the DA-EM, we can prove the self-annealing property of the EM algorithm for Gaussian mixtures. Based on these results, we give not only convergence behaviors of the equal posterior probabilities and initialization lower bound of the temperature parameter of the DA-EM, but also a theoretical explanation why the EM algorithm for Gaussian mixtures exhibits a self-annealing behavior.