Humans understand novel sentences by composing meanings and roles of core language components. In contrast, neural network models for natural language modeling fail when such compositional generalization is required. The main contribution of this paper is to hypothesize that language compositionality is a form of group-equivariance. Based on this hypothesis, we propose a set of tools for constructing equivariant sequence-to-sequence models. Throughout a variety of experiments on the SCAN tasks, we analyze the behavior of existing models under the lens of equivariance, and demonstrate that our equivariant architecture is able to achieve the type compositional generalization required in human language understanding.
Summary
---
(motivation)
Consider SCAN, a synthetic task where setences like S1="jump twice and run left" are supposed to be translated into action sequences like A1=JUMP JUMP LTURN RUN. One might replace the word "jump" in S1 with "walk" then translate to get A2=WALK WALK LTURN RUN. If instead S1 is translated into A1 and then the action JUMP is replaced with the action WALK then we should still get the same A2. Such a translation model is equivariant to permutations of "jump" and "walk".
This paper aims to
1) define a general notion of compositionality as equivariance,
2) build a model which is compositional in this general sense, and
3) apply the model to SCAN.
(approach - theory)
This work considers this kind of compositionality as equivariance to group actions. Previous work (Kondor & Trivedi, 2018) viewed convolution as equivariance to actions by translation groups. This work views language compositionality as equivariance to actions by permutation groups applied to a set of similar words (e.g. verbs in SCAN).
(approach - model)
The paper proposes G-Embed, G-RNN, G-Attention, and G-Conv (not new) layers that are equivariant to word permuatations (e.g., switching "jump" and "walk"). It then composes these modules in a fairly standard fashion to build a new G-seq2seq model which is invariant to group actions.
(experiments)
Experiments apply a G-seq2seq model to the SCAN tasks, comparing to strong baselines. G-seq2seq requires slightly more knowledge (a set of related words like verbs) than all the baselines, but less knowledge than Lake 2019.
1. G-seq2seq outperforms all baselines except Lake 2019 (unfair comparison) on basic compositional tasks ("Add Jump" and "Around Right").
2. Like other models, G-seq2seq fails on the "Length" task, though it is still among the best performers.
Strengths
---
The theory of compositionality as invariance to actions by permutation groups is new, interesting, and could turn out to be significant.
The proposed models are also new, interesting, and could be significant.
Experiments on SCAN verify that the proposed models work about as expected, sometimes beating strong baselines in the process.
Weaknesses
---
It's hard to know what the impact of this paper will be because 1) it's unclear whether this model can generalize to more useful domains and 2) the presentation may turn some readers away. While neither of these issues can really be solved, I think paper could be substantially better in both aspects. Corresponding suggestions:
1) How expensive is this? It seems quite expensive because the representation size scales with the number of permutation of the set of words equivariance is with respect to. How will it scale to larger problems in terms of computation/memory costs (especially larger vocab sizes)? What knowledge is required for applying this method to new domains--i.e., how do I choose a set of permutation equivariant verbs in general? More discussion of these issues may help increase the impact of the paper.
2) See next section.
Presentation Weaknesses / Points of Confusion / Missing Details
---
To mimic a typical decoder RNN there should be another input which copies the word \tilde{w}_{t-1} from the previous iteration as input, somehow fused with the attention feature \tilde{a}_t. How does the G-RNN know what the last word it generated was?
The notation $g^{-1} w$ in the first equation of section 4.1: I think $\psi^i$ is supposed to take an integer as input but $g^{-1} w$ is a permutation applied to a function. I'm not sure how to apply permutations to functions like w and it doesn't seem like the output should be an integer in any case so I find this notation confusing.
Taking a step back, I find some of the notation (e.g., previous point) a bit confusing. This makes it hard for me to get the main point. I think the idea is that equivariant models can be achieved by tracking a representation (e.g., via rows of the G-Embed matrix) for (almost?) every member of the acting group.
It may help the presentation to more frequently demonstrate the general concepts with examples, though doing so may be in conflict with the general nature of the paper's theoretical contribution. I'm sure this is a familiar tradeoff, but from my perspective the paper would probably be more impactful if the presentation leaned more on examples.
Equation numbers would be a really great addition. I found it hard to reference some of the material in writing my review.
"and the use of algebraic computation"
* This seems specific to the chosen example whereas the rest of the sentence is trying to be general.
Suggestions
---
* This seems related to [1], which uses group theory to define a notion of disentangled representation similar to compositionality. That may inspire future work and would be useful to mention in the related work.
* Why didn't performance on SCAN get to 100%? It would be useful to spend some time addressing points of failure for the model other than compositionality.
* The G-RNN doesn't have a bias. It's not necessary, but it may be interesting to describe why this design choice was made.
[1]: Higgins, Irina et al. “Towards a Definition of Disentangled Representations.” ArXiv abs/1812.02230 (2018): n. pag. 
Preliminary Evaluation
---
Quality: The theoretical contributions make sense and the experiments show they lead to useful models.
Clarity: The technical parts of the paper are somewhat unclear, but the rest of the paper is well written.
Significance: As discussed in the Weaknesses section this could turn out to be very significant or not significant at all, but that's true for a lot of good research.
Originality: The general notion of equivariant neural networks and good performance on SCAN are novel.
Overall, this is a very clear accept.
Post-Rebuttal Update
---
There was a lot of agreement between reviewers, though we came to slightly different conclusions about ratings. Though there is significant uncertainty about the impact of this work, I still think 8: Accept is the most appropriate rating. Overall, the other reviews and author responses only increased my confidence that this paper should be accepted.