Compositional Embeddings: Joint Perception and Comparison of Class Label Sets
Authors: Zeqian Li
Jacob Whitehill
Venue:  (2020)
Keywords: Embedding
One-shot Learning
Compositional Representation

Abstract: We explore the idea of compositional set embeddings that can be used to infer not
just a single class, but the set of classes associated with the input data (e.g., image,
video, audio signal). This can be useful, for example, in multi-object detection in
images, or multi-speaker diarization (one-shot learning) in audio. In particular, we
devise and implement two novel models consisting of (1) an embedding function
f trained jointly with a “composite” function g that computes set union opera-
tions between the classes encoded in two embedding vectors; and (2) embedding
f trained jointly with a “query” function h that computes whether the classes en-
coded in one embedding subsume the classes encoded in another embedding. In
contrast to prior work, these models must both perceive the classes associated
with the input examples, and also encode the relationships between different class
label sets. In experiments conducted on simulated data, OmniGlot, and COCO
datasets, the proposed composite embedding models outperform baselines based
on traditional embedding approaches.

Published as a conference paper at ICLR 2020
COMPOSITIONAL EMBEDDINGS: JOINT PERCEPTION AND COMPARISON OF CLASS LABEL SETS
Zeqian Li and Jacob Whitehill
Department of Computer Science
Worcester Polytechnic Institute Worcester, MA 01609, USA
{zli14, wwwhitehiiiiiiie @wppi edu
ABSTRACT
We explore the idea of compositional set embeddings that can used to infer not just single class, but the set of classes associated with the imput data (c.g., image, video, audio signal). This can be useful, for example, in multi-object detection images, or multi-speaker diarization (one-shot learning) in audio. In particular, we devise and implement two novel models consisting of (1) an embedding function f trained jointly with "composite" function g that computes set union opera- tions between the classes encoded in two embedding vectors; and (2) embedding f trained jointly with a "query" function h that computes whether the classes en- coded in one embedding subsume the classes encoded in another embedding. In contrast prior work, these models must both perceive the classes associated with the input examples, and also encode the relationships between different class label sets. In experiments conducted on simulated data, OmniGlot, and COCO datasets, the proposed composite embedding models outperform baselines based on traditional embedding approaches.
INTRODUCTION
Embeddings, especially as enabled by advances in deep learning, have found widespread use in nat- ural language processing, object recognition, face identification and verification, speaker verification and diarization (i.e., who speaking when (Sell et al. 2018) ), and other areas. What embedding functions have in common is that they map their input into fixed-length distributed representation (i.e., continuous space) that facilitates more efficient and accurate (Scott et al. 2018 downstream analysis than simplistic representations such as one-of-k: Moreover, they are amenable to one-shot and few-shot learning since the set of classes that can be represented does not depend directly on the dimensionality of the embedding space.
Previous research on embeddings has focused on cases where each example is associated with just class (e.g., the image contains only one person's 's face). In contrast, investigate the case where each example is associated with not just one, but an entire subser of classes from a universe S. The goal is to embed each example so that questions of two types can be answered (see Figure [a)): (1) Is the set of classes in example v, equal to the union of the classes in examples æ,, and x.? (2) Does the set of classes in example Va subsume the set of classes in example x?? Importantly, we focus on settings in which the classes present in the example must be perceived automatically.
We approach this problem using compositional set embeddings. Like traditional embeddings, we train a function f that maps each example x E R" into an embedding space 1. so that examples with the same classes are mapped close together and examples with different classes are mapped far apart. Unlike traditional embeddings, our function is trained to represent the set of classes that is associated with each example, so that questions about set union and subsumption can be answered by comparing vectors in the embedding space. We do not assume that the mechanism by which examples (e.g., images, audio signals) are rendered from multiple classes is known. Rather, the rendering process must be learned from training data. We propose two models, whereby f is trained jointly with either a "composition" function g (Model I) that answers questions about set union, or "query" function la (Model II) that answers question about subsumption (see Figure aa)).

---

Published as a conference paper at ICLR 2020
Frowding
Cusry
(2)
(2.3)
(3)
(12.3)
11.21
(1.2)
0.4
12)
11. 33
(3)
0.0
(1)
3)
(2)
(1.2.3)
Embedding Space
True [1.20)))))
(1.
2)
-0.75 -0.50
-0.25
0.00
0.25
0.50
0.75
1.00
(b)
Figure 1: (a): Overview of the paper: embedding function i' trained jointly with either the compo- sition function or the query function In particular, the goal is for to "compose" the embeddings of examples, containing classes T and UI respectively, to approximate the embedding of an ex- ample containing classes T U.u. (b): 2-D projection of the embedding space from Experiment on test classes and examples not seen during training (one-shot learning). Function composes two embeddings (two arrow tails) and maps the result back into the embedding space (arrow head). To substantial if imperfect degree, the embedding space is compositional as described (a).
To our knowledge, this computational problem is novel. We see at least two use-cases: (1) Speaker recognition and diarization (i.e., infer who is talking within audio signal) with multiple simulta- neous speakers: Given an audio signal containing speakers who were not part of the training set and who may be speaking simultaneously. and given one example of each person speaking in isolation (one-shot learning), infer which set of speakers is talking.
(2) Multi-object recognition in images: Given just the embedding of image Ta answer whether va contains the object(s) in another image Storing just the embeddings but not the pixels could potentially be more space-efficient. Be- cause of the novelty of the problem, it was not obvious what baselines we should compare. When evaluating models, sought assess the unique contribution of the compositional embedding above and beyond what a "traditional" embedding could achieve. Hence, we created baselines by endowing traditional embedding with some extra functionality to enable it to infer label sets.
Modeling assumptions and notation: For generality, we refer to the data to be embedded (images, videos, audio signals, etc.) simply "examples" Let the universe of classes be S. From any subset T T S, a ground-truth rendering function r 2 - Rn "renders" an example, i.e., r(T) = x. Inversely, there is also ground-truth classification function R 2 that identifies the label set from the rendered example, i.e., c(x) = T. Neither nor e is observed. We let eT represent the embedding (i.e., output of f) associated with some example containing classes T.
Contribution: To our knowledge, this is the first paper to explore how embedding functions can be trained both to perceive multiple objects the example and to represent the so that set operations can be conducted among embedded vectors. We instantiate this idea in two ways: Model for set union (f g) and Model for set containment (f & h). By evaluating on synthetic data, OmniGlot handwritten image data (Lake et al., 2015), well the COCO dataset (Lin et al. 2014). we provide proof-of-concep that "compositional set embeddings" can work.
detected objects
RELATED WORK
Embeddings: We distinguish between two types of embeddings: (1) "Perceptual" embeddings such as for vision (Facenet (Schroff' et al.) 2015)) and speech (x-vector (nnyder et al.] 2018)) where each class (c.g., person whose voice recorded or face photographed) may contain widely varying examples across speech content, facial expression, lighting. background noise, etc. (2) Word embeddings (word2vee (Mikolov et al. 2013), GloVe (Pennington al. 2014)) where each class
2

---

Published as a conference paper at ICLR 2020
contains only one exemplar by definition. Within the former, the task of the embedding function is to map examples from the same class close together and examples from other classes far apart. This often requires deep, non-linear transformations to be successful. With word embeddings, the class of each example is already clear and does not need to he inferred; instead, the goal is to give the embedded vectors geometric structure reflect co-occurrence, similarity in meaning, etc.
Compositional embeddings: Since at least 30 years, Al researchers, cognitive scientists, and com- putational neuroscientists have explored how the embeddings of multiple elements could be com- bined to reflect relationships between them or higher-level semantics. However, almost all this work was based on word embeddings. in which perception was not necessary. Some early work investigated how the grammatical structure and/or semantics of an input sentence can be repre- sented (Pollack 1989) an efficient manner neural networks, and how such network could be trained (Elman 1993). Given the advent of word embeddings, deep NLP architectures can com- bine the word-leve semantics, as represented by the embeddings of the individual elements of an input sentence, to infer higher-level attributes, c.g., sentiment (Nakov et al. 2016). Recent work has investigated to what extent contemporary recurrent neural networks can generalize to understand novel sentences (Lake & Baroni 2017) consisting of known words. Also, in the NLP domain, Doshi et al. (2018) developed compositional pairwise embeddings that model the co-occurrence relation- ships between two words given their common context. Probably the most algorithmically similar work to ours is by [yu et al. (2019) on compositional network emheddings: the goal is to predict whether two new nodes in a graph, which were not observed during training, are adjacent, using node-based features as predictors. In their approach, two embeddings are used: one to embed the node-based features, and another to aggregate these embedded features into a secondary embedding space. Structurally, their work differs from ours in that (1) the two embedding spaces in their model do not represent the same universe of objects; (2) the embeddings do not capture set relationships.
Deep set representations: Our paper is also about how to encode set of objects with neural network. One issue how to ensure invariance to the order in which examples are presented. Vinyals et al. (2015) proposed an approach based For producing sets as outputs, RRezatofighi et al. (2017) proposed probabilistic model, within a supervised learning paradigm where all classes known training time, that predicts both the cardinality and the particular elements of the set.
permutation-invariann content-based attention.
MODEL I: EMBEDDING/ f AND COMPOSITION
Given two examples va and Ha that are associated with singleton sets {s} and {t}, respectively, the hope is that, for some third example x. that is associated with both classes (i.e., {8,()) {)), we have
g(f(z)), ff (2x)) Re f(ze)
Moreover, hope that g can generalize to any number of classes within the set S. For example, if example va is associated with singleton set {u), then we hope
((g(((x)) ((x)), (xaa) M(x))
where is an example associated with {s, ł, u}.
There are two challenging tasks that and g must solve cooperatively: (1) f has to learn to perceive multiple objects that appear simultaneously and may possibly interact with each other - all without knowing the rendering process r of how examples are formed how classes are combined. (2) g has to define geometrical structure in the embedding space to support set union operations. One way to understand our computational problem is the following: If f is invertible, then ideally we would want y to compute g(e7, ezx) = ((r(c((>>(TT)) U c(f-)(ez))))
In other words, one (though not necessarily the only) way that g can perform well to learn to perform the following actions (without knowing or c): (I) invert each of the two input embeddings; (2) classify the two corresponding label sets; (3) render an example with the union of the two inferred label sets; and (4) embed the result.
One-shot learning: Model I can be used for one-shot learning on set of classes S not seen during training in the following way: We obtain & labeled examples 21..... 2y from the user, where each { = c(x;) is the singleton set formed from the ith element of S and |S] = k. We call these examples the reference examples. We then infer which set of classes is represented by new example
3

---

Published as a conference paper at ICLR 2020
r' using the following procedure: (1) Compute the embedding of i..,, f(='). (2) Use f to compute
the embedding of each singleton example 24, i.e., (()) = f(z)) (3) From e()..... (R). estimate
the embedding of every subset = {8 .81....,811 S according to the recurrence relation:
e(s ge (1 E(mc))
Finally, (4) estimate the label of x' as
arg [f(')) - et TES
(2)
Although the number of possible subsets is exponential in [S, for speaker diarization the number of overlapping speakers typically small, and thus the iteration is tractable.
3.1 TRAINING PROCEDURE
Functions f and are trained jointly: For each example associated with classes T, we compute et from the singleton prototypes according to Equation []] (To decide the order which we apply the recursion, we define an arbitrary ordering over the elements of S and iterate accordingly.) We then compute a hinge loss:
ff(x) etl - erl-c
for every T' T S. where is a small positive real number. In practice for each example a, we randomly pick one element T 2 for comparison. See Appendix for discussion of an alternative (but less effective) training procedure.
3.2 EXPERIMENT 1: SIMULATED 1-D AUDIO WAVEFORMS
To explore the viability Model I, we first conducted a simulation using 1-D "audio" signals, in which each "speaker" 8; S is modeled with a prototype P; R" consisting of the superposition of some randomly chosen frequencies and phases. Then, the simultaneous sound from multiple (up to 3) speakers is given by rendering function that computes vector sum of slightly perturbed versions of the prototype vectors and then clips the result. (See Figure (a) for example waveforms, and the Appendix for more details.) We trained an embedding and composition functions and g. as described in Section 3.] on a set of 250 speakers, We then tested these functions on test speakers seen during training after providing just single "reference" example of each speaker for one-shot learning. The goal is to identify the exact set of speakers who contributed to the formation of each audio waveform.
(and examples)
Architecture: For function we used a simple convolutional neural network that produces unit- length vectors R:32
BN-Conv 32) ReLU-BN BN-Con - ReRR-RLLUPPPPP COLLU--MP)--F((2)-RLLL-------
-22Norm
where Conv(k, f) is a 1-D convolutional layer with f filters of size k, stride and zero-padding to preserve the spatial extent of the example; BN is batch normalization; MP(k) is max-pooling layer with width and stride k; FC(n) is a cully-connected layer with n neurons; and L2Norm is a L lnznorrmalizaionn layer. We constructed the composition function (gDNN) be symmetric:
Symm(a, 62)) - - FC(3) BN- Reee-eeeU------ FC(3)) - R--RRe-UFF(PS -o2Nom
where Symm(a, a, b; k) Waa + W,b (2 3 b) a symmetric function (with parameter matrices W1. W2) of its two examples a, E IR" that produces vector in R
Assessment:
We evaluated accuracy (% correct) in multiple ways: (1) the accuracy, over all exam- ples, of identifying the exact set of speakers: (2) the accuracy, separately for each set size (1,2,3), of identifying the exact set of speakers; and (3) the accuracy, over all examples, distinguishing just the number of speakers in the set rather than their specific identities. As baseline, we used an ora- cle that returned the Most Frequently (MF) occurring label set in the test set (or a random selection among multiple most frequent elements). Results are shown in T Note that, for the rows that evaluate on k-sets, the embedding functions are still used to compare the test example to every possible subset (see Equation 2 not just subsets of size k. In general, the compositional embedding method was far more accurate (48.1% 1% for top- and 69.6% for top-3 on all subsets) compared to the baseline. The accuracy improvement was largest singletons (1-sets), which made up 1/3 of the
4

---

Published as a conference paper at ICLR 2020
Experiment 1 (1-D Waveforms): Accuracy
Reference examples)
Label Set Identification
(1)
{2)
{3}
f & 9DNN
MF
MMW
All
Exact
48.1 (7.3)
7.3 (0.2)
Top-3
69.6 (8.6)
21.7 (0.7)
1 1-sets
Exact
94.6 (5.9)
Top-3
100.0 (0.0)
Test examples
2-sets
Exact
33.7 (13.8)
(1)
[1.2]
21
Top-3
88.5 (10.5)
3-sets
Exact
16,0 (9.2)
Top-3
73.4 (13.5)
Set Size Determination
All
(7.9
33.3 (0.0)
(a)
(b)
Figure 2: Experiment 1. (a): Simulated audio signals. Each class generated by prototype wave- form. Each example is noisy superposition of one or more prototypes. "Reference" examples are used for one-shot learning: "test" examples are used for evaluation. (b): Mean (std.dev.) accuracy (% correct) in inferring the label sets exactly (top 1), within the top 3, and the size of each label set. Results are averaged over 50 test sets on classes not seen during training (one-shot learning).
test data, and for which any non-compositional embedding functions (i.e., f trained without any g) would likely work well. Even on 2-sets and 3-sets, however, the compositional embedding approach was substantially more accurate than the baseline. Moreover, part of the task involves inferring the number of elements in the label set (set size determination); on this problem too the compositional embedding was nearly twice as accurate (61.9% vs. 33.3%) compared the MF baseline.
Geometry of the embedding space: We visualized (using PCA) the embedding space for set of classes not used for training (Figure[[b)). Each marker (the symbol/color combination distinguishes the different label sets) represents the embedding of a test example. The clusters of markers for each label set are clearly distinguished by the embedding f. From the examples from each label set, one is randomly chosen the "reference" examples for 1-shot learning. Using composition function 9DNN, their embeddings are combined to estimate where, in the embedding space, an example for the union of their two label sets would lie; the estimated location is shown at the head of the arrow whose two tails come from the two reference examples. Although the estimated and actual clusters do not align exactly, there is substantial agreement. For instance, the examples for speakers 21, 3) (i.e., all 3 people talking simultaneously) are represented by the blue triangles pointing to the right, and the estimate, given by and gDNN from reference examples of {3) and (1, is shown the head of the arrow with label {1, 2, 3) beside it. Not all compositions are accurate, e.g., the estimated location for label set {1, 3) is somewhat below the actual cluster location.
3.3 EXPERIMENT 2: OMNIGLOT
We also evaluated our method the OmniGlot dataset (Lake al. 2015). OmniGlot contains
handwritten characters from 50 different alphabets; in total it comprises T623 symbols, each of which was drawn by 20 people and rendered as a 64x64 image. OmniGlot has been previously used in one-shot learning research (c.g., Rezende et al. (2016): Bertinetto et al. (2016)). In our experiment, the model is provided with one reference image for each singleton test class. Then, it uses f and to select the subset of classes that most closely match the embedding of each test example (Equation[]). (). In this study we considered class label sets up to size (i.e., singletons and 2- sets). The rendering function r randomly picks one of the 20 exemplars from each class; it randomly shifts, scales, and rotates it; and then adds it to an image with Gaussian noise (see Figure images with multiple classes, the pixel-wise minimum across all classes is applied before adding the noise. (See Appendix for more details.) Similar to Experiment 1, the goal is to train f and so that, on classes not seen during training, the exact set of classes contained in each test example can be
a)). (a)). For
5

---

Published as a conference paper at ICLR 2020
inferred. During both training and testing, each of the 15 class label sets (5 singletons and (2) 10
2-sets) occurred with equal frequency. All the embeddings were normalized to unit length.
Architecture: For f. we used ResNet-18 (He et al. 2016) that modified to have input channel and a 32-dimensional output. For 9. we tested several architectures of increasing complexity: (a)
Bi-linear: OLin Symm(a, d; 32) 1.2orm. (b) Bi-linear FC: 9Li++FC Symm(a, ba,b;
BN ReLU FC(32) L2Norm. (c) DNN: 9DNN is defined as Section 3.2
The process is similar to Experiment 1. See Appendix for details. Testing: Similar to training, the testing data are grouped into randomly selected classes (not seen during training). and images from these classes rendered using function from either singleton or 2-set class label sets. We optimize Equation 2 to estimate the label set for each test example.
Training:
Baselines: We compared to several baselines:
Most frequent (MF): Always guess the most frequent element in the test set. Since all classes occurred equally frequently, this was equivalent random guessing.
Traditional with simulated composite reference examples (SimRef)) Given the reference examples of the singleton label sets (e.g., (1), (3)), we can simulate reference examples for each composite label set (e.g.. (1,33) and then use a traditional embedding approach classify the test examples. We simulated imperfect knowledge of the rendering function r by performing other words, this approach simply superimposes pairs of reference images on top of each other to simulate composite examples. To estimate the label set of each test example, we select the reference example (including the simulated composite references) with minimal L2 distance.
pixel-wise minimum, but without shitting/scaligg/rttatoon
Traditional ʃ and average (Mean): f is trained as a traditional embedding function (only on singletons) using one-shot learning (Koch al. 2015). Then the embedding of composite image is computed using the mean of the embeddings of each class in its label set.
Traditional ff trained jointly with Imean (gmean): f is trained on only singleton embeddings but is optimized jointly with composition Imcan that computes the mean of its inputs. The difference with the previous baseline is that f can benefit from knowing how its embeddings are combined.
Results: As shown in Figure b)) the proposed & g method outperforms the Mean and Jmean baselines. Upon closer investigation, we discovered that, while Mean can distinguish each singleton from the other four singletons with high accuracy (0.979, not shown in table), it struggles when it must decide among all 15 possible label sets. The slightly more powerful f & IMean method (i.e., the composition function has no trainable parameters) can achieve better accuracy on 2-set images, but the accuracy on 1-set images was much worse than other methods. We argue that and y correspond to two different tasks, and the model not able to do good job on both tasks at the same time without optimizing g. If g is learnable function, then simple symmetric linear function (gLin) achieves the best performance. After we stack more FC layers, the performance gets worse. The reason could be overlitting, and it may be possible to achieve better performance with regularization or more training data.
4 MODEL II: EMBEDDING f AND QUERY FUNCTION h
In real life, it is very difficult to create a dataset that all singletons in a compositional set are labeled. Thus, want to extend our compositional embedding from "composition" to "containing".. Here we consider a second type of compositional embedding mechanism that tests whether the set of classes associated with example subsumes the set of classes associated with another example. We implement this using a "query" function à that takes two embedded examples as inputs:
(xa),, f(x))) True + c(xx) S c(x.)
In contrast to g, function not symmetric: its first and second arguments are the putative superset and subset, respectively. Also, h can be trained in an unsupervised manner w.r.t. the individual examples: it never needs to know which particular label set is associated with an example, but rather only pairwise information about which examples "subsume" other examples. For h, tried several functions (hpNN, h hran), analogous to the different implementations of g from Section 3.3 The final layers of all models have 1-dimensional output.

---

Published as a conference paper at ICLR 2020
Ref.
Accuracy
(2)
(3)
(4)
(5)
Label Set Identification
Test
JDNN
LLnn
Meam
Mean
SimRef
MF
All
Exact
77.8
77.7
81.5
75.3
43.7
41.3
6.67
2
3
(4)
(5)
Top-3
95.4
95.1
96.8
93.8
67.6
59.9
20.0
1-sets Exact
97.4
95.8
96.7
88.0
89.8
98.3
Top-3
99.5
99.1
99.4
98.3
98.9
99.9
(1.2
1.3
1.4)
15
233
2-sets Exact
68.0
68.6
73.9
68.9
20.6
12.8
Top-3
93.3
93.1
95.4 91.5
51.9
39.8
Set Size Determination
{2,4) [2.5} (3.4)
[3,5] {4.5}
All
96.5
96.6
197.2 90.5
76.7
66.8
|66.7
(a)
(b)
Figure 3: Experiment 2. (a): Reference and test examples of OmniGlot images. (b): Mean accuracy (% correct) in inferring the label set of each example exactly (top 1), within the top 3, and the size of each label set. Results are computed on classes not seen during training (one-shot learning).
Experiment (OmniGlot)
Experiment 4 (COCO)
IDNN
41
Fn.FC
hg.in
TradEmb
VDNNN
Fn
TradEmb
ResNet
% Correct
77.9
77.3
73.8
75.3
Correct
64.8
62.5
62.1
54.8
58.4
AUC
86.8
85.5
81.7
85.6
AUC
71.2
67.7
67.3
57.2
58.7
(a)
(b)
Table 1: Accuracy to query whether the classes in one example subsume the classes in another example, for the proposed / & h method versus "traditional" embedding function f as baseline. Method f & h is the proposed model; TradEmb is a baseline. (a): Experiment 3. (b): Experiment 4.
4.1 TRAINING PROCEDURE
Functions I and h are trained jointly. Since h is not symmetric, its first layer is replaced with two weight matrices for the different input embeddings (see Appendix). In contrast Model "reference" examples are not needed: only the subset relationships between label sets of pairs of examples are required. Model II can trained on one set of classes and applied to a different set of classes (see Experiment 3), akin to zero-shot learning. It is also useful when the training and testing classes are the same because, in contrast to traditional supervised training of detector for each possible class, labels for individual examples are needed. To train f and h, we backpropagate binary cross-entropy loss, based on correctly answering the query in Eq. 3 through both f and h.
4.2 EXPERIMENT 3: OMNIGLOT
Here we assess Model II in a one-shot learning setting (OmniGlot), i.e., training and testing classes different. As in Experiment 2, we consider class label sets of size up rendering function r. Let f(xxa) and f(x;) be the second arguments to h. For Ta. we always choose examples associated with two classes, i.c., c(za) = (s1, $2). For øb. half of the positive examples (i.e.. such that h (xx() fxx)) = True) contain either
and we use the same
and half contain both classes. For the negative examples (xa)) (*x)) False), 24 associated with some other singleton class 83 E {2). See Appendix for more details. Baseline: We compared our proposed method with a traditional (non-compositional) embedding method (TradEmb) that is trained to separate examples according to their association with just single class. In particular, for each composite example Ia (i.e., (c(#.)) = 2), we picked one of the two classes arbitrarily (according to some fixed ordering the elements of S); call this class $1. Then, chose both positive example Is (such that c(x;) = {s} }) and a negative example I, (such that c(x,) = {sa} & c(x,)), We then compute hinge loss so that the distance between fI..) and (Ix) is smaller than the distance
7

---

Published as a conference paper at ICLR 2020
(b)
(c)
(d)
(1)
Figure 4: Experiment 4 (COCO): An example image (left) of two people, talking a cell phone, and the other wearing a backpack. The image is padded to form square and then downscaled (a). The composite embedding (f & h) computed and then queried about the presence of the object in images (b), (c), (d), (c), and (f) containing person, cell phone, backpack, truck, and oven, respectively. The query function h, when given the embeddings of image (a) and another image, should return True for (b),(c)(d)) and False for (f).(f).
between f(xa) and fzze), and backpropagate the loss through f. During testing, we use to answer a query does c(xxa) contain c(xa)? by thresholding the distance between f(ra) and f fxx) (threshold of 0.5). Results are shown in Table Ta). Compositional embeddings, as implemented with a combination of f trained jointly with either hoNx, h or hyin- slightly outperformed the TradEmb baseline, in terms of both % correct accuracy and AUC. Moreover, there was an advantage of deeper architectures for
4.3 EXPERIMENT 4: COCO
We trained and evaluated Model II on COCO (Lin et. 2014). This a highly challenging problem: in the example in Figure 4 f has encode backpack, cell phone, and person; then, given completely different images of these classes (and others), & has to decide which objects were present in the original image. Here, training and testing classes are the same (but testing examples used for training). In COCO, each image may contain objects from multiple classes, and each object has bounding box. We used the bounding boxes to crop singleton objects from images. For training, we used the same strategy as Experiment 3. except that in positive queries (i.e., pairs of images Fay 24 such that (x(()))) (anx) True), image Th was always associated with just singleton label set. During testing. half of are contained in and half are not (see Appendix). Baseline: We compared
not
the TradEmb method: decide the singleton label set for each image during training, we pick the largest object. Since in this problem the training and testing classes are the same, we also implemented another baseline (see Appendix) consisting of ResNet classifier with multiple independent binary outputs (one for each class). We can then answer queries about the label sets of two images using the labels of the different classes estimated by the ResNet for each image. Results are shown in Table (b)) The proposed methods (f & one of the h functions) easily outperformed TradEmb. They also outperformed the ResNet baseline. One possible reason for the latter baseline's poor performance was that the data highly imbalanced (since most images contain just a few images). As in Experiment 3, deeper architectures for h performed better.
5 CONCLUSIONS
We proposed new kind of embedding mechanism whereby the set of objects contained in the input data (e.g., image, video, audio) must be both perceived and then mapped into a space such that the set relationships union (Model 1) and subset (Model III between multiple embedded vectors can be inferred. Importantly, the ground-trutt rendering process for how examples are rendered from their component classes is not known and must implicitly be learned. In experiments, conducted on simulated data, OmniGlot, and COCO, the accuracy was far from perfect but outperformed several baselines, including one based traditional embedding approach. The results provide proof-of-
8

---

Published as a conference paper at ICLR 2020
concept of how embedding function trained jointly with either the composition function g or the query function h, could be effectively optimized. One possible direction for further research to increase accuracy is to take better advantage of the statistical structure of class co-occurrence in specific application domain (e.g., which objects tend to co-occur the same image).
REFERENCES
Luca Bertinetto, João F Henriques, Jack Valmadre, Philip Torr, and Andrea Vedaldi. Learning feed- forward one-shot learners. In Advances in Neural Information Processing Systems, pp. 523-531, 2016.
Jeffrey I. Elman. Learning and development in neural networks: The importance of starting small. Cognition, 48(1):11-99, 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Mandar Joshi, Eunsol Choi, Omer Levy, Daniel S Weld, and Luke Zettlemoyer. pair2vec: Com- positional word-pair embeddings for cross-sentence inference. arXiv preprint arXiv:1810.0880 2018.
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In ICML deep learning workshop, volume 2, 2015.
Brenden M Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-seqqeeee recurrent networks. arXiv preprint arXiv:1711.00330, 2017.
Brenden Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 13306266):1332113333 2015.
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pictro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pp. 740-755. Springer, 2014.
Tianshu Lyu, Fei Sun, Peng Jiang, Wenwu Ou, and Yan Zhang. Compositional network embedding for link prediction. In Proceedings of the 13th ACM Conference on Recommender Systems, pp- 388-392, 2019.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv: 2013.
Preslav Nakov, Alan Ritter, Sara Rosenthal, Fabrizio Sebastiani, and Veselin Stoyanov. Semeval- 2016 task 4: Sentiment analysis in twitter. Proceedings of the 10th international workshop on semantic evaluation (semeval-2016), pp. 1-18, 2016.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532- 1543, 2014.
Jordan B Pollack. Implications recursive distributed representations. In Advances neural information processing systems, pp. 527-536, 1989.
S Hamid Rezatofighi, Anton Milan, Ehsan Abbasnejad, Anthony Dick, Ian Reid, et al. Deepsetnet: Predicting sets with deep neural networks. In 2017 IEEE International Conference on Computer Vision (ICCV), pp. 5257-5266. IEEE, 2017.
Danilo Jimenez Rezende, Shakir Mohamed, Ivo Danihelka, Karol Gregor, and Daan Wierstra. One- shot generalization in deep generative models. arXiv preprint 1603.05 2016.
Florian Schroff. Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the recognition, pp. 813-823, 2015.
the IEEE conference on computer vision and pattern

---

Published as a conference paper at ICLR 2020
Tyler Scott, Karl Ridgeway, and Michael C Mozer. Adapted deep embeddings: A synthesis of methods for k-shot inductive transfer learning. In Advances Neural Information Processing Systems, pp. 76-85, 2018.
Gregory Sell, David Snyder, Alan McCree, Daniel Gareia-Romero, Jesús Villalba, Matthew Ma- ciejewski, Vimal Manohar, Najim Dehak, Daniel Povey, Shinji Watanabe, al. Diarization hard: Some experiences and lessons learned for the jhu team in the inaugural dihard challenge. In Interspeech, pp. 2808-2812, 2018.
David Snyder, Daniel
Gregory Sell. Daniel Povey, and Sanjeev Khudanpur: X- vectors: Robust dnn embeddings for speaker recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5329-5333. IEEE, 2018.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. arXiv preprint 101.:v:1111.00311,, 2015.
A ALTERNATIVE TRAINING PROCEDURE
We also tried another method of training f and g with the explicit goal of encouraging g map eT and ez to be close to éTUH. This can be done by training and y alternately, or by training them jointly in the same backpropagation. However, this approach yielded very poor results. A possible explanation is that g could fulfill its goal by mapping all vectors to the same location (e.g., 0). Hence, a trade-off arises between g's goal and f's goal (separating examples with distinct label sets).
B EXISTENCE OF & g: ALGEBRAIC CONSTRUCTION
Since it was initially not clear to us whether functions ff and even exist with the desired properties that could plausibly be implemented as neural network, we first sought design them analytically. Composition function needs to map two vectors on a unit sphere back onto the same sphere, so that the location on the sphere uniquely identifies a set of classes. Here, we assume the set classes is the same for training and testing. Our construction is inspired by basic group theory, in particular how each element of a permutation group can be represented as rotation of Euclidean space and performed by multiplication with a permutation matrix.
Let |S| = We model g after the permutation group of degree m 2k consisting of all pairwise exchanges of coordinates 2i and 2i 1 (i 1...., k), where the group action is composition. Since each such permutation is independent of all the others, the group is commutative and contains contains 2| elements. Each member
contains 2* elements - just as we desire so that range of the permutation group can be associated with a unique permutation matrix, where multiplication among these matrices also commutative. Define vector eg E 2R whose length is and whose components are all distinct. The first condition is standard when creating embedding, and the second is important so that the permutations applied to the vector can be deduced unambiguously. S,
We associate vector eg with the empty set 0. Next, each singleton {si). where associate the m-dimensional permutation matrix P(s.) that swaps axes 2 and 2i 1.
We define f as neural network: In its first layers, all the classes associated with example detected independently using & binary classifiers. Next, for all the detected classes, their associated permutation matrices P are multiplied together, which yields another commutative permutation ma- trix the resultant matrix identifies all the classes present in the example. Finally, the result is multiplied by vector eg. This produces a vector with unit length in the embedding space R" If the first few layers comprise & binary classifiers (z( E {0, (i i,..., m., then the whole f network computes:
II (P(na) di(s)
f(x)
eg
ViSEES
We then construct so that, given two embedded vectors eu, it computes the product of their associated permutation matrices and multiplies the result by eg:
(ieT.ezi o( (Pre,, Pueo)= = PT Pure Preure
10

---

Published as a conference paper at ICLR 2020
This construction of f and و enables perfect inference of the union of classes associated with any examples, provided the binary classifiers are perfect. This gave us hope that compositional set embeddings could succeed.
C DETAILS OF EXPERIMENT 1
Each speaker was represented by "prototype" waveform comprising the sum of 8 sinusoids (range (-1,+1) with randomly chosen frequencies and phases. To construct each training and testing example, the prototypes of all the speakers contained in the particular example are added together and then clipped at [-4, +4]. To simulate noise, we slightly perturbed the frequencies and phases of each prototype by random noise drawn uniformly from [-0.02, +0.02]. We also perturbed the superposition by small amount (from [-0.02, +0.02)) prior clipping. The training dataset con- tained a total 250 simulated speakers. Each minibatch comprised 3072 examples from 5 unique speakers that were combined in randomly selected subsets T: 1024 of these contained individual speakers (singletons). 1024 contained combinations of 2 speakers, and 1024 contained combina- tions of 3 speakers. Functions/ and y were trained jointly as described in Section [3.1 Training was conducted for 4000 epochs with a learning rate of 0.002 and the Adam algorithm. We set the hinge parameter e 0.1. At test time, one of the singleton examples was randomly chosen as the "reference" example for one-shot learning. Similar to training, each test set consists of 3072 exam- ples comprising randomly chosen -ssess, 2-sets and 3-sets of speakers; see Figure 2 () for example waveforms.
D DETAILS OF EXPERIMENT 2
To generate example image from a class prototype, applied random affine transformations consisting of shift up to 20%, scaling up to 10%, and rotation up to 10 Gaussian noise was added with mean 0.9 and variance 0.1. We the hinge parameter e - 0.1.
Training is performed on 964 OmniGlot classes; from each of these, the 20 images are augmented using affine transformations (described above) yield 50 images. Each mini-batch comprises 10000 examples from 5 classes, with two images randomly selected per class: one as reference example, and one training example. The validation
consists of 20 OmniGlot classes used for training. Training is performed using Adam (Ir = .0003) to maximize the validation accuracy, up to a maximum of 100 epochs. Testing accuracy is computed over the 659 OmniGlot classes used for training or validation.
E DETAILS OF EXPERIMENT
The dataset used in this experiment is the same experiment including the distribution of training set, validation set and test set.
We also used the same ResNet-18 8 as for Experiment 2. Function h constructed the same except that (1) the first layer was relaxed to be asymmetric: Wiet + Wzez, and the output layer logistic sigmoid. For training and testing, the proportion of positive and negative queries was fixed to be equal. During training, each mini-batch contains 128 query pairs and each query pair composed by positive query and negative query. We use binary cross entropy loss and Adam optimizer (Ir = .0003) to optimize the models. During evaluation, 0.5 is used for thresholding.
F DETAILS OF EXPERIMENT 4
COCO's training set is used for training, and COCO's labels of subclasses used training labels. small part images (100) are taken as validation set.
For ResNet baseline, We modified ResNet's last's dimension to 80 and applied logistic sigmoid to all of them. Thus, the output layer can be used as 80 classifiers and each one corresponds to one possible subclass.
11

---

Published as a conference paper at ICLR 2020
AUC % Correct
75
65
60
55
50
3
10
12 13
Number of subclasses
Figure 5: /IDNN'S results according to the number of subclasses contained in images: Results of images contain more than 7 labeled objects are showed by dotted lines because they have fewer than 100 samples in test set.
During training, the loss is composed by binary cross entropy loss from all 80 binary classifiers. For every subclass in all 80 possibilities, if it the of subclasses of one image, then the label is 1, otherwise O. Adam optimizer ((Ir) = .0003) is used for optimization. During evaluation, for each query we assume the class labels of subelass images are already known.
ResNet is not optimized to answer queries about image pairs. Instead, it tries to encode each image into n-bit string (for n classes). While this representation can account for all 2n possible label sets, it may not be the most effective or efficient representation for the task, especially since some objects are very unlikely to co-occur with others. The proposed f&h embedding method can harness the co-occurrence structure to answer queries more accurately, whereas ResNet trained to recognize all the individual classes does not harness it.
For other models singleton images also required, which cropped according to COCO's la- bels of bounding boxes. All images were padded with zeros to be square and then downscaled to 128x 128.
We used the same architecture as for Experiment 3, except that the input layer was 3 channels instead of 1. Testing was the same Experiment 3 (likewise with distance threshold of 0.5). In both training and testing, the number of positive queries and negative queries are balanced.
In order explore how the number of subclasses affects h() function, also plot the accuracy and AUC with different number of subclasses in Figure We can see decreasing trend of performance when the images contain more kinds of labeled objects.
12


Reviews:
[{"review_id": "Hkx7Kvvk5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper describes a way to train functions that are able to represent the union of classes as well as to query if the classes in an image subsume the classes in another image. This is done throughly jointly training embedding functions, a set union function and a query function. The paper reads well.\n\nWhile the approach is reasonable, the experiments seem to be quite incomplete and no explanation is given why a trivial solution cannot be used instead of the learnt functions.\n\nThe paper argues for learning a set union function however much of the evaluation focuses on quite small sets of 2 or 3 items. On the evaluation that utilises larger sets, e.g. COCO, there isn't any analysis of how performance of the technique scales with the size of the set since that would be one of the defining characteristics of a set union function. The COCO experiment is also lacking in detail, for example, how many items are there in the positive and negative sets and how the test set is balanced. Finally, it seems that f, g and h could be trivial non-learnt functions. For example, f could be a function that maps an image to a binary representation of its classes (this could be a typical ResNet image classifier), g could be a function that does a binary OR of its two arguments and h could be a function that uses a binary AND and equality test on its two arguments. In this case, g and h don't need to be learnt at all. This may not be possible in the COCO experiment where the individual labels are not known but it seems quite unrealistic to have a dataset where only pairwise subset relationships are known.\n\nIt also seems that the f is always different between that used with g and that used with h, is this the case? SimRef also doesn't do data augmentation but there's no explanation why it is done for the proposed method and not for this baseline. The MF baseline in experiment 1 seems to be a straw man especially since the baselines in experiment 2 are much stronger.\n\n================================================================================\nUpdate after rebuttal:\n\nThanks for answering my questions and performing the additional experiments with a ResNet baseline and performing an additional analysis based on the number of subclasses in figure 5. I think these provide a substantially better analysis of the algorithm so I've increased my score correspondingly. For the final paper, I think it would be good to add TradEmb/ResNet to figure 5 as well to understand how those methods scale worse/better with the number of subclasses.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1edfYN0YS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a joint/compositional embedding procedure where a single instance can be mapped/embedded to multiple classes while preserving the class-specific information in the embedded representations. The authors look at class union and class query criteria for the composite embeddings. The proposed approach is evaluated appropriately. There are several issues with the work. \n\nDoes the proposal mean each embedding eventually corresponds to multiple classes/subclasses ie., one can learn something on-trivial about each class from these embeddings that is different from class-specific embedding? How do you avoid the trivial solution problem here i.e., the embeddings are going to be average of the class-specific embeddings --- as we see in the evaluations this is in fact happening (figure 1b)? Also, is this behaviour desired i.e., tending towards mean? \n\nAnd continuing along these lines, a clear choice of baseline for the proposal is to choose mean embeddings i.e., men of independent embeddings? Or is this not appropriate? Why is ML the best baseline? We can use the probability map (the input to final softmax) instead as the embedding as well correct? \n\n\"... x_a containing objects in another image \" -- this statement is not making sense, is it objects in x_a also present in another image x_b?\n\nIt is rather difficult to interpret the usefulness of g(.) when it is a nonlinear model like neural network. Simpler models (like Symm(a,b,.) i.e., just the first layer of what is being used now) should be evaluated instead to get better understanding of what is going on! \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lxwbMTtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n=======\nThis paper proposes compositional embeddings i.e. embeddings that can be used to infer multiple classes from the data. In particular, the paper deals with two types of composite functions for embeddings, one that computes union of the different classes represented by each embedding vector, and the other where the class of one of the embeddings is subsumed by the class of the other embedding. The actual composition functions are parameterized by neural networks whose parameters are learned from data. Results on synthetic as well as several real-world datasets highlight the superiority of the learned composite embeddings. \n\n\n\nComments:\n==========\n1) This paper presents a welcome contribution to the saturated literature on embeddings. The whole idea of compositionally and its application to speaker diarization and multi-object detection is novel. \n\n2) The execution of the idea is also excellent and thorough. Further, the paper is very well written and puts itself nicely in context of previous work. I think this should inspire future work on other kinds of composite functions other than the two considered here. \n\n3) The results on both the synthetic and real-world omniglot and COCO datasets are impressive and mostly well executed and show significant improvement over the \"most frequent\" baseline. \n\n\n4) My only concern regarding the paper is w.r.t some arbitrary decisions made in the experiments e.g. how was the exact neural architecture for f in section 3.2 chosen? It seems contrived. Is it possible to do some ablation studies? Also, I think it will be nice to provide some more details regarding the neural network training in Section 3.1.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new type of compositional embedding (with two proposed variants) for performing tasks that involve set relationships between examples (say, images) containing sets of classes (say, objects).  The setting is new and the reviewers are mostly in agreement (after discussion and revision) that the approach is interesting and the results encouraging.  There is some concern, however, that the task setup may be too contrived, and that in any real task there could be a more obvious baseline that would do better.  For example, one task setup requires that examples be represented via embeddings, and no reference can be made to the original inputs; this is justified in a setting where space is a constraint, but the combination of this setting with the specific set query tasks considered seems quite rare.  The paper may be an example of a hammer in search of a nail.  The ideas are interesting and the paper is written well, and so the authors can hopefully refine the proposed class of problems toward more practical settings.
Decision: Reject