Source-linked AI summary
Distance Dependent Chinese Restaurant Processes
David M. Blei, Peter I. Frazier
TL;DR
Traditional exchangeable clustering is inadequate for many temporal, spatial, and networked settings where dependencies depend on relationships among observations. The paper develops distance dependent CRPs with customer-assignment representations and Gibbs samplers, finding better fit for sequential data and a faster-mixing alternative formulation of the traditional CRP.
Problem
Traditional CRP mixtures cannot accommodate non-exchangeability, although many clustering applications involve temporal, spatial, or other relationships among observations.
Method
The paper develops distance dependent CRPs whose customer assignments depend on distances and derives Gibbs sampling methods based on customer-assignment representations.
Results
Distance dependent CRP mixtures provide a better fit than exchangeable CRP mixtures for the studied sequential data, while the alternative traditional-CRP formulation mixes faster.
Takeaways & Limitations
Distance dependent CRPs provide a flexible tool for non-exchangeable clustering across sequential and networked data settings.
Takeaways & Limitations
The network-data improvement may largely reflect avoidance of clustering abstracts from unconnected components, requiring further analysis beyond simpler network-aware clustering schemes.
Abstract
from arXiv · showhide
We develop the distance dependent Chinese restaurant process (CRP), a flexible class of distributions over partitions that allows for non-exchangeability. This class can be used to model many kinds of dependencies between data in infinite clustering models, including dependencies across time or space. We examine the properties of the distance dependent CRP, discuss its connections to Bayesian nonparametric mixture models, and derive a Gibbs sampler for both observed and mixture settings. We study its performance with three text corpora. We show that relaxing the assumption of exchangeability with distance dependent CRPs can provide a better fit to sequential data. We also show its alternative formulation of the traditional CRP leads to a faster-mixing Gibbs sampling algorithm than the one based on the original formulation.
1. Introduction
The paper develops a distance dependent Chinese restaurant process to model non-exchangeable clustering, motivated by temporal and spatial data that traditional CRP mixtures cannot accommodate. Its customer-assignment representation supports Gibbs sampling and connects the model to existing non-exchangeable partition distributions.
- Motivation: Traditional CRP mixtures assume exchangeability, but temporal and spatial data often require nearby observations to cluster together.The CRP’s exchangeability is also essential for its connection to Dirichlet process mixtures.
- Contribution: The distance dependent CRP makes customer seating assignments depend on distances based on time, space, or other characteristics.It can recover existing dependent distributions and can also be arranged to recover the traditional CRP.
- Inference: Representing partitions through customer-to-customer assignments yields table assignments and enables a straightforward Gibbs sampler for non-exchangeable and traditional CRP mixtures.The induced table assignment arises from connected customer assignments rather than direct table assignments.
- Related models: The distance dependent CRP overlaps with dependent Dirichlet process models only in the original DP or CRP, because the two classes differ in marginal invariance.Dependent DPs generally preserve marginal invariance, whereas distance dependent CRPs generally do not.
- Paper scope: The paper studies model properties, discrete and mixture settings, Gibbs sampling, relationships to dependent DPs, and empirical performance on three text corpora.The empirical study tests whether relaxing exchangeability improves sequential-data fit and whether the alternative CRP formulation mixes faster.
2. Distance dependent CRPs
The distance dependent CRP represents partitions through customer-to-customer assignments whose probabilities depend on distances and a decay function. This yields non-exchangeable clustering models, including sequential variants that favor nearby customers while recovering the traditional CRP in special cases.
- The CRP generates partitions by seating customers at tables, with existing-table probability proportional to table size and new-table probability proportional to α.
- The distance dependent CRP independently assigns each customer to another customer or itself, using f(d_ij) for links and α for self-links.The induced table assignment is obtained from customers reachable through assignment links.
- Customer assignments induce tables through reachability, including valid tables formed by cycles such as customer 1 linking to 2 and customer 2 linking to 1.
- The decay function controls how distance affects partitions; window, exponential, and logistic decays impose different distance sensitivities.The window decay limits links to distance a, while exponential decay decreases linking probability exponentially with distance.
- Distance dependent CRPs support time-, space-, or characteristic-based dependencies that the traditional CRP cannot accommodate.
- Sequential CRPs prohibit links to later customers, and their table assignments tend to group nearby customers more often than the traditional CRP.The traditional CRP is exchangeable, whereas sequential CRPs also include non-exchangeable distributions.
3. Posterior inference and prediction
Posterior inference is difficult because the distance dependent CRP places a prior over combinatorially many customer configurations. The paper uses Gibbs sampling that updates customer links through their induced partition changes and supports both fully observed and mixture settings, with prediction depending on the distance structure.
- Posterior inference is central for clustering analysis and prediction, but exact computation is intractable because the prior covers a combinatorial number of customer configurations.
- The Gibbs sampler defines its state with customer assignments c and repeatedly samples each latent link conditional on the other links and observations.The conditional combines the distance dependent CRP prior with the likelihood under the resulting partition.
- Removing a customer link can split a table when that link is the only connection, separating customers that point directly or indirectly to the removed customer.
- Resampling a customer link can join two tables, leave the partition unchanged, or do nothing when the new link is a self-link.
- The likelihood factors over tables, using representative observations and equality indicators for fully observed language models, or integrated component probabilities in mixture models.When the base measure and likelihood are conjugate, integrating out the mixture component yields a collapsed sampler; otherwise additional sampling is needed.
- For a future point under sequential distances, previously sampled customer assignments remain valid because assignments can only connect to the past.A new point inserted in the middle, or a point under nonsequential distances, changes the posterior and requires rerunning the Gibbs sampler.
4. Marginal invariance
Marginal invariance determines whether removing or leaving unobserved a customer changes the partition distribution. Distance dependent CRPs generally lack this property, unlike the traditional CRP, enabling dependence through intermediate points but complicating computation with missing observations.
- Marginal invariance means that removing a customer leaves the partition distribution over the remaining customers unchanged.
- The traditional CRP is marginally invariant, whereas distance dependent CRPs generally are not.The paper characterizes the traditional CRP as the only distance dependent CRP with this property, apart from constructions combining independent traditional CRPs.
- Random-measure models are marginally invariant and therefore induce partition distributions distinct from distance dependent CRPs, except at their intersection with the traditional CRP.
- Lack of marginal invariance allows an unobserved intermediate point, such as a common friend or city, to affect relationships between other points.
5. Empirical study
The distance dependent CRP improves text modeling for sequential and networked data while providing an alternative Gibbs sampler that mixes faster than the traditional sampler.
- Language modeling and mixture modeling: Across four text data sets, distance dependent CRPs provide better fits than traditional CRPs in fully observed and mixture-modeling settings.The study examines time-dependent and network-dependent data.
- Language modeling: Figure 4 shows that logistic decay consistently outperforms the traditional CRP, while exponential decay improves fit only at certain parameter settings.Bayes factors compare the distance dependent CRP with the traditional CRP.
- Mixture modeling: Held-out predictive likelihood favors the distance dependent CRP on NYT almost across all tested settings and on NIPS with logistic decay at 2 years.The best NYT setting uses a 14-day logistic-decay window.
- Modeling networked data: For CORA, a window decay of 1 restricts links to immediately connected documents, producing connected clusters and a log Bayes factor of 13,062.The graph is treated as undirected.
- Modeling networked data: The CORA analysis is a proof of concept, and its large improvement may partly reflect preventing clusters from spanning unconnected network components.The authors call for comparison with simpler network-aware clustering schemes.
- Comparison to the traditional Gibbs sampler: The customer-assignment sampler can change several customers’ cluster assignments through one assignment, enabling larger posterior moves than the traditional sampler.In comparisons on Science and New York Times documents, the traditional sampler more often stagnates at local optima, especially for Science.
6. Discussion
The distance dependent CRP broadens infinite clustering models to non-exchangeable settings and supplies a general-purpose Gibbs sampler. The authors identify further extensions to spatial, multilevel, and variational models.
- Discussion: The distance dependent CRP is a distribution over partitions with flexible, non-exchangeable seating assignments.Its customer-assignment representation is central to the model.
- Discussion: A general-purpose Gibbs sampler follows from the customer-assignment representation and supports sequential text mixture models.The sampler is presented as an inference tool for the developed model.
- Future directions: Future directions include spatial dependence, hierarchical models analogous to the hierarchical Dirichlet process, and variational inference.The variational method is suggested as a deterministic alternative to approximate inference.
Appendix A: A formal characterization of marginal invariance
The appendix characterizes when distance dependent CRPs are marginally invariant. For sequential distances, this occurs only for highly restricted decay functions; across general distances, only the identically zero decay function qualifies.
- Appendix A: A formal characterization of marginal invariance: Distance dependent CRPs are marginally invariant only for a small subset of their full class.This subset contains the traditional CRP and variants constructed from independent copies of it.
- A.1. Sequential Distances: The sequential distance dependent CRP with f(d) = a1[d ∈A] is equivalent to independent traditional CRPs with concentration parameter α/a.This equivalence also establishes marginal invariance for the construction.
- A.1. Sequential Distances: The sequential construction separates customers into groups based on distance and forbids clustering across groups.Within each group, clustering follows a traditional CRP with concentration parameter α/a.
- A.1. Sequential Distances: For sequential distances, the restricted decay-function family is also necessary: no other decay functions yield marginal invariance over all such distances.The proof first forces f(d) to equal either zero or f(0), then rules out positive finite-distance intervals.
- A.1. Sequential Distances: The sufficient-and-necessary characterization for sequential distances is summarized by Corollary 1.The allowed sets are A = ∅, {0}, or R, with a > 0.
- A.1. Sequential Distances: For sequential distances, decay functions of the form f(d) = a1[d ∈A] with A ∈{∅, {0}, R} are sufficient for marginal invariance.The resulting model partitions customers into groups and applies independent traditional CRPs within those groups.
- A.2. General Distances: For general distances, marginal invariance is even more restricted: f must be identically 0.Thus no nonzero decay function is marginally invariant over both sequential and non-sequential distances.
Appendix B: Gibbs sampling for the hyperparameters
The appendix extends Gibbs sampling to the concentration parameter and decay-function hyperparameters. It uses conditional independence to derive sampling targets, with exact finite-set evaluation for discrete priors and approximate Griddy-Gibbs sampling for continuous priors.
- Appendix B: Gibbs sampling for the hyperparameters: The concentration parameter α can receive a prior and be sampled within the Gibbs sampler.Given customer assignments c, α is conditionally independent of the observed data.
- Appendix B: Gibbs sampling for the hyperparameters: The assignment prior p(c | α) factorizes because customer assignments are independent under the generative process.The number of self-links K equals the number of tables for sequential distances but can differ from |z(c)| for non-sequential distances.
- Appendix B: Gibbs sampling for the hyperparameters: For the traditional CRP, the posterior expression for α reduces to the Antoniak form used for exact sampling with a gamma prior.This recovers the expression used by Escobar and West.
- Appendix B: Gibbs sampling for the hyperparameters: When α has a continuous prior, exact posterior sampling is generally difficult, so the appendix proposes Griddy-Gibbs approximation.The method evaluates the posterior on a finite grid and approximates its inverse CDF.
- Appendix B: Gibbs sampling for the hyperparameters: Decay-function hyperparameters can also be sampled because they are conditionally independent of the observed data given customer assignments and α.The sampler uses the corresponding conditional density, with priors that may or may not depend on α.
- Appendix B: Gibbs sampling for the hyperparameters: For window decay with sequential distances, the likelihood contribution simplifies according to the largest within-cluster distance threshold.The relevant product is 1 for a > max_i i − c_i and 0 otherwise.
- Appendix B: Gibbs sampling for the hyperparameters: Discrete hyperparameter priors can be handled by evaluating and normalizing the conditional density on their finite support.Continuous priors instead require approximate sampling, such as Griddy-Gibbs.