Memoized Online Variational Inference for Dirichlet Process Mixture Models

Michael C. Hughes, Erik B. SudderthNeurIPS 2013 · OpenReview

This paper introduces a robust, "tuning-free" approach to scaling Bayesian nonparametric models to massive datasets. By combining a clever caching strategy with principled "birth and merge" moves, the authors demonstrate how to escape the local optima that frequently plague traditional stochastic inference.

TL;DR

The authors propose Memoized Online Variational Inference, an algorithm that scales Dirichlet Process Mixture Models (DPMMs) to millions of data points without the headache of tuning learning rates. By caching sufficient statistics and using adaptive birth/merge moves, the model dynamically discovers the optimal number of clusters while remaining highly robust to poor initializations compared to standard stochastic gradient methods.

The Challenge with Bayesian Nonparametrics

Bayesian Nonparametric (BNP) models, such as the Dirichlet Process, are powerful because they do not require pre-specifying the number of clusters in the data—the model learns the complexity as it observes more evidence. However, scaling these models presents two primary computational challenges:

  1. Scalability: Traditional "batch" inference requires evaluating the entire dataset before making a single update, which is computationally infeasible for millions of images or documents.
  2. Local Optima: While Stochastic Variational Inference (SVI) scales well by processing small batches, it is notoriously sensitive to the "learning rate" (step size). If the rate is suboptimal, the model often gets stuck in poor local optima—for example, permanently merging two distinct clusters.

Methods: Memoization and Non-Local Moves

The authors introduce two key innovations to resolve these scalability and optimization issues:

1. Memoized Updates

In standard SVI, the algorithm takes a "noisy" gradient step based on the current batch. In Memoized VI, the algorithm maintains a cache (a "memo") of the sufficient statistics for every batch of data.

When the algorithm visits a batch, it subtracts the old cached statistics from the global total and adds the new ones. This allows the model to perform "noise-free" global updates that reflect the state of the entire dataset, even though it only processes one batch at a time. Crucially, this eliminates the need for a learning rate ($ ho_t$) altogether.

2. Birth and Merge Moves

To prevent the model from getting stuck in local optima, the authors developed "non-local" moves that drastically alter the model's structure:

  • Birth Moves: The model identifies data points that are poorly explained by current clusters and "proposes" several new clusters at once to expand the original model.
  • Merge Moves: The model identifies redundant or overlapping clusters and attempts to combine them to remove redundancy.
Illustration of the Birth Move and memoized summary updates across data batches.

Crucially, these moves are validated against the ELBO (Evidence Lower Bound). Because the memoized approach tracks the global objective exactly, the algorithm only accepts a merge or birth if it mathematically improves the overall model fit.

Key Insights

  • Additivity is the Secret Sauce: For exponential family models, global sufficient statistics are simply the sum of batch statistics. Caching these allows for exact global updates without holding the full dataset in memory.
  • Escaping the "Greedy" Trap: Standard Variational Inference is a greedy coordinate ascent. By adding birth/merge moves, the authors transform it into a more global search, allowing the model to "undo" bad decisions made early in training.
  • Nested Truncation: The authors utilize a "nested" variational bound. This allows them to add new clusters (increasing the truncation level $K$) without invalidating the mathematical guarantees of the previous state.

Key Results

The authors evaluated their approach on several benchmarks, including synthetic data, MNIST, SUN-397, and a massive Berkeley Segmentation Dataset (up to 8.64 million patches) for image denoising.

  • Robustness: On toy datasets, the memoized birth-merge (MO-BM) algorithm consistently found the correct true components regardless of starting conditions. Standard SVI and batch VI frequently failed, getting trapped in local optima.
  • Superior Model Fit: MO-BM consistently reached higher ELBO values than SVI, even when SVI was given "smart" initializations like k-means++.
Comparison of log evidence over multiple passes through the data. MO-BM (red) consistently reaches the highest evidence, avoiding the local optima that trap standard stochastic methods.
  • Scalability in Denoising: On the 8.64 million image patch dataset, the model successfully learned a complex mixture that performed image denoising at a level nearly identical to state-of-the-art specialized models, proving that the memory overhead of "memoization" is manageable at scale.

Limitations and Future Work

While highly effective, the memoized approach requires storing sufficient statistics for every batch. For datasets with a massive number of batches or very high-dimensional latent spaces, this memory requirement could become a bottleneck. Furthermore, unlike "streaming" SVI which might only see each data point once, Memoized VI is designed for environments where multiple passes through the data are feasible. Applying these birth/merge moves to more complex hierarchical models, like Latent Dirichlet Allocation, remains a promising direction for future research.

Summary updated

Abstract

Variational inference algorithms provide the most effective framework for large-scale training of Bayesian nonparametric models. Stochastic online approaches are promising, but are sensitive to the chosen learning rate and often converge to poor local optima. We present a new algorithm, memoized online variational inference, which scales to very large (yet finite) datasets while avoiding the complexities of stochastic gradient. Our algorithm maintains finite-dimensional sufficient statistics from batches of the full dataset, requiring some additional memory but still scaling to millions of examples. Exploiting nested families of variational bounds for infinite nonparametric models, we develop principled birth and merge moves allowing non-local optimization. Births adaptively add components to the model to escape local optima, while merges remove redundancy and improve speed. Using Dirichlet process mixture models for image clustering and denoising, we demonstrate major improvements in robustness and accuracy.
BibTeX
@inproceedings{hughes2013memoized,
  author = {Michael C. Hughes and Erik B. Sudderth},
  title = {{Memoized Online Variational Inference for Dirichlet Process Mixture Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=B1-RGYbO-S},
}

Loading related content...

Figure