  We consider a novel clustering task in which clusters can have compositional
relationships, e.g., one cluster contains images of rectangles, one contains
images of circles, and a third (compositional) cluster contains images with
both objects. In contrast to hierarchical clustering in which a parent cluster
represents the intersection of properties of the child clusters, our problem is
about finding compositional clusters that represent the union of the properties
of the constituent clusters. This task is motivated by recently developed
few-shot learning and embedding models can distinguish the label sets, not just
the individual labels, assigned to the examples. We propose three new
algorithms -- Compositional Affinity Propagation (CAP), Compositional k-means
(CKM), and Greedy Compositional Reassignment (GCR) -- that can partition
examples into coherent groups and infer the compositional structure among them.
We show promising results, compared to popular algorithms such as Gaussian
mixtures, Fuzzy c-means, and Agglomerative Clustering, on the OmniGlot and
LibriSpeech datasets. Our work has applications to open-world multi-label
object recognition and speaker identification & diarization with simultaneous
speech from multiple speakers.
