Bayesian cluster analysis: Point estimation and credible balls

Sara Wade; Zoubin Ghahramani

Source-linked AI summary

Bayesian cluster analysis: Point estimation and credible balls

Sara Wade, Zoubin Ghahramani

arXiv:1505.03339v2May 13, 2015stat.ME

TL;DR

Bayesian nonparametric clustering provides a posterior over partitions, but its high-dimensional structure is difficult to summarize. This paper develops decision- and information-theoretic point estimates and credible balls; comparison with 95% credible balls finds that posterior similarity matrices under-represent uncertainty.

Problem
Bayesian nonparametric cluster posteriors are difficult to summarize because partition space is huge and posterior mass is spread across many partitions.
Method
The paper uses partition losses, especially variation of information and Binder’s loss, to develop point estimates and credible balls for clustering posteriors.
Results
Comparison with 95% credible balls finds that uncertainty is under-represented by the posterior similarity matrix.
Takeaways & Limitations
Credible balls provide a direct quantification of uncertainty around a clustering point estimate.
Takeaways & Limitations
Scaling to very large datasets remains an important concern for Bayesian nonparametric mixture models, and avoiding MCMC can sacrifice clustering uncertainty information.

Abstract

from arXiv · show

Clustering is widely studied in statistics and machine learning, with applications in a variety of fields. As opposed to classical algorithms which return a single clustering solution, Bayesian nonparametric models provide a posterior over the entire space of partitions, allowing one to assess statistical properties, such as uncertainty on the number of clusters. However, an important problem is how to summarize the posterior; the huge dimension of partition space and difficulties in visualizing it add to this problem. In a Bayesian analysis, the posterior of a real-valued parameter of interest is often summarized by reporting a point estimate such as the posterior mean along with 95% credible intervals to characterize uncertainty. In this paper, we extend these ideas to develop appropriate point estimates and credible sets to summarize the posterior of clustering structure based on decision and information theoretic techniques.

1 Introduction

Bayesian nonparametric clustering yields a posterior over partitions, but summarizing its diffuse, high-dimensional structure requires principled point estimates and uncertainty summaries. The paper develops decision- and information-theoretic tools for these purposes, including variation-of-information-based estimation and credible balls.

Motivation: Classical clustering algorithms explore restricted partition spaces or require the number of clusters in advance, limiting formal uncertainty assessment.Examples include agglomerative hierarchical clustering and k-means.
Bayesian nonparametric clustering: Bayesian nonparametric models induce random partitions whose posterior represents uncertainty in the clustering structure and avoids specifying a finite number of components.The number of clusters can grow unboundedly as more data are collected.
Motivation: The posterior is difficult to summarize because MCMC spreads mass across many similar partitions in a huge partition space, making enumeration infeasible.This motivates concise tools for communicating posterior structure.
Goals: The paper extends point-estimate and 95% credible-interval ideas to partitions by asking for an appropriate point estimate and a 95% credible region.These questions frame the paper’s summary-tool development.
Decision-theoretic summaries: Decision theory selects a clustering by minimizing posterior expected loss, while the paper compares Binder’s loss with variation of information as partition metrics.The 0-1 loss is inadequate because it treats all unequal partitions identically, regardless of their similarity.
Credible balls: The proposed credible balls quantify uncertainty around a point estimate, and comparison with 95% credible balls finds posterior similarity matrices under-represent uncertainty.The paper also proposes algorithms for locating optimal partitions and constructing credible balls.

2 Review

Bayesian nonparametric mixture models use random partitions to represent clustering uncertainty, but their posterior requires principled summaries. The review introduces decision-theoretic point estimation and motivates losses that respect partition similarity and labeling invariances.

2.1 Bayesian nonparametric clustering: Bayesian nonparametric mixture models use countably infinite components, allowing the data to determine a potentially unbounded number of clusters.These models induce latent partitions of observations according to shared mixture components.
2.1 Bayesian nonparametric clustering: The posterior of a partition is proportional to the partition prior times the data’s marginal likelihood, but either quantity may lack a closed form.MCMC methods are therefore typically used to obtain approximate posterior samples.
2.1 Bayesian nonparametric clustering: Because all posterior samples cannot be described feasibly, the review frames appropriate posterior summary tools as necessary.The partition space is extremely large even for small sample sizes.
2.2 Point estimation for clustering: Decision-theoretic point estimation chooses the partition minimizing posterior expected loss, averaging loss over possible true clusterings weighted by posterior probability.The estimate is determined after specifying a loss function over clusterings.
2.2 Point estimation for clustering: The 0-1 loss yields the posterior mode but ignores how similar two unequal partitions are, motivating more general losses.It penalizes a one-observation discrepancy the same as a discrepancy involving many observations.
2.2 Point estimation for clustering: Binder’s loss penalizes pairwise disagreement errors, including splitting observations that should share a cluster and grouping observations that should differ.Its formulation respects invariance to data-index and cluster-label permutations through intersection counts.

3 A comparison of the variation of information and Binder’s loss

The section compares variation of information (VI) with Binder’s loss as metrics and loss functions on the partition lattice, using stretched Hasse diagrams to examine their geometry and behavior. It argues that VI has more intuitive behavior in several comparisons, while both metrics share lattice-alignment properties.

Metric properties: Both VI and Binder’s loss are metrics on the space of partitions and are aligned with the lattice structure.Their distances add vertically along covered paths and horizontally through the meet of two partitions.
Metric properties: The stretched Hasse diagrams make distances between partitions directly readable from distances to the one-cluster partition and their meet.For both metrics, the distance between two partitions is the sum of their distances from the meet, after accounting for their distances from the one-cluster partition.
Nearest partitions and balls: The closest partitions under the metrics are obtained by merging singleton clusters, splitting a size-two cluster, or otherwise splitting the smallest available cluster.The smallest non-trivial credible neighborhood is shared, but differences appear for larger balls, where the authors judge the VI ball closer to intuition.
Local partition comparisons: For VI, the loss of merging two singleton clusters or splitting a size-two cluster is 2/N, whereas Binder’s loss gives 2/N^2; both vanish as N increases, faster for Binder’s loss.These local differences are used to compare the nearest partitions under the two metrics.
Metric behavior: Binder’s loss makes the one-cluster partition more separated from other partitions than VI does and produces counter-intuitive preferences between extreme partitions.For equal-sized two-cluster partitions, Binder’s loss can favor the all-singletons extreme over the one-cluster extreme, whereas VI behaves more sensibly for N > 4.

4 Point estimation via the variation of information

The paper proposes variation of information (VI) as a loss for Bayesian cluster point estimation and uses greedy search to find low posterior expected-loss partitions. The search can consider partitions not sampled by MCMC, often producing better estimates than sampled partitions.

Choice of loss: VI is proposed as a loss function because its partition neighborhoods better match intuition than those under Binder’s loss, whose asymmetries favor splitting over merging.Both losses align with the partition lattice and coincide in the smallest non-trivial ball.
Computation: O(N^2) is the computational complexity for evaluating a candidate partition when the posterior similarity matrix is pre-computed.Direct evaluation from MCMC output is O(MN^2), which can be demanding for many samples or candidate partitions.
Computation: The search space cannot include every partition because the partition space is too large, so the algorithm restricts exploration to a smaller set of candidates.The implementation includes search functions for minimizing posterior expected Binder’s loss and VI.
Greedy search: A greedy search algorithm locates the optimal partition c∗ by exploring nearby partitions in the Hasse diagram and moving toward lower posterior expected loss.It evaluates candidate covers and partitions covering the current partition, with neighborhood size controlled by l.
Empirical result: In almost all simulated and real examples, the estimated clustering was not an MCMC-sampled partition and had lower expected loss than any sampled partition.This is an advantage of searching beyond partitions visited in the chain.

5 Credible balls of partitions

The paper defines credible balls as the smallest neighborhoods around the VI-based point estimate containing at least 1−α posterior probability. Their vertical and horizontal bounds summarize the cluster-count and distance extremes represented within that uncertainty region.

Credible-ball definition: A credible ball at level 1−α is the smallest ball around c∗ whose posterior probability is at least 1−α.Its radius ϵ∗ is the smallest nonnegative distance achieving that probability.
Metric choice: Credible balls can be defined using any metric on partitions, including VI and Binder’s loss, and the resulting balls typically differ.They coincide when the smallest non-trivial ball under either metric already has posterior probability at least 1−α.
Computation: MCMC samples provide an estimate of ϵ∗ by measuring each sample’s distance from c∗ and finding the radius containing at least 1−α of the samples.This yields an estimated credible ball from posterior simulation output.
Bounds: Vertical upper and lower bounds identify the most distant credible-ball partitions with respectively the smallest and largest numbers of clusters.These bounds summarize cluster-count extremes within the credible ball.
Bounds: Horizontal bounds identify the credible-ball partitions most distant from c∗, while all bounds describe how different the partition may be with posterior probability 1−α.In practice, bounds use partitions with positive estimated posterior probability.
Interpretation: Posterior similarity-matrix heat maps do not precisely quantify uncertainty, whereas credible balls provide an explicit Bayesian confidence level.The paper reports that uncertainty was under-represented by the posterior similarity matrix in comparisons with 95% credible balls.

6 Examples

The examples compare Binder’s loss and variation of information (VI) for posterior-based clustering estimates and use 95% credible balls to quantify uncertainty. VI avoids Binder’s tendency to create small clusters for uncertain observations, while credible balls reveal substantial partition variability.

Simulated and real examples compare point estimates from VI and Binder’s loss and describe uncertainty using credible balls.
A Dirichlet process mixture model is fitted using a marginal Gibbs sampler with 10,000 post-burn-in iterations.The burn-in period is 1,000 iterations.
Binder’s loss creates additional small clusters for uncertain border observations, with the strongest effect when clusters overlap.The first cluster remains well separated and is identified by both estimates in the second example.
The VI estimate has the smallest distance from truth for both Binder’s loss and VI in both examples, while also misclassifying fewer observations.
As sample size increases, the Binder estimate reaches 41 clusters at N = 1600, whereas the VI estimate remains at four clusters and misclassifies fewer points.The difference in misclassified points grows with sample size.
Posterior similarity matrices can suggest too much certainty, whereas the 95% credible ball precisely quantifies uncertainty around the optimal partition.

7 Discusssion

The discussion presents posterior-based point estimates and 95% credible balls as tools for summarizing Bayesian clustering uncertainty. It contrasts VI with Binder’s loss and notes scalability and broader extensions as future concerns.

The paper proposes VI alongside Binder’s loss for point estimation and finds Binder’s asymmetric splitting behavior can overestimate the number of clusters.A greedy search algorithm explores partitions beyond those visited by MCMC.
The 95% credible ball supplements posterior similarity heat maps by providing a precise quantification of uncertainty around the point estimate.
The posterior summary tools are available through the mcclust.ext R package, which expands on mcclust.
Future work includes Bayesian feature allocation, posterior consistency for the VI-estimated number of clusters, and scalability for very large datasets.
An algorithm avoiding MCMC could improve scalability but would lose uncertainty information about the clustering structure.

Supplementary material for Bayesian cluster

The supplementary material section identifies the paper and its authors and records the paper’s arXiv version and date.

The paper is titled “Bayesian cluster analysis: Point estimation and credible balls.”
Sara Wade and Zoubin Ghahramani are listed as the authors.
The paper is identified as arXiv:1505.03339v2, dated 8 February 2019.

1 Review of Lattice Theory

The partition space is organized as a partially ordered set and, more specifically, as a lattice with meet and join operations. Its greatest and least elements represent one cluster and all singleton clusters, respectively.

Partitions are ordered by set containment, with each cluster in one partition contained in a cluster of the other.
The covering relation connects partitions with no intermediate partition and defines edges in the Hasse diagram.
The partition space forms a lattice because every pair of partitions has a greatest lower bound and least upper bound.
The meet and join operators are defined as the greatest lower bound and least upper bound, respectively.
The greatest lattice element places every observation in one cluster, while the least places every observation in its own cluster.

2 Examples of Balls of Partitions

The examples illustrate credible balls around a partition under VI and Binder’s loss, with partitions ordered by increasing metric distance and different balls emerging across metrics.

VI and Binder’s balls center on c = ({1, 2}, {3, 4}) and color partitions by increasing distance from c.The figures use the same center and rainbow ordering to visualize nested balls.
The smallest non-trivial ball contains the red clusterings, while the next smallest adds the orange clusterings.This nesting description applies to both illustrated metrics.
The figures use credible-ball size to represent increasing uncertainty around the selected partition.Larger balls include progressively more distant partitions.
The smallest non-trivial balls coincide for VI and Binder’s loss, but the next smallest balls differ.The VI ball includes orange clusterings 0 and 1, whereas the Binder’s ball includes orange clustering 0 only.

3 Properties and Proofs

The section establishes structural properties of VI and Binder’s loss on partition space and characterizes the partitions nearest to any partition under both metrics.

VI and Binder’s loss are metrics on the space of partitions, supporting distance-based comparisons and credible balls.The metric framework includes non-negativity and the triangle inequality.
For both metrics, nearest partitions are obtained by merging small clusters or splitting the smallest non-singleton cluster, depending on the partition’s singleton structure.The cases distinguish partitions with at least two singletons, with at most one singleton, and with clusters of size two.
When a partition has at least two singletons, merging any two singletons is closest if the smallest non-singleton cluster exceeds size two; size two creates a tie with splitting it.This comparison is stated for the distance analysis and applies to both metrics through the surrounding property.
With at most one singleton, splitting the smallest cluster into a singleton and a remainder gives the closest partitions.The proof states that this result also holds for Binder’s loss.
The section also records special distance results for equal-size partitions and for two-cluster partitions under Binder’s loss.These are presented as Properties 3.6 and 3.7, with the latter assuming N is even and square.

Appendix III: Examples

The appendix presents simulated and galaxy examples using cross-tabulations of estimated or credible-bound cluster labels under Binder’s loss and VI.

Examples: Example 1 compares true cluster labels with estimated labels and with credible-bound labels obtained using Binder’s loss and VI.The comparisons are reported in Tables 1, 3, and 4.
Examples: Example 2 compares true cluster labels with estimated labels and with credible-bound labels under Binder’s loss and VI.The corresponding cross-tabulations appear in Tables 2, 5, and 6.
Example 2: In Example 2, the first cluster with decreased variance is well identified in both estimates.The table description points to the first row and column as evidence.
Credible bounds: The appendix lists cluster counts for upper vertical, lower vertical, and horizontal credible bounds in the examples.Reported counts include 3, 16, and 6 clusters for one set of bounds, and 4, 18, and 11 for another.
Galaxy example: The galaxy example uses a cross-tabulation of estimated cluster labels and VI credible-bound cluster labels.This comparison is identified as Table 7.