Representation Learning with Multisets
Authors: Vasco Portilheiro
Venue:  (2020)
Keywords: multisets
fuzzy sets
permutation invariant
representation learning
containment
partial order
clustering

Abstract: We study the problem of learning permutation invariant representations that can capture containment relations. We propose training a model on a novel task: predicting the size of the symmetric difference between pairs of multisets, sets which may contain multiple copies of the same object. With motivation from fuzzy set theory, we formulate both multiset representations and how to predict symmetric difference sizes given these representations. We model multiset elements as vectors on the standard simplex and multisets as the summations of such vectors, and we predict symmetric difference as the l1-distance between multiset representations. We demonstrate that our representations more effectively predict the sizes of symmetric differences than DeepSets-based approaches with unconstrained object representations. Furthermore, we demonstrate that the model learns meaningful representations, mapping objects of different classes to different standard basis vectors.

Under review as a conference paper at ICLR 2020
REPRESENTATION LEARNING WITH MULTISETS
Anonymous authors
Paper under double-blind review
ABSTRACT
We study the problem of learning permutation invariant representations that can capture "flexible" notions of containment. We formalize this problem via measure theoretic definition of multisets, and obtain a theoretically model. We propose training this model on novel task: predicting the size of the symmetric difference (or intersection) between pairs of multisets. We demonstrate that our model not only performs very well on predicting containment relations (and more effectively predict the sizes of symmetric differences than DeepSets- based approaches with unconstrained object representations), but that it also learns meaningful representations.
learning
INTRODUCTION
Tasks for which the input is an unordered collection, i.e. a set, are ubiquitous and include multiple- instance learning Ilse et al. (2018), point-cloud classification Zaheer al. (2017); Qi et al. (2017).
estimating cosmological parameters Zaheer et al. (2017); Ravanbakshh et al. (2016), colaaborative
filtering Hartford et al. (2018), and relation extraction Verga et al. (2017); Rossiello al. (2019).
Recent work has demonstrated the benefits of permutation invariant models that have inductive biases
well aligned with the set-based input of the tasks (Ilse et al. 2018 Qi al. 2017; Zaheer et al. 2017
Lee et al., 2019).
The containment relationship between sets and intersection more generally is often considered as measure of relatedness. For instance, when comparing the keywords for two documents, we may wish model that fcurrency, equil im) deseribes a more specific set of topics than (i.e. is "contained" in) (money, ba 1 ance, economi cs ). The containment order is natural partial order on sets. However, we are often interested not in sets, but multisets, which may contain multiple geo-location data over time period, and data in any multiple-instance learning setting [Isee et al. 2018). The containment order can be extended to multisets. Learning to represent multisets in way that respects this partial order is core representation learning challenge. Note that this may require modeling not just exact containment, but relations that consider the relatedness of individual objects. We may want to learn representations of the multisets' elements which induce the desired multiset relations. In the aforementioned example, we may want money & cur currency and ba ance equí libri um.
copies of the same object; examples include bags-of-worde
Previous work has considered modeling hierarchical relationships or orderings between pairs of individual items (Ganea et al.) (2018 Lai and Hockenmaier, 2017, Nickel and Kiela 2017; Suzuki ct al. [2019] Vendrov et al. [015 Vilnis et al. 20188] Vilnis and McCallum 2015 Li et al. 2019
Athiwaratkun and Wilson 2018). However, this work does not naturally extend from representing
individual items to modeling relations between multisets via the elements' learned representations. Furthermore, we may want to consider richer information about the relationship between two multisets beyond containment, such as the size of their intersection.
In this paper, we present a measure-theorete definition of multisets, which lets us formally define the "flexible containment" notion exemplified above. The theory lets us derive method for learning representations of multisets and their elements, given the relationships between pairs of multisets - in particular, we propose to use the sizes of their symmetric differences or of their intersections. We learn these representations with the goal of predicting the relationships between unseen pairs of multisets (whose elements may themselves have been unseen during training). We prove that this allows us to predict containment relations between unseen pairs of multisets. We show empirically that the theoretical basis of our model is important for being able capture these relations, comparing our

---

Under review as a conference paper at ICLR 2020
approach to DeepSets- based approaches (ahherr al. 2017) with unconstrained item representations. Furthermore, we demonstrate that our model learns "meaningful" representations.
RELATED WORK
2.1 SET REPRESENTATION
Qi et al. (2117) and Zaheer et al. (2017) both explore learning functions on sets. Importantly, they arrive at similar theoretical statements about the approximation of such functions, which rely on permutation invariant pooling functions. In particular, Zaheer et al. (2017) show that any set function (A) can be approximated by a model of the form p (LueA Ø(a)) for some learned p and which they call DeepSets. They note that the sum can be replaced by a max-pool (which is essentially the formulation of et al. (2017)), and observe empirically that this leads to better performancel [ More recently, there has been some very interesting work on leveraging the relationship between sets. Probst (2018) proposes a set autoencoder, while Skianis et al. (2019) learn set representations with network that compares the input set to trainable "hidden sets." However, both these approaches require solving computationally expensive matching problems at each iteration.
2.2 ORDERS AND HIERARCHIES
Vendrov et al. 2013) and Ganea et al. (0118) seek to model partial orders on objects via geometric relationships between their embeddings namely, using cones in Euclidean space and hyperbolic space, respectively. Nickel and Kiela (2017) use similar idea to embed hierarchical network structures hyperbolic space, simply using the hyperbolic distance between embeddings. These approaches are unified under the framework of "disk embeddings" by /uzuki et al. (2019). The idea is to map each object to the product space X x R, where X is a (pseudo- )mttrrc space. This mapping can be expressed as A + (f(A), r (A)), and it is trained with the objective that A = B if and only if d (BB) I r(B) - r(A). An equivalent statement can be made for multisets (see Proposition 3.2.4.
Other work has taken a probabilistic approach to the problem of representing hierarchical relationships. Lai and Hockenmaier (017)) attempt to formulate the Order Embeddings of Vendrov et al.) (2015)
probabilistically, modeling joint probabilities as the volumes of cone intersections. Vilnis et al. (018)
represent entities as "box embeddings," rectangular volumes, where containment of one box inside another models order relationships between the objects. (Marginal and conditional probabilities can be computed from intersections of boxes.) Vilnis and McCallum (2015) propose modeling words as Gaussian distributions in order to capture notions of entail entailment and generality, and this work has been extended to mixtures of Gaussians by Athhwaratkun and Wilson (2017).
2.3 FUZZY- AND MULTI- SETS
The theory of fuzzy sets can be traced back to Zadeh (1965). A fuzzy set A of objects from a universe U is defined via its membership function μ4 27 -> [0. IJ. Fuzzy set operations such intersection are then defined terms this function. In modern fuzzy set theory, intersection usually defined via I-norm, which is function T: [0, 1j2 - [o, 1] satisfying certain properties. The intersection of two fuzzy sets A and B is defined via the membership function HAnn (x) = T' (æ), p (x)). (More in-depth background, including the defining properties of t-norms, is provided in Appendix
B There is also more recent literature on extending fuzzy set theory to multisets (Casasnovas and Mayor 2008 Miyamoto 2000), using a membership function of the form μ. 47 [0, N.
where | (Z, 0:) is the number of appearances in A of an object with membership a.
'We believe there is an interesting theoretical distinction worth noting here, which may help explain this observation. Namely, max- max-pooling is idempotent, meaning that repeatedly pooling a representation with itself does not change the result. On the other hand, summation does not have this property, and so repeated copies of an element are reflected in the result. In this way, DeepSets (with the sum rather than max-pool) is in fact modeling multisets rather than sets, which depending on the application may be undesirable.
2

---

Under review as a conference paper at ICLR 2020
3 PROBLEM FORMULATION
Our goal is learn to represent and predict notion of containment between multisets. We begin with brief motivating example, and then move on to provide the formalization of the problem. Recall our example, where for A (currency, equilibrium and B {money, balance, economics), we have a sense in which A is "contained" seeing many such example pairs of multisets, want to be able to deduce that for A' (currency, food] and B' {money, food), the relation A' C B' holds.
B. After
3.1 MULTISETS
In general, there exists a universe f2 of objects (in our above example, words). We let Q* denote the set of all multisets of objects from Q formally defined as follows.
Definition 3.1.1 A multiset A is defined by a its membership function m. Ω + M, where M C R a subset of the non-negative reals, and ma maps each object to the "number of times" occurs in A.
The choice of M dictates the kind of multiset is. In particular, M {0, 1} gives classical sets, and M = N gives the traditional notion of multiset - set which may contain multiple copies of the same object. If M RR,, then we call A "fuzzy multiset."
The cardinality (or size) of multiset is defined with respect to measure À on Ω.
Definition 3.1.2 The cardinality of multiset A is | mA(x)dd(z).
We will always fix some measure À on Ω (which may be called the dominating measure) and take all cardinalities with respect to x. Note that Nikodym derivative) of some measure 14A1 on Ω with respect to X. We can thus identify a multiset A with the measure μld Ω and write A (S)).
always view m, density (i.e. the Radon-
In the case that the universe Ω is countable, we simply let À be the counting measure, in which case the cardinality of any multiset A is |A| Enen (z(x).
All the usual operations on pairs of multisets are defined in terms of their membership functions.
Definition 3.1.3 For two multisets A and B, their intersection An B, union A B, sum A + B, difference A - B, and symmetric difference AAB, are multisets given by the following memberships functions, respectively:
mann(E) = min min(ma(r)) mn)))
mayB(x) (mx)
(A)B(F) (mx(ma(z)),m((1))
mAAB(Z) (
mA+B(I) m=(x) mz)
These definitions are standard for multisets with both whole-numle and real-valued memberships (Casasnovas and Mayor 20088) Miyamoto 2000: Blizard 1989). To those familiar with fuzzy set theory, it should immediately stand out the intersection and union are given by the standard T-norm and T-conorm (functions used to define these operations on fuzzy sets; see Appendix B). This means that definition of fuzzy multiset contains copy of fuzzy set theory. Unfortunately, there is no intuitive way to use other T-norms in order to define multiset operations. (For intuition on the above operations and why this is the case, see Appendix A
Finally, for multisets, containment formally defined as follows.
2 Note that this is not the same formulation of "fuzzy multisets" usually given in literature (Casasnovas and Mayor 2008 Miyamoto 2000). However, this formulation will be much more easily amenable to the machine- learbing---eaangggg. setting. Our notion here is also more closely related to the "real-valued multisets" of Blizard 1989), although the author approaches the subject from standpoint of formal logic and axiomatic theory.
3

---

Under review as a conference paper at ICLR 2020
Definition 3.1.4 For two multisets A E S2 and B O say that B contains A, or A A B, if and only if ma( & mp(z) all E Q
Note however that demonstrated by our motivating example above, for two multisets and B, we want to have more "flexible" notion than A C B. (It is not actually the case that fourrency, equil ubriium S (money; ba ance, economics).. We will now formally provide structure allowing for this flexibility.
3.2 A "FLEXIBLE" NOTION OF CONTAINMENT
Let us first make two observations. Firstly, the desired flexibility will depend on some notion of "similairty" between the objects in S2. Secondly, this similarity must be exterally provided by our observations of these "subset" relations. In our example above, we had a sense that money s currency and balance equilibril um, because we observed that "contained" in B (perhaps along with many other similar examples). We now formalize this idea.
Definition 3.2.1 For two universes Ω and U, a map T O - UI is a called multiset transforma- tion Ω to U.
The idea is that there exists some multiset transformation 7' from Ω to U, but we may not observe the structure of or this new universe U. However, we indirectly observe this structure, because our notion of subsets will be taken in l rather than in Q?". In particular, in our example above, the sense in which A is "contained" in that (AA) C (B)).
The simplest example of such setting, on which we focus, is when 4 (l...., k} [k]]. That is, maps each multiset Q2" to a multiset of numbers from 1 to k. These numbers can be thought of as "tags," "classes," or "labels," meaning that each multiset has associated to it some tags, each of which may occur more than once. Say for our running example, T(A) {1,2) 2) and T(B) {1, 2, 3]. We then obtain that T(A) C TB)) as desired.
The example mapping T above is suggestive. It suggests a category of such T functions that are commonly useful: when each object in Ω is itself associated with a "tag" in U. Here, money and currency both are associated to tag 1, bal ancce and equilibe um are both associated to tag 2, and economic cs to tag 3. Our map T is induced by this element wise mapping. We formalize this notion as follows.
Definition 3.2.2 We call a function t: -> 14 a universe transformation. Each universe transforma- tion t induces pushforward multiset transformation T, where the membership function of T(A) is (T) = fe-1w) mz))d))(x).
Proposition 3.2.3 Every pushforward multiset transformation T preserves cardinalities; that is, for any A, we have | [T(]].
Note that if we view A as the measure μ4 on Q then the measure (T(A) on U is the honest-to- goodness pushforward measure μad o 11 The above result follows easily.
Let's summarize where we are so far. We observe some relations between pairs of multisets over Ω. We also assume there is multiset transformation T from l to some "latent" universe W4, and that observed relations are explained by relations that hold in Ll" In general, we wish to understand the structure of T, order predict similar relations for unobserved pairs of multisets. We may also hope that in the process we learn something about the structure of Z and that in general this learning process is feasible due to 2 being much smaller simpler than Ω. For example, we might assume that T' is in fact pushforward transformation induced by an unobserved labeling of the elements in Q by elements in 4 [
However, there is a problem with this setup: it is unlikely that for two multisets A E Ω and B E Ω*, we have either T(A) S T(B) or T(B) S T(A). However, there are richer relations that can exist
'It is worth noting that there do exist examples where each object in Qt does not obviously have an associated tag in [&], such as the RCVI dataset Lewis et (2004), which consists of documents each of which can he thought of multiset of words together with collections of categories for each document.
4

---

Under review as a conference paper at ICLR 2020
between two multisets than just containment, and which can be observed for any such pair. For example, regardless whether either of ((A) or T(B) is a subset of the other, we can ask about how much they overlap - i.. the size of either their intersection (A) n (,),, of their symmetric difference,
Note that if we also know their sizes [T(A) and [T(B)), then we can contains the other (Theorem 3.2.6). This follows directly from the following: (1) that the size of the symmetric difference gives rise to a (yseudo-)metric on multisets, which can then be used express a "disk embedding" inequality (Suzuki al. (019) relating containment to cardinalities (Proposition 3.2.4); and (2), the sizes of the symmetric difference and intersection are related via the sizes of the multisets themselves (Lemma(3.2.5) [.2.5). See Appendices(landdDDooe proofs; note also that for each of the following three statements, we assume A and B are multisets over the same universe.
know whether
Proposition 3.2.4 For any two multisets A and B, A S B if and only |f|ABII S [B] [A].
Lemma 3.2.5 For any two multisets A and B, |AAB| |A] [B| 2|An Bl.
Theorem 3.2.6 Given A and B (whose cardinalities we can calculate), it suffices to know either [An B| or AAB) to conclude whether A C B and whether B S A.
Theorem 3.2.6 thus motivates the use of either (T(A) n T(B) or [T(A)AT(B) to learn about containment, in the case where 7 preserves cardinalities. In particular, we then know the cardinalities [T(A) = AA| and [T] = [B]. and thus either (T) n T(B) or [T(A)AT(B)) is sufficient to deduce the containment relations between T (A) and T(B). We therefore that can training signal more readily available than binary yes-no containment
measurements of overlap between multisets to still learn to predict containment relations. Thus, the problem will be solving here is learning to predict either [T(A)AT(BB) [B] or (T(A) n T(B) from examples. Importantly, the error on these predictions will indicate how well we learned capture our "flexible" notion of containment.
3.3 THE LEARNING TASK
Formally, our learning task will therefore be as follows.
There exists universe Ω which we assume for practical purposes can be embedded in Rd for some known d. There is also some latent universe I = [k] together with an unknown multiset transformation T' 52* Ur We will assume that T preserves cardinalities
in practice this means either that T is a pushfoward transformation induced by some t: 52 + l4 or an "expectation transformation," " which we define in Section 4.2 We then observe samples (A, B) from training distribution D over pairs of multisets in f For practical reasons, our sampled multisets will whole- number multiplicities. For each such pair, we also observe the overlap via either [ T(A) or IT(A) n T(B).. Which of these is used is fixed beforehand for the entire task, and we assume this choice known. (We test both choices in our experiments.) Our assumption that T preserves cardinality is important, because together with these observations, it allows us to conclude whether T(A) is subset of TBB). We then pick hypothesis target universe ú [7:], and let & = k if k known. (Experimentally. we examine the cases & < k and i k.) Finally, our goal is learn model i.e. a map f. S2" + -i- that minimizes squared error the predicted overlaps. That is, we learn 7 order to minimize the appropriate choice of the following two losses:
( (((A)T(()))
-T(A)T((1)))) 27
L^ EARAA
((T(A)) -TTA) 27
Cn EABBD
MODEL DEFINITION
Having formulated our learning task, we now define our learnable model 7. Ω + ûr In order to do so, we want our model to give "representations" of the multisets in 2t in the most common machine-lcarning sense - i.c. vectors in some Euclidean space. We begin this section by defining how we obtain and use such representations, and then conclude by defining our model î itself that gives us these representations.
5

---

Under review as a conference paper at ICLR 2020
4.1 REPRESENTATION MULTISETS
Definition 4.1.1 For any universe Ú, a d-dimensional representation function is map v ú - R For multiset S E U", we call (S) the representation of S.
In general, we our representations of multisets be "useful," " in the sense that we can use them to perform common operations - such as those in Definition 3.1.3 More importantly for our task, need to be able calculate the size of either the symmetric difference the intersection of two multisets. Our choice of target universe 27 [k] gives us such representation function.
Definition 4.1.2 Let ú be the finite universe [k]. The natural representation function Ve it - IR is the map S + mms
This should an intuitive concept. For example, the natural representation function for classical sets gives the familiar indicator vector representation 1 (S) [lies..... jgs) Furthermore, we get "usefullness" of these representations for free, since all operations defined via membership functions (e.g. those in Definition 3.1.3) can be performed coordinate- wise. Furthermore, the cardinality of multiset S E Lt is given by thus sum of the entries in ( Together with the non-negativity of membership functions, this gives us the following. (As these two results are essentially immediate, omit their proofs.)
Lemma 4.1.3 For any multiset S E [k]]. |S| = 1 (S)]I1.
Proposition 4.1.4 For any two multisets R and S over [ic], we have |RAS| [1 (s(())l and R 5| min ( (R), V (S(),, where the minimum is applied coordinate-wice
We thus use the natural representation function on Li to train our model. We note that Proposition 4.1.4 could provide reason to prefer the size of the symmetric difference over the size of the intersection as the training signal. The reasoning is that Ei-distance has gradient which depends on both the representations (R) and V (S) in each coordinate (except at O), while the coordinate-wise minimum can only depend on one the representations in each coordinate. We test this idea in our experiments.
4.2 THE LEARNABLE MODEL.
Recall that the unobserved multiset transformation T S2" 44" preserves cardinalities. In particular, suppose for the purpose of exposition that 7' is the pushforward transformation induced by some labeling t Ω > U. We both want hypothesis class of models 7 to contain all such pushforward multiset transformations, and potentially be restricted those T which preserve cardinalities. Unfortunately. we cannot directly learn over the set of all pushforward transformations, as this is equivalent learning the correct discrete labeling Ω [k:]. which is both hard and non- differentiable problem Instead, we take probabilistic approach.
Definition 4.2.1 For two universes and U, a probabilistic universe transformation a map 8: + (i)), where ((U) is the space of probability measures on ú.
As we will see, probabilistic universe transformations to [ have the advantage of being smoothly parametrizable. In analogy the pushforward multiset transformation induced by l Ω U. we leverage our probabilistic transformation above to define a different kind of induced multiset transformation.
Definition 4.2.2 Let E S - ((u)) be a probabilistic universe transformation. The expectation multiset transformation Ω + ún is defined to be the map A + Ep-((aot-1\(P)
In fact, only about learning such labeling up to permutation (as permutations of labels cannot affect containment relations), but this still hard problem.

---

Under review as a conference paper at ICLR 2020
We first note that L is well defined, in the sense that [(A) is always valid measure on U. This can easily be seen by re- re-writing the expression as follows:
S (d( ((x)) dua(a).
1p-(uaot-11PP1
{(x)
L(A) has a natural interpretation, as the expected multiset obtained by sampling an element of U for each x E A according its corresponding distribution {(xr) (with contribution weighted by m (x)))
Additionally, we have the desirable property that L. preserves cardinalities (see Appendix B for proof).
Theorem 4.2.3 Any expectation multiset transformation Q2 ú preserves cardinalities, i.e. for any A E 52", |A| = [(A]]
We will thus let our learned model /: Ω2 - Li" be an expectation transformation L induced by some probabilistic universe transformation f. Note that expect to be able to learn not only in the case where the unknown 7 is pushforward transformation, but in fact when T itself is some expectation transformation (although we do test the latter experimentally.)
4.3 PUTTING IT ALL TOGETHER
The outstanding question is: how do parametrize representations V (A)) for any given A E ? By the definition of the natural representation function V we can write the i-th component of the representation of L (AA)
((()))(())) dua(z)= (
(1) mmcl)) dpa(x)= = 1 Ve(((x)), dua(.),
(L(a)(1) -
where the last two equalities come from viewing ((x) as a general measure and thus multiset on i. Now, assuming that in fact one of the multisets sampled from our training distribution D, we know that A has thus in fact for any multiset we are trying represent.) The above can then by simply written as V (I(A)); ExEA V (f(x)), where each x occurs in the sum mA(x) times. More simply, we have Vr (2(L(A)) L (E(())).
multiplicities. (This will also be the case during evaluation, and
Since each ((x) is just a distribution over & elements, suffices to learn a map from Ω to the probability simplex in & - the non-negative vectors whose components sum to 1. Recalling that we assumed our input universe 52 consists of vectors in RRd, we pick favorite dbjuut-featurization network Rd + R We then guarantee than we obtain a point in the probability simplex by taking ((a) to [[(((())\ll where f : IR + R is function applied component component-wise, wise. For differentiability. we choose the softplus function fz) log(1 + e²). Our complete model thus the representation f(o(a)) Our losses, in terms of these representations, are
f(p(a))
V (A) = E.EA [l(()(a)
L^ EA (I) ((B)]) - (T(A)AT(())))
Cn EABBaD
EXPERIMENTS
We begin here with an overview what want to test about model. In Section 5.1 move to describe our training and evaluation procedures. The experimental results themselves follow.
A clear question to seek the answer to empirically is whether the size of the symmetric difference or of the intersection works better in practice. (Recall that the symmetric difference may have more informative gradients, possibly leading better learning and performance.) We thus compare these two approaches, both in terms the error on the respective tasks themselves, and terms of the on predicting containment. More generally, the theory motivating model suggest that there
7

---

Under review as a conference paper at ICLR 2020
is a delicate balance in the properties that make the model well-posed We tackle this idea from two directions.
M((a)) First, we ask how important is the precise definition of our model, (AA = EnEA I(fd(a))i An obvious baseline to compare against (A) = E.res d(x), which should help us answer the question of how important it is that each object is mapped to a point in the probability simplex. Looking at this formulation, an immediate connection one might make is to the DeepSets model of Zaheer et al. (2017): V (A) pl PI(E ((2)) for some learnable function P1. The authors prove this model can learn any permutation invariant function - e.g. the size of the intersection or symmetric difference of two multisets. We thus use both the models above as baselines in all our experiments, calling the former "unrestricted multisets" and the latter "DeepSets"
The second category of question we ask here is whether we gain anything from our construction of the multiset operations on representations. We tackle this question replacing the terms (A) (B)II and min { v (AA) (B) in our losses with P2( (c) for learnable function p2. The intuition here is that this new prediction is in fact a second DeepSets model trying to learn of our prediction functions where we choose DeepSets because both intersection and symmetric difference are permutation invariant (i.e. commutative). This setting will be called the "learned operation" setting. We further test whether our parametrizations of the multisets operations are somehow intrisically good via scheme of "cross-wiring" them using one for task where we should use the other on which we elaborate Section 5.4
Finally, we will also examine the learned representations ((1:) of elements x E S
5.1 TRAINING AND EVALUATION PROCEDURES
We use MNIST (LeCun 1998) our dataset. The training set consists of 60,000 handwritten images of digits, and the test set of 10,000.
We train all the models on 3 x 10a training pairs of multisets (A, B) Ω. At each iteration of training,
both A and B are generated randomly, as follows. First a whole-number cardinality is uniformly sampled in some chosen range- in experiments ensure that the models aren't 't just learning from comparing pairs of singletons)) Once the cardinality Z then chosen uniformly at random (with replacement)
use [2, 5]. (We exclude singleton sets to
chosen, then that number of images from the training set. The multiset representation is calculated as usual, via one of the representation functions V/ defined above, and the predicted cardinality of the symmetric difference or intersection is then calculated using these representations. The value to be predicted is calculated directly from the labels of the images the multisets - c.g. if A two images of ones, and 1 is one and a three, the target value will be 1 for intersection, and 2 for symmetric difference. The squared error is minimized using Adam (Kingma and Ba 2015), with the default parameters $1 = 0.9 and 82 = 0.999, and a learning rate of 5 x 10 -, The learning rate was chosen by logarithmic grid search from 1 down to 5 x 10-6, training on up to 1 pairs during the search. (All models performed best with the chosen learning rate- chose to train the models for 3 x 10 iterations, finding that almost all of the models converged by this point.
at least no worse than any of the other learning rates.) Given this learning rate, we
Evaluation is performed similarly to training, with the addition of multiset sizes uniform on [2, 20), and with images sampled from the test set. Importantly, this means that the none of the images seen during training appear during evaluation. Each model is evaluated on 3 x 10 such multiset pairs, and unless otherwise stated we let 6 Ω + R
(that is, h = k = 10).
For the object featurizing function é, we use a variant of the LeNet-5 neural network (LeCun) 1998). Specifically, we adopt the same architecture as used by Ilse et al. (Ise et al. 2018). (See Appendix for network architectures, including those used for P1 and p2.)
'In particular, the restriction of the object representation to the probability simplex is important for our sypecaaioo-rransfomatoooooo model be well-defined and cardinality-
map between multisets; furthermore, the guarantee that the learned representations v (A) and v(B (B) for any pair (A, B) preserve cardinalities is theoretically key both for our being able to use |A] and [B (in addition to our observed symmetric differences or intersections) in order to deduce containment relations, as is the way in which we parametrize operations multisets via operations on their representation. There are many possible directions of inquiry; we break apart the empirical question into two rough categories.
8

---

Under review as a conference paper at ICLR 2020
5.2 CARDINALITY PREDICTION
We examine the performance of six kinds of models - multisets, unrestricted multisets, and DeepSets, each with or without learned multiset operations on the tasks of predicting cardinality, either of the symmetric difference of the intersection. We will refer here to Tables (symmetric difference) and [ (intersection), which report the mean absolute errors of the predictions. Within each of the tables, two patterns are immediately clear. First, a amount portion of the prediction error may be explained by whether the multiset operations are learned, or taken to be the poorrtically-motivae parametrizations; the models with learned operations exhibit more than twice the prediction error. definitions, it does not
While this shows there a benefit to using our mecortiially-mooivann necessarily mean that our definitions are intrinsically or uniquely well-suited for the task. We will revisit this point later.
The second salient pattern is that move away from the expectation tranonontttaoootitooooooo model (which we simply call "multisets" in our tables), first to the unrestricted multiset model, and then to DeepSets, there is a rapid decrease in performance (in some cases almost ten-fold). This suggests that the theory behind our model is indeed useful.
Finally, when we compare across the two tables that is, compare cardinality prediction for symmetric difference and for intersection - we observe a surprisingly large gap in error. The error on intersection size prediction is consistently about twice small as on the other task. is worth noting that if anything, we expected an opposite effect. This gap is intriguing, and we believe that it should be explored further.
5.3 CONTAINMENT PREDICTION
We now compare the same models above on what is perhaps the more important task: prediction whether there exists a containment relation between (AA) and T(B) for some A and B. In particular, for any such pair, we predict whether T(A) = T(B), (A) ç T(B), T(B) Ç. T(A), or there is containment relation (i.e. we treat this a classification problem). We perform this prediction by relying of Theorem 3.2.6 (and the assumptions on our representations). In particular, for any pair A and B, we predict the containment relation implied by Proposition [3.2.4] where we take the cardinality of the symmetric difference predicted by our model. (If the model predicts intersection, we just use Lemma 3.2.5 to go from one to the other.) Note that in this experiment we sample pairs A and B such that the probability of each kind of containment is essentially uniform. Referring to Tables and we observe almost exactly the same patters as above with over 96% accuracy achieved by both multiset models. The one difference is that for the unnormalized model and the DeepSets model (with non-learned operations), the version of the models trained on the intersection task perform noticeably worse than the corresponding models trained symmetric difference. Furthermore, on all other models, the performances are comparable. This further complicates the picture from above, as it suggests that while intersection may somehow be easier learn predict the cardinality of, perhaps the task itself is a worse way to capture containment relations.
5.4 (CROSS-WIRING OPERATIONS
Motivated by our observation that models less closely aligned with our theory seems to perform worse, we devise small test to see whether our symmetric difference and intersection cardinality operations are somehow intrinsic. To do so, we perform two experiments. First, we train our regular expectation- transformation- based multiset model to predict symmetric difference cardinality, but where it's prediction function given by min { V (A), V (B)). Similarly, in the second experiment, we train the model to predict intersection cardinality, but where the prediction function is || (A) (B)Il, We observe that the former model achieves and mcan-absolute error of 2.3710 10 on the test set, while the
second achieves ones of 0.9929. There values significantly higher than the errors achieved with the "correct" prediction functions, suggesting that there indeed a sense in which these are the "right" functions.
5.5 EXAMINING LEARNED REPRESENTATIONS
We finally turn to examining the rojjectrepreseentttionn learned by our model. As one would expect, the learned representations of objects approximate the standard basis vectors (as shown in Figure
9

---

Under review as a conference paper at ICLR 2020
D for n 3). This suggests our expectation- qupectation-tranffomaatio transformation model is learning appropriate point-mass probabilities corresponding to each object's ' label in U.
We also examine the case À < k, which may occur when we don't know the true size of U. Here, the "pinched" nature of the restricted representations may be undesirable (Figure 2a). This problem, of course, gets worse with the discrepancy between number of objects and dimension (Figure (2)). On the other hand, the unrestricted multiset model is able learn more balanced-fooking clusters. However, the clusters for d = n appear slightly less well-separated (Figures and 4. The DeepSets model didn't learn interpretable representations (Figure [4c). Furthermore, when we measure the accuracy of the regular multiset model on the containment prediction task above of each of the models, obtain good results even when à is "too small." In particular, fixing & 5: k = 5 we obtain accuracy of 0.9586, and gives 0.9045. This suggest that the representations learned are fact robust to small discrepancies in dimension.
0.8
0.2
0.4
0.0
2.0
02
Figure 1: Three-dimensional representations of test-set MNIST images generated by the restricted multiset model trained on multisets of sizes E [2, 5); the model is trained on images of zeros, ones, twos.
CONCLUSION
We propose novel task: predicting the size of either the symmetric difference of the intersection between pairs of multisets. We motivate this construction via measure-theoretic notion of "flexible containment." We demonstrate the utility of this idea, developing theoretically-mottive that given only the sizes of symmetric differences between pairs of multisets, learns representations of such multisets and their elements. These representations allow us to predict containment relations with extremely high accuracy. Our model learns to map each type of object thus essentially performing semi-supervised clustering. One interesting area for future theoretical work is understanding related problem: clustering n objects given multiset difference sizes. As that
model
standard basis vector,
first step, we show in Appendix H the clusters. We would also be curious to see if one can learn the latent multiset space U.
specific multiset comparisons are sufficient to recover
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ben Athiwaratkun and Andrew Wilson. Multimodal word distributions, In Association for Computa- tional Linguistics (ACI.), 2017.
Ben Athiwaratkun and Andrew Gordon Wilson. On modeling hicrarchical data via probabilistic order embeddings. In International Conference on Learning Representations, 2018. URL https
Wayne D. Blizard. Real-valued multisets and fuzzy sets. Fuzzy Sets and Systems, 33(1):77 97,
1989.
Jaume Casasnovas and Gaspar Mayor. Discrete t-norms and operations on extended multisets. Fuzzy Sets and Systems, 159:1 167-117777 2008.
Octavian Ganca, Gary Becigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
2018.
Jason Hartford, Devon R Graham, Kevin Leyton-Browe and Siamak Ravanbakhsh. Deep models of interactions across sets. arXiv preprint 180:::2880002777 2018.
Maximilian Ilse, Jakub M. Tomezak, and Max Welling. Attention-based deep multiple instance learning. In Proceedings of the 35th International Conference on Machine Learning (ICMI., 2018.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Alice Lai and Julia Hockenmaier. Learning to predict denotational probabilities for modeling entailment. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics (EACL). 2017.
Yann LeCun. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, 1998.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- former: A framework for attention- baasdd permutation-intee invarrann neural networks. In International Conference on Machine Learning (ICML), 2019.
David D. Lewis, Yiming Yang, Tony G. Rose, and Fan Li. Revl: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361-397, 2004.
Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smoothing the ge- ometry of probabilistic box embeddings. In International Conference on Learning Representations, 2019. URL
net/
Sadaaki Miyamoto. Fuzzy multisets and their generalizations. In Proceedings of the Workshop on Multisel Processing: Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of View, Workshop on Membrune Computing (WMP), 2000.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. In Advances Neural Information Processing Systems 30 (NeurIPS), 2017.
Malte Probst. The set autoencoder: 2018.
Unsupervised representation learning for sets. OpenReview,
Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Siamak Ravanbakhsh, Junier B Oliva, Sebastian Fromenteau, Layne Price, Shirley Ho, Jeff G Schneider, and Barnaáss Póezos. Estimating cosmological parameters from the dark matter distribution. In International Conference Machine Learning (ICML), 2016.

---

Under review as a conference paper at ICLR 2020
Gactano Rossiello, Alfio Gliozzo, Robert Farrell, Nicolas R Fauceglia, and Michael Glass. Learning relational representations by analogy using hierarchical siamese networks. In North American Chapter of the Association for Computational Linguisties: Human Language Technologies (NAACL- HITT), 2019.
Konstantinos Skianis, Giannis Nikolentzos, Stratis Limnios, and Michalis Vazirgiannis. Rep the set: Neural networks for learning set representations. ArXiv, 2019.
Ryota Suzuki, Ryusuke Takahama, and Shun Onoda. Hyperbolic disk embeddings for directed acyclic graphs, In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing high-dimensional data using t-sne. Journal of Machine Learning Research, 2008.
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. In International Conference on Learning Representations (ICLR), 2015.
Patrick Verga, Arvind Neelakantan, and Andrew McCallum. Generalizing to unseen entities and entity pairs with row-less universal schema. In European Chapter of the Association for Computational Linguistics (EACL), pages 613 122, 2017.
Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. In International Conference on Learning Representations (ICLR), 2015.
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), 2018.
Lotf A. Zadeh. Fuzzy sets. Information and Control, 8(3):338 353, 1965.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems 30 (NeurIPS), 2017.
A MULTISET OPERATIONS
Here provide through examples intuitive understanding of the binary multiset operations from Definition 3.1.3
Consider the two (non-fuzzy) multisets, A = (1,1, and B (1,1,,,,,33 should contain all their elements in common: AnB = 11, That is, we take the minimum number of times each element appears in either A B, and that is the number of times the element appears in A n B. This straightforwardly gives us MAnB (x)) = minfm (z)) m (z)))
Their intersection
Following similar reasoning, we can convince ourselves that multiset union should be defined as ( = max mmxx(m_)) (z), mz(x)] It is important to differentiate this from "multiset addition," which simply combines two multisets directly: A + 11 1, 2,2, for our example above, and in general m = m + m3(x).
Multiset difference is little harder define. The main problem is that we cannot rely on notion of "complement" for multisets. Instead, let again try to reason by example. For our example multisets above, we have A
21, To arrive at this result, we remove from each copy of an element which also appears in B. Note that if B had more of certain element than A. that element would not appear in the final result. In other words, we are performing a subtraction counts which is "glued" to minimum value of zero. That is, MA (x) max x mz(x), 0}. We can further convince ourselves of the correctness of this expression by noting that we recover the identity A (A \ B) An B.
A
Finally, symmetric multiset difference can be defined using our expression for multiset difference. combined with either multiset addition or union. In particular, note that AAB (A) +B) ())
12

---

Under review as a conference paper at ICLR 2020
(A), U) A) addition and union both work because (A \ B) and (B \ 4) are necessarily disjoint. This gives us:
mA^B(() = max(ma(x) (x)) max(mn(1) x (x)()) (1m0))mm())) mn(
(The equation still holds if we replace the addition with maximum.)
B FUZZY SETS
fuzzy set A over a universe given by a function my Ω - [0, 1]. Intuitively, ma maps each Ω to "how much of member" is of A, scale from 0 to With this simple idea, fuzzy set operations can be defined. This is traditionally done by leveraging element-wise fuzzy logical operations, which we define below.
Definition B.0.1 A t-norm is function T [0, 1|2 + [0, 1], satisfying the following properties:
Commutativity: ((a,b) a(b,a)
Monotonicity: !fa and S d, then T(a, S d(e,d)
Associativity: T(a, [(,, c)) = (T(,a))).
1 the identity: T(a, 1) =
T-norms generalize the notion of conjunction. Note that the above conditions imply that for any a. T(a, 0) = 0, and that T(1, = 1. These two observations show that t-norms are "compatible" with classical, non-fuzzy logic- where we identify with "false" and with "true." " The standard t-norm is T(a, b) min(a, [a,b], 6).
Definition B.0.2 A strong negator is a strictly monotonic, funntionng, [0, + [0, such that n0) n(1)= and n(n(x=) = x.
Unsurprisingly, strong negators generalize logical negation. The standard strong negator is n(x))
1 x.
Definition B.0.3 An S-norm (also called a t-conorm) is a function with the same properties as t-norm, except that the identity element is 0.
S-norms generalize disjunction. For every t-norm (and given negator), we can define a comple- mentary s-norm: S(a, b) naT (a)),, n(b))). n()))) This is generalization of De Morgan's laws. The standard s-norm, complementary to the min t-norm, is S(a, b) = max (a, b}.
The membership function for the intersection of two fuzzy sets A and B is naturally defined as (Ana = (T) (x)) for a t-norm T. Similarly, the complement of fuzzy set is given by (g(x) = (x)) for strong negator n, and the union of two fuzzy
is given by ( (() Mg (x)) for an s-norm S. Usually, we want T and to be complementary with respect to n. Then, we can generalize all the usual set operations fuzzy sets by combining the three basic operations above.
C PROOF OF PROPOSITION 3.2.4
We show that for any two multisets A and B over the same universe Ω A C B and only |AAB| B - |A]. In fact, noting that it is always the that JAAB > |B| - ||A] (which will not prove but is easy to show), the following proof shows this holds with equality.
Proof. Let À be the dominating measure with respect to which the cardinalities are taken.
We first show the forward direction. Suppose A C B, that is, for every x E Ω, we have mA(x) S mz(r). The result follows directly (with equality):
MAAB(T) dx(x)= - (B(()) mA(x) dX(x)= = mz(x) dx(x) / ma(x) dd(x)).
13

---

Under review as a conference paper at ICLR 2020
For the converse direction, suppose the other hand that |AAB| < B - -AA. Now suppose for the sake of contradiction that for some x" E Ω. we have ma(x") > my (z*). Then -g(=") < Im (x*) m. m (z But this implies that
B - |A| / ma(a) ma(x) d2(z) mB(L) mA(ω) dd(x) JAAB).
which is contradiction.
D PROOF OF LEMMA 3.2.5
We show that for any multisets A and B over the same universe 92, |AAB| -A]+
Proof. Let be the dominating measure with respect to which the cardinalities are taken. Let BA Ω be the elements
52 on which mx(x) my p and similarly let Ω2 C Ω be the elements z E S on which mg > ma(x). Finally let Gg be those elements æ E Q for which ma(2)= (z) Note that Q2 S2p, and Go are disjoint, and that their union is the entire universe Ω. We can then write the cardinality of the intersection of A and B as
/ mAnB(T)) dA(x) = /
min (im mp( dx(x)
R
mB(²) d)(x)+ / ma(œ) dl(x) S.o ma(x) dx(x).
We then observe that [A| + [B] 2/A n B| is
MA(F) d)(x) + / ma(x) dA(x) + / ma(ω) dA(x)
.nn
2o
+ mB(x) dx(x)= + / mB(a) dd(x)= + I mB(x) dd(x)
Ra
R2
Go
ma(x) dx(x) ma(x) dx(x) - / ma(x) dD(x).
-2 Jan
Su
Simplifying, we obtain
[ mA(z) - (2(x) (T)()) d)(x)+ + [ J mB(#) - mA dX(x)= = S/ (ma()) - mB(x)) d)(z).
Ra
But this is exactly the cardinality of the symmetric difference |AAB)
E PROOF OF THEOREM 4.2.3
We will show that for any probabilistic universe transformation e Ω A(l), the induced expectation transformation L S2 - Lt" preserves cardinalities. That is, |A| = [[(A]]. (For easy of notation, we write WI here rather than the l/ used in statement of the result in the main text.)
Proof. Recall that since L(A) is a multiset and thus a measure, we have [((A) (L(A))()).
Expanding L(A), we obtain
( (((=)) dpa(o)) (2)) (((=))(() dua(x)= dda(=)= PA |A],
where the second equality holds because {(x) is probability measure over 24
F NETWORK ARCHITECTURES
Given input images with e channels, and an output dimension d, the function ø is parametrized by the network:
14

---

Under review as a conference paper at ICLR 2020
Table Mean absolute errors in symmetric difference size prediction on MNIST
sizes [2, 5]
sizes
[2, 10]
sizes
[2, (2,20)
Multisets Multisets, learned op.
0.0722
0.1264
0.2061
1.1748
1.7159
4.0468
Unrest. multisets
0,5614
0.7693
1.1813
Unrest. multisets, learned op,
1.1402
1.7317
4.4426
DeepSets
0.6630 1.2152
1.4097
4.0330
DeepSets, learned op.
1.9386
5.2831
Table 2: Mean absolute errors in intersection size prediction on MNIST
sizes E [2, 5]
sizes [2, 10)
sizes [2, 20)
Multisets Multisets, learned op.
0.0375
0.0648
0.1092
0.6021
0.8583
2.3487
Unrest. multisets
0.30644
0.4211
0.5708
Unrest. multisets, learned op,
0.6122
0.8750
2.5015
DeepSets
0.3583
0.6763
2.4277
DeepSets, learned op.
0.5258
0.8420
2.6967
1. A wwo-dimensional convolution layer with input channels, 20 output channels, kernel size
5, and stride (no padding)
2. A ReLU activation
3. A two-dimensional max-pooling layer with kernel size 2 and stride 2
4. A two-dimensional convolution layer with 20 input channels, 50 output channels, kernel size 5, and stride (no padding)
5. A ReLU activation
6. A two-dimensional max-pooling layer with kernel size 2 and stride 2
7. A fully-connected linear layer with output size d (the input size is determined by e)
For the DeepSets model, we used for Pi the architecture:
1. A fully-connected linear layer with input size d and output size 100
2. A hyperbolic tangent activation
3. A fully-connected linear layer with input and output size 100
For p2 used:
1. A fully-connected linear layer with input and output size 100
2. A hyperbolic tangent activation
3. A fully-connected linear layer with input size 100 and output size
G ADDITIONAL FIGURES
15

---

Under review as a conference paper at ICLR 2020
Table Accuracy on containment prediction for models trained on symmetric difference on MNIST
sizes [2, 5]
Multisets
0,9653
Multisets, learned op.
0.2576
Unrest. multisets
0,6332
Unrest. multisets, learned op,
0.2679
DeepSets
0.6299
DeepSets, learned op.
0.2487
Table 4: Accuracy on containment prediction for models trained on intersection on MNIST
sizes E [2, 5]
Multisets
0.9633
Multisets, learned op.
0.2494
Unrest. multisets
0,4916
Unrest. multisets, learned op,
0,2819
DeepSets
0,5018
DeepSets, learned op.
0.3389
0.6
0.0
0.5
0.0
022
0,2
0.4
0.8
0.6
02
1.0
1.8
1.0
0.8
(b) Model trained zeros, twos, threes, and fours.
(a) Model trained on zeros, ones, twos, and threes.
Figure 2: Three-dimensionn representations of test-set MNIST images generated by the restricted multiset model trained on multisets of sizes E [2, 5]. Note that in (b) the representations of twos and threes are essentially inseparable.
H CLUSTERING OBJECTS GIVEN n 11 SYMMETRIC SET DIFFERENCE SIZES
We are interested in the following problem. Suppose we have set of n objects 24 each of which belongs to one of & clusters, C1...., . Cg. Let M 2d [1.....k]* be the function which takes any subset of U4 and gives the multiset of cluster labels represented in that subset. We are given oracle access to the function A 24 24 N which gives the size of the symmetric set difference between the cluster-label multisets: A(A, B) M (A) (B)). How many queries are required to determine the clusters Ct....,C Cs (up to permutation)?
We show that the clusters can be determined with this is as a training data problem, rather than an oracle querying problem; we show n - training examples
specific queries. (Another way to think of
be sufficient.) We do this in two steps. The step lets identify & disjoint subsets of U such that no two of these subsets contain objects from the same cluster. The second step confirms that these subsets in fact the clusters CI,..., Ck.
16

---

Under review as a conference paper at ICLR 2020
C20
(a) Model trained on zeros, (b) Model trained on zeros, ones, (c) Model trained on zeros, ones, and twos.
twos, and threes.
twos, threes, and fours.
Figure 3: Three-dimensional representations of test-set MNIST images generated by the unrestricted multiset model trained on multisets of sizes []. Note that in (c), the clusters essentially form tetrahedron, with one of the vertices being the combination of twos and threes.
-5
-3
180
-00
(a) Multiset model, restricted Φ. (b) Multiset model, unrestricted ø. (c) Pure DeepSets model.
Figure 4: Two dimensional TSNE (van der Maaten and Hinton, 2008 "projections" of the ten-
dimensional representations test-set MNIST images generated by the models; the models were trained on multisets of sizes [2.5].
The first step consists of logarithmically "splitting" U. The very first query in this step is (U!+/?) C, k/21 C.) which tells us that [[/23] C, and Uh=11/21 C2 are disjoint in terms of represented clusters. We proceed recursively, each query "splitting" the sets in half (in terms of which clusters they contain). The number of such steps required is - (which the number of internal nodes in balanced binary search tree for & objects). We'll call the resulting disjoint sets ČI...., Cx (since we technically don't yet know they correspond to the
clusters).
For the second step, we must verify that the objects in each of our sets resulting from step one all belong to the same cluster. This can be done by ordering the objects within each set, and comparing each consecutive pair as singletons. For each of our sets C₁ thus make |C_l 1 such queries.
Across all such sets, we thus make Σ |Cal - = n - k queries.
So, the total number of queries made is (A: 1) (n k) 1.
17


Reviews:
[{"review_id": "r1gycv53Kr", "reviewer": "AnonReviewer2", "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": "This paper presents a framework for learning representations of multisets.  The approach is built on top of the DeepSets (Zaheer et al., 2017) model, which already is capable of learning representations of multisets, with a new objective of predicting the size of symmetric differences between two multisets, plus a small change in the implementation of the DeepSets model by restricting the per-element module to output a point in the probability simplex.\n\nI liked the background on fuzzy sets and the development of fuzzy multisets and different operations on these multisets.  The definitions and arguments are quite clear and helpful.  One small suggestion for page 4 is that I can understand why the formulation is the only sensible choice for multisets with desired properties, but a claim like this deserves a proper proof.\n\nModel-wise the paper made two contributions for learning representations for multisets as mentioned above: (1) proposed the symmetric difference prediction as a task for learning representations, the argument for this task is that predicting symmetric difference implicitly encourages the model to learn about containment; (2) a slight change in the DeepSets model architecture where the outer rho function is identity and the inner phi function has to output a point in the simplex.\n\nI found these technical contributions to be a bit small.  In addition to this, the paper only presents results on MNIST in a toyish setting, this makes me feel the paper may be more suited for publication in a workshop (idea is interesting, small scale experiments to illustrate the insights, but not complete enough to be published at a conference).\n\nRegarding contribution (1), I can see why predicting symmetric difference makes sense as argued in the paper, but I’m not convinced that this is better than other alternatives.  In order to show that this is a reasonable approach for learning representations, some results that compare this with other possible learning objectives would be necessary.  But I don’t see any such results in this paper.\n\nRegarding contribution (2), I feel the restriction of the phi function to output points in simplex is not very well motivated and confusing in the first read.  Again I can understand why we may want to do this but don’t see why we need to do this.  I’m also concerned that such an architecture may only be good for the task of predicting symmetric difference as it is customized for this task.  Figure 3 shows that an unrestricted model seems to learn better representations despite a worse symmetric difference prediction error, which again confirms the concern.\n\nAnother thing about the experiment setup: the second baseline, labeled “DeepSets” in Table 1 actually changed two things compared to the proposed approach: (1) changing the psi function and (2) also changed the symmetric difference function.  It would be good to isolate the contribution of the two.\n\nOverall I feel this paper is not yet ready to be published at ICLR.", "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 carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SklYt2LaYH", "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": "Authors of this paper propose train a model by predicting the size of the symmetric difference between pairs of multisets. With the motivation from fuzzy set theory, both the multiset representation and predicting symmetric difference sizes given these representations are formulated.\n\nIn Section 3.3, authors stated that theorem 3.3.1 provides the compelling reason to use symmetric difference over intersection or non-symmetric difference. The statement seems not so straightforward, and how it works as the learning criterion for semi-supervised clustering in the experiments. \n\nFor the relaxation used for the normalization of \\phi(a), does this restrict the feasible space of the standard basis vectors? In Section 4.3, authors claimed that in the case of n=3, 98.9% classification accuracy can be obtained by simply picking the maximum valued coordinate of the representation of each object. A systematic comparison in terms of the classification accuracy is important for evaluating the semi-supervised clustering problem. \n\nIn Section 4.2, authors directly model the mean absolute errors in symmetric difference size prediction. It might be more interesting to see what real problems the proposed model can naturally be applied.", "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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1x15XL7Yr", "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": "This paper proposes a new task of learning from sets, predicting the size of the symmetric difference between multisets, and gives a new method to solve the task based on the fuzzy set theory.\nAlthough the topic of learning from sets is relevant and using the fuzzy set theory for the task is interesting, I have the following concerns regarding with the clarity, significance, and evaluation.\n\n- Motivation is not clearly presented. The new task of predicting the size of the symmetric difference between multisets is proposed, while its application is not well discussed.\n    Although Theorem 1 characterizes the task using the subset inclusion relationship, its relevance to applications is still not clear.\n- The problem to be solved is not mathematically formulated. In particular, what are input and output?\n- More detailed explanation of the data preparation would be required.\n    How to transform images to pairs of multisets?\n    Is the label (number) of each is used as an element of a multiset?\n- For the second comparison partner, why is \\Delta(A, B) defined as \\rho_2(\\Psi(A) + \\Psi(B))?\n    For fair comparison, this function should be the same with the proposed method, that is, ||\\Psi(A) - \\Psi(B)||_1 for the learned \\Psi by DeepSets.\n- In experiments, one of the most straightforward ways is to first predict labels for each image, followed by computing the symmetric difference from the predicted labels. Comparison with such baseline should be performed.\n\nMinor comments:\n- P.1, L.1 of the second paragraph: \"The the\" -> \"The\"\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers appreciated the problem to learn a multiset representation, two reviewers found the technical contribution to be minor, as well as limited experiments. The rebuttal and revision addressed concerns about the motivation of the approach, but the experimental issues remain. The paper would likely substantially improve with additional experiments.
Decision: Reject