Bayesian Hierarchical Clustering with Exponential Family: Small-Variance Asymptotics and Reducibility

Juho Lee, Seungjin Choi

Abstract

Bayesian hierarchical clustering (BHC) is an agglomerative clustering method where a probabilistic model is defined and its marginal likelihoods are evaluated to decide which clusters to merge. While elegant, BHC is computationally expensive and sensitive to hyperparameter tuning. This paper introduces Relaxed Bayesian Hierarchical Clustering (RBHC), a non-probabilistic version of BHC derived through small-variance asymptotics (SVA). By simplifying BHC's complex marginal likelihoods into a distance-based dissimilarity measure, the authors achieve significant speedups and eliminate tedious tuning while retaining the ability to automatically infer the number of clusters.

Introduction

Hierarchical clustering typically falls into two categories: fast, intuitive distance-based methods (like Ward’s method) that require manual tree cutting, and probabilistic Bayesian methods (BHC) that naturally determine cluster counts but scale poorly ($O(n^2 \log n)$). This research bridges the gap by applying Small-Variance Asymptotics to BHC, resulting in a scalable algorithm that maintains statistical rigor without the computational overhead.

Methodology: The SVA Bridge

The core innovation lies in taking a conjugate-exponential family model and letting the variance approach zero. This process transforms complex Bayesian marginal likelihood integrals into a non-probabilistic optimization problem. The resulting Relaxed BHC (RBHC) uses a dissimilarity measure equivalent to the change in "Bregman information" upon merging clusters. This connects Bayesian nonparametrics directly to classical geometry-based clustering.

A critical finding is that this new measure is "reducible" (or nearly so in practice). Reducibility ensures that merging two clusters does not make a third, distant cluster suddenly appear "closer" than the original pair. This property allows the use of the Nearest Neighbor Chain Algorithm (NNCA), which optimizes the time complexity to $O(n^2)$ and space complexity to $O(n)$, making it viable for large-scale applications.

Experimental Setup

The authors evaluated RBHC against standard BHC and traditional linkages using both synthetic and real-world datasets:

  • Synthetic Data: Generated from Poisson, Multinomial, and Gaussian distributions to test handling of different data types.
  • MNIST: A subset of 3,000 handwritten digits (0, 3, 7, and 9), downsampled to $7 \times 7$ vectors.
  • Caltech101: A dataset of 2,033 images across three categories, represented as 1,000-dimensional visual words.

Key Results

Performance was measured using the Adjusted Rand Index (ARI), where 1.0 indicates a perfect match to ground truth.

Clustering performance (ARI) on synthetic datasets across different distributions.

As shown in the synthetic results, RBHC (both greedy and NNCA versions) consistently outperforms standard BHC. On Poisson data, RBHC achieved an ARI of 0.469 compared to BHC's 0.265, highlighting BHC's struggle with hyperparameter sensitivity in certain distributions.

Clustering performance (ARI) on real-world datasets MNIST and Caltech101.

On real-world data, the advantage remains clear. For MNIST, RBHC reached an ARI of 0.637, while BHC trailed at 0.253. The RBHC-nnca variant produced results identical to the greedy version but with significantly better computational scaling, proving that the "almost-reducible" nature of the measure does not compromise accuracy in practice.

Conclusion

RBHC successfully combines the strengths of Bayesian nonparametrics with the efficiency of distance-based clustering. By leveraging small-variance asymptotics and reducibility, the authors provide a robust framework that scales to large datasets and simplifies the clustering pipeline. While the current threshold heuristic for determining the number of clusters works well, future work may explore more automated, dynamic ways to determine this stopping distance.

Summary updated

Abstract

Bayesian hierarchical clustering (BHC) is an agglomerative clustering method, where a probabilistic model is defined and its marginal likelihoods are evaluated to decide which clusters to merge. Wh...
BibTeX
@inproceedings{lee2015bayesian,
  author = {Juho Lee and Seungjin Choi},
  title = {{Bayesian Hierarchical Clustering with Exponential Family: Small-Variance Asymptotics and Reducibility}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=shK2SYUgCRQ},
}
Figure