Monotone and Separable Set Functions: Characterizations and Neural Models

We thank the reviewer for their comments, which will improve our paper.

Why is the condition of monotonicity necessary? The set containment problem only requires separability does it not?

Separabality alone does not suffice for set containment. In a neural network setting, such problems require us to design a function $F$ such that the order between $F(S)$ and $F(T)$ can serve as boolean test for whether $S$ is a subset of $T$. For this $F$ needs to satisfy two conditions.

(I) $F(S)\le F(T) \implies S\subseteq T$ (II) $F(S) \not\le F(T) \implies S\not\subseteq T$

We would like to emphasize that for high accuracy, $F$ needs to satisfy both conditions (I) and (II).

Separability alone satisfies condition (I). Monotnicity implies $S\subseteq T \implies F(S)\le F(T)$, which is equivalent to (II). Hence, without monotonicity, confition (II) may not be satisfied. Here, we will have $F(S) \not\le F(T)$ (thus predicting $S\not\subseteq T$) but in reality, $S$ is a subset of $T$. Hence, non-monotonicity ensures in large false negatives.

Am I correct in concluding that existing DeepSet models are monotone if they simply enforce non-negativity in their parameters, and separable as long as they have at least 2 layers?

Indeed, MASNET-ReLU can be seen as a special case of the deep sets model as it is of the form $F(S) = M _\psi(\sum _{x \in S} M _\theta(x))$.

But it's not entirely correct that to attain monotonicity, all the parameters of MASNET need to be non-negative. We choose the inner MLP $M _\theta$ to end with a non-negative activation like $ReLU$, but the weights can be negative as well. For the outer transformation $M _\psi$, we have chosen a non-negative function such as a neural network with non-negative weights and ReLU activation, or simply the identity. To attain weak separability we require that $M _\theta$ has $\geq 2$ layers.

The difference in architecture appears incremental. However this required a very detailed analysis, which we built up gradually starting from Section 2. Our key contribution involves three aspects: (1) characterization of existentence of MAS functions; (2) characterization of weakly MAS function, stability and more.

It is useful for the community to know that set containment problems can be better addressed by implementing deepsets in the correct way. Apart from deepset, we also provided more expressive neural formulations, which learns the activation functions automatically by trainable neural integrator (we mentioned them in appendix. If the reviewer thinks that it would highlight the contribution better, we will put it in main.)

results do not show significant improvement over existing baselines

The incremental improvement of the baselines might be misleading. One of the key reason why DeepSet and Set Transformer does well for the text and point cloud datasets lies in the distribution of classes (subset vs non-subset) our datasets. The non-subset to subset ratio in the datasets for our experiments with text and point cloud was taken to be 9:1. Due to this data imbalance, deepSets and Set Transformers are predicting almost all pairs as non-subsets (due to the data imbalance), resulting in high false negative rate.

This becomes more clear when we look at the False Negative rates of the models:

The high false negative rate of baselines are due to lack inductive bias as they do not have a built-in design of monotonicity. Since MASNET is equipped with the inductive bias of monotonicity, it predicts the true subsets correctly most of the time (and, all the time) in case of noisy (respectively, exact) set containment tasks. By design $MASNet(S) \leq MASNet(T) \implies S \subseteq T$: hence, the true subsets are never misclassified and thus the False Negative Rate is zero.

Here, we present the results on synthetic data with a balanced class ratio (1:1 ratio of subsets to non-subsets). We observe that we outperform them by a large margin.

For the text datasets as well, we sepeated the experiments during the rebuttal by taking 1:1 ratio of subsets to non-subsets and re-training the baselines and MASNET on this data. We present the results in the following table to demonstrate our point.

We observe that we outperform the baselines by a large margin.

Are Set Transformers with ReLU activations and >2 layers separable? The analysis was largely focused on Deep Sets, which are a much more limited architecture

The exact characaterization of conditions of separability for set transformer is extremely challenging; but we can prove it is not monotone. Therefore, it can be effectively used for set containment, as it will show high false negative rate (as shown in previous discussion too too)

We consider a set transformer model with sum pooling, namely $F(X;W _Q,W _V,W _K) = \text{SumPool}(\text{Attn}(X))$. Explicity, this is defined for a give multiset $X=(x _1,\ldots,x _n)$ by first defining query, keys and values per point $q _i=W _Qx _i, k _i=W _Kx _i, v _i=W _Vx _i, \quad \forall i=1,\ldots,n$ and then taking a weighted average, defined by weights $\alpha _{i,j}=\frac{e^{q _i\cdot k _j}}{\sum _s e^{q _i\cdot k _s}}$ to obtain a permutation invariant function $F(X;W _Q,W _V,W _K)=\sum _{i,j}\alpha _{i,j}v _i .$

Lemma: Let $V=\mathbb{R}^d$, and let $F: \mathcal{P} _{\leq \infty}(V) \to \mathbb{R}^D$ be a Set Transformer defined by $F(X;W _Q,W _V,W _K) = \text{SumPool}(\text{Attn}(X)$, then $F$ is not a pointwise monotone function.

Proof We need to show that there exist some parameters $W _Q,W _V,W _K$ for which the function $X\mapsto F(X;W _Q,W _V,W _K)$ is not monotone. Choose any matrix $W _Q=W _K$ which has no kernel, and any non zero $W _V$. Choose some vector $x _1$ such that $W _Vx _1$ is non zero. By swapping $x _1$ with $-x _1$ if necessary, we can choose some index $j$ such that for $v _1=W _Vx _1$, the $j$-th index is negative $v _1[j]<0$. By assumption we also have that $q _1=k _1$ is a non-zero vector, and hence it has a positive norm.

Now, let $S$ be the singleton set $S=(x _1)$, which is a subset of $T=(x _1,0 _d)$, where $0 _d$ denotes the all zero vector in $\mathbb{R}^d$. We note that $F(S;W _Q,W _V,W _K)=v _1$ While, since $v _2,q _2,k _2$ are all zero, $F(T;W _Q,W _V,W _K)=(\alpha _{1,1}+\alpha _{1,2})v _1.$ Note that $\alpha _{1,1}+\alpha _{1,2}=\frac{e^{\|q _1\|^2}}{e^{\|q _1\|^2}+1}+\frac{1}{2}>1 ,$ and it follows that $F(T;W _Q,W _V,W _K)[j]<F(S;W _Q,W _V,W _K)[j]$ which shows that this function is not monotone. This concludes the proof.

It is plausible that the set transformer model could be modified in some way, so that it is monotone. We believe this is a good direction for future work, and we thank the reviewer for pointing it out.

Do you observe significant difficulties in training networks with the 'hat' activation functions?

Training MASNET-Hat was not very difficult. For example, we refer to eq (8) of the paper, where we used a parametric version of Hat function, given by

Dear Reviewer McwL,

We realized that the first para in our response to the following question may be confusing due to a typo. We clarify here for better understanding.

Are Set Transformers with ReLU activations and >2 layers separable? The analysis was largely focused on Deep Sets, which are a much more limited architecture

The exact characterisation of conditions of separability for set transformer is extremely challenging; but we rigorously prove that it is not monotone (we presented a Lemma with proof in the rebuttal itself). Therefore, it can not be effectively used for set containment, as it will show high false negative rate (as presented experimental results and preceding discussions too)

Dear Reviewer Mcwl,

Could we request you to let us know if our response addresses your rebuttal-questions. We would be more than happy to provide any additional results/analysis, if you deem suitable.

Dear Reviewer McwL,

We further conducted experiments on MNIST. Results are follows, which show that under the similar model capacity, MASNet Hat is better than MasNet ReLU. Therefore, we observe the utility of Hat functions across a span of applications from Amazon datasets to text retrieval and image classification.

Accuracy numbers are in the following table:

Since the discussion period will conclude in less than 12 hours, we would be indeed very grateful if you could let us know of any remaining concerns. We would be happy to address them promptly.

Thank you for your reply. Our replies are inline.

I understand that the proposed architecture can also be used with the "hat" activation functions, but I remain somewhat suspicious of the usefulness of those activation functions in more general settings in practice.

Our hat functions are more effective in practice than other activation function like ReLU. We already experimented this during discussion period and presented for other reviewers. Specifically, we provide more effective comparison of MASNET-HAT vs MASNET-ReLU by ensuring approximately equal number of parameters on a large class of setups i.e., synthetic dataset (1:1 ratio of subset-nonsubset pairs) and also a wide class of real datasets- MSWEB,MSNBC; Bedding and Feeding from Amazon datasets; NFCorpus and SciFacts from BEIR dataset.

Acc on synthetic dataset

Acc on real dataset

These two results demonstrate that the HAT activation is effective and outperforms ReLU when evaluated under comparable model capacity. Since both models are monotone, the improved performance can be attributed to the superior separability of MASNET-HAT compared to MASNET-ReLU under similar model capacity.

Moreover, in our proof of MASNET-ReLU's separability, we crucially relied on the fact that a single-layer network with the HAT activation function is separable. In this sense, the HAT function serves as a foundational stepping stone in establishing the separability of MASNET-ReLU. Without first introducing and analyzing the HAT activation, it would not have been possible to rigorously justify the separability of MASNET-ReLU, despite its seemingly simpler architecture.

We would also like to emphasize that, as a class of functions, HAT activations are significantly richer than ReLU. Unlike ReLU, which is inherently piecewise linear, HAT activations are not restricted to piecewise linearity and can capture more complex functional forms.

The RELU form of MasNET seems even less distinct from a baseline Deep Set architecture than I thought, given your comment. Is there any difference at all between MasNET-RELU and a Deep Set with ReLU activations and multi-layer feedforward encoders and decoders?

We are sorry for the confusion. MASNET-ReLU is not the same as DeepSet with ReLU activation. DeepSets have form of $F(S) = M_{\theta_2}(\sum_{x \in S} M_{\theta_1}(x))$, where $S \subseteq V$ and $F: 2^V \to \mathbb{R}^d$. For such a DeepSet to be a MASNET-ReLU, we need to have $M_{\theta_1}: V \to \mathbb{R}^d$ to be a non-negative vector-valued function, which in our case is a neural network with ReLU activation in the last layer; and $M_{\theta_2}: \mathbb{R}^d \to \mathbb{R}^d$ is a vector-to-vector monotone increasing function. We can provide monotonicity using two ways:

1. Using a neural network with non-negative weights and a hardcoded monotonically increasing activation function.
2. Using a neural integral based technique inspured from [1] where we model $M_{\theta_2}$ to be co-ordinate wise monotone function. This we achieve by modelling the derivative of $M_{\theta_2, i}$ using a non-negative neural network and use a neural integral to compute $M _{\theta _2}$, as follows: $M _{\theta_2, i}(x _i) = \int _0^{x _i} h _{\theta _2, i}(t) dt$, where $h _{\theta _2,i} : \mathbb{R} \to \mathbb{R}^+$ is a non-negative neural network.

This makes our architecture significantly different from "Deep Set with ReLU activations and multi-layer feedforward encoders and decoders", because we need to essentially constrain the outer decoder to preserve the partial order of vector monotonicity, which we can achieve by the above couple of prescribed methods.

[1] Unconstrained Monotonic Neural Networks by Wehenkel and Louppe

We are open to hear more from you. If you have questions, please do not hesitate to write to us. The neural integral approach was discussed Appendix for a general context. If the reviewer suggests, we can bring them in main if the paper gets accepted.

I thank the authors for their very thorough responses, and apologize for my lateness in replying in kind. The experiments with balanced class distributions do show a stronger empirical argument for MASNet. I also appreciate the detailed analysis of the Set Transformer case - this is a compelling argument that should make it into the paper.

My concerns about the incremental nature of the architecture remain, however. I understand that the proposed architecture can also be used with the "hat" activation functions, but I remain somewhat suspicious of the usefulness of those activation functions in more general settings in practice. The RELU form of MasNET seems even less distinct from a baseline Deep Set architecture than I thought, given your comment. Is there any difference at all between MasNET-RELU and a Deep Set with ReLU activations and multi-layer feedforward encoders and decoders?

We thank the reviewer for their comments, which we will incorporate in the revised version, if accepted.

One issue is the lack of compelling motivation for MAS as opposed to monotone functions.

We begin with two applications which are based on the set containment task:

(1) In recommendation system design, one problem is to recommend item having a particular set of features $S$. Here, we represent each item as a set of corresponding features $T$ and the problem is to find all sets $T$ such that approximately, $S\subseteq T$. (2) Text entailment where we are given a small query sentence $q$ and the goal is to find the set of corpus items $c$ from a large corpus $C$, where $q \implies c$ or $c$ entails $q$. Here, $q$ and $c$ are typically represented as sets of contextual embeddings (S for q and T for c) and the entailment problem can be cast as the problem of checking if $S\subset T$.

In a neural network setting, such problems require us to design a function $F$ such that the order between $F(S)$ and $F(T)$ can serve as boolean test for whether $S$ is a subset of $T$. For this $F$ needs to satisfy two conditions.

(I) $F(S)\le F(T)$ implies $S\subseteq T$ (II) $F(S) \not\le F(T)$ implies $S\not\subseteq T$

We would like to emphasise that for high accuracy, $F$ needs to satisfy both conditions (I) and (II). Monotone function ensures that if $S \subseteq T$, then we have $F(S) \le F(T)$ or equivalently $F(S) \not\le F(T)$ implies $S\not\subseteq T$ (i.e., condition (II) above). However, monotone-only condition does not ensure the condition (I). As a result, if we predict $S\subseteq T$ based on $F(S) \le F(T)$ when $F$ is monotone but not separable, it will give large number of false positives. Therefore, we need to define the notion of separable functions to ensure our function satisfies condition (I).

Here, we run some additional experiments for the text entailment application on BEIR datasets: NFCorpus and SciFact. The following table reveals that MAS functions perform better than all baselines (including four new baselines, suggested by Rev b3Mt) as well as monotone (but not MAS) functions. As per Prop-6 from our paper, DeepSet with single layer ReLU network as the embedding model is not separable (even weakly), which we chose for the monotone (but not MAS) set model for our experiment. Accuracy is reported as follows:

This strengthens our argument that monotonicity alone is not sufficient for set containment.

The authors may want to focus first on their most important 2-3 findings as opposed to talking about stability, infinite sets (less relevant to ML) and new activation functions.

We did ponder on this, but realized that there are several cases where infinite sets and stability are crucial. Note that by infinite sets, we mean the ground set or the universal set is infinite. Such cases are applicable when dealing with continuous features or representations. For example, in case of point clouds and images, the features come from a continuous distribution; in the context of health records, some features (e.g., blood sugar) may be continuous. Even in text applications, where the vocabulary consists of discrete words, the contextual embeddings of a word in a sentence (e.g., BERT embeddings or LLM encoder output) are effectively continuous vectors. Since the possible occurrences of a word across sentences can be really diverse, the set of token embeddings (with added positional encoding) can be roughly considered as an infinite set in practice, due to the very small resolution.

Stability or holder separability also has practical implications, especially for infinite sets. Typically, in applications, we encounter approximate set containment rather than exact set containment, labelled by human annotators. For example, if two images consist of A = ("leopard") and B = ("tiger", "tree"), then a human annotator is likely to assign $A \subset B$. Holder separability can better account for this than exact set containment.

paper is pepped with inaccuracies

We sincerely apologise for the inadvertent errors in the current version of the manuscript. In our internal repository, the manuscript was in order; however, during the final stages of submission to OpenReview, a few hasty edits introduced these typos. In fact, during the original submission, we uploaded a version in supplementary material, which has all broken Appendix references fixed.

We would like to emphasise that these issues have already been resolved in our internal version. Unfortunately, OpenReview does not allow us to update the current submission version, but we will ensure that all such errors are fully corrected in the camera-ready version, if the paper is accepted.

We hope that these typos—already fixed on our end—do not detract from the technical strengths of the work, which you also recognised.

in line 31 15 is cited as relevant to the paper.

The paper considers a reduction to the set splitting problem to prove the hardness result. This is the task of partitioning a set $S = S_1 \sqcup S_2$ such that for a collection of subsets $\mathcal{C} = (C_i \ |\ i : C_i \subset S )$, we must have $C_i \not \subset S_1 \text{ and } C_i \not \subset S_2, \forall i$. This is basically preventing set containment for a subset family. For some context, we intended to mention some of the relevance of set monotonicity to learning theory. But we understand the connection may appear quite remote, and we will clarify this more in final version, if our paper gets accepted.

Why introduce a new activation function if embedding can implemented by a simple architecture with two layers?

When we fine-tune a large $N$ layer model for different tasks, sometimes the practice is to freeze the first N-1 layer and only train/fine tune the last layer. Thus, here we fine-tune only one layer rather than two layers. In such cases, the variant of our model with exactly one layer with a new activation function can be more easily plugged and played. Moreover, for such large models--- which require large memory to fit--- adding more layers will make it difficult to train with available resources.

To elaborate more, we consider image retrieval applications, where we are given a segment of an image as the query: $q$ and the goal is to retrieve all images in the database which contain the object(s) in $q$. In this task, we only fine-tune the last layer of CNN with our new activation function. Experiments were performed on the MNIST dataset, and the goal was to retrieve all the images with the same digit as the query image segment. The performance is measured in accuracy, where each image in the corpus was assigned a boolean label of 0/1 depending on whether the digit in the image is same as that of the query segment.

Apart from the practical usage, the hat activation was introduced was firstly as a tool to develop the TRI function, which was a key step in theoretically justifying that two-layer neural nets can be used to develop a MAS function. Hence, to prove that a simple architecture with two layers can serve as MAS function, we had to develop this new activation function.

The introduction of parameters in the denominators in (8) could lead to numerical instability while training. Can it be avoided?

We didn't incur too much instability during training of MASNET-Hat, where the Hat function admits the particular form in (8). We have two learnable parameters in the denominator: the support width $\beta$ (where $\beta> 0$) and the peak $\gamma$ (where $\gamma \in (0,1)$). The way we tackled this was in the particular form of parametrizing $\beta$ and $\gamma$ during our training. This was done as follows:

1. For ensuring $\beta > 0$, we introduced an unconstrained learnable parameter $\hat{\beta}$ and then tried several different parametrizations of $\beta$, as follows: (i) $\beta = \left|\hat{\beta}\right|$ (ii) $\beta = \hat{\beta}^2$ (iii) $\beta = \text{ELU}(\hat{\beta}; \nu) + \nu$, where $\nu > 0$ is a hyper-parameter and $\text{ELU}(x, a) = \begin{cases}x, \text{ if } x > 0; \ a(e^x - 1), \text{ if } x \leq 0 \end{cases}$ Amongst these choices, the third one worked best. An intuitive explanation is: training instability comes to picture when $\beta \to 0$. But in the third parametrization, $\beta \to 0 \iff \hat{\beta} \to -\infty$, thus for most values of $\hat{\beta}$, we have $\beta >> 0$. The choice of the hyperparameter $\nu$ slightly affected the accuracy, but with no significant impact.

2. For ensuring $\gamma \in (0,1)$, we again chose a learnable unconstrained parameter $\hat{\gamma}$, a hyper-parameter $\tau$, and used the tempered-sigomid based parametrization of $\gamma = \text{Sigmoid}(\tau \cdot \hat{\gamma})$. Since $\gamma \to 0 \iff \hat{\gamma} \to -\infty$ like before, we had a stable training since $\gamma >> 0$ for most values of $\hat{\gamma}$. As observed in our experiments, the temperature hyperparameter $\tau$ didn't affect the accuracy a lot.

Here, we give a table of the avg and std (across seeds) of accuracy for different parametrizations of $\beta$.

Dear Reviewer 7bQs,

Sorry to bother you again. Could you kindly check our follow-up responses (Re. rationale behind introducing a new activation function, and More re. motivations behind Hat activations) and let us know if we’ve correctly understood and addressed your concern? We now realize that our initial explanation was unconvincing due to a misunderstanding on our part.

We’d be very grateful if you could take a quick look and let us know.

Best,

Authors

Dear Reviewer 7bQs,

In an attempt to answer your questions about justifying the new class of Hat activation functions, we've followed up our experiments on synthetic data with some additional experiments on real-world datasets, namely MSWEB and MSNBC. We solved the task of exact set containment where the ratio of subsets to non-subsets was taken to be 1:1. We considered the two MASNET models where MASNET-Hat is equipped with a one-layer neural network as the embedding model and MASNET-ReLU has a two-layer architecture with a comparable number of parameters (1.1x the no of parameters of MASNET-Hat). The accuracy numbers are as follows:

This backs up our intuition that Hat activation shows better separability than ReLU with a comparable number of parameters.

Could you please let us know if our answers addressed your concerns?

Dear Reviewer 7bQs,

We would really like to thank you for engaging with us.

We acknowledge that we misunderstood the intent of your question in the original rebuttal. Our response focused on the utility of a one-layer network, whereas your question was more concerned with the rationale behind introducing the new activation function. We provide a clarification below. We kindly request the reviewer to look into it and please get back to us once more.

In our initial experiments, we compared a single-layer MASNET-HAT (HAT is the new activation function) with a two-layer MASNET-ReLU (the two layer network which the reviewer has pointed out). The small difference between performances of MASNET-ReLU and MASNET-HAT in this setting should not be taken as evidence against the utility of the HAT function. Instead, the observed performance gap is primarily due to the increased number of parameters in MASNET-ReLU, resulting from its deeper architecture.

To more directly evaluate the effectiveness of the HAT function, we conducted experiments where we approximately equalized the number of parameters between MASNET-HAT and MASNET-ReLU.

First, we control the hidden dimension of a two-layer MASNET ReLU, so that the parameter count of MASNET-ReLU becomes close to (1.1x) MASNET-HAT with a single layer on our synthetic dataset with a 1:1 subset-pair non-subset-pair ratio The following results show that MASNET-HAT performs better.

Next, we compare a two-layer MASNET-HAT with a two-layer MASNET-ReLU on the same dataset. The following results show that MASNET-HAT performs better.

These two results demonstrate that the HAT activation is effective and outperforms ReLU when evaluated under comparable model capacity. Since both models are monotone, the improved performance can be attributed to the superior separability of MASNET-HAT compared to MASNET-ReLU under similar model capacity.

Moreover, in our proof of MASNET-ReLU's separability, we crucially relied on the fact that a single-layer network with the HAT activation function is separable. In this sense, the HAT function serves as a foundational stepping stone in establishing the separability of MASNET-ReLU. Without first introducing and analyzing the HAT activation, it would not have been possible to rigorously justify the separability of MASNET-ReLU, despite its seemingly simpler architecture.

We would also like to emphasize that, as a class of functions, HAT activations are significantly richer than ReLU. Unlike ReLU, which is inherently piecewise linear, HAT activations are not restricted to piecewise linearity and can capture more complex functional forms.

Thank you for pointing out the issue with the sentence construction (we cannot change the sentence anymore, unfortunately, since the edit button is frozen). We will definitely ensure a more polished and formal discussion in the final version, should the paper be accepted.

Dear Reviewer 7bQs,

We wanted to follow up on whether your concerns about the motivation and justification for introducing the class of hat activations have been addressed by our experiments and intuitions that we provided. Since the author-reviewer discussion period has been extended by a couple of days, we were wondering if we could provide you with some deeper insights into it or other aspects of our methods/theory.

We would appreciate it if you kindly let us know what you think. We will be more than happy to provide any further clarifications.

Best,

Authors

Dear Reviewer 7bQs,

In an attempt to further strengthen our claim on why we need a new Hat activation, we have performed more experiments on Amazon Baby Registry datasets (Bedding, Feeding) and BEIR datasets (NFCorpus, SciFact). We have kept the number of parameters of two-layer MASNET-ReLU and two-layer MASNET-Hat to be similar. The accuracy numbers are given as follows:

Here, we observe that, under similar parameter scale, using Hat function shows advantage over ReLU, following our theoretical insight that ReLU networks learn to simulate Hat functions.

Hope this strengthens our point on why Hat functions are useful even outside theoretical analysis.

Since the discussion period is going to end soon, we would kindly request you to please let us know if our response addresses your rebuttal questions.

We thank the reviewer for their suggestions, which will improve our paper.

A large portion of the set literature seem to be ignored in this work (see References).

Many thanks, we will incorporate and discuss them in the main paper if our paper gets accepted.

Fspool used a sort-based pooling strategy and introduced the responsibility problem. Both HORSE and INSET are designed specifically for subset selection. Specifically, HORSE is built on attention and to retrain information from both the input ground set and the optimal subset. In contrast, our method focuses on characterising and neural design for monotone and separable set functions, specifically for the set containment task.

How are MAS functions related to the MBC methods... have some connection with the problem tackled in this work.

Relation to MBC works: The goal of the MBC works is to design a set function $F$, which, if applied on any subsets from partitions of a set $S$ and pooled through an activation $g$, should return $F(S)$. Thus, at a high level, MBC functions analyse and design functions for the following batch consistency condition: $g(F(S _1),...,F(S _n)) = F(S)$. MBC methods achieve this by imposing certain restrictions on attention-based set architectures. Similar to this, our work also puts restrictions on the inner embedding transformation and the outer vector-to-vector transformations. However, the nature of restrictions for our method is very different. Our method offers neural restrictions to ensure monotonicity and weak separability, which would translate partial order of set containment to the partial order of coordinate-wise vector dominance.

MASNET can be made Mini Batch Consistent: The reviewer's question triggered us to think if MASNET can be made minibatch consistent. Since set containment is the major theme of our work, with potential applications in retrieval and recommendation systems, processing huge sets at once can be a key bottleneck, and it would be nice to make MASNET process over mini-batches and then design some aggregation mechanism to make the aggregated embedding equal to the embedding of the entire set. If we consider a partition of a given set $S = \bigcup _{i=1}^k S _i$, where $S _i$'s are all disjoint, then $MASNET(S _i) \leq MASNET(S)$ by monotonicity. But, we can try to find an appropriate pooling mechanism over the subset embeddings to make the aggregated embedding same as that of the entire set.

For example, if the outer transformation $M _{\theta _2}$ of MASNET as in eq(7) of the main text was invertible, and then we may define a particular permutation-invariant pooling function $g$ such that $g(X _1, X _2, \cdots, X _k) = M _{\theta _2}(\sum _{i=1}^k M _{\theta _2}^{-1}(X _i))$. Then we have that: $g(MASNET(S _1), \cdots, MASNET(S _k))$ $= M _{\theta _2}(\sum _{i=1}^k M _{\theta _2}^{-1}(MASNET(S _i)))$ $= M _{\theta _2}(\sum _{i=1}^k \sum _{x \in S _i}\sigma\circ M _{\theta _1}(x))$ $= M _{\theta _2}(\sum _{x \in S} \sigma \circ M _{\theta _1}(x)) = MASNET(S)$ This is irrespective of how we partition $S$ into $S _1, \cdots, S _k$. And this would enable us to process the subsets independently and aggregate them accordingly.

For our purposes, we have needed the outer transformation $M _{\theta _2}$ to be a vector-to-vector monotone function. But that doesn't guarantee injectivity or invertibility. Thus, we need to restrict the choice of $M _{\theta _2}$ to be monotone and invertible. One possible choice is to use ideas from relevant works like [A], [B] to design monotone and invertible neural networks, and analyse the expressibility properties of the resulting set model.

[A] Unconstrained Monotonic Neural Networks by Wehenkel and Louppe

[B] Analyzing Inverse Problems with Invertible Neural Networks by Ardizzone et. al.

Experimental comparison with MASNET: We compare the suggested methods against our method on BEIR datasets for text retrieval applications. The following table shows the results, which show that we perform better.

The set sizes are smaller... What happens when the set sizes grow to millions?

In the following experiments on synthetic data (with 1:1 ratio of subsets to non-subsets), we keep $|S|$ fixed and increase $|T|$.

Following are the results.

Table: Accuracy for set containment when $|T|$ goes large.

We observe that (1) Our method outperforms the baselines more and more significantly, as $|T|$ goes large. (2) Accuracy of all methods worsens as $|T|$ goes large. But, the degradation of performance of the baselines is very large, whereas the degradation of our method is quite modest. Intuitively, the chances of wrongly predicting $S \subseteq T$ increase as $|T| >> |S|$, but MAS functions still do better as they're equipped with provable separability.

Sum decomposable functions like deepsets have been shown limited expressivity compared to attention-based methods. what would be required to propose an architecture based on the transformer .. that is monotone and separable? A discussion is enough.

Set Transformers are not monotone. Attention makes the monotonicity challenging due to the normalising factor in the denominator. We give a constructive proof of the fact that, for a large class of weights for set transformer, we can find sets $S \subseteq T$, such that $F(S) \not \le F(T)$. Thus, it's not pointwise monotone, unlike MASNET, as shown below:

Lemma: Let $V=\mathbb{R}^d$, and let $F: \mathcal{P} _{\leq \infty}(V) \to \mathbb{R}^D$ be a Set Transformer defined by $F(X;W _Q,W _V,W _K) = \text{SumPool}(\text{Attn}(X))$, then $F$ is not a pointwise monotone function.

Proof We need to show that there exist some parameters $W _Q,W _V,W _K$ for which the function $X\mapsto F(X;W _Q,W _V,W _K)$ is not monotone. Choose any matrix $W _Q=W _K$ which has no kernel, and any non-zero $W _V$. Choose some vector $x _1$ such that $W _Vx _1$ is non-zero. By swapping $x _1$ with $-x _1$ if necessary, we can choose some index $j$ such that for $v _1=W _Vx _1$, the $j$-th index is negative $v _1[j]<0$. By assumption we also have that $q _1=k _1$ is a non-zero vector, and hence it has a positive norm.

Now, let $S$ be the singleton set $S=(x _1)$, which is a subset of $T=(x _1,0 _d)$, where $0 _d$ denotes the all zero vector in $\mathbb{R}^d$. We note that $F(S;W _Q,W _V,W _K)=v _1$ While, since $v _2,q _2,k _2$ are all zero, $F(T;W _Q,W _V,W _K)=(\alpha _{1,1}+\alpha _{1,2})v _1.$ Note that $\alpha _{1,1}+\alpha _{1,2}=\frac{e^{\|q _1\|^2}}{e^{\|q _1\|^2}+1}+\frac{1}{2}>1 ,$ and it follows that $F(T;W _Q,W _V,W _K)[j]<F(S;W _Q,W _V,W _K)[j]$ which shows that this function is not monotone. This concludes the proof.

To achieve monotonicity in interaction based set models, one could extend the notion of attention without the normalization factor, i.e., to use functions of the form $F(S) = \sum _{x, y \in S} \psi(x, y)\phi(x) + \sum _{z \in S} \gamma(z)$ where $\psi : V \times V \to \mathbb{R} _{\geq 0}$ is a non-negative function to model the interaction between elements and $\phi, \gamma : V \to \mathbb{R} _{\geq 0}^m$ are vector-valued functions with non-negative entries. Such set functions are monotone by design. Obtaining separability results in such cases could be quite challenging and this seems like interesting direction for future work.

For separability, we first point out to Corollary-4(l-173) from the main text, where we show that one can't achieve both mononicity and separability for infinite ground sets. Thus, for a "monotone version" of a set transformer, achieving full separability is impossible, and we thus fall to the notion of weak separability: which requires every pair of non-subset $S \not \subseteq T$ to be separated by at least one set of parameters. The exact characterization of parameters that makes this "monotone version" of transformer separable too, is challenging.

Experimental evidence that set transformer is not MAS Monotonicity means that $S\subseteq T \implies F(S) \le F(T)$, or in other words, that in the set containment problem, there can be no false negatives. Hence, non-monotonicity ensures in large false negatives. Similarly, the absence of separability results in a large false positive rate. To evaluate this experimentally, we perform experiments on synthetic data with a 1:1 ratio between the number of subset-pairs and non-subset pairs. Results are as follows:

Table: Acc, FNR, FPR for synthetic data with 1:1 class ratio

We see that MASNET has no false negatives due to monotonicity, and a low false positive rate due to separability, as we expected. In contrast, the present implementation of Set Transformers has high rates of both false positives and false negatives.

Appendix link missing

We sincerely apologize for the inadvertent errors in the current version of the manuscript. In our internal repository, the manuscript was in order; however, during the final stages of submission to OpenReview, a few hasty edits introduced these typos. In fact, during the original submission, we uploaded a version of the full paper in supplementary material, which has all broken Appendix references fixed.

In any case, all these errors have been fixed in our current version of our manuscript, and all will be in order for the final version of the paper.

We thank the reviewer for their comments, which we will incorporate in the revised version, if accepted.

I’m not an expert on partial-ordered sets or lattices, but I’d imagine that the results of Theorem 1 follow pretty easily from standard elementary results in those fields. It’s nice that the proofs are self-contained but it would be good to mention any standard results this can be derived from if any.

We agree that this problem of designing set embeddings that captures the notion of set containment is a very fundamental question, and lots of our proof techniques-specially those related to existential characterization of MAS functions, boil down to combinatorial arguments. However, we did an extensive literature survey and were unable to find significant existing work that derives results related to set embeddings that preserve the partial order of monotonicity.

We note that for some of the theorems we did employ some standard techniques: In Theorem 2 we leveraged probabilistic methods based techniques similar to Alon’s text on probabilistic methods [1], for Theorem 3 we have leveraged standard combinatorial results like the Erdos-Szekeres Theorem [2]. We have referenced [2] in the main text but accidently omitted [1], we will fix this in the final version.

[1] The Probabilistic Method by Noga Alon and Joel Spencer

[2] Erdős, P.; Szekeres, G. (1961), "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3–4: 53–62

I would have liked to see more end-to-end experiments of using MAS models to solve realistic modelling problems such as the examples in “Deep Sets”: point-cloud classification, Text Concept Set retrieval, Sum of Digits, etc. The paper only provides experiments that predict containment which is a much easier task for these embeddings given their inductive bias.

During the rebuttal, we performed several experiments on realistic examples as per your suggestion. Here, we present results on image classification on MNIST dataset from given segment of an image and text retrieval from BEIR datasets (NF Corpus and Scifact). For both of these realistic tasks, we intuitively think that having set containment as an inductive bias along with the power of weak separability might be helpful, which is reflected in our experimental results as well.

Specifically, for image classification, we used a N-layer CNN $a _N(a _{N-1}(....(a _1(x))))$, where we froze the first $N-1$ layers and modify the last layer to ensure that $a _N (\bullet)$ is a MAS function. Thereafter, we predict the boolean 0/1 label on which images of the MNIST dataset have the same digit(object) as the candidate segment image.

For BEIR dataset, we used BERT embedding as input to a MAS function. Following table shows the results, which shows that we perform better than standard set based models at a similar scale of parameters.

For both the experiments, we report the accuracy numbers in the following table:

It looks like Prop 8 contradicts Prop 6: As far as I can tell, a hat function can be monotone and non-negative, in which case by Prop 6, there exists an S not-subset of T for which F(S,(A,b)) <= F(T, (A,b)) for all A, b, so F is not weekly MAS. Am I missing something?

Thanks for raising the point, but we'd like to point out that, a hat function cannot be monotone.

According to definition 7, a hat activation is a real-valued function that is (a) non-negative (b) compactly supported (c) not identically zero and (d) continuous. Hence, if $\sigma: \mathbb{R} \to \mathbb{R}$ is a hat activation, there exists $a,b\in \mathbb{R}$ such that $a < b$ and $\sigma(x) = 0$ for $x \in (-\infty, a] \cup [b, \infty)$. Thus, if $\sigma$ was monotone, then $\sigma(x)$ would be identically zero, for all $x\in \mathbb{R}$, which is in contradiction with (c).

Since a hat function can never be monotone, we cannot apply Prop-6 to hat activations (since it only applies to monotone activation functions such as Sigmoid or ReLU), and thus Prop-6 does not contradict Prop-8.

In Theorem 13, isn’t it true that for all injective functions F:P _{<=k}(V) → R^m there is an M such that F(S) =M (F(S) ). Also you’re using ‘F’ to denote both the MAS and the desired function F. Can you change the notation for one of them to make the theorem statement clearer?

We agree with the reviewer the notation for one of the functions should be changed. Theorem 13 should read as follows:

Let $V$ be a finite ground state, and let $F: P _{\leq k}(V) \to \mathbb{R}^m$ be a MAS function. Then for every multiset-to-vector monotone function $f: P _{\leq k}(V) \to \mathbb{R}^s$, there exists a vector-to-vector monotone function $M:\mathbb{R}^m \to \mathbb{R}^s$ such that $f(S)=M (F(S))$.

With this correction, the theorem statement is now clearer and implies a non-trivial result.

The actual definition of “weak separability” is missing due to a typo in the paper.

Sorry about this, we accidently commented out the definition just before sumbission, while doing some edits. The definition of weak-separability is as follows:

“The parametric set function $F: P _{\leq \infty}(V) \times \mathcal{W} \to \mathbb{R}^m$ is weakly separable, if given $S, T \subseteq V$ such that $S \not \subseteq T$, there exists a parameter $w \in \mathcal{W}$ such that $F(S; w) \not \le F(T; w)$”.

This essentially means that at least some point in the parameter space separates any given pair of non-subsets.

In Theorem 12, do you mean m rows instead of columns?

Yes, and the matrix A as in Theorem 12 has dimensions $m \times d$. We meant $m$ rows only, and sampling them independently.

What does “m” refer to in line 331?

Instead of $(\alpha +m\beta)$, it should read $\alpha +\gamma\beta$, where $\gamma \in (0,1)$ is as defined in line 330. Thus, $\alpha + \gamma\beta \in (\alpha, \alpha + \beta)$, which means it’s an interior point of the support.

Thanks for pointing out all these typos, we have fixed these in our current version of the manuscript, so that the final version of the paper will be corrected.

Dear Reviewer z6Li,

I thank the author for addressing my concerns. With the new results and fixes I'm changing my rating to 5.

We are happy to know that our response have addressed your concerns. Re. rating, we still observe the old rating. An updated rating will make the rating invisible to us (and will become visible during final decisions). Could you please check once?

Dear Reviewer z6Li,

We would like to thank you for your positive feedback and comments, which we would surely include in the final version of the paper, if accepted. Since the discussion period will be over soon, we would like to ask if you have any concern, which you want us to clarify.

Thanks

Authors