MAD-Bayes: MAP-based Asymptotic Derivations from Bayes

Tamara Broderick, Brian Kulis, Michael I. Jordan

Abstract

The classical mixture of Gaussians model is related to K-means via small-variance asymptotics: as the covariances of the Gaussians tend to zero, the negative log-likelihood of the mixture of Gaussians model approaches the K-means objective, and the EM algorithm approaches the K-means algorithm. Kulis & Jordan (2012) used this observation to obtain a novel K-means-like algorithm from a Gibbs sampler for the Dirichlet process (DP) mixture. We instead consider applying small-variance asymptotics directly to the posterior in Bayesian nonparametric models. This framework is independent of any specific Bayesian inference algorithm, and it has the major advantage that it generalizes immediately to a range of models beyond the DP mixture. To illustrate, we apply our framework to the feature learning setting, where the beta process and Indian buffet process provide an appropriate Bayesian nonparametric prior. We obtain a novel objective function that goes beyond clustering to learn (and penalize new) groupings for which we relax the mutual exclusivity and exhaustivity assumptions of clustering. We demonstrate several other algorithms, all of which are scalable and simple to implement. Empirical results demonstrate the benefits of the new framework.

Introduction

In unsupervised learning, K-means remains the "gold standard" due to its simplicity and computational efficiency. However, it suffers from two significant limitations: the requirement to pre-specify the number of clusters ($K$) and the rigid assumption that every data point belongs to exactly one cluster.

Bayesian Nonparametrics (BNP) offer a robust alternative. Models like the Dirichlet Process (DP) can infer the number of clusters from data, while the Indian Buffet Process (IBP) allows for "feature allocation," where a single data point can be described by multiple latent features (e.g., an image containing a "person," "dog," and "outdoors"). Despite their flexibility, BNP inference typically relies on complex, computationally expensive stochastic methods like Gibbs sampling or Variational Inference, which lack the "hard-assignment" speed of K-means.

Methodology: The MAD-Bayes Framework

The MAD-Bayes (MAP-based Asymptotic Derivations) framework bridges the gap between the flexibility of BNP and the speed of K-means. The core technique involves small-variance asymptotics, examining the behavior of the Bayesian posterior as the variance of the data likelihood ($\sigma^2$) approaches zero.

Objective over Algorithm

Unlike previous approaches that simplified specific sampling algorithms, MAD-Bayes simplifies the Maximum A Posteriori (MAP) objective itself. As $\sigma^2 \to 0$, the log-likelihood term in the posterior transforms into a squared Euclidean distance, mirroring the K-means objective. To prevent the model from over-fitting by assigning every point its own cluster, the authors scale the prior hyperparameters relative to the variance, causing the prior parameter to vanish exponentially as variance decreases.

BP-means and Feature Learning

The flagship contribution of this framework is BP-means, derived from the Indian Buffet Process. The resulting objective function minimizes the reconstruction error of a data matrix $X \approx ZA$ (where $Z$ is a binary feature matrix and $A$ is a feature means matrix) plus a penalty $\lambda^2$ for every new feature introduced. This $\lambda^2$ penalty acts as a formal justification for "elbow-method" heuristics, providing a principled way to penalize model complexity.

Experimental Evaluation

Tabletop Object Discovery

The authors tested BP-means on a dataset of 100 images featuring combinations of four distinct objects: a prehistoric axe, a Klein bottle, a cellphone, and a $20 bill. Unlike clustering, which would require $2^4 = 16$ clusters to represent every possible combination, BP-means efficiently identifies the 4 underlying features.

Feature learning on tabletop data: binary assignments represent the presence of objects, demonstrating how the model learns additive and subtractive feature combinations.

This highlights a key insight regarding identifiability: in feature learning, there is no single "true" set. A scene can be described as an empty table with objects added, or a full table with objects subtracted. The BP-means objective handles this combinatorial complexity far more efficiently than traditional clustering.

Computational Efficiency

One of the most striking results of the MAD-Bayes framework is the massive gain in speed. On the Tabletop dataset, a single run of BP-means took only 0.36 seconds, compared to 8,500 seconds for a standard IBP Gibbs sampler.

Performance comparison: BP-means (BP-m) and its variants achieve massive speedups over traditional Gibbs sampling while maintaining the ability to find the optimal number of features.

Even when accounting for multiple random restarts to avoid local optima, the MAD-Bayes approach remains orders of magnitude faster than stochastic inference methods.

Conclusion

The MAD-Bayes framework provides a principled derivation for simple, scalable algorithms from complex Bayesian models. By moving beyond simple clustering to feature learning, BP-means allows for more nuanced data representation without the computational overhead of traditional BNP methods. While challenges remain regarding local optima and hyperparameter tuning for $\lambda^2$, the framework opens new doors for applying BNP flexibility to large-scale, real-world datasets.

Summary updated

Abstract

The classical mixture of Gaussians model is related to K-means via small-variance asymptotics: as the covariances of the Gaussians tend to zero, the negative log-likelihood of the mixture of Gaussians model approaches the K-means objective, and the EM algorithm approaches the K-means algorithm. Kulis & Jordan (2012) used this observation to obtain a novel K-means-like algorithm from a Gibbs sampler for the Dirichlet process (DP) mixture. We instead consider applying small-variance asymptotics directly to the posterior in Bayesian nonparametric models. This framework is independent of any specific Bayesian inference algorithm, and it has the major advantage that it generalizes immediately to a range of models beyond the DP mixture. To illustrate, we apply our framework to the feature learning setting, where the beta process and Indian buffet process provide an appropriate Bayesian nonparametric prior. We obtain a novel objective function that goes beyond clustering to learn (and penalize new) groupings for which we relax the mutual exclusivity and exhaustivity assumptions of clustering. We demonstrate several other algorithms, all of which are scalable and simple to implement. Empirical results demonstrate the benefits of the new framework.
BibTeX
@inproceedings{broderick2013mad,
  author = {Tamara Broderick and Brian Kulis and Michael I. Jordan},
  title = {{MAD-Bayes: MAP-based Asymptotic Derivations from Bayes}},
  booktitle = {International Conference on Machine Learning},
  year = {2013},
  url = {https://openreview.net/forum?id=SJ4cJsW_WB},
}
Figure