We present a compositional embedding framework that infers not just a singleclass per input image, but a set of classes, in the setting of one-shotlearning. Specifically, we propose and evaluate several novel models consistingof (1) an embedding function f trained jointly with a "composition" function gthat computes set union operations between the classes encoded in two embeddingvectors; and (2) embedding f trained jointly with a "query" function h thatcomputes whether the classes encoded in one embedding subsume the classesencoded in another embedding. In contrast to prior work, these models must bothperceive the classes associated with the input examples and encode therelationships between different class label sets, and they are trained usingonly weak one-shot supervision consisting of the label-set relationships amongtraining examples. Experiments on the OmniGlot, Open Images, and COCO datasetsshow that the proposed compositional embedding models outperform existingembedding methods. Our compositional embedding models have applications tomulti-label object recognition for both one-shot and supervised learning.