Combinatorial Clustering and the Beta Negative Binomial Process

We develop a Bayesian nonparametric approach to a general family of latent class problems in which individuals can belong simultaneously to multiple classes and where each class can be exhibited multiple times by an individual. We introduce a combinatorial stochastic process known as the negative binomial process ( ) as an infinite-dimensional prior appropriate for such problems. We show that the is conjugate to the beta process, and we characterize the posterior distribution under the beta-negative binomial process ( ) and hierarchical models based on the (the ). We study the asymptotic properties of the and develop a three-parameter extension of the that exhibits power-law behavior. We derive MCMC algorithms for posterior inference under the , and we present experiments using these algorithms in the domains of image segmentation, object recognition, and document analysis.