PaperlayerView exact revision on arXiv

Source-linked AI summary

MAD-Bayes: MAP-based Asymptotic Derivations from Bayes

Tamara Broderick, Brian Kulis, Michael I. Jordan

arXiv:1212.2126v2stat.ML

TL;DR

The paper addresses limitations of clustering models that require exclusive assignments and a fixed number of clusters. It derives small-variance objectives directly from Bayesian MAP problems and extends them to feature learning, producing scalable algorithms that model overlapping latent structure and outperform existing feature-allocation learners in speed.

  • Problem

    Clustering imposes mutually exclusive, exhaustive assignments and often requires the number of clusters in advance, whereas some data require overlapping features.

    Source: §1 · p. 1

  • Method

    The paper applies small-variance asymptotics directly to Bayesian MAP problems, using EPPF and EFPF representations and extending the framework from CRP clustering to beta-process feature learning.

    Source: §1 · p. 2, §2 · p. 3

  • Results

    The resulting algorithms model latent structure beyond clustering and are much faster than existing feature-allocation learners studied in Bayesian nonparametrics.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The framework provides a general route from Bayesian nonparametric MAP problems to simple hard-assignment objectives and scalable algorithms for overlapping feature structure.

    Source: §1 · p. 2, §6 · p. 9

    Feature allocations may be non-identifiable because multiple combinatorial representations can encode the same data combinations.

    Source: §5.1 · p. 7

Abstract

from arXiv · show

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.

1. Introduction

The paper develops a general small-variance-asymptotic framework applied directly to Bayesian MAP problems, extending K-means-like optimization beyond clustering to feature learning.

1. Introduction

  • K-means is scalable and popular but imposes mutually exclusive, exhaustive clusters and requires the number of clusters in advance.Feature allocation can instead assign each data point any nonnegative number of features.Source: §1 · p. 1
  • DP-means removes the need to fix cluster cardinality, but its derivation depends on a Gibbs sampler and does not directly extend to feature learning.Source: §1 · p. 1
  • The paper derives the DP-means objective independently of inference algorithms by applying small-variance asymptotics directly to a Gaussian-mixture MAP problem expressed through the CRP EPPF.Source: §1 · p. 2
  • The framework extends beyond DP mixtures because Bayesian nonparametric models can yield new algorithms for K-means and related discrete optimization problems.Source: §1 · p. 2
  • For feature learning, the paper uses beta-process and Indian-buffet-process analogues to derive BP-means, which permits multiple features per data point, plus additional scalable algorithms.The framework represents the feature-learning MAP problem through an exchangeable feature probability function.Source: §1 · p. 2

2. MAP Asymptotics for Clustering

This section formulates clustering as a Bayesian MAP problem and shows that jointly shrinking variance and cluster-count hyperparameters yields a penalized K-means objective.

2. MAP Asymptotics for Clustering

  • The CRP supplies a prior over clusterings through sequential table assignments, whose resulting probability is represented by an exchangeable partition probability function.Source: §2 · p. 2
  • A clustering MAP estimate maximizes the posterior, equivalently minimizing the negative log joint likelihood over cluster assignments and means.Source: §2 · p. 2
  • As σ2 →0, the prior hyperparameter is scaled so the limiting objective avoids assigning every point to its own cluster.The scaling uses a constant λ2 > 0 and makes θ tend to zero with σ2.Source: §2 · p. 3
  • The Gaussian likelihood contributes squared-distance terms, while the CRP contributes a cluster-count penalty in the asymptotic negative log posterior.Source: §2 · p. 3
  • The resulting DP-means objective is the K-means distortion plus λ2 for each cluster after the first, with the offset reflecting that nonempty partitions require at least one cluster.Kulis & Jordan (2012) obtained a similar objective from a DP Gibbs sampler, whereas this derivation comes directly from MAP asymptotics.Source: §2 · p. 3

3. MAP Asymptotics for Feature Allocations

The paper extends small-variance MAP asymptotics from clustering to feature allocations, using the IBP and linear Gaussian model to derive BP-means. The resulting objective combines reconstruction error with penalties for nonempty features and supports a convergent optimization algorithm.

  • Feature allocations allow each data point to belong to multiple features, unlike clustering's single-assignment structure.The linear Gaussian model represents each observation's mean as the sum of its associated feature means.Source: §3 · pp. 3–4
  • The IBP supplies a prior over feature allocations with any finite, nonnegative number of features, while its EFPF expresses allocation probabilities exchangeably.Source: §3 · p. 3
  • Small-variance MAP asymptotics scale γ = exp(−λ2/(2σ2)) to prevent every observation from receiving its own feature.Source: §3 · p. 4
  • The BP-means objective is a feature-matrix reconstruction term plus a λ2 penalty for every nonempty feature, including the first.Unlike DP-means, feature allocations may contain zero features, so the first feature is also penalized.Source: §3 · p. 4
  • The BP-means algorithm alternates feature assignments with singleton-feature proposals and converges in finitely many iterations to a local minimum.The convergence guarantee does not imply convergence to the global optimum, and the feature landscape may have more complex local optima.Source: §3 · p. 4

4. Extensions

The framework extends to collapsed and bounded-cardinality objectives. Collapsing replaces learned means with empirical estimates, while parametric variants impose feature or cluster caps with activation penalties.

4.1. Collapsed objectives

  • Collapsed DP-means replaces cluster means with empirical cluster means and retains the original objective's form.Source: §4.1 · p. 5
  • The collapsed DP-means algorithm assigns points to existing clusters when squared distance is at most λ2, otherwise creating a new cluster, and converges finitely to a local minimum.Source: §4.1 · p. 5
  • The collapsed BP-means objective extends this construction to feature allocations, where each row may contain any finite number of active features.Its feature means are replaced by the empirical estimate (Z′Z)^−1Z.Source: §4.1 · p. 5

4.2. Parametric objectives

  • With a fixed maximum K, the parametric clustering objective caps clusters at K while penalizing each newly activated cluster up to that cap.Source: §4.2 · pp. 5–6
  • The parametric feature objective is analogous to K-means but applies to feature allocations with a cap of K possible features.Its K-features algorithm alternates binary feature assignments with updating A = (Z′Z)^−1Z′X, and assignment optimizations can be parallelized.Source: §4.2 · p. 6

5. Experiments

The experiments evaluate scalable feature-learning algorithms on tabletop and face images, comparing feature allocations with Gibbs sampling and conventional K-means. The results show substantial computational advantages and more interpretable, non-exclusive groupings, while also exposing evaluation and identifiability limitations.

5.1. Tabletop data

  • The new algorithms require substantially less computation than Gibbs sampling, with even 1000 BP-means restarts taking an order of magnitude less total time than one Gibbs run.Stepwise K-features is the fastest of the new algorithms, and the figure compares per-run time, total repeated-run time, and final feature counts.Source: §5.1 · p. 7, Figure 1 · p. 7
  • The tabletop experiment lacks a clear single accuracy criterion, and IBP feature counts below 7 were not obtained under the tested initializations and hyperpriors.The authors note that IBP is not designed to find a fixed feature count or roughly equal feature sizes as N varies.Source: §5.1 · pp. 7–8
  • Feature K-means finds one feature per tabletop object, whereas BP-means adds a superfluous feature combining the Klein bottle and $20 bill.The collapsed algorithm also finds an optimal feature encoding.Source: Figure 2 · p. 7, §5.1 · p. 8

5.2. Faces data

  • Repeated feature K-means on faces selects one generic base feature plus two features encoding hair, chin, skin, and other facial differences at λ2 = 5.All four possible combinations of the three features are represented among the example faces.Source: §5.2 · p. 8, Figure 3 · p. 8
  • For three groups, feature allocation and clustering produce different assignments: clustering emphasizes hair, while features separately encode hair and facial structure.The three-cluster counts are (154,151,95), while the three-feature combination counts are (139,106,80,75).Source: §5.2 · p. 8
  • With four groups, no sample face falls in cluster 4, while the feature allocation gives sparser and more interpretable groupings than clustering.The four-cluster counts are (121,150,74,55), and clustering divides shorter-haired pictures into three separate clusters.Source: §5.2 · pp. 8–9, Figure 3 · p. 8

6. Conclusions

The paper presents a general methodology for deriving hard-assignment objectives from Bayesian MAP problems and applies it to latent feature models. The resulting algorithms model latent structures beyond clustering, run faster than existing Bayesian nonparametric feature-allocation learners, and remain open to further optimization.

  • The methodology explicitly incorporates structural variables into Bayesian posteriors through combinatorial functions such as the EPPF and EFPF.It is applied to several generative models for unsupervised learning, especially latent feature models.Source: §6 · p. 9
  • The resulting algorithms represent latent structures beyond clustering while running faster than existing Bayesian nonparametric feature-allocation learners.Source: §6 · p. 9
  • Further improvements may come from adapting advances in K-means initialization and fast, distributed execution.The authors note that their current algorithmic optimizations, including K-means++-style initialization, do not exhaust these possibilities.Source: §6 · p. 9

A. DP-means objective derivation

The DP-means derivation starts from the Gaussian mixture model's joint distribution and applies a small-variance limit after reparameterizing the penalty. The remainder becomes asymptotically equivalent to the target expression as σ2 approaches zero.

B. BP-means objective derivation

The BP-means derivation applies the same small-variance-asymptotic recipe to a feature model with observed data, feature indicators, and feature means. The resulting expression combines reconstruction error, a feature-count penalty, and λ2.

C. Collapsed DP-means objective derivation

The collapsed DP-means derivation applies the standard small-variance recipe to a model with observed data and cluster indicators. Algebraic manipulation then rewrites its objective in a form more directly resembling the uncollapsed reconstruction objective.

C. Collapsed DP-means objective derivation

C.1. More interpretable objective

  • The collapsed objective is made more interpretable by algebraically rewriting its trace term.Source: §C.1 · p. 11
  • The rewritten form uses C := Z′Z and the projection matrix C′ := Z(Z′Z)−1Z′ to express cluster structure through cluster assignments and means.Source: §C.1 · p. 11

D. Collapsed BP-means objective derivation

The collapsed BP-means derivation applies a small-variance limit to obtain an objective for feature-based assignments, then generalizes it to multivariate Gaussian covariances. The generalized objective replaces Euclidean distances with Mahalanobis distances and penalizes covariance size.

D. Collapsed BP-means objective derivation

  • The collapsed BP-means derivation applies the limit σ2 →0 after setting γ := exp(−λ2/(2σ2)) to obtain the asymptotic objective.The derivation uses the vanishing behavior of exp(−λ2/(2σ2)) and σ2 log(σ2), with invertibility ensured by merging features with identical membership.Source: D. Collapsed BP-means objective… · pp. 11–12

E. General multivariate Gaussian likelihood

  • The generalized likelihood assumes xn ∼N(µk, σ2Σk), with positive definite Σk governed by an inverse Wishart prior and a fixed number of clusters.The analysis allows extension to varying cluster numbers through the preceding reasoning.Source: E. General multivariate Gaussian… · p. 12
  • The resulting optimization can use known Σk as inputs while optimizing cluster means and assignments.When covariances are not fixed, the optimization includes the covariance matrices as variables.Source: E. General multivariate Gaussian… · p. 12
  • The generalized objective replaces squared Euclidean distance with Mahalanobis distance and adds a λ2-weighted penalty on covariance-matrix size.The form is described as reminiscent of Sung & Poggio (1998).Source: E. General multivariate Gaussian… · p. 12

F. Proof of BP-means local convergence

The convergence proof shows that each iteration step does not increase the objective and that the update for A has a closed-form minimizer. Because only finitely many relevant feature allocations exist, the algorithm terminates after finitely many configurations.

F. Proof of BP-means local convergence

  • Each iteration’s first step does not increase the objective, while the second removes features with identical index collections.The proof retains one feature among duplicates before applying the parameter update.Source: F. Proof of BP-means local convergence · p. 13
  • When Z′Z is invertible, A = (Z′Z)−1Z′X minimizes the objective with respect to A.This follows by setting the gradient to zero after the feature-duplication cleanup.Source: F. Proof of BP-means local convergence · p. 13
  • The algorithm must finish in finitely many iterations because only finitely many relevant feature allocations can occur.Allocations with duplicate-index features or unnecessary features unique to one data point would increase the penalty and are excluded.Source: F. Proof of BP-means local convergence · p. 13
Loading 1212.2126v2…