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. Tasks for which the input is an unordered collection, i.e. a set, are ubiquitous and include multipleinstance learning Ilse et al. (2018) , point-cloud classification Zaheer et al. (2017) ; Qi et al. (2017) , estimating cosmological parameters Zaheer et al. (2017) ; Ravanbakhsh et al. (2016) , collaborative filtering Hartford et al. (2018) , and relation extraction Verga et al. (2017) ; Rossiello et 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 et al., 2017; Zaheer et al., 2017; Lee et al., 2019) . The containment relationship between sets -and intersection more generally -is often considered as a measure of relatedness. For instance, when comparing the keywords for two documents, we may wish to model that {currency, equilibrium} describes a more specific set of topics than (i.e. is "contained" in) {money, balance, economics}. The containment order is a natural partial order on sets. However, we are often interested not in sets, but multisets, which may contain multiple copies of the same object; examples include bags-of-words, geo-location data over a time period, and data in any multiple-instance learning setting (Ilse et al., 2018) . The containment order can be extended to multisets. Learning to represent multisets in a way that respects this partial order is a 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 ≈ currency and balance ≈ equilibrium. 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 et al., 2019; Vendrov et al., 2015; Vilnis et al., 2018; 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-theoretic 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 to capture these relations, comparing our approach to DeepSets-based approaches (Zaheer et al., 2017) with unconstrained item representations. Furthermore, we demonstrate that our model learns "meaningful" representations. 2 RELATED WORK 2.1 SET REPRESENTATION Qi et al. (2017) 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 f (A) can be approximated by a model of the form ρ a∈A φ(a) for some learned ρ and φ, which they call DeepSets. They note that the sum can be replaced by a max-pool (which is essentially the formulation of Qi et al. (2017) ), and observe empirically that this leads to better performance. 1 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 a network that compares the input set to trainable "hidden sets." However, both these approaches require solving computationally expensive matching problems at each iteration. Vendrov et al. (2015) and Ganea et al. (2018) 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 a similar idea to embed hierarchical network structures in hyperbolic space, simply using the hyperbolic distance between embeddings. These approaches are unified under the framework of "disk embeddings" by Suzuki et al. (2019) . The idea is to map each object to the product space X × R, where X is a (pseudo-)metric 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 X (f (A), f (B)) ≤ r(B) − r(A). An equivalent statement can be made for multisets (see Proposition 3.2.4) . We propose a novel task: predicting the size of either the symmetric difference of the intersection between pairs of multisets. We motivate this construction via a measure-theoretic notion of "flexible containment." We demonstrate the utility of this idea, developing a theoretically-motivated model 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 to a standard basis vector, thus essentially performing semi-supervised clustering. One interesting area for future theoretical work is understanding a related problem: clustering n objects given multiset difference sizes. As a first step, we show in Appendix H that n − 1 specific multiset comparisons are sufficient to recover the clusters. We would also be curious to see if one can learn the latent multiset space U. Following similar reasoning, we can convince ourselves that multiset union should be defined as It is important to differentiate this from "multiset addition," which simply combines two multisets directly: A + B = {1, 1, 1, 1, 1, 2, 2, 2, 3} for our example above, and in general m A+B = m A (x) + m B (x). Multiset difference is a little harder to define. The main problem is that we cannot rely on a notion of "complement" for multisets. Instead, let us again try to reason by example. For our example multisets above, we have A \ B = {1, 2}. To arrive at this result, we remove from A each copy of an element which also appears in B. Note that if B had more of a certain element than A, that element would not appear in the final result. In other words, we are performing a subtraction of counts which is "glued" to a minimum value of zero. That is, m A\B (x) = max{m A (x) − m B (x), 0}. We can further convince ourselves of the correctness of this expression by noting that we recover the identity Finally, symmetric multiset difference can be defined using our expression for multiset difference, combined with either multiset addition or union. In particular, note that A B = (A\B)+(B \A) = (A \ B) ∪ (B \ A) -addition and union both work because (A \ B) and (B \ A) are necessarily disjoint. This gives us: (The equation still holds if we replace the addition with a maximum.)
Based on fuzzy set theory, we propose a model that given only the sizes of symmetric differences between pairs of multisets, learns representations of such multisets and their elements. This paper proposes a new task of set learning, predicting the size of the symmetric difference between multisets, and gives a method to solve the task based on fuzzy set theory.