Source-linked AI summary
Bayesian Agglomerative Clustering with Coalescents
Yee Whye Teh, Hal Daumé III, Daniel Roy
TL;DR
Traditional agglomerative clustering lacks predictive semantics and a coherent way to handle missing data. This paper uses a Kingman’s coalescent prior with bottom-up greedy and sequential Monte Carlo inference. The authors report better performance than other agglomerative algorithms and good results in document modeling and phylolinguistics.
Problem
Traditional agglomerative clustering lacks predictive semantics and a coherent mechanism for handling missing data.
Source: §1 · p. 1Method
Results
The model performs better than other agglomerative clustering algorithms and gives good results in document modeling and phylolinguistics.
Source: §6 · p. 7Takeaways & Limitations
Greedy inference can suit applications where a single good tree suffices, while SMC provides an arbitrarily accurate approximation to the full posterior.
Source: §4.2 · p. 4The algorithms take O(n^3) time, except Greedy-Rate1, which takes O(n^2); the authors recommend Greedy-Rate1 among the greedy methods.
Source: §6 · p. 8
Abstract
from arXiv · showhide
We introduce a new Bayesian model for hierarchical clustering based on a prior over trees called Kingman's coalescent. We develop novel greedy and sequential Monte Carlo inferences which operate in a bottom-up agglomerative fashion. We show experimentally the superiority of our algorithms over others, and demonstrate our approach in document clustering and phylolinguistics.
1 Introduction
The introduction motivates probabilistic models as a way to address limitations of traditional agglomerative clustering. It proposes a Bayesian model that combines a tree prior, hierarchical data structure, and efficient agglomerative inference.
1 Introduction
- Traditional agglomerative clustering is efficient and easy to implement, but lacks predictive semantics and a coherent mechanism for missing data.Probabilistic models can address these limitations, quantify goodness of fit, predict on new data, and integrate within more complex models.Source: §1 · p. 1
- Existing Bayesian tree models use MCMC to sample posterior trees, while flat-mixture approaches efficiently find a tree but do not share information across it.The introduction frames the proposed approach as combining advantages of both probabilistic approaches.Source: §1 · p. 1
- The proposed model places a prior over trees, computes their posterior, shares statistical strength through a hierarchical data distribution, and induces an exchangeable distribution over data points.Its inference algorithms construct trees agglomeratively.Source: §1 · p. 1
2 Kingman’s coalescent
Kingman’s coalescent describes genealogies as a continuous-time process of partitions that merges lineages backwards from the present. Its finite n-coalescents have uniform tree-topology marginals and are infinitely exchangeable.
2 Kingman’s coalescent
- A genealogy is represented by a time-indexed partition of the individuals, with each block identifying an ancestor’s descendants.The partition-valued function is piecewise constant and fully characterizes the genealogy.Source: §2 · p. 2
- Kingman’s n-coalescent is a continuous-time, partition-valued Markov process that starts with singleton lineages and merges them backwards until one remains.Each pair of lineages merges independently at rate 1; a draw is a binary tree with a single root and the n individuals as leaves.Source: §2 · p. 2
- The marginal distribution over tree topologies is uniform and independent of coalescent times, and the coalescent is infinitely exchangeable.The genealogy of any m contemporary individuals embedded in an n-coalescent is a draw from the m-coalescent.Source: §2 · p. 2
3 Hierarchical clustering with coalescents
The model places a coalescent prior on a latent tree and generates observations through a Markov process evolving forward along that tree. Shared paths induce dependence between observations, with its strength determined by when they coalesce.
3 Hierarchical clustering with coalescents
- The model places a coalescent prior on a latent tree whose leaves correspond to observed data points.The tree has n−1 coalescent points, each joining two subtrees at a time in the past.Source: §3 · p. 3
- A continuous-time Markov process evolves forward along the tree, branching independently at each coalescent point to generate a distribution over the observations.Latent variables represent the process state just before branching, and each leaf variable is its observed data point.Source: §3 · p. 3
- Observations share the Markov-process path until they split, so more recent coalescence implies greater dependence between them.The induced distribution over observations inherits the n-coalescent’s infinite exchangeability.Source: §3 · p. 3
4 Agglomerative sequential Monte Carlo and greedy inference
The section develops bottom-up inference for coalescent trees using sequential Monte Carlo and greedy algorithms. It also gives model-specific likelihood calculations, hyperparameter updates, and predictive-density procedures.
4 Agglomerative sequential Monte Carlo and greedy inference
- Inference integrates out latent variables and builds the tree from coalescent events, choosing each duration and subtree pair using a local prior and likelihood.The full tree is represented as n −1 coalescent events, and each local likelihood term corresponds to a candidate pair's coalescence.Source: §4 · pp. 3–4
4.1 Sequential Monte Carlo algorithms
- SMC incrementally approximates the tree posterior with weighted particles, resampling when the estimated effective-sample-size ratio falls below one half.Each particle represents an initial sequence of coalescent events; resampling reallocates particles toward high-probability regions and prunes low-probability ones.Source: §4.1 · p. 4
- PriorPost evaluates every pair and significantly outperforms PriorPrior, but works reasonably on small data sets and fails on larger ones with highly peaked duration posteriors.PriorPrior is computationally efficient but performs badly with many objects because it draws pairs uniformly.Source: §4.1 · p. 4
4.2 Greedy algorithms
- Greedy-MaxProb and Greedy-MinDuration have O(n^3) cost, while Greedy-Rate1 reduces this to O(n^2); all three perform about equally well.Greedy-Rate1 replaces the prior rate with 1 and coalesces the pair with the most recent optimal time.Source: §4.2 · p. 4
4.3 Examples
- For Brownian diffusion, Gaussian messages support local-likelihood calculations; the multinomial example models independent entries with Markov transitions and uses Newton steps for the optimal duration.The multinomial optimal duration cannot be solved analytically.Source: §4.3 · p. 5
4.4 Hyperparameter estimation and predictive density
- Hyperparameters are estimated by alternating between genealogy estimation and conditional re-estimation; Brownian Λ has a closed-form MAP update, unlike the iterative multinomial update.For Brownian motion, a new individual's merge-time probability with a given sibling is available in closed form; density estimation sums over siblings and integrates time using equally spaced samples.Source: §4.4 · p. 5
5 Experiments
Experiments compare the proposed algorithms on synthetic data and apply Greedy-Rate1 to document clustering and phylolinguistics. Greedy-Rate1 generally performs well against other hierarchical clustering methods, with specific exceptions and scope qualifications across tasks.
Synthetic Data Sets
- SMC-PostPost performs best on the synthetic data, followed by SMC-PriorPost, SMC-PriorPrior, and Greedy-Rate1.All algorithms improve with increasing D and n; SMC methods improve as sample count S increases, and performance is robust to mutation-rate mismatch, possibly because of the experimental setup.Source: §5 · p. 5, Figure 2 · p. 6
MNIST and SPAMBASE
- Greedy-Rate1 gives the best reported performance on MNIST and SPAMBASE scores except for SPAMBASE purity.The comparison reports purity, subtree scores, and leave-one-out accuracy.Source: Table 1 · p. 6, §5 · p. 6
Phylolinguistics
- Across WALS subsets, Greedy-Rate1 performs at least as well as the other techniques except at the two sparsity extremes.PPCA performance stays around 76%, while the other algorithms degrade as sparsity increases.Source: §5 · p. 6, Figure 3 · p. 7
- The recovered Indo-European tree separates Germanic from Romance languages but makes some errors for Iranian and Greek languages.It is based on 48 languages with at most 30 unknown features each, selected from a sparse WALS database.Source: §5 · p. 6, Figure 3 · p. 7
NIPS
- Cutting the NIPS coalescent tree at branches with log likelihood ratio greater than zero produces nine clusters, separating Bayesian from non-Bayesian learning.Clusters two and three would merge under a slightly higher threshold; cluster 2 has an LLR of 0.105.Source: Table 2 · p. 7, §5 · p. 7
6 Discussion
The paper concludes that its coalescent-based Bayesian agglomerative model has efficient greedy and SMC inference and performs well in clustering applications. It contrasts the coalescent prior with related tree models and identifies computational and statistical questions that remain open.
Discussion
- The model uses Kingman’s coalescent as its tree prior and provides greedy and SMC inference, with empirical performance better than other agglomerative algorithms and good results in document modeling and phylolinguistics.Greedy-Rate1 takes O(n^2) time, while the other algorithms take O(n^3).Source: §6 · pp. 7–8
- Unlike the Dirichlet diffusion tree’s fragmentation process, this model uses a coalescent process, which allows simpler inference algorithms.Bayesian hierarchical clustering instead uses a flat mixture model and does not represent distributions over trees.Source: §6 · pp. 7–8
- Open questions include the induced random distribution and posterior consistency, as well as generalizations to varying mutation rates and non-binary trees.The authors also identify developing O(n^2) SMC algorithms as future work.Source: §6 · p. 8