An Application of Reversible-Jump MCMC to Multivariate Spherical Gaussian Mixtures

Alan D. MarrsNeurIPS 1997

Choosing the "right" number of clusters in a Gaussian Mixture Model (GMM) is notoriously difficult. This paper by Alan D. Marrs extends the Reversible-Jump Markov Chain Monte Carlo (RJMCMC) algorithm to multivariate data, allowing the model to automatically "jump" between different numbers of components to find the optimal fit without manual tuning.

The "Goldilocks" Problem of Mixture Models

Gaussian Mixture Models are a staple of machine learning, used for everything from density estimation to setting the centers of Radial Basis Function (RBF) networks. However, they suffer from a persistent challenge: determining the optimal number of components ($k$).

If $k$ is too small, the model underfits the data; if it's too large, it overfits. Traditional frequentist methods (like the Likelihood Ratio Test) struggle here because models with different numbers of components aren't strictly "nested," making the mathematics complex. Standard Bayesian approaches often require running multiple separate models for different values of $k$ and comparing them—a computationally expensive and inefficient process.

Reversible-Jump MCMC

To solve this, the author utilizes Reversible-Jump MCMC (RJMCMC), a sophisticated Bayesian technique that treats the number of components ($k$) as a random variable itself.

Unlike standard MCMC, which explores a fixed-dimensional space, RJMCMC can move between parameter subspaces of different dimensions. The paper defines five types of "moves" for the algorithm:

  1. Updating weights: Adjusting how much each Gaussian contributes.
  2. Updating parameters: Tweaking the means ($\mu$) and variances ($\sigma$).
  3. Updating allocation: Re-assigning data points to different clusters.
  4. Updating hyper-parameters: Refining the priors of the model.
  5. Split/Combine (The "Jump"): This is the core innovation. The algorithm can propose splitting one Gaussian into two or merging two neighbors into one.

To ensure the "jump" is mathematically valid, the author uses a Jacobian determinant to account for the change in dimensionality, ensuring the Markov chain remains reversible and converges to the correct distribution. While previous work focused on univariate (1D) data, this paper extends the math to multivariate spherical Gaussians (where clusters are multi-dimensional "balls"). By assuming spherical Gaussians (where variance is the same in all directions for a single component), the author keeps the Jacobian calculation manageable for multivariate data while still capturing complex global distributions. Furthermore, when combining components, the algorithm uses a distance-based probability rather than random selection, making the "combine" move much more likely to be accepted.

Experimental Datasets

The paper evaluates the algorithm on two primary datasets:

  • Simulated Toy Data: 1,000 bivariate (2D) samples generated from a known 20-component mixture model. This provides a "ground truth" to see if the algorithm can recover the original structure.
  • Peterson-Barney Vowel Data: A classic dataset in speech processing consisting of 780 samples. It measures four formant frequencies (features) for 10 different utterances, representing a real-world, higher-dimensional challenge.

Key Results

By including the number of components in the hierarchical prior model, the researcher doesn't have to "guess" the number of clusters. The algorithm naturally spends more time in the "most likely" values of $k$.

On the 20-component simulated data, the RJMCMC chain successfully converged.

Trace plot and histogram showing the convergence of the number of components (k) to a MAP estimate of 17.

As shown above, the chain converged to a Maximum A Posteriori (MAP) value of $k=17$. While not exactly 20, the author notes this is an encouraging result given the high degree of overlap between the original clusters and the relatively small sample size.

Comparison of the 20-component generating model and the resulting MAP estimate model.

The visual comparison between the generating model and the MAP estimate model demonstrates the algorithm's ability to recover the underlying spatial structure effectively.

For the Peterson-Barney vowel data, the algorithm successfully generated a joint distribution of all parameters. When projected onto the first two principal components, the estimated model showed a clear, logical clustering of the vowel sounds. Unlike Expectation-Maximization (EM) algorithms that give a single "best" point estimate, this RJMCMC method provides a full sample of the joint distribution, allowing researchers to see the uncertainty in their cluster assignments.

Limitations and Future Work

  • The Spherical Assumption: The model assumes clusters are spherical. In many real-world datasets, clusters are elongated (ellipsoidal) due to correlations between features. Extending this to full covariance matrices would be the next logical—though mathematically much more complex—step.
  • Computational Cost: MCMC methods are generally slower than the EM algorithm. While RJMCMC is more robust, it may be overkill for very simple problems or massive datasets where speed is the primary concern.
  • Application to RBFs: The author suggests that the next step is using these estimated centers to define the hidden layer of Radial Basis Function networks, potentially automating the architecture design of those neural networks.

Summary updated

BibTeX
@inproceedings{marrs1997application,
  author = {Alan D. Marrs},
  title = {{An Application of Reversible-Jump MCMC to Multivariate Spherical Gaussian Mixtures}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure