Abstract
Adaptive clustering of grouped data is traditionally performed using the Hierarchical Dirichlet Process Mixture Model (HDPMM). However, this approach is often limited by its rigidity in feature handling and poor computational scalability. We introduce the Versatile Hierarchical Dirichlet Process Mixture Model (vHDPMM), a framework that allows data points to possess both shared "global" features and group-specific "local" features. To enable large-scale application, we developed a parallel, distributed sampler that bypasses the computational bottlenecks of traditional methods—specifically the calculation of Stirling numbers—achieving orders-of-magnitude speedups on datasets containing millions of points.
Introduction
Clustering grouped data, such as pixels across multiple images or words within diverse document collections, requires models that can capture both universal patterns and group-specific nuances. The standard HDPMM fails in two critical areas. First, it is rigid, assuming all features of a data point are "global" and shared across all groups. In practice, many features are local (e.g., the spatial coordinates of an object in a specific photo) while others are global (e.g., the object's color). Second, it lacks scalability. Traditional inference relies on "Stirling numbers of the first kind" to estimate table counts in the Chinese Restaurant Franchise (CRF) metaphor. This calculation is a massive computational bottleneck that prevents HDPMM from scaling to high-resolution data.
The vHDPMM Framework
The proposed vHDPMM addresses these limitations by splitting each data point into a global component ($x$) and a local component ($y$). While global components are clustered across all groups, local components are clustered within their specific group but remain "tied" to a global cluster. This structure allows the model to distinguish between objects that share global characteristics but differ in local context.
To further enhance the model, we provide a theoretical framework to automatically determine which data dimensions are global and which are local by monitoring the marginal likelihood. If a local feature is incorrectly treated as global, the likelihood drops sharply, allowing for automated feature organization without manual engineering.
Scalable Inference via Parallel Sampling
The core technical innovation of this work is a parallel and distributed sampler that processes groups concurrently. Unlike serial samplers, our approach utilizes a "Direct Assignment" alternative that avoids the pre-computation of Stirling numbers. This is critical for scalability; handling groups of $10^6$ points would otherwise require terabytes of memory for Stirling number lookup tables.
Additionally, the sampler incorporates Split-Merge moves. By using auxiliary sub-clusters to propose the splitting or merging of existing clusters, the model can effectively escape local optima, a frequent challenge in Bayesian clustering tasks.
Experimental Evaluation
The model was evaluated across synthetic and real-world datasets, including Gaussian mixtures, high-resolution image cosegmentation (~1.6 million pixels per image), and biological classification data (Tetragonula bees).
Key Results
- Accuracy: On synthetic data, vHDPMM achieved significantly higher Normalized Mutual Information (NMI) scores (e.g., 0.862 vs 0.769 for global-only HDPMM) by leveraging local information to refine global clusters.
- Computational Speed: In a head-to-head comparison on a 4-group Gaussian task, our sampler completed inference in 18.6 seconds, whereas the standard CRF-based HDPMM sampler required 6,760 seconds—a speedup of over 360x.
- Scalability: The distributed implementation successfully processed 50 million 5D data points across four machines in approximately 31 minutes.
- Qualitative Performance: In image cosegmentation tasks, vHDPMM successfully isolated infrequent features, such as a small white diploma on a toy duck, which standard HDPMM models typically blurred into the background.
Discussion and Conclusion
By bypassing the "Stirling number bottleneck" and introducing a flexible local-global feature tie, vHDPMM makes HDP-style models viable for modern computer vision and big data tasks. While the automated feature detection is robust, future work will address the exhaustive search required for the initial global feature in extremely high-dimensional spaces. The implementation is publicly available, providing a scalable tool for complex hierarchical clustering.
Implementation: github.com/BGU-CS-VIL/VersatileHDPMixtureModels.jl
Summary updated