Zhang-Zhang-Yi (2004) Competitive EM Algorithm for Finite Mixture Models

Summary

Zhang, Zhang, and Yi (2004) propose the Competitive Expectation-Maximization (CEM) algorithm for finite Gaussian Mixture Models (GMMs), which simultaneously solves EM's three main failure modes: local maxima traps, boundary convergence of degenerate components, and inability to determine $k$ automatically. CEM uses local Kullback divergence $J(m;\theta)$ to assign competitive split/merge probabilities — high-divergence components (poor local fit) are more likely to split, low-divergence hypothetical merges are more likely to be accepted — so the algorithm directs structural operations where they are most needed rather than sampling operation type uniformly. A Metropolis-style acceptance step with temperature $\gamma = 10$ allows uphill moves, and the CEM$^2$ sequential-update rule prevents cascading multi-component death. CEM decisively beats Annihilation EM (AEM; Figueiredo-Jain 2002) when prior probabilities are unequal (success rate $P_s$ = 90.2–96.9% vs. 60.3–71.0% vs. 19.0–59.2% for EM) and is applied to Chinese character stroke extraction.

Key Claims

• EM has three structural failure modes: (1) sensitivity to initialization and local maxima; (2) boundary convergence (a component's variance collapses around a few points); (3) no automatic $k$ selection.
• Deterministic Annealing EM (DAEM; Ueda-Nakano 1998) escapes local maxima via temperature annealing but cannot redistribute components in data space when trapped.
• Split and Merge EM (SMEM; Ueda-Nakano-Ghahramani-Hinton 2000) uses split/merge when locally trapped but fixes $k$ and defines split/merge criteria separately, causing cyclic futile oscillation between operations.
• AEM (Figueiredo-Jain 2002) adds a Minimum Message Length (MML)-based criterion and annihilation but fails when component priors are unequal because the penalty is not sensitive to per-component fit quality.
• CEM model evaluation criterion (from Figueiredo-Jain 2002, eq. 5): $L(\theta, \mathbf{X}) = \log p(\mathbf{X}|\theta) - \frac{N}{2}\sum_m \log\!\frac{n\alpha_m}{12} - \frac{k}{2}\log\frac{n}{12} - \frac{k(N+1)}{2}$, where N is the number of parameters per component.
• Split/merge probabilities via local Kullback divergence (eqs. 7–10): $J(m;\theta) = \int f_m(x;\theta)\log\frac{f_m(x;\theta)}{p_m(x;\theta_m)} dx$ where $f_m$ is the empirical distribution weighted by posterior component assignments. $P_\text{split}(m;\theta) \propto J(m;\theta)$; $P_\text{merge}(m,l;\theta) \propto \beta / J(m';\theta')$ where $m'$ is the hypothetical merged component.
• Metropolis acceptance (eq. 14): $P_a = \min(\exp\{[L(\theta(t+1),\mathbf{X}) - L(\theta(t),\mathbf{X})]/\gamma\}, 1)$ with $\gamma = 10$.
• Annihilation (eq. 15): component $m$ dies if $n\alpha_m < N$; CEM$^2$ sequential updating prevents simultaneous death of multiple components.
• Example 1 (8-GMM, equal priors $\alpha_i = 1/8$, 2000 samples): CEM $P_s$ = 99.6–100.0%, EM $P_s$ = 46.7–73.3%, AEM $P_s$ = 100.0% but with 250.1–313.5 average iterations vs. CEM's 11.7–52.4. AEM equivalent to CEM with equal priors.
• Example 2 (4-GMM, $\alpha_4 = 0.1$ unequal prior, 1000 samples): CEM $P_s$ = 90.2–96.9%, AEM $P_s$ = 60.3–71.0%, EM $P_s$ = 19.0–59.2%. CEM's decisive advantage comes from the per-component $J(m;\theta)$ criterion which is not fooled by the small-prior component.
• Application to Chinese character stroke extraction: 500–2500 foreground pixels per character; CEM applied as a GMM to 2D pixel coordinates correctly extracts strokes, including overlapping strokes.
• AEM's key failure mode: when $\alpha_4 = 0.1$, the global MML penalty under-penalizes the small component early in search, causing AEM to miss the correct $k$.

Concepts Introduced or Extended

• Mixture of Normals

Entities Mentioned

• Baibo Zhang
• Changshui Zhang
• Xing Yi

Quotes

"When there is great disparity between the components' prior probabilities, it sometimes fails to find the global optimal solution." — on AEM (Figueiredo-Jain 2002), p. 132

"CEM is insensitive to the initial configuration of the component number and model parameters." — key advantage claimed by the authors, p. 132–133

My Take

The core innovation is replacing uniform operation-type sampling with competitive, data-driven probabilities derived from local fit quality — a simple and elegant idea. The $J(m;\theta)$ criterion is the right thing to measure: a component that poorly fits its local data should split; two components whose post-merge divergence is low were probably representing the same cluster. The Metropolis acceptance step is borrowed from simulated annealing and the $\gamma=10$ is set by experiment without theoretical justification. CEM$^2$ comes from Celeux et al. (1999). The approach is strictly frequentist/maximum likelihood (ML) with no Bayesian interpretation; a Bayesian counterpart would use reversible-jump Markov chain Monte Carlo (MCMC) (Green 1995). The MML criterion inherited from Figueiredo-Jain is known to outperform Bayesian Information Criterion (BIC) / Minimum Description Length (MDL) for mixture model selection; the contribution here is the competitive mechanism layered on top of it.