An Alternative Prior Process for Nonparametric Bayesian Clustering

Hanna M. Wallach, Shane T. Jensen, Lee H. Dicker, Katherine A. HellerAISTATS 2010

Abstract

Standard Bayesian clustering models like the Dirichlet Process (DP) often suffer from a "rich-get-richer" bias, leading to a few massive clusters and many small ones. This paper introduces the Uniform Process (UP) as an alternative prior that promotes balanced cluster sizes. We demonstrate that the UP's number of clusters grows at a rate of $O(\sqrt{N})$, and despite its non-exchangeable nature, it offers superior performance and finer granularity in real-world document clustering tasks.

Introduction

In nonparametric Bayesian modeling, the Dirichlet Process (DP) and Pitman-Yor Process (PYP) are standard choices because they allow the number of clusters to grow automatically with the data. However, these models possess a "rich-get-richer" property: the probability of a new data point joining a cluster is proportional to that cluster's current size. While suitable for power-law phenomena like word frequencies, this bias is often undesirable for clustering tasks where more uniform group sizes are expected, such as DNA motif grouping or technical document categorization. In such cases, a DP often produces a single "giant" cluster that obscures the underlying structure. This paper investigates the Uniform Process (UP) as a mathematically grounded alternative to avoid this bias.

The Uniform Process

The defining characteristic of the Uniform Process (UP) lies in its predictive probability. Unlike the DP or PYP, where the probability of joining a cluster $k$ is proportional to its size, the UP assigns a constant probability: $P(\text{join cluster } k) \propto 1$.

Technical Considerations

  1. Asymptotic Growth: The authors prove that under the UP, the expected number of clusters $K_N$ grows at $O(\sqrt{N})$, significantly faster than the $O(\log N)$ growth of the DP.
  2. Exchangeability: A significant challenge for the UP is its lack of exchangeability; the order of observations affects the joint probability of the partition. To address this, the authors developed a Gibbs sampling algorithm valid for fixed orderings and demonstrated the model's robustness to data permutations.
  3. Predictive Formulation: The conditional prior for cluster assignment is defined by propagating values through the entire sequence, ensuring the Gibbs sampler accounts for the non-exchangeable nature of the process.

Experimental Results

Cluster Growth and Distribution

Simulations verify the theoretical growth rates. As shown in the following figure, the number of clusters in the UP grows at a rate comparable to a Pitman-Yor process with $\alpha = 0.5$, but with a distinct internal distribution.

Expected number of clusters vs. number of observations for different concentration parameters $\theta$.

While the DP produces a small number of very large clusters, the UP results in a much larger number of clusters with a nearly uniform size distribution. This "anti-power law" property is visualized in the cluster size distribution plot, where the mean number of clusters remains relatively constant across different cluster sizes until the boundary effects of the finite sample size $N$ take over.

Mean number of clusters vs. cluster size for the Uniform Process, showing a balanced distribution.

Document Clustering Performance

The model was evaluated on a dataset of 1,200 carbon nanotechnology patent abstracts. On a held-out set of 200 abstracts, the Uniform Process consistently achieved higher log-probabilities than the Dirichlet Process across various concentration parameters. Furthermore, the UP discovered more clusters, providing a finer-grained thematic partitioning that is often more useful for technical data analysis.

Discussion and Conclusion

The Uniform Process offers a compelling alternative for clustering tasks where the "rich-get-richer" assumption fails. Although it sacrifices exchangeability—a property often assumed for mathematical convenience rather than physical reality—the authors show that the resulting model is robust to data ordering.

Future work may explore optimizing data ordering when no natural sequence (like chronology) exists and extending the UP to other domains like image segmentation. The Uniform Process demonstrates that moving beyond standard exchangeable priors can yield more realistic and performant Bayesian models for complex data.

Summary updated

BibTeX
@article{wallach2010alternative,
  author = {Hanna M. Wallach and Shane T. Jensen and Lee H. Dicker and Katherine A. Heller},
  title = {{An Alternative Prior Process for Nonparametric Bayesian Clustering}},
  journal = {AISTATS},
  year = {2010},
}
Figure