Learning RNNs with Commutative State Transitions
Authors: Edo Cohen-Karlik
Amir Globerson
Venue:  (2020)

Abstract: Many machine learning tasks involve analysis of set valued inputs, and thus the learned functions are expected to be permutation invariant. Recent works (e.g., Deep Sets) have sought to characterize the neural architectures which result in permutation invariance. These typically correspond to applying the same pointwise function to all set components, followed by sum aggregation. Here we take a different approach to such architectures and focus on recursive architectures such as RNNs, which are not permutation invariant in general, but can implement permutation invariant functions in a very compact manner. We 
 first show that commutativity and associativity of the state transition function result in permutation invariance. Next, we derive a regularizer that minimizes the degree of non-commutativity in the transitions. Finally, we demonstrate that the resulting method outperforms other methods for learning permutation invariant models, due to its use of recursive computation.

Under review as a conference paper at ICLR 2019
LEARNING RNNS WITH COMMUTATIVE STATE TRAN- SITIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Many machine learning tasks involve analysis of set valued inputs, and thus the learned functions are expected to be permutation invariant. Recent works (e.g., Deep Sets) have sought to characterize the neural architectures which result permutation invariance. These typically correspond to applying the same pointwise function to all set components, followed by sum aggregation. Here we take a dif- ferent approach such architectures and focus on recursive architectures such as RNNs, which are not permutation invariant in general, but can implement permuta- tion invariant functions in very compact manner. We first show that commutativity and associativity of the state transition function result in permutation invariance. Next, we derive a regularizer that minimizes the degree of non-commutativity the transitions. Finally, we demonstrate that the resulting method outperforms other methods for learning permutation invariant models, due to its use of recursive computation.
INTRODUCTION
Many of the successes of deep learning can be attributed to a choice of architecture that fits the application domain, A key example of this are convolutional neural nets (Krizhevsky et al.) 2012) that employ extensive parameter tying across the image, reflecting the shift invariance of visual labels. It is clear that such inductive bias is necessary for any domain if one needs to learn from limited number of examples. This has prompted much recent interest in the question of modeling architectures that capture invariances of particular domains.
One such example is the setting where the input to the network a set of objects and the true output does not depend on the order of the objects in the set. In this case, the function that we seek to learn is permutation invariant. It would thus be advantageous to retrict learning to models that are permutation invariant by design. This was the observation in the work Deep Sets (Zaheer et al.) 2017]. which gave necessary and sufficient conditions for a network to be permutation invariant.
The underlying idea in many of the permutation invariant architectures is to apply the same network Ni to all items in the set, then sum the outputs and apply another network N2 to the summation. Clearly this is permutation invariant. Similarly other models using attention (Vinyals al. 2016 Lee et al. 2019) are permutation invariant since they only rely on comparisons between elements in the set.
Although the above approaches results in invariant models, these are not clearly the smallest models that can compute given invariant function. For example, consider the problem of computing the permutation invariant function f(r1,..., .nn) max; Iy In order to calculate it with DeepSet approach, one would need to set (x) _ for large k and then N2(2) 1// This would approximate the lop metric and therefore the max function. However, order to implement these two functions N1,N; N2 with ReLU networks, one would need O ( to achieve accuracy (e.g., Telgarsky| 2017] Lemma 3.4), and thus calculating this seemingly simple function to good accuracy would take a fairly large network. Clearly, if one max the aggregation function in DeepSets, this could be avoided, but the same would then be true for other aggregation functions.
On the other hand, the max function be easily implemented via simple RNN. Consider an RNN with the following state update $t+1 = max (s;-1, xx) and set sp -oc. Then clearly we would have on max;-1 Tj. Namely, will implement the permutation invariant max function.

---

Under review as a conference paper at ICLR 2019
Furthermore, the $1+1 state update can be very easily be implemented using one hidden layer ReLU network, because maz(s, x) = RsLU((s - z) + (zLU(z)= (eLU(-2))
The above example demonstrates that RNNs can in cases be natural computational model for permutation invariant functions. The goal of this paper is to ask which RNNs compute permutation invariant functions, and how they be learned.
Clearly, most RNNs are not permutation invariant, as their state has the capability of tracking temporal patterns, and is thus sensitive to changes in ordering. Here show that by restricting RNN state updates to caamuuaaive-assocattyy functions, RNNs do become invariant, and the resulting set of functions is very expressive.
After establishing the commutaivv-assooiitive constraints, we turn to ask how one can learn RNNs that satisfy the latter constraint. We show that for ReLU activation functions the commutative constraint corresponds to a closed form regularizer on the parameters of the RNN and suggest learning with this regularizer in order achieve commutativity.
We show empirically that learning with commutative regularization leads to architectures that are permutation invariant in practice and that outperform DeepSets on several benchmarks.
Taken together, our results highlight the importance of the function class used for learning permutation invariant functions, and the important role of recursive computation for these tasks.
PROBLEM FORMULATION
We consider the problem of learning functions that map sequence of inputs 21,.... y. We note we could have also addressed the problem generating an output sequence ,/......Ur but single output for simplicity.
, 3n output
We say that such a function f(x....., Øn) is permutation invariant for any permutation n of [n]] and for all inputs have:
f(1 ...) (1)x (r)))
(2.1)
We next ask: how should an RNN be constructed such that is guaranteed to be permutation invariant.
We consider standard RNNs, parameterized follows. Let E Re be the state vector at time t. Then the state update rule is:
(2.2) where (xx) E Rd is a perepprocessing" network (of arbitrary architecture), a is pointwise non- linearity such as ReLU or tanh, and A, W, θ are matrices which transform the appropriate dimensions, specifically,
St+1 Ao (Wv(x.) + Os,)
R W e kxxd and θ e Bexr, We note that we add a matrix A to allow the non-linearity to be taken in R such that k
Finally, the output is obtained via:
y g(
(2.3)
where g is any multilayer neural net (the specific architecture will not be important for our derivation).
To simplify the derivation of permutation invariance make the assumption that the dimension of the RNN state, and the dimension of the transformed input (bxx) are the same, i.e. r a
Next, we introduce the following notation for the RNN state transition:
S
Aa (X+)(x)) + Os+) (b(.).) 8t
(2.4)
Thus, the operation takes two vectors in Rdd and outputs vector in Red, Namely o: Rd Rd With this notation it is clear that:
R
(... ((s0 (xxx)) vxx2)) ... (xx))
(2.5)
We use parentheses to emphasize that the order of applying does matter and these operations are neither commutative nor associative for general RNNs.
It is always possible to achieve by padding either a or by zeros as necessary. For the reminder of this paper we omit the notation does not affect derivations.
2

---

Under review as a conference paper at ICLR 2019
3 PERMUTATION INVARIANT RNNS
In this section we relate properties of the state transition operator to the permutation invariance properties the RNN. Without loss generality we assume that the v/(x) = æ, since this just pre-processing step.
Definition 3.1. An RNN is permutation invariant if the function f Fn) g(st) implemented by the RNN is permutation invariant.
We begin with basic definitions.
Definition 3.2. The operator is commutative for all x., x! it holds that a o x' = x'
Definition 3.3. The operator is associative for all x; x', it holds that (x x')o xo it) Definition 3.4. If an RNN has a o operator that is both commutative and associative we refer to it as Commutative-Associativi RNNs.
Theorem 3.5. If RNN Commutativ--Asociian then it is permutation invariant. Namely St does not depend on the order of 01...., Zn.
Proof. The associativity property of the operator implies that we can remove the parentheses in Eq. 22.5 commutativity implies that we can then switch the order of the æ, arbitrarily. Thus we have that for all permutations
8t 80 Øt 822 ... 2t, 80 x1) xx(2) ... Wgt
(3.1)
Therefore the state invariant the input order, and so is the output y.
complementary question that of universality. Namely, are the above permutation invariant RNNs sufficiently expressive to capture any permutation invariant function?
Theorem 3.6. Let f(æ1..... Fan) be permutation invariant function Then it can be implemented with coamuutativ-Associattte RNNs.
Proof. Since the function f is permutation invariant, it follows from Theorem in the DeepSets paper (Zaheer al. 2017) that there exist two functions & and p such that f(x), ..... ,.,) p EE d(æ;)). We can now implement this architecture with a Commutarive-Associatiee RNNs as follows: set 6. = p and æo x x'. Clearly this implements the DeepSet function and is Commutative- Associative because is just addition.
We conclude that Commutative-Assoott RNNs implement permutation invariant functions and are also sufficiently expressive to capture all permutation invariant functions.
4 COMMUTATIVE REGULARIZATION
In the previous section highlighted the importance of having RNN operator that is both commutative and associative. This suggests that in order to learn a permutation invariant RNN we would like learn RNNs under the constraint that associative and commutative. In this section and the remainder of the paper, we focus on the latter, namely introducing a constraint (or equivalently, regularizer) that commutative.
Formally. the constraint that o is commutative corresponds to requiring:
# x о Va, x' E Rd
(4.1)
Recall that depends on the matrices A, W. θ and thus the above constraint translates to a non-linear constraint these three matrices. However, it is not clear how write this constraint in way that facilitates optimization. This will be our goal in what follows.
We begin by replacing requirement 4.1 with
convenient proxy.

---

Under review as a conference paper at ICLR 2019
Lemma 4.1. there exists distribution, D, over R R with non-zero density over its support then
Ex Eu [ x' x
0 Pf x'
Yz, x' Rd
(4.2)
Proof. The proof relies on the fact that for a continuous non-negative random variable, X, is holds that (see Section
B
x
= =1
(4.3)
We now use 4.3 in order to complete the proof. Denote by R the random variable R(x, x') Obviously, R non-negative by definition. Note also that for any pair æ' have | o x' x o = = x x' o a. follows that:
[ x' x'
R 0 = p R= = P xo = x' ox, Vx, x' E R =1
B
(4.4)
The above lemma already gives the strong result that with probability one the network is commutative, In fact a stronger result is possible, stating that the network is commutative for all inputs. We only need to add the restriction of the network A, W, θ Lipschitz. This will hold for example, if restrict A, W, θ to any compact set (e.g., see similar argument in Arjovsky et al. (017).
Lemma 4.2. Assume the network defined by A, W, θ has a Lipschitz constant bounded by K, and that Eq. 4.2 holds under the conditions therein. Then Va, x' holds that x x' x'
Proof. Denote f(x x²) = || x' - x'' x Then f also has a Lipschitz constant bounded by L that a function of K. Assume in contradiction that there exists Tp. T such that f(zg. xg)) for some >> 0. Let [3(c,r) denote an by ball centered at with radius
Then because f is
Lipschitz it follows that for all E [[[ 2/)] z holds that f(z) > 5. Let 7 denote the minimal
density value B[[ x/11, 2 By assumption on we have that 7 > 0. It therefore follows that
P (XX > 0.5c TP 2 [[x0, 2/1, c
27. > 0.5 and therefore TP [(()) 0 and we
have a contradiction with Lemma
As conclusion of lemma 4.1 we can express E || x' x'' 221 in terms of matrices A, W, θ for a specific distribution and derive conditions under which is equal to zero. Definition 4.3. Consider an RNN parameterized by matrices A, W, as in 2.2 with ReLU activation.
A (A, W, O) = Em,
|100 x' x'o x|
(4.5)
Below we show that A(A, W, +) can be expressed as simple function of A, W, O when using the ReLU non-linearity.
Let DD be a multivariate Gaussian distribution with zero mean and covariance identity. In order to calculate A(A, W. Q) we will make use of the following integral (Cho & Saul 2009):
R (u )))(v m)
[=|||||b|2 (sin (0u,v) (It w) cos (fu,v)) g(u,,)) v)
(4.6)
π
turns out that A(A, W. θ) is a simple function of the above g v) function, as stated next.
Let w, denote the tth row of W, 9 the 7th row of θ and a; the 4th column of A. Also, denote the following horizontal stacking of the vectors as
u; = [0
wil
V = [w, 011
(4.7)
and the matrices with these as columns by U and respectively.
c.g. Var, x' e Rd fo(æ, x0) 0
4

---

Under review as a conference paper at ICLR 2019
Theorem 4.4. Assume a, x' are independent Gaussian vectors, each with unit covariance. Then:
AA O)
ai aj (gluss uc)) 2g(u;; 05) + g(U;; 0z))
(4.8)
x
Proof. Define the stacked vector:
The function A(A, O) is given by:
B ||A Ao (Wa Oz²) Ao (Wa' @z)) ! 2
E
(4.9)
We can write 4.9
using definitions in Eq. 4.7 as:
Ao Ao (U² Ao (vTz) ) =E 1 O (== A Ao (U²
E
2E o Uz* A Ao (v*z) (2 A= Ao (v=z)
Denoting ū (Uz), ú (Vz),
write:
E ū A Au
24 A Aö + A"
(4.10)
Letting A Q, we can now write the above as:
h h
E
2 3
+
Σ Σ
Qi
(4.11)
i=1j-1
and more compactly
h
Σ
Qij (ū,ūū 2ūā + ):
(4.12)
writing back ti = olu. 2) and ūi = a o(0; 2) we have
Q B z)o(u, 2) 20(u; 2)0(U,- 2) + o(e 2)0(1,- z)
(4.13)
Using Eq. 4.6, we have that Eq. 4.13 results in the expression in Eq. 4.8
Theorem 4.4 provides an interesting characterization of when an RNN is commutative. As mentioned earlier, an RNN commutative iff A(A, W, O) expression for A it provides measure of non-commutativity which we will optimize in what follows. The function in Eq. 4.8 does not provide clear structual constraints on the matrices A, W, θ but rather elaborate dependence between their elements. The function A indeed achieves value of zero the ReLU implementation the max function discussed the intro, as well as (infinitely) many other commutative state transition functions.
Since the theorem gives closed-form
LEARNING COMMUTATIVE RNNS
In the previous section we obtained a function A(A, W, whose value reflects the degree which the state transition operator o is commutative.
If we could enforce the constraint A(A, W) 0 we could optimize over commutative RNNs. Here we follow standard approach to learning with constraints and add A (AA, W, θ) as a regularizer multiplied by regularization coefficient X > 0 to whatever training loss is being optimized (e.g.. squared error for regression, cross entropy for classification etc). We note that if we have training data for which zero training loss be achieved with commutative RNN, then the optimum of the regularized objective will be a commutative RNN regardless of the value X. We have indeed found this to be the case in experiments.
5

---

Under review as a conference paper at ICLR 2019
RELATED WORK
In recent years, the question of invariances and network architecture has attracted considerable attention, and in particular for various forms of permutation invariances. Several works have focused on characterizing architectures that are "by-design" permutation invariant (Zaheer 2017 Vinyals et al. [016]] Oi et al. 2017 Hartford et al. 2018).
While the above works address invariance for sets, there has also been work on invariance of computations on graphs (Maron et al. 2019 Herzig et al., 2018). In these, the focus is on problems that take graph as input, and the goal is for the output to invariant to all equivalent representations of the graph. Another approach to graph invariant computations are called neural message passing architectures (Gilmer et al. 2017). Finally, there also recent work on graph-based representations and their relation graph-isomorphism (Xu al. 2018).
Our work is a departure from these ideas in two respects. First, the typical approach is to consider an architecture that is invariant by design. Here depart from this by considering architecture that is not generally invariant, but can be invariant for a particular setting of its parameters. This also allows handle cases of "near invariance" where ordering may affect the output in some cases. Second, the typical approach is non temporal, whereas ours puts a specific emphasis on state based computation. This is in fact natural approach for processing data streams, where many algorithms store a sketch of the data and update it as samples arrive (c.g., see Alon et al. 1999).
EXPERIMENTS
In order to demonstrate the versatile nature of commutative RNNs evaluate method several tasks. For each task we compare performance to a relevant DeepSet architecture. In order to fairly compare
implemented our version of DeepSets in TensorFlow. We also explored two aggregation (i.e., pooling) methods for DeepSets: max and sum, both of which were considered in Zaheer et al. (2017).
method to Zaheer et al. (2017)
7.1 SEQUENCES OF DIGITS
Perhaps the simplest suite of problems over sets are basic operations involving sets of digits, as done in Zaheer al. (2017). We evaluate method over three such tasks, Sum, Max and Parity (the latter was not used in the DeepSets paper). we show that commutative RNNs are able to capture all functions easily whereas other baselines struggle and require adaptations to the specific problem at hand. We treat the sum and max experiments as regression problems. Given a set {æ1...., Zn.] where the output,
f(1z1,... xx,) is I-dimensional, we apply the mean square error loss, (f({z1,... : σn,) v)* where y the ground truth. Namely, th I3 and y maxx,21........, for the Sum and Max experiments respectively.
(a) Sum of Digits
(b) Max of Digits
(c) Parity of Digits
Figure 1: Experiments digit sets. All graphs depict accuracy function of the sequence length.
In la and lb a prediction f((=1,... xn )), is considered correct its rounded value equal to the
ground truth, i.e., [f((21,..,,..) xx)) yl 0.5.

---

Under review as a conference paper at ICLR 2019
7.1.1 SUM OF DIGITS
We follow the exact setting described in Zaheer al. (2017). We randomly generate 100k sequences of between 3 to 10 digits long where the label is the sum of the digits of the sequence. We evaluate performance over sequences of lengths of 10 up to 100 digits long. Results are shown in Figure Ta and demonstrate that DeepSets with sum-aggregation and commutative RNNs behave similarly, as expected. However DeepSets with max aggregation does not generalize well.
7.1.2 MAX DIGITS
We perform the exact same experiment as 7.1.1 with the change that the label of a sequence is assigned with the maximal digit the specific sequence. Results are shown in Figure. abland similar to 7.1.1 except here the DeepSet sum does not generalize well.
7.1.3 PARITY
For the parity experiment generate 100k binary sequences of lengths up to 10 where the assigned label if the number of I's in the binary sequence odd and otherwise. As before, we evaluate over sequences with length up 100. Since the parity is binary classification problem, we apply the cross-entropy loss. Results are shown figure Ic Here both variants DeepSets do not generalize well, whereas the commutative architecture has simple solution for the parity aggregation, and therefore generalizes well.
7.2
IMAGE BASED SEQUENCE OF DIGITS
MNIST8m (Loosi et al.) is collection of 8 million 28 x 28 grey-scale images of digits (o......) : 9).
We repeat experiments 7.1.1 and 7.1.2 where instead of sets of numerical values, we use sets of images drawn randomly to create sequences of length up to 10. We evaluate the performance of the learned models on sequences up to length 50. Figure. shows that in both cases the commutative architecture performs well, whereas DeepSets only work when using the true underlying aggregation scheme.
Commenativv
1.8
1.6
35
08-
0.8
Dummitativ Deuplita Sun-Ags pnrppies Max
Sequence Lmngth
Sequiecce Langth
(a) Sum of set of MNIST digits.
(b) Max of a set of MNIST digits.
Figure 2: Experiments on MNIST digits. As seen in the plots, Commutative RNNs without any adaptations perform equally to DeepSet architecture with modified pooling scheme.
EVALUATION ON ECG RECORDINGS
also evaluate on the ECG5000 dataset (Chen et al. 2015), which is a sequence classification problem between normal and abnormal ECG activity. There is no reason to expect this task is pertmutation invariant, but since our method only regularizes for invariance, it can also handle variant data. Results this data for DeepSets, plain RNN and Commutative RNNs gives errors 0.9, 0.944, 0.952 respectively. Thus, indeed the regularizing effect of our methods leads to improved results on variant data well.
7

---

Under review as a conference paper at ICLR 2019
Table 1: Point-cloud Classification
Method
Accuracy
DeepSets
0.83
Commutative RNNs
0.822
Table 2: Accuracy on the ModelNet40 dataset.
8.1 POINT CLOUD CLASSIFICATION
Point clouds are sets of 3-dimensional vectors which represent objects. Such representations of objects useful in various fields such robotics, computer graphics, 3D scanners, etc. The nature of point-clouds suggests that these are order-less objects and thus a natural candidate for evaluation of methods designed handle sets. As in Zaheer al. (2017) we use ModelNet40 Wu et al. (2013), collection of 12k 3D representations of 40 different categories. We treat this as 40-way classification problem. From each 3D representation we produce point-cloud which consists of 100 3-dimensional vectors. Results are shown in Table 2, and are comparable for DeepSets and Commutative RNNs.
To summarize the empirical comparisons above, our results demonstrate that using recurrent methods to handle sets provides results that are more robust to the underlying aggregation method, and can outperform DeepSets in several settings.
DISCUSSION
We have introduced an approach to permutation invariant computation that relies on recursive archi- tectures. While recursive architectures are generally non permutation-ine -nvvrriann we give conditions on their parameters such that they become invariant. The two conditions are that the state transition is associative and commutative. Of these, we focus on the latter, which we show is equivalent to minimizing certain function of the RNN parameters. To do so we integrate the coonccmmuttativity" of inputs with respect to Gaussian distribution. We believe this is a promising approach for other constraints on input space, which may be likewise represented via an appropriate measure over space.
A first natural extension of our approach is seek regularizer for the associative property. We explored using the Gaussian integration for this purpose but the integrals do not seem to have a closed form expression, and are related to integrating multivariate Gaussians under linear constraints, which is considered a hard problem (Miwa et al. 2003). However, it is possible that under other distributions the integral will become feasible, or that some distributions will allow faster mixing of sampling techniques.
Another extension is other activation functions. Our derivation for the commutative regularizer relies on the structure of the ReLU function, but variants such as leaky ReLU can also be ana- lyzed similarly. We leave analysis of other alternatives such as tanh, or more broadly LSTM like architectures for further work.
Here we consider the case of single hidden layer state transition, although we have no constraint on the depth of the networks for v((x) (the input processing stage) and the g(s) (the state to output mapping). We note that one layer transitions are often used in practice, but would interesting to explore regularizers for transitions with more layers.
Another interesting learning-theoreti question is what the sample complexity of learning with commutative and associative regularizers. For example, it might happen that in some cases the com- mutative constraint sufficient to ensure a low enough sample complexity such that generalization is good even without enforcing associativity. Finally, it would be interesting to apply approach to problems that are not "strictly permutation invariant" where regularization is expected to be more effective than hard constraint permutation invariance.
8

---

Under review as a conference paper at ICLR 2019
A PROOF OF EQ. 4.3
Here we prove Eq. 4.3 Let be probability space. Let X a continuous random variable
such that Yo E Q it holds that ((w) > (non-negative). Assume E X O, from Markov inequality,
1 n
PP/ X
< nlE
X
(A.1)
holds for any n > 0. To show that
=
1, given > 0, for any n > 1 we have
0
x
x 0, therefore PP
X > or equivalently, P p(x <
On the other hand, suppose P x = 0] = 1, denote by E = Ω the set on which X(w) * 0. We can write
X(w)dP(w) = -S ((w)dP(W) [ ((w)dP(w)
E
x
(A.2)
where both terms evaluate zero. SE ((w)dP(w) = since E has zero measure with respect to and Soy, X (w)dP(w) = since Ve E X(w) =
REFERENCES
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning, ICMI, 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 214-223 2017. URL http://proceedingg mlr press/770/arjovsky/ 7a html
Yanping Chen, Eamonn Keogh, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, and Gustavo Batista. The uer time series classification archive, July 2015. www. cs..c... .ccreedu/ reamonn/imme series data/
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Y. Bengio, D. Schu- urmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems 22, pp. 342-350. 2009.
Justin Gilmer, Samuel Schoenholz, Patrick F, Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning, pp. 1263-1272, 2017.
Jason Hartford, Devon Graham, Kevin SeyytonBBrown, and Siamak Ravanbakhsh. Deep models of interactions across sets. In International Conference Machine Learning, pp. 1914-1923, 2018.
Roei Herzig, Moshiko Raboh, Gal Chechik, Jonathan Berant, and Amir Globerson. Mapping images to scene graphs with permutation-ine sermutation-invariant structured prediction. Advances in Neural Information Processing Systems, pp. 7211-7221, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. tional neural networks. In Advances neural information processing systems, pp. 1097-1105, 2012.
Imagenet classification with deep convolu-
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invant inviaaiiiinnnnniaanttt neural networks. In Proceedings of the 35th International Conference on Machine Learning, 2019.
Gaëlle Loosli, Stéphane Canu, and Léon Bottou. Training invariant support vector machines using selective sampling.
Haggai Maron, Heli Ben Hamu, Naday Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In 7th International Conference Learning Representations, ICLR, 2019.

---

Under review as a conference paper at ICLR 2019
Tetsuhisa Miwa, AJ Hayter, and Satoshi Kuriki. The evaluation of general non-centred orthant probabilities. Journal of the Royal Statistical Society: Series (Statistical Methodology), 65(1): 223-234, 2003.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point for 3d classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 652 660, 2017.
Matus Telgarsky. Neural networks and rational functions. Proceedings of the 34th International Conference Machine Learning-Volume 70, pp. 3387-3393. JMLR. org, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912-1920, 2015.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 6th International Conference Learning Representations, ICLR, 2018.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander Smola. Deep Sets. In Advances in neural information processing systems, pp. 3391-3401, 2017.
10


Reviews:
[{"review_id": "rye8e_rTFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: this paper proposes a new principled methodology for deriving and training RNN neural networks for prediction of permutation invariant functions. Authors show on simple tasks their method may outperform DeepSets, the state of the art.\n\n\nAlthough the idea is interesting and the paper reflects thorough work, I believe in its current form results are too weak to deserve publication. More specifically.\n\n1)Mathematical results and statements are mostly trivial and may well be omitted or included as an appendix. They don't seem to convey anything profound (with the exception of theorem 3.6, but this follows from results on deepsets paper). Some of these results are also mostly anectodal \n\n2)The regularization idea seems interesting, but I am concerned it is showing that the final learned networks have a deepset-like architecture: more specifically, theorem 3.6 shows RNN can implement permutation invariant functions by making identifying the parameters with the ones of deepperm. Also, as the authors mentioned, when learning a permutation invariant function then for any degree of regularization the regularization loss can be made zero. So for me, results seem to indicate that the network might have learned a deepperm kind of representation, which equivalently can be expressed as a RNN. Authors should make clear there are fundamental differents between both frameworks\n\n3)Overall, the experimental validation section is weak and an extensive description of network architectures is lacking. Without them it is hard to resolve my concerns on 2). ", "extra_scores": {"experience_assessment": "I have published one or two 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": "SkeVXO9RKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper starts with presenting an RNN formulation and essentially writing out the sequence of RNN applications. Not surprisingly, if these applications were associative and commutative the RNN would be permutation invariant.  Then a condition for commutativity is formulated in terms of an expectation of a difference.  Based on a prior result, it is shown that the expectation can be computed in closed form.  Although it is not shown if an RNN regularized that way is permutation invariant, since the associativity is not demonstrated, empirically it is shown that it may be already of use.\n\n   Contributions:\n   1. A regularizer for RNNs that enforces commutativity\n   2. A closed form for computing it\n   3. A fully learnable permutation invariant \"deep\" network, per an empirical demonstration\n\n   The main contribution is the empirical demonstration of the learnable nature of the obtained function unlike the prior art (e.g.  DeepSets) where a choice of the aggregation function severily affects the results.\n\n    The theoretical component of the paper is unclear:\n      1. Section 3 is rather trivial.\n      2. Theorem 3.6 is hard to connect to an RNN and the rest of the paper. Unclear why bother learning the RNN at all if it needs to converge to addition of the input and hidden state to be universal anyway.\n      3. In essence, the result of the paper is a way to encourage commutativity in an RNN and a demonstration that it works in practice for encouraging permutation invariance. The other explanations make things confusing and do not seem to contribute to the rest of the paper.\n\nCould it be that the network indeed learns addition operator?  RNNs usually are only able to operate on very small sequences because of the vanishing gradient problem, yet the proposed approach will not directly work on the more robust LSTM.\n\nSignificance or lack of the difference between the proposed method and DeepSets is unclear as the plots are missing the error bars.\n\n The table and the accuracies reported in Section 8 are impossible to interpret. It is unclear whether the authors done cross validation.  If so, it would be helpful to see standard deviations of the reported numbers\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "ByxIDYM0KS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The rebuttal did not address my concerns convincingly. There were also simple fixes that the authors could have implemented but they decided not to update the paper. I will keep my original assessment. \n\n--------------\n\nThe premise of the work is very interesting: RNNs that are permutation-invariant. Unfortunately, the paper seems rushed and needs a better justification for not having a RNN memory that is associative. It also should cast the contributions in light of other existing work (not cited). The paper says \"In this section and the remainder of the paper, we focus on the latter [commutative RNN memory operator], namely introducing a constraint (or equivalently, regularizer) that is commutative\", but it never talks about the impact of a RNN memory using a non-associative operator. Being commutative is easy, isn't Equation (2.4) commutative if \\Theta = W? Being associative is hard, since non-linear activations are not easily amenable to associativity.\n\nSection 4: \"The above example demonstrates that RNNs can in some cases be a natural computational model for permutation invariant functions.\" => Janossy pooling (Murphy et al., 2019) gives an alternative way to use RNNs, with a way to make their method tractable. Actually, my guess to why the RNNs experiments work well, even without an associative memory, is because the training examples come in multiple permuted forms, which is the data-augmentation version of the pi-SGD optimization described in Janossy pooling. \n\nOn page 1, \"consider the problem of computing the permutation invariant function f(x_1, . . . , x_n) = max_i x_i\", what follows is not a proof of necessity. It is an informal argument that either should be made formal or should be described as informal.\n\nThere is a lot of missing related work for sets:\nMurphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. \"Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs.\" ICLR 2019.\nWagstaff, Edward, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, and Michael Osborne. \"On the limitations of representing functions on sets.\" ICML 2019.\nLee, Juho, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. \"Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks.\" ICML 2019.\n\nAlso missing related work for graphs:\nBloem-Reddy, Benjamin, and Yee Whye Teh. \"Probabilistic symmetry and invariant neural networks.\" arXiv:1901.06082 (2019).\nMurphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. \"Relational Pooling for Graph Representations.\" ICML 2019.\n\nThe paper has an interesting question but needs to build on prior work. As of now, I am unconvinced that not having an associative operator for the RNN memory will lead to a good nearly permutation invariance function (unless there is data augmentation, per Janossy pooling).\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines learning problems where the network outputs are intended to be invariant to permutations of the network inputs.  Some past approaches for this problem setting have enforced permutation-invariance by construction.  This paper takes a different approach, using a recurrent neural network that passes over the data. The paper proves the network will be permutation invariant when the internal state transition function is associative and commutative.  The paper then focuses on the commutative property by describing a regularization objective that pushes the recurrent network towards becoming commutative.  Experimental results with this regularizer show potentially better performance than DeepSet, another architecture that is designed for permutation invariance.

The subsequent discussion of the paper raised several concerns with the current version of the paper. The theoretical contributions for full permutation-invariance follow quickly from the prior DeepSet results.  The paper's focus on commutative regularization in the absence of associative regularization is not compelling if the objective is really for permutation invariance.  The experimental results were limited in scope.  These results lacked error bars and an examination of the relevance of associativity. The reviewers also identified several related lines of work which could provide additional context for the results that were missing from the paper.

This paper is not ready for publication due to the multiple concerns raised by the reviewers.  The paper would become stronger by addressing these concerns, particularly the associativity of the transition function, empirical results, and related work. 
Decision: Reject