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.
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.
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