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 <italic>negative binomial process</italic> (<inline-formula> <tex-math>${\rm NBP}$</tex-math><alternatives><graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq1-2318721.gif"/></alternatives> </inline-formula>) as an infinite-dimensional prior appropriate for such problems. We show that the <inline-formula> <tex-math>${\rm NBP}$</tex-math><alternatives><graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq2-2318721.gif"/></alternatives> </inline-formula> is conjugate to the beta process, and we characterize the posterior distribution under the beta-negative binomial process (<inline-formula><tex-math>${\rm BNBP}$</tex-math><alternatives> <graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq3-2318721.gif"/></alternatives></inline-formula>) and hierarchical models based on the <inline-formula><tex-math>${\rm BNBP}$</tex-math><alternatives><graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq4-2318721.gif"/> </alternatives></inline-formula> (the <inline-formula><tex-math>${\rm HBNBP}$</tex-math><alternatives> <graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq5-2318721.gif"/></alternatives></inline-formula>). We study the asymptotic properties of the <inline-formula><tex-math>${\rm BNBP}$</tex-math><alternatives> <graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq6-2318721.gif"/></alternatives></inline-formula> and develop a three-parameter extension of the <inline-formula><tex-math>${\rm BNBP}$</tex-math><alternatives> <graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq7-2318721.gif"/></alternatives></inline-formula> that exhibits power-law behavior. We derive MCMC algorithms for posterior inference under the <inline-formula><tex-math>${\rm HBNBP}$</tex-math> <alternatives><graphic position="float" orientation="portrait" xlink:type="simple" xlink:href="broderick-ieq8-2318721.gif"/></alternatives></inline-formula>, and we present experiments using these algorithms in the domains of image segmentation, object recognition, and document analysis.