  The problem of inferring a clustering of a data set has been the subject of
much research in Bayesian analysis, and there currently exists a solid
mathematical foundation for Bayesian approaches to clustering. In particular,
the class of probability distributions over partitions of a data set has been
characterized in a number of ways, including via exchangeable partition
probability functions (EPPFs) and the Kingman paintbox. Here, we develop a
generalization of the clustering problem, called feature allocation, where we
allow each data point to belong to an arbitrary, non-negative integer number of
groups, now called features or topics. We define and study an "exchangeable
feature probability function" (EFPF)---analogous to the EPPF in the clustering
setting---for certain types of feature models. Moreover, we introduce a
"feature paintbox" characterization---analogous to the Kingman paintbox for
clustering---of the class of exchangeable feature models. We provide a further
characterization of the subclass of feature allocations that have EFPF
representations.
