Warped Mixtures for Nonparametric Cluster Shapes

Tomoharu Iwata, David Duvenaud, Zoubin Ghahramani

TL;DR

The Infinite Warped Mixture Model (iWMM) solves a classic problem in unsupervised learning: standard Gaussian Mixture Models (GMMs) fail when clusters are curved or complexly shaped. By using Gaussian Processes to nonlinearly "warp" a simple latent mixture into the observed space, this model can automatically infer the number, shape, and intrinsic dimensionality of non-Gaussian clusters.

What Problem Does This Paper Address?

In traditional clustering, we often assume that data points in a cluster are distributed according to a parametric density, usually a Gaussian. However, real-world data is rarely that polite. Imagine a dataset where points form a "banana" shape or a spiral. A standard GMM will try to cover that single curved cluster with many small ellipsoids, leading to an overestimation of the number of clusters and a poor representation of the data's underlying structure.

While Dirichlet Process Mixture Models (DPMMs) allow for an infinite number of clusters, they still rely on these rigid parametric shapes. The authors tackle the gap between manifold learning (which finds low-dimensional structures) and probabilistic clustering (which assigns points to groups), creating a generative model that handles "nonparametric" cluster shapes.

Methods

The core idea of the iWMM is to perform clustering in a "simple" latent space and then map those clusters into the "complex" observed space.

  1. The Latent Space: The model assumes that data points originate in a low-dimensional latent space where they do follow a standard Infinite Gaussian Mixture Model.
  2. The Warping Function: To get from the latent space to the observed space, the model uses a nonlinear mapping function $f$ sampled from a Gaussian Process (GP). This allows the model to smoothly bend, stretch, and warp the latent Gaussians into arbitrary shapes (like curves or manifolds) in the observed space.
  3. Inference: The authors use a Markov chain Monte Carlo (MCMC) approach. Specifically:
  4. Collapsed Gibbs Sampling to assign points to clusters.
  5. Hybrid Monte Carlo (HMC) to sample the latent coordinates and kernel hyperparameters.
  6. Crucially, they analytically integrate out both the mixture parameters (means/covariances) and the warping function itself, making the inference more efficient.

This can be viewed as a generalization of the Gaussian Process Latent Variable Model (GPLVM). While a GPLVM warps a single Gaussian, the iWMM warps a whole mixture of them.

Datasets

The model was evaluated on a mix of synthetic and real-world benchmarks:

  • Synthetic Shapes: "2-curve", "3-semi", "2-circle", and "Pinwheel" datasets—all designed to be impossible for standard GMMs to cluster correctly.
  • UMIST Faces: A dataset of grayscale images of individuals turning their heads.
  • UCI/LIBSVM Benchmarks: Standard classification datasets used here for unsupervised clustering and density estimation: Iris, Glass, Wine, and Vowel.

Key Insights and Ideas

  • Simplicity via Warping: Complex observed densities are often just simple densities that have undergone a nonlinear transformation. By learning that transformation, we get more interpretable clusters.
  • Automatic Dimensionality: The model can infer the intrinsic dimensionality of each cluster. For example, it can recognize that a cluster in a 10D space actually lies on a 1D curved line.
  • Flexibility Aids Mixing: Interestingly, the authors found that allowing the number of clusters to vary (the "infinite" part) actually helped the MCMC sampler escape local minima. The model could "split" a complex cluster into two during intermediate steps to better explore the space before merging them back into a single warped manifold.
  • Generative Power: Because it is a fully probabilistic generative model, it doesn't just cluster; it can perform density estimation and handle missing data.

Key Results

  • Clustering Accuracy: On the "2-curve" synthetic data, the iWMM achieved an average Rand Index (a measure of clustering similarity) of 0.86, compared to just 0.52 for the standard infinite GMM.
  • Density Estimation: The iWMM consistently outperformed Kernel Density Estimation (KDE) and standard iGMMs in terms of test log-likelihood across almost all real-world datasets (e.g., on the "Glass" dataset, iWMM scored 5.76 vs. KDE's 1.26).
  • Face Manifolds: When applied to the UMIST face images, the model successfully recovered 1D manifolds representing the "head-turning" motion for different individuals, even placing front-facing images of different people near each other in the latent space.

Limitations and Future Work

  • Computational Complexity: Like most Gaussian Process models, the iWMM suffers from $O(N^3)$ scaling due to the need to invert large covariance matrices. This limits the model to datasets of a few thousand points unless "sparse GP" approximations are used.
  • Topological Challenges: The model struggled with certain complex topologies. For instance, in the "2-circle" test, it failed to recover the 1D circular topology of the inner circle, instead modeling it as a 2D blob.
  • Future Directions: The authors suggest extending the model with Hierarchical Dirichlet Processes or Dirichlet Diffusion Trees for more complex latent structures, and implementing sparse GP methods to scale to much larger datasets.

Summary updated

Abstract

A mixture of Gaussians fit to a single curved or heavy-tailed cluster will report that the data contains many clusters. To produce more appropriate clusterings, we introduce a model which warps a latent mixture of Gaussians to produce nonparametric cluster shapes. The possibly low-dimensional latent mixture model allows us to summarize the properties of the high-dimensional clusters (or density manifolds) describing the data. The number of manifolds, as well as the shape and dimension of each manifold is automatically inferred. We derive a simple inference scheme for this model which analytically integrates out both the mixture parameters and the warping function. We show that our model is effective for density estimation, performs better than infinite Gaussian mixture models at recovering the true number of clusters, and produces interpretable summaries of high-dimensional datasets.
BibTeX
@inproceedings{iwata2013warped,
  author = {Tomoharu Iwata and David Duvenaud and Zoubin Ghahramani},
  title = {{Warped Mixtures for Nonparametric Cluster Shapes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=1_RIdnWLuO2},
}

Loading related content...

Figure