We provide a rigorous treatment of exchangeable feature allocations (in and ). In we define a notion of *exchangeable feature probability function* (EFPF) that is the analogue for feature allocations of the EPPF for clustering. We then proceed to define a *feature paintbox* in . Finally, in we discuss a class of models that we refer to as *feature frequency models* for which the construction of the feature paintbox is particularly straightforward, and we discuss the important role that feature frequency models play in the general theory of feature allocations.

The Venn diagram shown in is a useful guide for understanding our results, and the reader may wish to consult this diagram in working through the paper.

As shown in the diagram, random partitions (RPs) are a special case of random feature allocations (FAs), and previous work on random partitions can be placed within our framework. Thus, in the diagram, we have depicted the equivalence already noted of exchangeable RPs, RPs that possess an EPPF, and Kingman paintboxes. We also see that random feature allocations have a somewhat richer structure: the class of FAs with EFPFs is not the same as those having an underlying feature paintbox. But the class 