Structured Reordering for Modeling Latent Alignments in Sequence Transduction
Authors: bailin wang
Mirella Lapata
Ivan Titov
Venue: NeurIPS 2021 Poster (2021)
Keywords: language understanding
sequence models
latent variable models
compositional generalization
systematic generalization

Abstract: Despite success in many domains, neural models struggle in settings where train and test examples are drawn from different distributions. In particular, in contrast to humans, conventional sequence-to-sequence (seq2seq) models fail to generalize systematically, i.e., interpret sentences representing novel combinations of concepts (e.g., text segments) seen in training. Traditional grammar formalisms excel in such settings by implicitly encoding alignments between input and output segments, but are hard to scale and maintain.  Instead of engineering a grammar, we directly model segment-to-segment alignments as discrete structured latent variables within a neural seq2seq model. To efficiently explore the large space of alignments, we introduce a reorder-first align-later framework whose central component is a neural reordering module producing separable permutations. We present an efficient dynamic programming algorithm performing exact marginal inference of separable permutations, and, thus, enabling end-to-end differentiable training of our model.  The resulting seq2seq model exhibits better systematic generalization than standard models on synthetic problems and NLP tasks (i.e., semantic parsing and machine translation).

Structured Reordering for Modeling Latent Alignments in Sequence Transduction
Bailin Wang's Mirella Lapata' Ivan 1.2
University of Edinburgh University of Amsterdam *Innopolis University bailin. wang@ed. ac. uk, fmlap, ititov]@nnt ed. ac uk
Abstract
Despite success many domains, neural models struggle in settings where train and test examples drawn from different distributions. In particular, in contrast to humans, conventional sequence-to-sequenee (seq2seq) models fail to generalize systematically, i.e., interpret sentences representing novel combinations of concepts (e.g., text segments) seen in training. Traditional grammar formalisms excel in such settings by implicitly encoding alignments between input and output segments, but are hard to scale and maintain. Instead of engineering a grammar, we directly model sonnentttt-segmeeet alignments as discrete structured latent variables within neural seq2seq model. To efficiently explore the large space of alignments, we introduce reorder-firtt align-later framework whose central component is neural reordering module producing separable permutations. We present an efficient dynamic programming algorithm performing exact marginal and MAP inference of separable permutations, and, thus, enabling end-to-end differentiable training of our model. The resulting seq2seq model exhibits better systematic generalization than standard models synthetic problems and NLP tasks (i.e., semantic parsing and machine translation).
Introduction
Recent advances in deep learning have led to ma- jor progress in many domains, with neural models sometimes achieving or even surpassing human perfor- mance 449. However, these methods often struggle in out-of-distribution (ood) settings where train and test ex- amples are drawn from different distributions. In partic- ular, unlike humans, conventional sqquence-to-sequemee (seq2seq) models. widely used in natural language pro- cessing (NLP). fail to generalize systematically [4] [2] (28,,
Training Examples
what is the length of the colorado river
len river( riverid 'colorado'
what is the longest river
longest( river( all )
ie.. correctly interpret sentences representing novel combi- nations of concepts seen in training. Our goal to provide mechanism for encouraging systematic generalization in seq2seq models.
Test Example
what is the length of longest river
len( longest( river( all )
To get an intuition about our method, consider the semantic parsing task shown in Figure [ learner needs to map natural language (NL.) utterance to program which can then be executed on a knowledge base. To process the test utterance, the learner needs to first decompose it into two segments previously observed in training (shown in green and blue), and then combine their corresponding program fragments to create
semantic parser needs to generalize to test examples which con- tain segments from multiple training amples (shown in green and blue).
Figure 1:
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

program. Current seq2seq models fail in this systematic generalization setting [12 [2] In contrast, traditional grammar formalisms decompose correspondences between utterances and programs into compositional mappings of substructures [46], enabling grammar-based parsers to recombine rules acquired during training, as needed for systematic generalization. Grammars have proven essential in statistical semantic parsing in the pre-neural era [7], and have gained renewed interest now as a means of achieving systematic generalization [18,4]] However, grammars are hard to create and maintain (e.g., requiring grammar engineering or grammar induction stages) and do not scale well to NLP problems beyond semantic parsing (e.g., machine translation). In this work, we argue that the key property of grammar- based models, giving rise to their improved ood performance, is that grammar implicitly encodes alignments between input and output segments. For example, in Figure [ the expected segment-lever alignments are 'the length + len and 'the longest river longest (river (all))'. The encoded alignments allow for explicit decomposition of input and output into segments, and consistent mapping between input and output segments. In contrast, decision rules employed by conventional seq2seq models do not exhibit such properties. For example, recent work [15] shows that primitive units such as words usually inconsistently mapped across different contexts, preventing these models from generalizing primitive units to new contexts. Instead of developing a full-fledged grammar-based method, we directly model segment-level alignments as structured latent variables. The resulting alignment-driven seq2seq model remains end-to-end differentiable, and, in principle, applicable to any sequence transduction problem.
Modeling segment-level alignments requires simultancously inducing a segmentation of input and output sequences and discovering correspondences between the input and output segments. While segment-level alignments have been previously incorporated in neural models (50 (55), to maintain tractability,, these approaches support only monotonic alignments. The monotonieity assumption is reasonable for certain tasks (e.g.. summarization), but it is generally overly restrictive (e.g., consider semantic parsing and machine translation). To relax this assumption, we complement monotonic alignments with an extra reordering step. That is, we first permute the source sequence so that segments within the reordered sequence can be aligned monotonically segments of the target sequence. Coupling latent permutations with monotonic alignments dramatically increases the space of admissible segment alignments.
The space of general permutations is exceedingly large, so, to allow for efficient training, we restrict ourselves separable permutations (5). We model separable permutations hierarchical reordering of segments using permutation trees. This hierarchical way of modeling permutations reflects the hierarchical nature of language and hence is arguably more appropriate than 'flat' alternatives [B3]. Interestingly, recent studies [45] (4) demonstrated that separable permutations are sufficient for capturing the variability of permutations linguistic constructions across natural languages, providing further motivation for our modeling choice.
Simply marginalizing over all possible separable permutations remains intractable. Instead, inspired by recent work on modeling latent discrete structures [9] [4], we introduce a continuous relaxation of the reordering problem. The key ingredients of the relaxation are two inference strategies: marginal inference, which yields the expected permutation under a distribution; MAP inference, which returns the most probable permutation. In this work, we propose efficient dynamic programming algorithms to perform exact marginal and MAP inference with separable permutations, resulting in effective differentiable neural modules producing relaxed separable permutations. By plugging these modules into an existing module supporting monotonic segment alignments (55), we obtain end-to-end differentiable seq2seq models, supporting non-monotonic segment-level alignments.
In summary, our contributions are:
A general seq2seq model for NLP tasks that accounts for latent non-monotonic segment-level alignments.
Novel and efficient algorithms for exact marginal and MAP inference with separable permu- tations, allowing for end-to-end training using a continuous relaxation [
Experiments on synthetic problems and NLP tasks (semantic parsing and machine transla- tion) showing that modeling segment alignments is beneficial for systematic generalization.
'Our code and data are available at httpp///ggtthbocaa//rrrrl///o//t
2

---

2 Background and Related Work
2.1 Systematic Generalization
Human Iearners exhibit systematic generalization, which refers to their ability to generalize from training data to novel situations. This is possible due to the compositionality of natural languages to a large degree, sentences are built using an inventory of primitive concepts and finite structure- building mechanisms [8] For example, if one understands 'John loves the girl', they should also understand 'The girl loves John' [13]. This is done by "knowing' the meaning of individual words and the grammatical principle of subject-verb verboobeee composition. As pointed out by Goodwin et al. 15 systematicity entails that primitive units have consistent meaning across different contexts. In contrast, in seq2seq models, the representations experiments in Lake and Baroni (27). This is also consistent with the observation that seq2seq models tend to memorize large chunks rather than discover underlying compositional principles [20]. The memorization of large sequences lets the model fit the training distribution but harms out-of- distribution generalization.
word are highly influenced by context (see
2.2 Discrete Alignments as Conditional Computation Graphs
Latent discrete structures enable the incorporation of inductive biases into neural models and have been beneficial for range of problems. For example, input-dependent module layouts [2] or graphs [77 have been explored in visual question answering. There is also large body of work on
inducing task-specific discrete representations (usually trees) for NI. sentences [9] [7] (36 [54]. The trees are induced simultancously with learning model performing a computation relying tree (typically a recursive neural network [43)), while optimizing a task-specific loss. Given the role the structures play in these approaches - i.e., defining the computation flow we can think of the structures as conditional computation graphs.
the
In this work, we induce discrete alignments as conditional computation graphs to guide seq2seq models. Given source sequence r with n tokens and target sequence y with m tokens, we optimize the following objective:
X (ncodes(x)
Co y) log PP (X, M)
(1)
where Encode is a function that embeds x into X E TR with h being the hidden size, M E {0, 1 >> is the alignment matrix between input and output tokens. In this framework, alignments M are separately predicted by po [MMM[X] to guide the computation pe (y) X, M) that maps to y.
The parameters of both model components (ø and 0) are disjoint.
Relation to Attention Standard encoder-decoder models 33 rely on continuous attention weights i.e. M a: E A=-1 for each target token < i < m. Discrete versions of attention (aka hard attention) have been studied in previous work [1] 53] and show superior performance in certain tasks. In the discrete case M is sequence of m categorical random variables. Though discrete, the hard attention only considers word-level alignments, i.e., assumes that each target token is aligned with a single source token. This is a limiting assumption; for example, in traditional statistical machine translation, word-basee models (e.g., (6]) are known to achieve dramatically weaker results than parase-based models (e.g., (26)). In this work, we aim to bring the power of phrase-level (aka segment-level) alignments neural seq2seq models.
3 Latent Segment Alignments via Separable Permutations
Our method integrates a layer of segment-level alignments with a seq2seq model. The architecture of our model shown in Figure 2 Central to this model the alignment network, which decomposes the alignment problem into two stages: (i) imput reordering and (ii) monotonic alignment between the reordered sequence and the output. Conceptually, we decompose the alignment matrix from Eq [ into two parts:
M Mpn
"One of our models (see Section 3.2 still has flavor of standard continuous attention in that it approximates discrete alignments with continuous expectation.
3

---

original encoding
how many states do not have rivers reordered encoding
Structured Reordering
Monotonic Decoding
count exclude state_ __all loc 1 river_ai all
The architecture of seq2seq model for semantic parsing. After encoding the input utterance, our model permutes the input representations using our reordering module. Then, the reordered encodings will be used for decoding the output program in monotonic manner.
Figure 2:
where Mpe E R is a permutation matrix, and Mmo E _axm represents monotonic alignments. With this conceptual decomposition, we rewrite the objective in Eg T as follows:
Lo y) log Ep. Pp (MM...,
M X,, M
(3)
where M denotes the reordered representation. With slight abuse of notation, & now de- notes the parameters of the model generating permutations, and ø' denotes the parameters used to produce monotonic alignments. Given the permutation matrix Mpe- the second expectation ( M Pa (yl M X. M.)), which we denote as pe.æ' (y) pM can be handled by existing methods, such as SSNT (55) and SWAN [50]. In the rest of the paper, we choose SSNT as the module for handling monotonic alignment We can rewrite the objective optimize in the following
compact form:
La (x, u) log (Ma(M)) Mp)
3.1 Structured Latent Reordering by Binary Permutation Trees
Inspired by Steedman 47 we restrict word reorderings to separable permutations. Formally, separa- ble permutations are defined in terms of binary permutation trees (aka separating trees (5)), i.e. if per- mutation can be represented by a permutation tree, it is separable. A binary permutation tree over per- mutation of sequence 1 is binary tree in which each node represents the ordering of segment f. the children exhaustively split their parent into sub-segments i... and Is + 1++1... +1..... Each node has binary label that decides whether the segment of the left child precedes that of the right child. Bracketing transduction grammar [BTG, [2), which is proposed in the context of machine translation, is the cor- responding context-free grammar to represent binary per- mutation trees. Specifically, BTG has one non-terminal (X) and three anchored rules:
X1,6
X1,4
X1,3
X
Si : X Straight X x
X1,2 the
X2,3
X1,4
Xa,5
X5,6
I.j.k : x
Invented
X X
girl saw the hedgehog
x
24
Figure 3: The tree represents the re- ordered sentences 'saw the girl the hedgehog' where A, denotes Inverted and Straight, respectively.
where X the anchored non-terminal covering the seg- ment from to & (excluding k). The first two rules decide whether to keep or invert two segments when construct- ing larger segment; the last rule states that every word
in an utterance is associated with non-terminal X An example shown in Figure 3 Through this example, we note that the first two rules only signify which segments to inverse; additional process of interpreting the tree (i.e., performing actual actions of keeping or inverting segments) is needed to obtain the permutated sequence. This hierarchical approach generating separable permutations reflects the compositional nature of language, and, thus, appears more appealing than using 'flat' alternatives [10] 16 33 Moreover, with BTGs, we can incorporate segment-level features to model separable permutations, and design tractable algorithms for learning and inference.
In initial experiments, found that SWAN works as well as SSNT but is considerably slower.

---

By assigning score to each anchored rule using segment-level features, we obtain a distribution over all possible derivations, and use it to compute the objective in Eq
P+ (D(x)) IR (Q(R)
x) (o,0))((1, = log (D (v) Mo pc
(5)
Z Φ)
where fe is a score function assigning a (non-negative weight to an anchored rule R E (S, TT T). (zz Φ) = Ep, IRED (R) is the partition function, which can be computed using the inside algorithm, MP is the permutation matrix corresponding to the derivation D. BTG, along with the weight assigned for each rule, is a weighted context-free free grammar (WCFG). In this WCFG, the weight is only normalized at the derivation level. As will see in Algorithm we are interested in normalizing the weight of production rules and converting the WCFG to an equivalent PCFG following Smith and Johnson 42 so that the probability of derivation can be computed follows:
Ps (D(p)) x))
II ()
RED
where (R) is the weight of the production rule R under the transformed PCFG. The details of the conversion are provided in the Appendix.
The challenge with optimizing the objective in Eq is that the search space of possible derivations exponential, making the estimation of the gradients with respect to parameters of the reordering component (Ø) non-trivial. We now present two differentiable surrogates we use.
3.2
Soft Reordering: Computing Marginal Permutations
The first strategy is to use the deterministic ex- pectation of permutations to softly reorder sentence, analogous to the way standard atten- tion approximates categorical random variables. Specifically, we use the following approxima- tion:
Algorithm 1 Dynamic programming for comput- ing marginals and differentiable sampling of per- mutation matrix wrt. parameterized grammar
Input: (R( probability of an anchored rule R sampling: whether perform sampling
Mye Mp pe La. (2. v) R Po (yl X)
1: for := to n do
2:
E
1
3: end for
where M is the marginal permutation matrix, and it can be treated as structured attention 255) Methods for performing marginal inference for anchored rules, i.e., computing the marginal dis- tribution of production rules are well-known in NLP [32). However, we are interested in the marginal permutation matrix (or equivalently the expectation of the matrix components) as the matrix is the data structure that is ultimately used in our model. As a key contribution of this work, we propose an efficient algorithm to ex- actly compute the marginal permutation matrix using dynamic programming.
4: for w == 2 to n do
> width of spans
5:
for = to n
w + 1 do
6:
k: = - w
7:
if sampling then
8:
Go( s_ s_arg max ( ( (t)
9:
else
computing marginals
GR G
11:
end
if
for
j := + 1 to k- do
E += (g(,),, EE E
14:
E +- G p (Zi..t)) EE))
end for 16: end for
15:
In order to compute the marginal permutation matrix we need to marginalize over the expo- nentially many derivations of each permutation. We propose to map derivation of BTG into its corresponding permutation matrix in a recursive
17:
end for
18: return E
manner. Specifically, we first associate word i with an identity permutation matrix M,+1 = 1; then associate Straight and Inverted rules with direct $ and skew @ sums of permutation matrices, respectively:
A
0
To
A
A o B
A
0
B
B
0
For example, the permutation matrix of the derivation tree shown in Figure 3 can be obtained by:
M ((IM3 @ M3) e M1) @ (M² a Mg)
(7)
5

---

Intuitively, the permutation matrix of long segments can be constructed by composing permutation matrices of short segments. Motivated by this, we propose dynamic programming algorithm, which takes advantage of the observation that we can reuse the permutation matrices of short segments when computing permutation matrices of long segments, as shown in Algorithm|]] While the above equation is defined over discrete permutation matrices encoding a single derivation, the algorithm applies recursive rules to expected permutation matrices. Central to the algorithm is the following recursion:
E
Go(SLe,)) + E + Go(Taa)) e E K
Σ
(8)
where E is the expected permutation matrix for the segment from to k: G is the probability
of employing the production rule R. defined in Eq Overall, Algorithm T Tis bottom-up method
that constructs expected permutation matrices incrementally in Step 13 and [4 while relying on the
probability of the associated production rule. We prove the correctness of this algorithm by induction the Appendix.
3.3 Hard Reordering: Cuumbel-Permutation by Differentiable Sampling
During inference, for efficiency, it is convenient to rely on the most probable derivation D' and its corresponding most probable y:
arg max Pe (y) MD) X)
where D' = arg maxp Po (Diz). The use of discrete permutations MD D' during inference and soft reining-inference reorderings during training lead training- inference gap which may be problematic. Inspired by
recent Gumbel-Softmax operator [21 31 that relaxes the sampling procedure of a categorical distri- bution using the Gumbel-Max trick, we propose differentiable procedure to obtain an approximate sample M from p( [[)).. Concretely, the Gumbel-Softmax operator relaxes the perturb-and-MA. procedure (39], where we add noises to probability logits and then relax the MAP inference (i.e., arg max in the categorical case); we denote this operator as s s_arg max. In our structured case, we perturb the logits of the probabilities of production rules (RR), and relax the structured MAP inference for our problem. Recall that p(D ()) is converted to PCFG, and MAP inference for PCFG is algorithmically similar to marginal inference. Intuitively, for each segment, instead of marginalizing over all possible production rules in marginal inference, we choose the one with the highest probability (i.e., a local MAP inference with categorical random variables) during MAP inference. By relaxing each local MAP inference with Gumbel-Softmax (Step & of Algorithm [ we obtain a differentiable sampling procedure. D We choose Straight-Through Gumbel-Softman so that the return of Algorithm [ is discrete permutation matrix, and in this way close the training-inference gap faced by soft reordering.
Summary We propose two efficient algorithms for computing marginals and obtaining samples of separable permutations with their distribution parameterized via BTG. In both algorithms, PCFG plays important role of decomposing global problem into sub- -robplls,ems which explains why convert p(D|x) into a PCFG in Eq 6 Relying on the proposed algorithms, we present two relaxations of the discrete permutations that let induce latent reorderings with end-to-end training. We refer to alignments. denote the versions which use soft marginal permutations and hard Gumbel permutations, respectively.
the resulting system as ReMoto, short for a seq2seq model with
Soft-ReMoto and
Segment-Level Alignments Segments are considered the basic elements being manipulated in our reordering module. Concretely, permutation matrices are constructed by hierarchically reordering input segments. SSNT, which is the module top of our reordering module for monotonically generating output, conceptually also considers segments as basic elements. Intuitively, SSNT alternates between consuming an input segment and generating an output segment. Modeling segments provides strong inductive bias, reflecting the intuition that sequence transduction in NLP can be largely accomplished by manipulations the level of segments. In contrast, there is no explicit notion of segments in conventional seq2seq methods.
'If we change s_ s_arg max with arg max in Step & of Algorithm we will obtain the algorithm for exact MAP inference.

---

Dataset
Input
Output
Arithmetic SCAN-SP GeoQuery
((1 + 9) ((7 + 8)/4))
((19+) +)/)))
jump twice after walk around left thrice
after (twice (jump), thrice(walk (around, left)))
how many states do not have rivers?
count(xxclude(stat((al))) loc_ (river((all))
Table Examples of input-output pairs for parsing tasks.
Arithmetic
SCAN-SP
Model
IID
LEN
IID
LEN
Seq2Seq
100.0
0.0
100.0
13.9
LSTM-based Tagging
100.0
20.6
100.0
57.7
Sinkhom-Attention Tagging
99.5
8.8
100.0
48.2
Roft-ReMoto
100.0
86.9
100.0
TOO.0
-shared parameters
100.0
40.9
100.0
100.0
Herd-ReMoto
100.0
83.3
100.0
100.0
Table 2: Accuracy (%) the arithmetic and SCAN-SP tasks.
However, different from reordering module where segments first-class objects during modeling, the alternating process of SSNT is realized by a series of token-level decisions (e.g., whether to keep consuming the next input token). Thus, properties of segments (e.g., segment-level features) are not fully exploited in SSNT. In this sense, one potential way to further improve ReMoto is to explore better alternatives to SSNT that can treat segments first-class objects well. We leave this direction for future work.
Reordering in Previous Work In traditional statistical machine translation (SMT), reorderings are typically handled by distortion model [e.g..[[] in a pipeline manner. Neubig et [35), Nakagawa [44] and Stanojević and Sima' an [4] also use BTGs for modeling reorderings. Stanojević and Sima'an 44 go beyond binarized grammars, showing how to support 5-ary branching permutation trees. Still, they assume the word alignments have been produced on preprocessing step, using an alignment tool [38] Relying on these alignments, they induce reorderings. Inversely, we rely on latent reordering to induce the underlying word and segment alignments.
Reordering modules have been previously used in neural models, and can be assigned the following two categories. First, reordering components [9] were proposed for neural machine translation. However, they are not structured or sufficiently constrained in the sense that they may produce invalid reorderings (e.g., a word is likely to be moved to more than one new position). In contrast, our module is a principled way of dealing with latent reorderings. Second, the generic permutations (i.e., one-to-one matchings or sorting), though having differentiable counterparts [IO] 33], do not suit our needs as they are defined in terms of tokens, rather than segments. For comparison, in our experiments, we design baselines that are based on Gumbel-Sinkhorn Network [33] which is used previously in NLP (e.g., (30)]
4 Experiments
First, we consider two diagnostic tasks where test the neural reordering module on its own. Then we further assess our general seq2seq model ReMoto on two real-world NLP tasks, namely semantic parsing and machine translation.
4.1 Diagnostic Tasks
Arithmetic We design a task of converting an arithmetic expression in infix format the one in postfix format. An example is shown in Table [ We create synthetic dataset by sampling data from PCFG. In order to generalize, a system needs to learn how manipulate internal sub-structures (i.e., segments) while respecting well-formedness constraints. This task can be solved by the shunting- yard algorithm but we are interested to see neural networks can solve it and generalize ood by learning from raw infix-postfix pairs. For standard splits (IID), we randomly sample 20k infix-postfix pairs whose nesting depth is set to be between and 6; 10k, 5k, 5k of these pairs are used as train, dev and test sets, respectively. To test systematic generalization, create Length split (LEN) where
7

---

training and dev examples remain the same as IID splits, but test examples have a nesting depth of 7. In this way, we test whether a system can generalize unseen longer input.
SCAN-SP We use the SCAN dataset [27], which consists of simple English commands coupled
with sequences of discrete actions. Here we use the semantic parsing version, SCAN-SP [8. where the goal is to predict programs corresponding to the action sequences. An example is shown in Table [ As in these experiments our goal is to test the reordering component alone, we remove parentheses and commas in programs. For example, the program after (twice (jump), thrice (walk (around, left))) is converted to sequence: after twice jump thrice walk around left. In this way, the resulting parentheses- the NL utterance 'jump twice after walk around left thrice'. The grammar of the programs is known so we can reconstruct the original program from the intermediate parentheses- the grammar. Apart from the standard split (IID, aka simple split (27)) we create a Length split (LEN) where the training set contains NL utterances with a maximum length 5, while utterances in the dev and test sets have minimum length of 6
sequence can be viewed as a reordered sequence of
sequences using
In both diagnostic tasks, we use ReMoto with a trivial monotonic alignment matrix Mmo (an identity matrix) in Eq Essentially, ReMoto becomes a sequence tagging model. We consider three baselines: (1) vanilla Seq2Seq models with Luong attention (2);; (2) an -TM--baed tagging model which learns the reordering implicitly, and can viewed as a version ReMoto with a trivial Mp and Mm:: (3) Sinkhorn Attention that replaces the permutation matrix of Roft-ReMoto in Eq 4 by Gumbel-Sinkhorn networks
Baselines and Results
We report results by averaging over three runs in Table In both datasets, almost all methods achieve perfect accuracy in IID splits. However, baseline systems cannot generalize well the challenging LEN splits. In contrast, our methods, both Soft-ReMoto and Hard-ReMoto, perform very well on LEN splits, surpassing the best baseline system by large margins (> 40%). The results indicate that ReMoto, particularly its neural reordering module, has the right inductive bias to learn reorderings. We also test a variant does not generalize well to the LEN split on the arithmetic task, showing that it is beneficial to split models of the 'syntax" (i.e., alignment) and 'semantics', confirming what has been previously observed 17, 40
where parameters 8, ø with shared input embeddings. This variant
4.2 Semantic Parsing
Our second experiment is on semantic parsing where ReMoto models the latent aligmment between NI. utterances and their corresponding programs. We use GeoQuery dataset (56) which contains 880
utterance-programs pairs. The programs are in variable-free form 23 an example is shown in Table
0 Similarly to SCAN-SP, we transform the programs into parentheses-fres form which have better structural correspondence with atterances.Again we can reconstruct the original programs based on the grammar. An example of such parentheses-free form is shown in Figure 2 Apart from the standard version, we also experiment with the Chinese and German versions of GeoQuery [22] 48) Since different languages exhibit divergent word orders 47], the results in the multilingual setting will tell us if our model can deal with this variability.
In addition to standard IID splits, we create LEN split where the training examples have parentheses- free programs with maximum length 4; the dev and test examples have programs with minimum length 5. We also experiment with the TEMP split 18 where training and test examples have programs with disjoint templates.
Baselines and Results Apart from conventional seq2seq models, for comparison, we also imple- mented the syntactic attention 44). Our model ReMoto is similar in spirit to the syntactic attention, 'syntax' in their model (i.e., alignment) and 'semantics' (i.c., producing the representation relying
"Since we use the program form, the original length split sequence, is not very suitable in our experiments.
27 which is based on the length of action
'We use the varaible-free free form, as opposed to other alternatives such lambda calculus, for two reasons: variable-frre programs have been commonly used in systematic generalization settings [18 41), probably it is easier to construct generalization splits using this form; 2) the variable-free form is more suitable for modeling alignments since variables in programs usually make alignments hard to define.
8

---

EN TEMP
ZH
DE TEMP
Model
IID
LEN
IID
TEMP
LEN
IID
LEN
Seq2Seq
75.7
38.8
21.8
72.5
25.4
19.8
56.1
18.8
15.2
Syntactic Attention
40
74.3
39.1
18.3
70.2
27.9
18.7
54.3
19.3
14.2
SSNT [55]
75.3
38.7
19.1
71.6
23.8
17.8
55.2
19.8
14.1
Soft-ReMoto
74.5
39.3
19.8
73.4
30.3
17.3
35.8
19.5
13.4
Hard-ReMoto
75.2
43.2
23.2
74.3
45.7
22.3
55.6
22.3
16.6
Table 3: Exact-match accuracy (%) on three splits of the multilingual GeoQuery dataset. Numbers
underlined are significantly better than others (p-value & 0.05 using the paired permutation test).
on the alignment) are separately modeled. In contrast to structured mechanism for modeling alignments, their syntactic attention still relies on the conventional attention mechanism. We also com- pare with SSNT, which can be viewed ablated version of ReMoto by removing our reordering module.
Results are shown in Table For the challenging TEMP and LEN splits, our best performing model Metd achieves consistently stronger performance than seq2seq. syntactic attention and SSNT. Thus, our model bridges the gap between conventional seq2seq models and specialized state-of-the-art
grammar-baser models [18 41
4.3 Machine Translation
Our final experiment is small-scale machine translation tasks, where ReMoto models the latent aligmments between parallel sentences from two different languages. To probe systematic generaliza- tion, we also create LEN split for each language pair in addition to the standard IID splits.
English-Jar Jaggiis-Japanese We use the small en-ja dataset extracted from TANKA Corpus. The original split (IID) has 50k/500/500 examples for train/dev/test with lengths 4-16 words 8 We create a LEN split where the English sentences of training examples have maximum length 12 whereas the English sentences dev/test have a minimum length 13. The LEN split has 50k/538/538 examples for train/dev/test, respectively.
Chinese-Englise We extract subset from FBIS corpus (LDC2003E14) by filtering English sen- tences with length 4-30. We randomly shuffle the resulting data to obtain an IID split which has 141k/3k/3k examples for train/dev/test, respectively. In addition, we create LEN split where English sentences of training examples have maximum length 29 whereas the English sentences of dev/test examples have length 30. The LEN split has 140k/4k/4k examples as train/dev/test sets respectively.
Baselines and Results In addition to the conventional seq2seq, we com- pare with the original SSNT model which only accounts for monotonic alignments. We also implemented variant that combines SSNT with the local reordering module [9 our baseline to show the advantage of our structured ordering module.
EN-JA
ZH-EN
IID
LEN
IID
LEN
Seq2Seg
35.6
25.3
21.4
18.1
SSNT [55]
36.3
26.5
20.5
17.3
Local Reordering [9
36.0
27.1
21.8
17.8
Sott-ReMoto
36.66
27.5
22.3
19.2
Hard-ReMoto
37.4
28.7
22.6
19.5
Table BLEU scores on the EN-JA and ZH-EN translation.
Results are shown in Table Our model, especially Hard-ReMolo, con- sistently outperforms other baselines on both splits. In EN-JA translation, the advantage of our best-performance Hard-ReMoto slightly more pronounced the LEN split than in the IID split. In ZH-EN translation, while SSNT and its variant do not outperform seq2seq in the LEN split, ReMoto can still achieve better results than seq2seq. These results show that our model is better than its alternatives at generalizing to longer sentences for machine translation.
'QQG [] achieves 35.0% in the English LEN, and SBSP 18 (without lexicon) achieves 65.9% English TEMP in exccution accuracy. Both models are augmented with pre-trained representations (BERT).

---

original imput: EEj *
3 -
H1 state
5
KK
My P
3 bonder
lomest
reordered imput: !H He
bander A &
Songer D37
which E (. liver 4 mputa which
prediction: state" next_to_2" longest river loc_2 countryid_dd countxyyd.EBVITYSSS ground truth: state next_to_2 longest river loc_2 countryid. __NTTTENTTTY_
original input: according' to" the newspaper* 5 there" was? a² big" fire 10 last" night reordered input: according' to² the newspaper! 5 night last big" fire a there was?
prediction: #11 & t 1,2,34455 1 X 1 # 8,6 2
ground truth: 3T F & & PETE
Table Output examples of Chinese semantic parsing and English-Japanees translation. For clarity, the input words are labeled with position indices, and, for semantic parsing, with English translations. prediction consists of multiple segments, each annotated with a superscript referring to input tokens.
Interpretability Latent alignments, apart from promoting systematic generalization, also lead to better interpretability as discrete alignments reveal the internal process for generating output. For example, in Table [ we show few examples from model. Each output segment is associated with an underlying rationale, i.e. a segment of the reordered input.
Conclusion and Future Work
In this work, we propose a new general seq2seq model that accounts for latent segment-level alignments. Central to this model is novel structured reordering module which is coupled with existing modules to handle non-m non-monotonic segment alignments. We model reorderings as separable permutations and propose efficient dynamic programming algorithm to perform marginal inference and sampling. It allows latent reorderings to be induced with end-to-end training. Empirical results both synthetic and real-world datasets show that our model can achieve better systematic generalization than conventional seq2seq models.
The strong inductive bias introduced by modeling alignments in this work could be potentially beneficial in weakly-supervised and low-resource settings, such as weakly-supervised semantic parsing and low-resource machine translation where conventional seq2seq models usually do not perform well.
Acknowledgements
We thank Miloš Stanojević and Khalil Sima'ar an for their valuable comments; Lei Yu and Chris Dyer for providing the preprocessed data for machine translation; the anonymous reviewers for their helpful feedback. We gratefully acknowledge the support of the European Research Council (Titov: ERC StG BroadSem 678254; Lapata: ERC CoG TransModal 681760) and the Dutch National Science Foundation (NWO VIDI 639.6229222222 (90.0222518), Titov also supported by the Analytical Center for the Government of Russian Federation (agreement 70-2021-00144 dd. 01.11 11.201, IGK 000000D733321SQ0000)
References
[1] Yaser Al-Onaizan and Kishore Papineni. Distortion models for statistical machine translation. In Proceedings of the 21st International Conference Computational Linguistics and 44th Anmual Meeting of the Association for Computational Linguistics, pages 529-536, 2006.
[2] Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 39-48, 2016.
[3] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0475. 2014.
10

---

[4] Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: what required and can be learned? ICLR. 2019.
[5] Prosenjit Bose, Jonathan F Buss, and Anna Lubiw. Pattern matching for permutations. Informa- lion Processing Letters, 65(5):277-283 1998.
[6] Peter F Brown, Stephen Della Pietra, Vincent Della Pietra, and Robert L Mereer. The mathematics of statistical machine translation: Parameter estimation. Computational linguistics, 19(2):233-31, 1993.
[7] Kehai Chen, Rui Wang, Masao Utiyama, and Eicchiro Sumita. Neural machine translation with reordering embeddings. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1787-1799, 2019.
[8] Noam Chomsky. Aspects of the theory of syntax. Number no. 11 Massachusetts Institute of Technology. Research Laboratory of Electronics. Special technical report. The MIT Press, Cambridge, Massachusetts, 50th anniversary edition edition, 1965. ISBN 978-0-262-52740-88
[9] Caio Corro and Ivan Titov. Learning latent trees with stochastic perturbations and differentiable dynamic programming- In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages Computational Linguistics. doi: 10. (0.18853/v1//19.10 1551. URL htthttt:::// wwwww/ org//
Florence, Italy, July 2019, Association for
anthology/P19-11555
[10] Marco Cuturi, Olivier Teboul, and Jean-Phillipe Vert. Differentiable ranks and sorting using optimal transport. arXiv preprint 1905 2019,
[11] Yuntian Deng, Yoon Kim, Justin Chiu, Demi Guo, and Alexander M Rush. Latent alignment and variational attention. arXiv preprint arXiv: 2018.
[12] Catherine Finegan- Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. Improving text-to-SQL evaluation methodology. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3-1-360, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 181331111/118-0033. URL https:t////// //tp:://www... www.wwwwlll........... aclweb. org/ anthology/P18-1033 1033
[13] Jerry A Fodor and Zenon W Pylyshyn. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-))3--1, 1988.
[14] Yao Fu, Chuanqi Tan, Bin Bi, Mosha Chen, Yansong Feng, and Alexander Rush. Latent template induction with Gumbel-CRFs. arXiv preprint 1xXi:20011.1424, 2020.
[15] Emily Goodwin, Koustuv Sinha, and Timothy O'Donnell. Probing linguistic systematicity. arXiv preprini 2rXiv:2005.04315. 2020.
[16] Aditya Grover, Eric Wang. Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. arXiv preprint arXiv:
2019.
[17] Serhii Havrylov, Germán Kruszewski, and Armand Joulin. Cooperative learning of disjoint syntax and semantics. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguisties: Human Language Technologies, Volume (Long and Short Papers), pages 1188-1128, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18855/111N19--1155 URL /https://wwtt aclweb
org/ hegg/nthologyy//// N19 1115
[18] Jonathan Herzig and Jonathan Berant. Span-based semantic parsing for compositional general- ization. arXiv preprint arXiv:2009.0640 20000, 2020.
[19] Po-Sen Huang, Chong Wang, Sitao Huang, Dengyong Zhou, and Li Deng. Towards neural phrase-based machine translation. arXiv preprint arXiv:1706.05566, 2017.
11

---

[20] Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. The compositionality of neural networks: integrating symbolism and connectionism. 30XXvv/908.088.. [cs, stat], August 2019.
htt.ttttpaaxii..... org/ haap//bss///9/ 190. 08351
arXiv: 003511
[21] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparamcterization with gumbel-sone softmax. arXiv preprint 1111:1611.01114, 2016.
[22] Bevan Jones, Mark Johnson, and Sharon Goldwater. Semantic parsing with Bayesian tree transducers. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 488-496, Jeju Island. Korea, July 2012. Association for Computational Linguistics. URL https::///// //www/wwwww// aclweb. org/ http//atthhhlyyyeee /12- 1051
[23] Rohit J Kate, Yuk Wah Wong, and Raymond J Mooney. Learning to transform natural to formal languages. In AAAI, volume 5, pages 1062-1068, 2005.
[24] Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measuring compositional generalization: A comprehensive method on realistic data. arXiv preprini arXiv:1912.09713, 2019.
[25] Yoon Kim, Carl Denton, Luong Hoang, and Alexander Rush. Structured attention networks. arXiv preprini arXiv: 170.0008877 2017. 2017.
[26] Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Kallison-Burcea Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondłej Bojar, Alexandra Constantin, and Evan Herbst. Moses: Open source toolkit for statistical machine translation. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions, pages 177- 180, Prague, Czech Republic, June 2007, Association for Computational Linguisties. URL https: //www//wwww..c aclweb. wwgg/anthologg/P00-22000
[27] Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequeme recurrent networks. In International Conference Machine Learning, pages 2873-2882, PMLR, 2018.
[28] Joao Loula, Marco Baroni, and Brenden M Lake. Rearranging the familiar: Testing composi- tional generalization in recurrent networks. arXiv preprint arXiv: 2018.
[29] Minh-Thang Luong, Hieu Pham, and Christopher Manning. Effective approaches to attention- based neural machine translation. arXiv preprini arXiv: 04025 2015.
[30] Chunchuan Lyu and Ivan Titov. AMR parsing as graph prediction with latent alignment. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pages 397-407, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.11853/1//11--1 anthology/P18-1037
URL httpp::/www.......
org/
[31] Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint 1611007111007/1 2016.
[32] Christopher Manning and Hinrich Schutze. Foundations of statistical natural language process- ing. MIT press, 1999.
[33] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with Gumbel-Sinkhone networks. arXiv preprint arXiv:/802.000 08660, 2018.
[34] Tetsuji Nakagawa. Efficient town BTG parsing for machine translation preordering. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 208-218, Beijing, China, July 2015, Association for Computational Linguistics. doi: 10.3 L/P15 1021. URL www aclweb. org/ aanthology/P55-122
12

---

[35] Graham Neubig, Taro Watanabe, and Shinsuke Mori. Inducing a discriminative parser to opti- mize machine translation reordering. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 843 843, Jeju Island, Korea, July 2012. Association for Computational Linguistics. URL. https: /wwww//wwwww.// aclweb. org/ anthology/ttaaaaaa Datplllooyyy/-111111100 117-
[36] Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie. Sparsemap: Differentiable sparse structured inference. In International Conference on Machine Learning, pages 3799- 3808. PMLR, 2018.
[37] Will Norcliffe-Brone Efstathios Vafeias, and Sarah Parisot. Learning conditioned graph structures for interpretable visual question answering. arXiv preprint arXin:1880.00244. 2018.
[38] Franz Josef Och and Hermann Ney. A systematic comparison of various statistical alignment models. Computational Linguisties, (9 2003. doi: 10.1 10.1162/099120003333333433
URL. httpt:ttp///wwwt.t aclweb. org http///naoooogg//00000000000
[39] George Papandreou and Alan L Yuille. Perturb-and-map random fields: Using discrete optimiza- tion learn and sample from energy models. In 20/ International Conference on Computer Vision, pages 193-200. IERE, 2011.
[40] Jake Russin, Jason Jo. Randall C O' O'Reilly, and Yoshua Bengio. Compositional generalization in a deep seq2seq model by separating syntax and semantics. arXiv preprint arXiv:1904.09700 2019.
[41] Peter Shaw, Ming- Wei Chang. Panupong Pasupat, and Kristina Toutanova. Compositional generalization and natural language variation: Can a semantic parsing approach handle both? arXiv preprint 10Xv:20010.12255, 2020.
[42] Noah A Smith and Mark Johnson. Weighted and probabilistic context- free grammars are equally expressive. Computational Linguistics, 33 2007.
[43] Richard Socher, Jeffrey Pennington, Eric H Huang. Andrew Y Ng, and Christopher D Manning. Semi-supervised recursive autoencoders for predicting sentiment distributions. In Proceedings of the 2011 conference on empiricul methods in natural language processing, pages 15 151-161, 2011.
[44] Miloš Stanojević and Khalil Sima' an. Reordering grammar induction. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 44 44-54, 2015.
[45] Miloš Stanojević and Mark Steedman. Formal basis of language universal. Computational Linguistics, pages 1-34, 2018.
[46] Mark Steedman. The syntactic process, volume 24. MIT press Cambridge, MA, 2000.
[47] Mark Steedman. A formal universal of natural language grammar. Language, 96(3):618-666 660,
2020.
[48] Raymond Hendy Susanto and Wei Lu. Semantic parsing with neural hybrid trees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[49] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Superglue: A stickier benchmark for general-purpone language understanding systems. arXiv preprint arXiv:1905.0053: 2019.
[50] Chong Wang, Yining Wang, Po-Sen Huang, AbdeIrahman Mohamed, Dengyong Zhou, and
Li Deng. Sequence modeling via segmentations. In International Conference on Machine Learning, pages 3674-3683. PMLR, 2017.
[51] Yuk Wah Wong and Raymond Mooney, Learning for semantic parsing with statistical machine translation. In Proceedings of the Human Language Technology Conference of the NAACI, Main Conference, pages 339-446, New York City, USA, June 2006. Association for Computational Linguistics. URL https: //ww//wwcoo aclweb. org/ anthology/N06--o 1056
13

---

[52] Dekai Wu. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational linguisties, 23(3):377-403, 1997.
[53] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In International conference on machine learning, pages 2048-2057, PMLR, 2015.
[54] Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Wang Ling. Learning to compose words into sentences with reinforcement learning. arXiv preprint arXiv: 1.X1::611.001000 1.09100, 2016.
[55] Lei Yu, Jan Buys, and Phil Blunsom. Online segment to segment neural transduction. arXiv preprint 1609.08144 2016.
[56] John M 7elle and Raymond J Mooney. Learning to parse database queries using inductive logic programming. Proceedings of the national conference on artificial intelligence, pages 1050-1055, 1996.
[57] Luke Zettlemoyer and Michael Collins. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. arXiv preprint arXiv: 1420, 2012.
14


Reviews:
[{"review_id": "t9jLiaRRFIJ", "reviewer": "Reviewer_fSuH", "summary": "This paper targets the problem of systematic generalization in sequence to sequence models, particularly in the scenario of modeling segment alignments as discrete structured latent variables. To explore the searching space of alignments, the authors proposed to use a reorder-first align-later framework, and use hierarchical permutation trees to produce separable permutations, which has the exact marginal inference with dynamic programming enabling end-to-end training. Experiments show that the proposed approach outperforms standard models on both synthetic and real NLP tasks with better systematic generalization.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Overall I think the idea of reordering and then model alignment is quite interesting and important for the area of seq2seq learning, as it solves a big issue of conventional approaches (e.g. SSNT) that only works for monotonic alignment while in real scenarios many applications such as machine translation do not hold. Also, the motivation of connecting learning systematic generalization and segment alignments seems reasonable.\n\nI only have some detailed question about this submission:\n\n-- In section 2.2, you discussed the connection between discrete alignment and continuous attention. Will the proposed target also be achieved by using the attention weights for the segment alignments? Or is there any reason we have to work on discrete alignment (which might potentially be more costly)?\n\n-- In Line 154 & 155, do these two equations have a typo? Why do “straight” and “inverted” have the same results? Moreover, it would be much better to give more context explaining these terms such as “straight”, “inverted” as well as BTG to make it easier to understand the method.\n\n-- What is the algorithm you used for inference? How to decide the best permutation of reordering?\n\n-- All the experiments seem to be quite small scale with a small architecture. Is it because the proposed method cannot work on a larger scale? Will this idea be applied to large scale problems such as WMT using Transformer based models?\n\n-- What is the computational cost for both soft and hard ReMoto, and how does this compare to previous works in both training and inference time?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author did not have a separate section about the limitation or societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4 hours"}, "extra_text": {}}, {"review_id": "W0sMAt4jzb4", "reviewer": "Reviewer_iq7F", "summary": "The paper tackles the problem that conventional sequence-to-sequence models (seq2seq models) fail to generalize systematically; i.e., they are suboptimal for handling the compositionality of language. The paper makes the following contributions: (1) a new seq2seq model for NLP tasks that accounts for latent non-monotonic segment-level alignments and (2) an algorithm for exact marginal inference with separable permutations, which makes end-to-end training possible. The proposed approaches are evaluated both on synthetic data and two real-world NLP tasks: semantic parsing and machine translation. The experiments show that the proposed model mostly outperforms conventional seq2seq models in an IID setting, and even more strongly outperforms existing models in settings where test examples are longer than training examples. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "The authors do a great job introducing the motivation for their work (i.e., the problems with currently existing models). Furthermore, the experiments are designed well to show the benefits of the proposed approaches, and I like the fact that the experiments are done on both synthetic data and real-world datasets. The experimental results demonstrate the benefits of the proposed model. The paper is written clearly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not explicitly talk about the limitations of their work, but the experiments make some potential limitations obvious (e.g., seq2seq could perform better in some IID settings). I don't see a reason to expect any negative societal impact of the work.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "R1_YPxifyh", "reviewer": "Reviewer_pMgt", "summary": "The order of the input and output (including their associated representations) can matter for the performance and interpretability of a sequence to sequence model. Based on monotonic alignment seq2seq model (e.g. SSNT), the paper proposes to learn a separable permutation over the input representations so that the monotonic alignment can lead to better performance and interpretability. The authors test their methods on toy datasets and small scale semantic parsing and medium sized machine translation tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Monotonic alignment seq2seq model is an interesting family of seq2seq models that can not only boost performance (particularly when the monotonic assumption holds in large) but also provide some interpretability for the prediction task. To relax the monotonic assumption, this paper proposes to learn a permutation matrix $M_p$ as a first step before the monotonic alignment seq2seq model; the paper proposes a way to combine these two steps in an end to end fashion.\nThe permutation matrix is parameterized only for separable permutations, which have their linguistic groundings. In 3.2, the authors show that the matrix can be estimated efficiently as an expectation of the underlying BTG separable permutation marginals. An alternative is to add a gumbel softmax trick to simulate the hard permutation choice. The separable permutation marginal calculation is new and the authors have shown the proofs and important technical details for this algorithm (e.g. the WCFG normalization). The algorithm is generally applicable to any parameterized BTG, however neither in the paper nor in the appendix, I can see how the BTG is parametrized for various experiments, making myself unable to reproduce the experiments in thoughts. \n\nThe authors have shown the benefits of the proposed approach via toy examples and some real tasks. One question I have for the Geoquery experiments is that the baseline and the proposed methods have too low accuracy (maybe due to missing argument mapping), as a reference, https://arxiv.org/pdf/1601.01280.pdf reports a seq2seq with attention baseline, achieving 84.6 accuracy on Geoquery, and this is not SOTA at all. \n\nThe other minor writing/formatting/missing references:\n- Eq(2), this formulation is not used throughout the paper and potentially misleads readers to factorization methods. From my understanding, the paper proposes two steps approaches and the matrix doesn't necessarily come from the factorization in Eq(2).\n- Line 155: It seems that the order of the two non terminals should be reversed.\n- Line 226: Gumbel-Softmax should be outside of parenthesis.\n- In general, the order of the input matters for performance which can be another motivation of the paper, thus related to https://arxiv.org/pdf/1511.06391.pdf. The paper also connects to self attention widely used in NLP, it seems that specific parametrization of self attention can lead to permutations.\n\n＃After discussions with the authors: the authors have clarified all my questions concerning the formalism, presentation and experiments. I feel that the paper can benefit from discussing in details the various settings and the rationales behind, not only the semantic parsing experiments that we have discussed here but also other scenarios as other reviewers pointed out. The authors have shown generally deep understanding of the encountered problems and I have adjusted my score from 5 to 6, confident that the final paper will be better quality to best convey the proposed ideas.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors could mention in the future work testing the methods on large scale datasets (for both semantic parsing and machine translation). Also, the proposed methods seem to integrate well with current pretrained methods and are worth trying in the future to boost task performance. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "Hkh4ZBkyrn3", "reviewer": "Reviewer_VWV9", "summary": "The authors propose a model for sequence transduction tasks that allows for source tokens to be reordered and then monotonically aligned with the target tokens. The reordering and the alignment are latent, and since all monotonic alignments can be marginalized over using the approach introduced in the SSNT paper (Yu et al., 2016), the authors focus on approximating the marginalization over the latent source permutation. The authors consider in particular separable permutations, whose derivations are induced by a PCFG. The authors propose two approximation approaches, one which uses a dynamic program to obtain an expected permutation matrix (which is used instead of the expected likelihood under the permutation-matrix distribution), and one which samples a hard permutation matrix during learning and uses a ST-Gumbel-Softmax gradient estimator. The authors experiment on a number of synthetic and small-scale real-world tasks and generally find that their approach outperforms baselines, and is especially performant in settings that require generalization to longer inputs than those seen in training.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The paper is interesting, generally clearly written, and it seems technically sound. I think the core contribution of the paper is, as the authors suggest on line 66, to propose a hierarchical approach to modeling permutations of input, as opposed to other, flatter alternatives. \n\nOverall I think this is a nice paper, but I have some suggestions/concerns:\n- I'm not sure the authors' emphasis on the model capturing segments or on segment alignment is either justified or needed. As far as I can tell, the SSNT model computes alignments between tokens. It's true that segmentations are induced either by multiple tokens aligning to a single token or by the alignment skipping contiguous source tokens, but it seems like the model doesn't ever really represent segments themselves as first-class objects. Rather, it seems like the major inductive bias afforded by SSNT-type models is that the alignment needs to be monotonic, and so an alternative hypothesis for the success of both SSNT and ReMoto is that monotonic (token-level) alignment is a useful inductive bias (even if perhaps we need the alignment to be monotonic in a reordered source sequence). So, while I don't think this hurts the paper much, I think we would need much more evidence before concluding it's the segment alignment that is helping here.\n- Experimentally, I think the paper is generally good, although it seems important to have an SSNT baseline in Table 3 for the semantic parsing experiments (so we can separate the contributions of monotonic alignment and reordering).\n- Given that Hard-ReMoto seems to generally work best, it might be worth discussing to what extent we need the Markov assumptions made by the permutation-derivation model. For instance, would it better to just use an autoregressive parameterization of the derivation distribution?\n- There are other approaches to obtaining differentiable permutations that should perhaps be mentioned, like \" Stochastic optimization of sorting networks via continuous relaxation\" (ICLR, 2019) and \"Differentiable Ranks and Sorting\nusing Optimal Transport\" (NeurIPS 2019)\n\nMinor suggestions:\n- I think the authors should explicitly describe the SSNT model and the parameterization of p(y | X, M) in the main text; otherwise it is hard to follow what exactly is going on. \n- Equation (9) should probably have just p_{phi} rather than an expectation under it.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents uses the class of separable permutations, which in contrast to the unrestricted class of permutations, can be reasoned about in polynomial time using dynamic programming algorithms to introduce explicit reordering and alignment variables in seq2seq models. The reviewers remarked on the technical clarity, interestingly novel approach, and thorough experiments. This technique improves interpretability and, most importantly, provides a demonstrated bias for compositional generalization, both of which are important concerns in sequence transduction modelling. This represents a serious and successful attempt to address these issues by changing the underlying assumptions of the model, rather than relying on data augmentation.
Decision: Accept (Poster)