Sequence-to-Sequence Learning with Latent Neural Grammars
Authors: Yoon Kim
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: sequence-to-sequence learning
compositional generalization
synchronous grammars

Abstract: Sequence-to-sequence learning with neural networks has become the de facto standard for sequence modeling. This approach typically models the local distribution over the next element with a powerful neural network that can condition on arbitrary context. While flexible and performant, these models often require large datasets for training and can fail spectacularly on benchmarks designed to test for compositional generalization. This work explores an alternative, hierarchical approach to sequence-to-sequence learning with synchronous grammars, where each node in the target tree is transduced by a subset of nodes in the source tree. The source and target trees are treated as fully latent and marginalized out during training. We develop a neural parameterization of the grammar which enables parameter sharing over combinatorial structures without the need for manual feature engineering. We apply this latent neural grammar to various domains---a diagnostic language navigation task designed to test for compositional generalization (SCAN), style transfer, and small-scale machine translation---and find that it performs respectably compared to standard baselines.

Sequence-to-Sequenee Learning with Latent Neural Grammars
Yoon Kim MIT CSAIL yoonkimemit.co edu
Abstract
Sequence-to-sequee learning with neural networks has become the de facto standard for sequence prediction tasks. This approach typically models the local distribution over the next word with powerful neural network that can condition on arbitrary context. While flexible and performant, these models often require large datasets for training and can fail spectacularly on benchmarks designed to test for compositional generalization. This work explores an alternative, hicrarchical approach to seguence-to-sequence learning with quasi-synchronous grammars, where each node the target tree is transduced by a node in the source tree, Both the source and target trees treated latent and induced during training. We develop a neural parameterization of the grammar which enables parameter sharing over the combinatorial space of derivation rules without the need for manual feature engineering. We apply this latent neural grammar to various domains-a diagnostic language navigation task designed to test for compositional generalization (SCAN), style transfer, and small-scale machine translation and find that it performs respectably compared to standard baselines.
1 Introduction
Sequence-to sawtennc-tt-sqqueeee -o-sequence learning with neural networks [62, 22, 106] encompasses powerful and general class of methods for modeling the distribution over an output target sequence y given an input source sequence
Key to its success is a factorization of the output distribution via the chain rule coupled with a beshly-prrmettrizeedd neural network that models the local conditional distribution over the next word given the previous words and the input. While architectural innovations such attention [8], convolutional layers [39], and Transformers [110] have led to significant improvements, this word-by- word-by-word modeling remains
the approach, and with good reason since any distribution over the output can be factorized autoregressively via the chain rule, this approach should be able to well-approximate the true target distribution given large-enough data and model.'
However, despite their excellent performance across key benchmarks these models are often sample inefficient and can moreover fail spectacularly diagnostic tasks designed test for compositional generalization [68, 63]. This is partially attributable to the fact that standard -ouueceet--sequecce models have relatively weak inductive biases (c.g. for capturing hierarchical structure [79]), which can result in learners that over-rely on surface-level (as opposed to structural) correlations.
In this work, we explore an alternative, hierarchical approach to sequence-to-sequeee with latent neural grammars. This work departs from previous approaches in three ways. First, we model the distribution over the target sequence with guasi-synchronous grammar [103] which assumes a hierarchical generative process whereby each node in the target tree is transduced by
learning
Much of the work was completed while the author was at MIT-IBM Watson AI. Code is available at https: //gttubb. comm/yookiimneurrll-eeeeo
'There are, however, weighted languages whose next-word conditional distributions are to compute a formal sense, and these distributions cannot be captured by locally normalized autogressive models unless one allows the number of parameters (or runtime) to grow superpolynomially in sequence length [72].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

nodes in the source tree. Such node-level alignments provide provenance and causal mechanism for how each output part is generated, thereby making the generation process more interpretable. We additionally find that the explicit modeling of source- and target-side hierarchy improves composi- tional generalization compared to hieraachrchcc models. Second, in contrast the existing line of work on incorporating (often observed) tree structures into sequence modeling with neural networks [35, 5, 89, 37, 126, 1, 97, 18, 34, inter alia], we treat the source and target trees as fully latent and induce them during training. Finally, whereas previous work on synchronous grammars typically utilized log-linear models over bandcrafteed/pipelnne features (20, 56, 115, 103, 112, 27, 42, inter alia] we make of neural features to parameterize the grammar's 's rule probabilities, which enables efficient sharing of parameters over the combinatorial space of derivation rules without the need for any manual feature engineering. We also use the grammar directly for end-to-end generation instead of as part of larger pipelined system (e.g. to extract alignments) [122, 41, 14].
We apply our approach to variety of sequence-to-sequee igation task designed to test for compositional generalization [68], style transfer on the English Penn Treebank [78], and small-scale English-French machine translation- and find that it performs respectably compared to baseline approaches.
learning tasks language nav-
2 Neural Synchronous Grammars for Sequence-to-Sequence Learning
We use æ = 21 .1..... Fs. y = y1,...., yr to denote the source/target strings, and further use 8, to refer to source/target trees, represented as set of nodes including the leaves (i.e. yield(s) x and (t) = y).
2.1 Quasi-Synchronour Grammars
Quasi-synchrone grammars, introduced by Smith and Eisner [103], define a monolingual grammar over target strings conditioned on source tree, where the grammar's 's rule set depends dynamically on the source tree s. In this paper we work with probabilistic punsi-synchronous context-free grammars (QCFG), which can be represented as a tuple G[s] = (S.W, , P, Σ, R(s). where S is the distinguished start symbol, .' is the set of nonterminals which expand to other nonterminals, P is the set of nonterminals which expand to terminals (i.e. preterminals), Σ is the set of terminals, and R[s] is a set of context-free rules conditioned s, where each rule is one of
S Alass, A[a.] + Blay]C[as). Dia + w,
AEN, a, Ss A B,CENUP, at a3, S E a a
We use 0 to parameterize the rule probabilities (r)) for each r E R(s). In the above, as's 's are subsets of nodes in the source tree s, and thus a QCFG tranduces the output tree by aligning each target tree node to a subset of source tree nodes. This monolingual generation process differs from that of classic synchronous context-free grammars [1 [118] which jointly generate source and target trees in tandem (and therefore require that source and target trees be isomorphic), making QCFGs appropriate tools for tasks such as machine translation where syntactic divergences are elements of the power set of the above formulation as presented is completely intractable. We follow prior work [103, 112] and restrict o; 's be single nodes (i.e. ag ajj, 0i E s), which amounts to assuming that each target tree node is aligned to exactly one source tree node.
common. 2 Since the o,
In contrast to standard, "flat" seuueecce-t-sequeeee models where any hierarchical structure necessary for the task must be captured implicitly within a neural network's 's hidden layers, synchronous grammars explicitly model the hierarchical structure on both the source and target side, which acts as a strong source of inductive bias. This tree transduction process furthermore results in a more interpretable generation process as each span in the target aligned to a span in the source via node- level alignments. 3 More generally, the grammar's 's rules provide a symbolic interface to the model with which operationalize constraints and imbue inductive biases, and we show how this mechanism can be used to, for example, incorporate phrase-level copy mechanisms (section 2.4).
It is also possible to model syntactic divergences with richer grammatical formalisms [101, 81]. However these approaches require more expensive algorithms for learning and inference.
'Similarly, latent variable attention [121, 7, 28, 96, 119] provides for more a interpretable generation process than standard soft attention via explicit werd-level alignments.

---

2.2 Parameterization
Since each source tree node o₂ is likely to occur only few times (or just once) in the training corpus, parameter sharing becomes crucial. Prior work on QCFGs typically utilized log-linear models over handcrafted features to share parameters across rules [103, 42]. In this work we instead use neural parameterization which allows for easy parameter sharing without the need for manual feature engineering. Concretely, we represent each target nonterminal and source node combination A(ax] as an embedding,
A[ax]] = U + ha.
where is the embedding for A, and ha; is the representation of node given by running TreeL.TMM over the source tree e [107, 134]. These embeddings are then combined to produce the probability of each rule,
PS + A(a:))
o exp (u eAas))))))
po(A[(x) + Blay]C(ax])
exp (fi(e (fa(eB(a,)) + + x exp (fa(ep(a.) u + bw),
po(D[a:] + w)
where f1. f3. f4 are feedforward networks with residual layers (see Appendix A.1 for the exact parameterization). Therefore the learnable parameters in this model are the nonterminal embeddings (i.e. nn for A E {S) U. U P), terminal embeddings/biases (i.e. Uw: by for w E E), and the parameters of the STM and the feedforward networks.
2.3 Learning and Inference
The QCFG described above defines distribution over target trees (and by marginalization, target strings) given source tree. While prior work on QCFGs typically relied on an off-the-shelf parser over the source to obtain its parse tree, this limits the generality of the approach. In this work, we learn probabilistic source-side parser along with the QCFG. This parser a monolingual PCFG with parameters that defines posterior distribution over binary parse trees given source strings, i.c. (s(s x). Our PCFG uses the neural parameterization from Kim et al. [64]. With the parser in hand, are now ready to define the log marginal likelihood,
log (y (yl x>) = log Σ (x)
Σ po(t (s)s(s(x))
Here T(x) and T(y) are the sets of trees whose yields synchronous context-free grammars, it is not possible to efficiently marginalize over both T(y) and T④x) due the non-isomorphic assumption. However, we observe that the inner sum- mation Lv) (a = ( s) can be computed with the usual inside algorithm [9] in ((W)((V (377)))77) where is the source length and T is the target length. This motivates the following lower bound on the log marginal likelihood,
and y respectively. Unlike in
log Po.o x>) Eerpo(el æ) (oyy 8)],
which is obtained by the usual application of Jensen's inequality (see Appendix A.2).*
An unbiased Monte Carlo estimator for the gradient with respect to 0 straightforward to compute given sample from (s(s I æ)), since can just backpropagate through the inside algorithm. For the gradient respect to di we use the score function estimator with a self-critical baseline [92].
V à (spppo(s [m) [log (3 s)] x (log pe (y s') log pe ( 3)) V Ps xx)
As standard variational approaches, one can tighten this bound with the use of a variational distribution (a( (a æ, y), which results in the following evidence lower bound,
log ( x)) 2 Bargy (=l=.v) [log (1 #)] (< y) || (s [=)]]
This is equivalent to our objective if we set (s y) = (s(s x). Rearranging some terms, we then have,
Ea-py(a [logee(y) s)] = log (3. x) - KL[ps x)) [s.s x. 3)]-
Hence, our use (o x) as variational distribution militating towards learning a model which achieves good likelihood but at the same time has a posterior distribution pe. æ; y) that close to the prior (s |x) (i.e. learning model where most of the uncertainty about s is captured by æ alone). This is arguably reasonable for many language applications since parse trees are often assumed to be task agnostic.

---

where s' is a sample from (s(s x) and is the MAP tree from P æ). We also found it important to regularize the source parser by simultaneously training it as a monolingual PCFG, and therefore add V Pg()) to the gradient expression above. Obtaining the sample tree s', the argmax tree 8, and scoring the sampled tree log Ps x) all require ((5)) dynamic programs. Hence the runtime is still dominated by the (($T7)) dynamic program to compute lagpa(y s') and log pa (y 8).6 We found this to be manageable on modern GPUs with vectorized implementation of the inside algorithm. Our implementation uses the Torch-Struct library [93].
Predictive inference For decoding, we first run MAP inference with the source parser to obtain argmax, (s æ)). Given 8, finding the most probable sequence argmax, y Po ()) (i.e. the consensus string of the grammar G(š) ) is still difficult, and in fact NP-hard [102. 16, 77J. We therefore
resort to an approximate decoding scheme where we sample K target trees (()) {(K) from G[$),
rescore the yields of the sampled trees, and return the tree whose yield has the lowest perplexity.
2.4 Extensions
Here show that the formalism of synchronous grammars provides flexible interface with which to interact with the model.
Phrase-level copying Incorporating copy mechanisms into pruuence-to-equenee models has led to significant improvements for tasks where there is overlap between the source and target sequences [58. 83, 48, 73, 47, 95]. These models typically define a latent variable at each time step that learns to decide to either copy from the source or generate from the target vocabulary. While useful, most existing copy mechanisms can only copy singletons due to the word-level encoder/decoder! In contrast, the hierarchical generative process of QCFGs makes it convenient to incorporate phrase-level copy mechanisms by using a special-purpene nontermiina//retemmina that always copies the yield of the source subtree that is combined with. Concretely, letting Acopy E E be a COPY nonterminal, we can expand the rule set R[s] to include rules of the form AcoPy [av] the probabilities to be,
- v for u E Σt, and define
Po (Acorryloa [cx] ++v)
v) def = yield(a)))
(The preterminal copy mechanism is similarly defined.) Computing pa s) in this modified grammar requires a straightforward modification of the inside algorithm. In our style transfer experiments section 3.2 we show that this phrase-level copying important for obtaining good performance. While not explored in the present work, such a mechanism can readily be employed to incorporate external transformations rules (e.g. from bilingual lexicons or transliteration tables) into the modeling process, which has been previously investigated at the singleton-level [88, 3].
Adding constraints on rules For some applications we may want place additional restrictions on the rule set to operationalize domain-specific constraints and inductive biases. For example, setting aj 0g E descendant(a:) for rules of the form A[a,] + B[a,]C([s, would constrain the target tree hierarchy to respect the source tree hierarchy, while restricting a; to source terminals (i.e. would enforce that each target terminal be aligned to source terminal. We indeed make use of such restrictions in our experiments.
og (s) for rules of the form D[a,]
Incorporating autoregressive language models Finally, we remark that simple extensions of the QCFG can incorporate standard autoregressive language models. Let Pis (w 7) be a distribution over the next word given by (potentially conditional) language model given arbitrary context (e.g. woennce------uunnceeee model). One
y = ee for monolingual language model and 7 = I, ye for way to embed this language model into a QCFG would be to use special LM preterminal DrM E P that is not combined with any source node, and define the emission probability to be.
Po(Dis Pm - w) def (u /7).
(The nonterminal probabilities po (A(as) + DauC() and (o(Ala) - Blaz] DiMs are computed with the associated symbol embedding up Both the QCFG and the language model can then be trained jointly.
*This motivates our use of generative rather than a discriminative parser on the source side. This runtime incidentally is the same as that of the bitext inside algorithm for marginalizing over both source and target trees in rank-two synchronous context-free grammars. 'However see Zhou et al. [132], Panthaplackel et al. [87], and Wiseman et al. [114].
'Letting 0[s, t, N] = (NV + ya:a) be the inside variable for N being the root of the subtree over ya:..
we simply set 8 s, t, Acorr [as]] = 1 [yy.: yield(a:)).

---

Approach
Simple Jump
A. Right
Length
Po[run] - RUN
Pa. [look] - LOOK
RNN [68]
99.7
1.7
2.5
13.8
CNN [29]
100.0
69.2
56.7
0.0
Po [walk] WALK
Transformer [38]
1.0
53.3
0.0
Poljump] JUMP
TS-base [38]
99.5
33.2
14.4
Pa [right - TURN-RIGHT
Syntactic Attn [94]
100.0
91.0
28.9
15.2
Pa[left] TURN-LEFT
Meta Seq2Seq [67]
99.9
99.9
16.6
Willook left) - Po Pollook
CGPS [70]
99.9
98.8
83.2
20.3
Ni Wlloook right] -+ Fb (right)] Po
Equivar. Seq2Seq [44]
100.0
99.1
92.0
15.9
Na [walk left) - Po(left] Po [walk]
Span-based SP [54]
100.0
100.0
N4 [waakk right) [right) Fo, [[alk]]]]]
LANE [76]
100.0
100.0
100.0
100.0
Ni [look right twice] - N,, [lolo right) N. [lobk right)
Program Synth. [85]
100.0
100.0
100.0
100.0
Ni |walk left twice] - .N., |wwal left] Na left]
NeSS [19]
100.0
100.0
100.0
100.0
|look thrice] N₂ [Nolook thrice] Po]Book]
NQG-T5 [98]
100.0
100.0
100.0
Ni [look right thrice] - N's (look right thrice] Na lloo right)
GECA [6]
87.0
82.0
No llook right thrice] - N: (look right] Ni |look right]
R&R Data Aug. [4]
88.0
82.0
Ni |walk left thrice] No. (walk left thrice] Na |walk left'
Neural QCFG (ours)
96.9
96.8
98.7
95.7
No [walk left thrice] -+ Na [wallk left)
N. [walk left)
Table 1: Accuracy on the SCAN dataset splits compared to previous work.
Table 2: Frequently
rules from MAP tar-
get trees on the add primitive (jump) train set.
For some cases we may want to make use of a conditional language model that condition subparts of the source sentence. This may be appropriate for learning to translate conpoopposiii phrases whose translations cannot be obtained by stitching together independent translations of subparts (e.g. idioms such as "kicked the bucket"). In this case we can make use of a special nonterminal ALM E N which is combined with source tree nodes to produce rules of the form ALM[as] - for Et. The associated probabilities are then defined to be,
Po (A u) def (L yicld(a;))-
While these extensions can embed flexible autoregressive models within a QCFG, 9 they also inherit many of the issues attendant with such models (e.g. over-reliance on surface form). In preliminary experiments with these variants, we found the combined model to quickly degenerate into the uninteresting case of always using the conditional language model, and hence did not pursue this further. However it is possible that modifications to the approach (e.g. posterior regularization to penalize overuse of the conditional language model) could lead to improvements.
3 Experiments
We apply the neural QCFG described above to variety of sequence-to seguence-to-sqquenee to-sequence learning tasks. These experiments are not intended to push the state-of-the-an on these tasks but rather intended to assess whether our approach performs respectably against standard baselines while simulatenously learning interesting and interpretable structures.
3.1 SCAN
We first experiment on SCAN [68), diagnostic dataset where a model has to learn to translate simple English commands to actions (e.g. jump twice after walk - WALK JUMP JUMP). While conceptually simple, standard scquence-to-sequence models have been shown to fail on splits of the data designed to test for compositional generalization. We focus on four commonly-used splits: (1) simple, where train/test split is random, (2) add primitive (jump), where the primitive command jump is seen in isolation in training and must combine with other commands during testing, 10 (3) add template (around right), where the template around right is not seen during training, and (4) length, where the model is trained on action sequences of length at most 22 and tested on action sequences of length between 24 and 48.
AAterrativeeyy, can also embed QCFG within an autoregressive language model with a binary latent variable 2, (with distribution (=, x. ()) )))) at each time step. This aarable--marinnaizzed over during training-selects between Pts xr 22) and Po(ye 8, ce),, where the latter next-word probability distri- bution in the QCFG can be computed with probabilistic Earley parser [105]. The difference between the approaches stems from whether the switch decision is made by the QCFG or by the language model.
10 QCFG defined this paper places zero probability on length-one target strings, which presents an issue for this split of SCAN where jump + JUMP is the only context in which "JUMP" occurs in the training set. To address this, in cases where the target string is a singleton we simply replicate the source and target, i.e. jump + JUMP becomes jump jump - JUMP JUMP.
5

---

Nolo12]
010
Nalouu
Nito1o
0s
0g
Natoy1
N400l1
Nalosl
Natos]
twice
after
Polos]
Polo
Polas]
Polos]
Polon]
Polos]
Polon]
P
run left
C4
twice
TURN-RIGHT
JUMP
TURN-RIGHT
JUMP
TURN-LEFT
RUN
TURN-LEFT
RUN
jump right
Figure 1: Generation from the neural QCFG test example from the add primitive (jump) split of SCAN. The induced tree from the learned source parser is shown on the left, and the target tree derivation shown on the right. We do not show the initial root-level node (i.e. S - No (a12)). While the model does not distinguish between preterminals and terminals on the source tree, we have shown them separately for additional clarity. We also show some of the nove- alignments with dashed lines.
In these experiments, the nonterminals A E N are only combined with source nodes that govern at least two nodes, and the preterminals P ' are only combined with source terminals. We set [W| = 10 and [P] = 1, and place two additional restrictions on the rule set. First, for rules of the form S + A A[as] we restrict a to always be the root of the source tree. Second, for rules of the form A[ax] + B [[as]C[aax] we restrict a.j, Ogg either be a descendant of a; or oi itself (i.e. Oj, 04 E (escendant(a:) U {a=}). These restrictions operationalize the constraint that the target tree hierarchy respects the source tree hierarchy, though still in much looser sense than in an isomorphism. We found these constraints be crucial in learning models that perform well on the compositional splits of the dataset. See Appendix A.3.1 for the full experimental setup and hyperparameters.
Results Table shows our results against various baselines on SCAN. While many approaches are able to solve this dataset almost perfectly, they often make use of SCAN-specific knowledge, which precludes their straightforward application to non-synthetic domains. The neural QCFG performs respectably while remaining domain-agnostic. In Table 2 we show some examples of frequently- occurring rules based on their MAP target tree counts on the training set of the add primitive (jump) split. Many of the rules are sensible, and they furthermore illustrate the need for multiple nonterminal symbols. For example, in order to deal with source phrases of form "cr thrice" in a grammar that only has unary and binary rules, the model uses the nonterminals N1 and Ng in different ways when combined with the same phrase. Figure I shows an example generation from the test set of the add primitive (jump) split, where we find that node-level alignments provide explicit provenance for each target span and thus makes the generation process more interpretable than standard attention mechanisms. These alignments can also be used to diagnose and rectify systematic errors. For example, we sometimes found the model to incorrectly split "x sand,after] y" to "x x" (or y"" at the root node, When we manually disallowed such splits during decoding, performance increased by 1 %%-2% across the board, showcasing benefit of grammar-based models which makes it possible to directly manipulate model generations by intervening on the set of derivation rules.
3.2 Style Transfer
We next apply our approach on style transfer on English utilizing the StylePTB dataset from Lyu
et al. [78]. We focus on the three hard transfer tasks identified by the original paper: (1) active to passive, where a sentence has to be changed from active to passive voice (2808 examples), (2) adjective emphasis, where a sentence has to be rewritten to emphasize a particular adjective (696 examples) (3) verb/action emphasis, where a sentence has be rewritten to emphasize a particular verb/action (1201 examples)." !1 'The main difficulty with these tasks stems from the small training set combined with the relative complexity of these tasks.
For these experiments we set | = PP| = 8 and use the same restrictions on the rule set as in the SCAN experiments. We also found it helpful to contextualize the source embedding with bidirectional LSTM before feeding to the TreeLSTM encoder." 12 We further experiment with the
11 To encode information about which word to be emphasized in the adjective/verb emphasis tasks, we binary variable whose embedding is added to the word embedding on encoder side.
12 A drawback of using contextualized word embeddings as input to the TreeLSTM is that since the repre- sentations ha, for each node
function of the entire sentence (and not just the leaves), no

---

Transfer Type
Approach
BLEU-1
BLEU-2
BLEU-3
BLEU-4 METEOR ROUGE-L CIDEr
GPT2-finttnee
0.476
0.329
0.238
0.189
0.216
0.464
1.820
Seq2Scq Retricve-Ead
0.373
0.220
0.141
0.103
0.131
0.345
0.845
0.681
0.598
0.503
0.427
0.383
0.663
4,535
Human
0.931
0.881
0.835
0.795
0.587
0.905
8.603
Active to Passive
Seq2Seq
0,505
0.349
0.253
0.190
0.235
0.475
2,000
Neural QCFG
0,431
0.637
0,548
0.472
0,415
0.695
4.294
Seq2Seq + copy
0.838
0.735
0.673
0.598
0.467
0.771
5.941
Neural QCFG copy
0.836
0.771
0.713
0.662
0.499
0.803
6.410
GPT22linetune
0.263
0,079
0.028
0.000
0.112
0.188
0.386
Seq2Seq
0.187
0.058
0.018
0.000
0.059
0.179
0,141
Retrieve-Fdth
0.387
0.276
0.211
0.164
0.193
0,369
1.679
Human
0.834
0.753
0.679
0.661
0.522
0.811
6.796
Adj. Emphasis
Seq2Seq
0.332
0.333
0.051
0.000
0.142
0.27
0.845
Neural QCFG
0.348
0.178
0.062
0.000
0.162
0.317
0.667
Scq2Seq + copy
0.505
0,296
0.184
0.119
0.242
0.514
1.839
Neural QCFG + copy
0.676
0.506
0.393
0.316
0.373
0.683
3.424
GPT2-finetune
0.309
0.170
0.095
0.041
0.140
0.292
0.593
Seq2Seq
0.289
0.127
0.066
0.038
0.098
0,275
0,300
Retricve-Eche
0.416
0.284
0,209
0.148
0.223
0.423
1.778
Human
0.649
0,569
0.493
0.421
0.433
0,693
5.668
Verb Emphasis
Seq2Seq
0.355
0.152
0.083
0.043
0.151
0,320
0.530
Neural QCFG
0.431
0,250
0.140
0.073
0.219
0,408
1.097
Seq2Seq + copy
0.526
0.389
0.294
0.214
0.294
0.464
2.346
Neural QCFG + copy
0.664
0.512
0.407
0.319
0.370
0.589
3.227
Table 3: Results on the hard style transfer tasks from the StylePTB dataset [78]. For each transfer type, the top four rows are from Lyu et al. [78], while the bottom four rows are from this paper. Metrics such as BLEU and ROUGE are normally scaled to [0, 100] (as in Table 4), but here we keep them at [0, 1] as in the original paper.
phrase-level copy mechanism described in section 2.4. The original paper provides several strong baselines: finetuned GPT2, a standard sequence-to-scquene model, and the retricve-and-edit model from Hashimoto et al. [53]. We also train our own baseline sequence-to-sequence model with word-level copy mechanism. See Appendix A.3.2 for more details.
Results Table 3 shows the results where we observe that the neural QCFG performs well compared the various baselines. We further find that incorporating the copy mechanism improves results substantially for both the baseline LSTM and the neural QCFG. Figure 2 shows a test example from the active-lo-passive task, which shows the word- and phrase-level copying mechanism in action. In this example the source tree is linguistically incorrect, but the grammar is nonetheless able to appropriately transduce the output. Given that linguistic phrases are generally more likely to remain unchanged in these types tasks, incorporating this knowledge into the learning process could potentially improve results." 15 For example in Figure 2 the ideal case would be to copy the phrase "a 2-for-1 stock split" but this is not possible due to the incorrectly predicted source tree. Finally, although our approach ostensibly improves upon the basclines according to many of the n-gram- based metrics, we observed the generated sentences to be often ungrammatical, highlighting the limitations of automatic metrics for these tasks while at the same time indicating opportunities for further work in this area.
longer guarantee that target derivations such A[as] A ys. only depend on a, This somewhat hinders the interpretability of the node-level alignments.
13 As in the original paper we calculate the automatic metrics using the nlg-eval library, available at https:// //g: //gi thub. com/ /at///aaaaaaaaaaaeeaaeeaaaaae /nlg-/lga// eval.
"Even for models that do not explicitly use the copy mechanism, we indirectly allow for copying by replacing the (unk) token with the source token that the preterminal is combined with in the neural QCFG case, or the source token that had the maximum attention weight in the LSTM case. This explains the outperformance of our baseline sequence-to so-suuencce models compared the baselines from Lyu et al. [78], which roughly uses the same architecture.
''There are many ways to do this. For example, one could identify the longest overlap between the source and target, and use posterior regularization on the source PCFG to encourage to be valid constituent.
7

---

012
Nglo12]
0113
Natoral
Necer [17]
Nataral
Nitosl
unffirst corp.
2-for-1
stock spit
Nalasa
Nylasl
Palool
077 0/2
Prtagl Powllasl
split
Polazl
Prellaal
by
00
01
dedlared
2-for-1
is
declared
unifirst corp.
Figure 2: A test example from the active to passive style transfer task on the Penn Treebank. The induced tree from the learned source parser shown on the left, and the target tree derivation is shown the right. The source tree is linguistically incorrect but the model still able to correctly tranduce the oulput. Some examples of COPY nonterminals/preeemmnnt and their aligned source nodes are shown with dashed arrows.
3.3 Machine Translation
Our final experiment is on a small-scale English-Frence machine translation dataset from Lake and Baroni [68]. Here we are interested in evaluating the model in two ways: first, to see if it can perform well as a standard machine translation system on a randomly held out test set, and second, to if it can systematically generalize to unseen combinations. To assess the latter, Lake and Baroni [68] add 1000 repetitions of am daxy - je suis daxiste to the training set and test 8 new sentences that use daxy in novel combinations (e-g. he is daxy - il est daxiste and am not daxy - je ne suis pas daxiste). As the original dataset does not provide official splits, we randomly split the dataset into 6073 examples for training (1000 of which the "i am daxy" example), 631 examples for validation, and 583 for test." 16
For these experiments, we set [ IP| 14 and combine all source tree nodes with all nonter- minals/preterminal.. We place two restrictions on the rule set: for rules of the form S - Alaaa we restrict a; to be the root of the source tree (as in previous experiments), and for rules of the form A(a;] - B[a,)C[ax,) we restrict aj 0g to be the direct children of a; such that a * 0g (or a; itself a; has no children)." 17 As in the style transfer experiments, we also experiment with a bidirectional LSTM encoder which contextualizes the source word embeddings before the TreeLSTM layer. Our baselines here include standard .STM/Transformrr models as well as approaches that explicitly target compositional generalization [70, 19].
Results Table 4 shows BLEU on the regular test set of 583 sen- tences and accuracy on the 8 daxy sentences." 18 While the neural QCFG performs nontrivially, it soundly outperformed by well- tuned Transformer model, which performs impressively well even the daxy test set. We thus consider our results on machine trans- lation to be largely negative. Interestingly, the use of contextualized word embeddings (via the bidirectional LSTM) improves BLEU but hurts compositional generalization, highlighting the potential pitfalls of using flexible models which can sometimes entangle representations in undesirable ways." 20 Figure 3 shows several ex- amples of target tree derivations from the neural QCFG that does
Approach
BLEU daxy acc.
LSTM
25.1
12.5%
Transformer
30.4
100%
CGPS [70]
19.2
100%
NeSS [19]
100%
Neural QCFG
23.5
100%
+ BBLSTMM
26.8
75.0%
Table 4:
Results on English- French machine translation.
The original dataset has 10000 examples (not including the daxy examples), but many of them involve duplicate source sentences. We removed such duplicates in split of the data. 17 These restrictions are closer to the strict isormorphic requirement in synchronous context- grammars than in previous experiments. However they still allow for non isormorphic trees since os can be inherited if it has children.
18 For CGPS and NeSS, the original papers only assess accuracy on the daxy test set, and furthermore do not provide the training/valian valiaiiioill splits. To obtain BLEU for CGPS, we run the publicly available code (https://gg / thub com/yli1 1ylllyliyhae.. 1/CGPS) on our split of the data. For NeSS, the code is not publicly available but the authors provided version of their implementation. However, the provided code/hhperprrrmeeeess were tailored for the SCAN dataset, and despite our best efforts adapt the code/htypepprammeerss to our setup we were unable obtain sensible results on the machine translation dataset.
The Transformer did, however, require some hyperparameter tuning given the small size of our dataset. Similar findings have been reported by Wu al. [120] in the context of applying Transformers to moderately sized character-level transduction datasets.
This variant of the neural QCFG also does poorly on the compositional splits of SCAN.
8

---

Niall as tall as my father
Noll (1 not cat
Nati as tail as my father]
Pall
Nali m not a cat)
Pold
Pall]
Nyalm as tall as my father]
Pall
Nafm call
je
Nuslas tall as my father]
Naim]
Nolnot a cat)
suis
Nafas tail as)
Nafmy father]
Pra(m]
Pa/m]
Pa [nol]]
N11 cal)
Maslas tall)
Palas]
Prfmyl Paltather)
pes
Pisla] Ps[cal]
Pal (as)
Ps [tall))
que
mon
pere
chat
aussi
grand
Niall am very daxy
Nialhe is daxy .]
Niathe is not daxy II
Nyli am very daxy]
Pa(l
Nye is daxy)
Pa1l
N₂ [he is not daxy)
Pa
Palil
Nyzlam very daxy)
Ps Ihel
Nialia daxyl
Pylhel
Nia not daxy!
je
Pylam]
Niz(very daxy)
Pylis)
Pa(daxy)
il
Nglis)
Ingl daxy)
suis
Palveryl
Pa[daxyl
est
Pralis]
Palis] Pylnot)
Paldaxy]
tres
daxiste
est
daxiste
Figure 3: Target tree derivations from the English-French machine translation experiments. Top left is an example from the regular test set, top right is made-up example (which incorrectly translated by the model), and the bottom three trees are from the dayy test set. We do not explicitly show the source trees here instead show the source phrases as arguments to the target tree nonterminals/pretemmnnaa
not use contextualized word embeddings. The induced source trees are sometimes linguistically incorrect (e.g. in the top left example "as tall as" would not be considered a valid linguistic phrase), but the QCFG is still able to correctly transduce the output by also learning unconventional trees on the target side as well. This is reminiscent classic hierarchical phrase-based approaches to machine translation where the extracted phrases often do not correspond to linguistic phrases [20]. Finally, although the model does well on the daxy test set, it still incorrectly translates simple but unusual made-up examples such "i m not cat" (Figure 3, top right). This is despite the fact that examples of the form (am,m) not a æ - je ne suis pas (un,une) occur multiple times in the training set."' We speculate that while the probabilistic nature of the grammar and the use of distributed representations enables easier training, they contribute to the model's 's being (still) vulnerable to spurious correlations.
4 Discussion
While we have shown that neural quasi-synchronous grammars can perform well for some sequence- to-sequence learning tasks, there are several serious limitations. For one, the [[ ( dynamic program will likely pose challenges in scaling this approach to larger datasets with longer sequences." Predictive inference was also much more expensive since we found necessary to sample and score large number of target trees to perform well on the non-synthetic datasets (see Appendix A.3). The conditional independence assumptions made by the QCFG may also be too strong for some tasks that involve complex dependencies, and the approach may furthermore be inappropriate for domains where the input and output are not naturally tree-structured. The models were quite sensitive to hyperparameters and some datasets needed training over multiple random seeds to perform well. These factors make our approach much less "off-the-shelf" than standard sequence-to-sequee
models, although this may be partially attributable to the availability of a robust set of hyperparameters for existing approaches.
The other models were also unable to correctly translate this sentence.
Indeed, realistic machine translation datasets with longer sequences we quickly ran into memory issues when running the model on just single example, even with multi-GPU implementation of the inside algorithm distributed over four 32GB GPUs. To apply the model on longer sentences, an interesting future direction might involve working with a "soft" version of the grammar, where the nonterminals embeddings are contexualized against source elements via soft attention. The runtime and memory for marginalizing over target trees in this soft QCFG would have linear (instead of cubic) dependence source length.

---

At the start of this project, our initial hope was to show that classic, grammar grammar-based based approaches to sequence transduction had been unfairly overlooked in the current deep learning era, and that revisiting these methods with contemporary parameterizations would prove to be more than just an academic exercise. Disappointingly, this seems not to the case. While we did observe decent performance on niche datasets such as SCAN and StylePTB where inductive biases from grammars were favorably aligned to the task at hand, for tasks like machine translation our approach was thoroughly steamrolled by a well-tuned Transformer.
What role, then, can such models play in building practical NLP systems (if any)? It remains to be seen, but we venture some guesses. Insofar as grammars and other models with symbolic components are able to better surface model decisions than standard approaches, they may have a role in developing more controllable and interpretable models, particularly in the context of collaborative human-machin systems [40]. Alternatively, inflexible models with strong inductive biases have in the past been used to guide (overly) flexible neural models in various ways, for example by helping to generate additional data [58, 75] or inducing structures with which to regularize/augment models [24, 74,3 3, 127]. In this vein, it may be interesting to explore how induced structures from grammars (such as the tranduction rules in Table 2) can be used in conjunction with flexible neural models.
5 Related Work
Synchronous grammars Synchronous grammars and tree transducers have a long and rich history in natural language processing [2. 101, 118, 80, 36, 32, 84, 56, 115, 45, 12, 23, inter alia]. In this work we focus on the formalism of quasi-synchronous grammars, which relaxes the requirement that source trees be isomorphic to target trees. Qquasi-synchrone
grammars have enjoyed applications
across wide range of domains including in machine translation [103, 42, 43], question answering [112], paraphrase detection [27], sentence simplification [117, 116), and parser projection [104]. Prior work on quasi-synchronous grammars generally relied on pipelined parse trees for the source and only marginalized out the target tree, in contrast to the present work which treats both source and
target trees latent.
Compositional sequence-to-sqquenee learning Lake and Baroni [68] proposed the influential SCAN dataset for assessing the compositional generalization capabilities of neural sequence-to- sequence models. There has since been a large body of work on compositional sequence-to-see -equuneece learning through various approaches including modifications to existing architectures [70, 94, 44, 17, 26], grammars and neuro-symbolic models [86, 98, 85, 19, 76), meta-learning [67, 25], and data augmentation [6, 49, 50, 4]. Our approach is closely related to NQG-T5 [98] which uses a rules-based approach to induce non-pobbabilistic QCFG and then backs off to flexible sequence-to-sequence model during prediction the grammar cannot parse the input sequence.
Deep latent variable models There has much work neural parameterizaaions of classic proba- bilistic latent variable models including hidden Markov models, [109, 113, finite state transducers [91, 71] topic models [82, 30, 31], dependency models [59, 51, 15, 52, 123], and context-free gram- mars [64, 61, 133, 131, 125, 124]. These works essentially extend feature-based unsupervised learning [10] to the neural case with the use of neural networks over embedding parameterizations, which makes easy to share parameters and additionally condition the generative model on side information such auxiliary latent variables [52, 64], images [130, 60, 55J, video and audio [129], and source-side context [113, 99]. Since we marginalize over unobserved trees during learning, our work is also related the line of work on marginalizing out latent variables/structures for sequence transduction tasks [46, 33, 11, 66, 128, 90, 57, 69, 108, 111, inter alia].
6 Conclusion
In this paper we have studied sequence-to-sequence learning with latent neural grammars. We have shown that the formalism suuuhisynchoooous grammars provides a flexible tool with which to imbue inductive biases, operationalize constraints, and interface with the model. Future work in this area could consider: (1) revisiting richer grammatical formalisms (e.g. synchronous tree-adjoining grammars [101]) with contemporary parameterizations, (2) conditioning on other modalities such as images/audio for grounded grammar induction [100, 130, 60, 129], (3) adapting these methods to other structured domains such as programs and graphs, and (4) investigating how grammars and
symbolic models can be integrated with pretrained language models to solve practical tasks.
10

---

References
[1] Roee Aharoni and Yoav Goldberg, Towards String-to- Tree Neural Machine Translation. In Proceedings of ACL. 2017.
[2] Alfred Aho and Jeffrey Ullman. Syntax Directed Translations and Pushdown Assembler. Journal of Computer and System Sciences, 3:37-56, 1969.
[3] Ekin Akyürek and Jacob Andreas. Lexicon learning for Few-Shot Neural Sequence Modeling. In Proceedings of ACL, 2021.
[4] Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning to Recombine and Resample Data for Compositional Generalization. In Proceedings of ICLR, 2021.
[5] David Alvarez-Melis and Tommi Jaakkola. Tree-structured Decoding with Doubly-Recurrent Neural Networks. Proceedings of ICLR, 2017.
[6] Jacob Andreas. Good-Enough Compositional Data Augmentation. Proceedings of ACL, 2020.
[7] Jimmy Ba, Volodymyr Mnih, and Koray Kavukcuoglu. Multiple Ohject Recognition with Visual Attention. In Proceedings of ICLR, 2015.
[8] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural Machine Translation by Jointly Learning Align and Translate. In Proceedings of ICLR, 2015.
[9] James K. Baker. Trainable Grammars for Speech Recognition. In Proceedings of the Spring Conference the Acoustical Society of America, 1979.
[10] Taylor Berg-Kirkpatren Alexandre Bouchard-Cond Cotte John DeNero, and Dan Klein, Painless Unsupervised Learning with Features. In Proceedings of NAACL, 2010.
[11] Phil Blunsom, Trevor Cohn, and Miles Osborne. A Discriminative Latent Variable Model for Statistical Machine Translation. In Proceedings of ACL, 2008
[12] Phil Blunsom, Trevor Cohn, and Miles Osborne. Bayesian Synchronous Grammar Induction. In D. Koller,
D. Schuurmans, Y. Bengio, and L. Bottou, editors, Proceedings of NeurlPS, 2009.
[13] Rares- Darius Buhai, Yoni Halpem, Yoon Kim, Andrej Risteski, and David Sontag. Empirical Study of the Benefits of Overparameterrizatio Learning Latent Variable Models. Proceedings of ICML, 2020.
[14] David Burkett, John Blitzer, Dan Klein. Joint Parsing and Alignment with Weakly Synchronized Grammars. Proceedings of NAACI, 2010.
[15] Jan Buys and Phil Blunsom. Neural Syntactic Generative Models with Exact Marginalization. In Proceedings of NAACL, 2018.
[16] F. Casacuberta and Colin De La Higuera. Computational Complexity of Problems on Probabilistic Grammars and Transducers. In Grammatical Inference: Algorithms and Applications, volume 1891, pages 15-24, 2000.
[17] Rahma Chaabouni, Roberto Dessi, and Eugene Kharitonov. Can Transformers Jump Around Right in Natural Language? Assessing Performance Transfer from SCAN, arXiv:2012.00857, 2021.
[18] Xinyun Chen, Chang Liu, and Dawn Song. Tree-to- tree Neural Networks for Program Translation. In Proceedings of NewrlPS, 2018.
[19] Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. Compositional Generalization via Neural-Symboud Stack Machines. In Proceedings of NeurlPS, 2020.
[20] David Chiang. A Hierarchical Phrase-Basee Model for Statistical Machine Translation. In Proceedings of ACL, 2005.
[21] Justin T. Chiu Alexander M. Rush. Scaling Hidden Markov Language Models, Proceedings of EMNLP, 2020.
[22] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning Phrase Representations using RNN Incoder-Decodee for Statistical Machine Translation. In Proceedings EMNLP, 2014.

---

[23] Trevor Cohn and Mirella Lapata. Sentence Compression as Tree Transduction. Journal of Artificial Intelligence Rexearch, 34(1):637-674, 2009.
[24] Trevor Cohn, Cong Duy Vu Hoang, Ekaterina Vymolova, Kaisheng Yao, Chris Dyer, and Gholamreza Haffari. Incorporating Structural Alignment Biases into an Attentional Neural Translation Model. In Proceedings of NAACI, 2016.
[25] Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. Meta-Learning Compositionally Generalize. In Proceedings of ACL, 2021.
[26] Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The Devil the Detail: Simple Tricks Improve Systematic Generalization of Transformers. In Proceedings of EMNLP, 2021.
[27] Dipanjan Das and Noah A. Smith. Paraphrase Identification as Probabilistic Quasi-Synchronous Recogni- tion. In Proceedings of ACL,, 2009.
[28] Yuntian Deng, Yoon Kim, Justin Chiu, Demi Guo, and Alexander M. Rush. Latent Alignment and Variational Attention. In Proceedings of NeurlPS, 2018.
[29] Roberto Dessi and Marco Baroni. CNNs found to jump around more skillfully than RNNs: Compositional generalization in seq2seq convolutional networks. In Proceedings of ACL, 2019.
[30] Adji B. Dieng, Francisco J. R. Ruiz, and David M. Blei. The Dynamic Embedded Topic Model. 197.::1907.55555, 2019.
[31] Adji B. Dieng, Francisco J. R. Ruiz, and David M. Blei. Topic Modeling in Emhedding Spaces. Transactions of the Association for Computational Linguisties, 8, 2020.
[32] Yuan Ding and Martha Palmer. Machine Translation Using Probabilistic Synchronous Dependency Insertion Grammars. In Proceedings of ACL, 2005.
[33] Markus Dreyer, Jason Smith, and Jason Eisner. Vareible Modeling of String Transductions with Finite-State Methods. In Proceedings of EMNLP, 2008.
[34] Wenchao Du and Alan W Black. Top-Down Lexicalized Probabilistic Context-Free Grammar. In Proceedings of NAACL, 2019.
Neural Response Generation with
[35] Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent Neural Network Grammars. Proceedings of NAACL, 2016.
[36] Jason Eisner. Leamiing Non-Isomorphic Tree Mappings for Machine Translation. In Proceedings of ACL.
2003.
[37] Akiko Eriguchi, Yoshimasa Tsuruoka, and Kyunghyun Cho. Learning to Parse and Translate Improves Neural Machine Translation. In Proceedings of ACL, 2017.
[38] Daniel Furrer, Mare van Zee, Nathan Scales, and Nathanael Schärli. Compositional Generalization Semantic Parsing: Pre-training vs. Specialized Architectures. arXiv:2007.08971 2020.
[39] Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional Sequence to Sequence Learning. In Proceedings of ICML, 2017.
[40] Sebastian Gehrmann, Hendrik Strobelt, Robert Krueger, Hanspeter Pfister, and Alexander M Rush. Visual Interaction with Deep Learning Models through Collaborative Semantic Inference. IEEE Transactions on Visualization and Computer Graphics. 26(1):884 894, 2019.
[41] Daniel Gildea. Loosely Tree-Based Alignment for Machine Translation. In Proceedings of ACL, 2003.
[42] Kevin Gimpel and Noah A. Smith. Feature-Rich Translation by Suasi-Synchronous Lattice Parsing. In Proceedings of EMNLP, 2009.
[43] Kevin Gimpel and Noah A. Smith. Quasi-Synchronous Phrase Dependency Grammars for Machine Translation. In Proceedings of EMNLP, 2011.
[44] Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt, Pormutation Equivariant Models for Compositional Generalization in Language.. In Proceedingy of ICLR, 2020.
[45] Jonathan Grachl, Kevin Knight, and Jonathan May. Training Tree Transducers. Computational Linguistics. 34(3):391-475 2008.
12

---

[46] Alex Graves. Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks. In Proceedings ICML, 2006.
[47] Jiatao Gu, Zhengdong Lu, Hang Li, and Victor OK Li. Incorporating Copying Mechanism in Sequence- to-Sequence Learning. 2016.
[48] Caglar Gulcehre, Sungjin Ahn, Ramesh Nallapati, Bowen Zhou, and Yoshua Bengio. Pointing the Unknown Words. In Proceedings of ACL, 2016.
[49] Demi Guo, Yoon Kim, and Alexander Rush. Sequence-Leve Mixed Sample Data Augmentation. In Proceedings of EMNLP, 2020.
[50] Yinuo Guo, Hualei Zhu, Zeqi Lin, Bei Chen, Jian-Guang Lou, and Dongmei Zhang. Revisiting Iterative Back-Translation from the Perspective of Compositional Generalization. Proceedings of AAAI, 2021.
[51] Wenjuan Ham, Yong Jiang, and Kewei Tu. Dependency Grammar Induction with Neural Lexicalization and Big Training Data. In Proceedings of EMNLP, 2017.
[52] Wenjuan Han, Yong Jiang, and Kewei Enhaneing Unsupervised Generative Dependency Parser with Contextual Information. In Proceedings of ACL, 2019.
[53] Tatsunori B. Hashimoto, Kelvin Guu, Yonatan Oren, and Percy Liang. A Retrieve-and- Framework for Predicting Structured Outputs. In Proceedings of NeurlPS, 2018.
[54] Jonathan Herzig and Jonathan Berant. Span-based based Semantic Parsing for Compositional Generalization. arXiv:2009.06i0 2020.
[55] Yining Hong, Qing Li. Song-Chun Zhu, and Siyuan Huang. VLGrammar: Grounded Grammar Induction of Vision and Language. S.Ki:2113..1977 2021.
[56] Liang Huang, Kevin Knight, and Aravind Joshi. A Syntax-Directed Translator with Extended Domain of Locality. In Proceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing. 2006.
[57] Po-Sen Huang, Chong Wang. Sitao Huang, Dengyong Zhou, and Li Deng. Towards Neural Phrase-based Machine Translation. In Proceedings ICLR, 2018.
[58) Robin Jia and Percy Liang. Data Recombination for Neural Semantic Parsing. In Proceedings of ACL., 2016.
[59] Yong Jiang, Wenjuan Han, and Kewei Tu. Unsupervised Neural Dependency Parsing, In Proceedings of EMNLP, 2016.
[60] Lifeng Jin and William Schuler: Grounded PCFG Induction with Images. In Proceedings of AACL. Association for Computational Linguistics, 2020.
[61] Lifeng Jin, Finale Doshi Velez, Timothy Miller, Lane Schwartz, and William Schuler. Unsupervised I Learning of PCFGs with Normalizing Flow. In Proceedings of ACI. 2019.
[62] Nal Kalchbrenner and Phil Blunsom. Recurrent Continuous Translation Models, Pruceedings of EMNLP, 2013.
[63] Najoung Kim and Tal Linzen. COGS: A Compositional Generalization Challenge Based on Semantic Interpretation. In Proceedings of EMNLP, 2020.
[64] Yoon Kim, Chris Dyer, and Alexander M. Rush. Compound Probabilistic Context- Free Grammars for Grammar Induction. In Proceedings of ACL, 2019.
[65] Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander Rush. OpenNMT: Open-source toolkit for neural machine translation. In Proceedings of ACL, System Demonstrations, 2017.
[66] Lingpeng Kong, Chris Dyer, and Noah A. Smith. Segmental Recurrent Neural Networks. In Proceedings of ICLR, 2016.
[67] Brenden M. Lake. Compositional generalization through meta sequence-to--sqquene lcarning. In Proceedings of NewrIPS, 2019.
[68] Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of suueence-to-seqeene recurrent networks. In Proceedings of ICML, 2018.
13

---

[69] Xiang Lisa Li and Alexander M. Rush. Posterior Control of Blackbox Generation. In Proceedings of ACL, 2020.
[70] Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hestness. Compositional Generalization for Primitive Substituiinns In Proceedings of EMNLP, 2019.
[71] Chu-Cheng Lin, Hao Zhu, Matthew R. Gormley, and Jason Eisner. Neural Finite-State Transducers: Beyond Rational Relations. In Proceedings of NAACI, 2019.
[72] Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R. Gormley, and Jason Eisner. Limitations of Autoregres- sive Models and Their Alternatves. In Pruceedings of NAACL, 2021.
[73] Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Fumin Wang. and Andrew Senior. Latent predictor networks for code generation. In Proceedings of 2016.
[74] Lemao Liu, Masao Utiyama, Andrew Finch, and Eiichiro Sumita, Neural Machine Translation with Supervised Attention. In Proceedings of COLING, 2016.
[75] Qi Liu, Matt Kusner, and Phil Blunsom. Counterfactual Data Augmentation for Neural Machine Translation. In Proceedings of NAACL, 2021.
[76] Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Zhou, Nanning Zheng, and Dongmei Zhang. Compositional Generalization by Learning Analytical Expressions. In Proceedings of NeurIPS, 2020.
[77] Rune B. Lyngse and Christian N. S. Pedersen. The consensus string problem and the complexity of comparing hidden Markov models. J. Comput. Syst. Sci., 65(3):545- 569, 2002.
[78] Yiwei Lyu, Paul Pu Liang, Hai Pham, Eduard Hovy, Barnabás Póczos, Ruslan Salakhutdinov, and Louis- Philippe Morency. StylePTB: A Compositional Benchmark for Fine- mne-grained Controllable Text Style Transfer. In Proceedings of NAACL, 2021.
[79] R. Thomas McCoy, Robert Frank, and Tal Linzen. Does Syntax Need to Grow on Trees? Sources of Hierarchical Inductive Bias in seruuence-toSeqquene Networks. Transactions of the Association for Computational Linguistics, 8:125-140, 2020.
[80] I. Dan Melamed, Multitext Grammars and Synchronous Parsers. In Proceedings of NAACL, 2003.
[81] I. Dan Melamed, Giorgio Satta, and Benjamin Wellington. Generalized Multitext Grammars. In Proceedings of ACL, 2004.
[82] Yishu Miao, Edward Grefenstette, and Phil Blunsom. Discovering Discrete Latent Topics with Neural Variational Inference. In Proceedings of ICML, 2017.
[83] Ramesh Nallapati, Bowen Zhou, Cicero dos Santos, Caglar Gulcehre, and Bing Xiang. Abstractive Text Summarization using Sequence- coaeiecettt-eqquee to-qqueence RNNs and Beyond. In Proceedings of CoNLL.
[84] Rebecca Nesson, Stuart Shieber, and Alexander Rush. Induction of Probabilistic Synchronous Tree- insertion Grammars for Machine Translation. In Proceedings of AMTA, 2006.
[85] Maxwell I. Nye, Armando Solar-Lezama, Joshua B. Tenenbaum, and Brenden M. Lake. Learning Compositional Rules via Neural Program Synthesis. In Proceedings of NeurlPS, 2020.
[86] Inbar Oren, Jonathan Herzig. Nitish Gupta, Matt Gardner, and Jonathan Berant. Improving Compositional Generalization in Semantic Parsing. In Proceedings of EMNLP, 2020.
[87] Sheena Panthaplackel. Miltiadis Allamanis, and Mare Brockschmidt. Copy that! Editing Sequences by Copying Spans. In Proceedings of AAAI, 2021.
[88] Nikhil Prabhu and Katharina Kann. Making Point: Pointer-Geenerator Transformers for Disjoint Vocabularics. In Proceedings of AACI: Student Research Workshop, 2020.
[89] Maxim Rabinovich, Mitchell Stern, and Dan Klein. Abstract Syntax Networks for Code Generation and Semantic Parsing. In Proceedings of ACL, 2017.
[90] Colin Raffel, Kinh-Thang Luong, Peter J. Liu, Ron J. Weiss, and Douglas Eck, Online and Linear- Time Attention by Enforcing Monotonic Alignments. In Proceedingy of ICML, 2017.
[91] Pushpendre Rastogi, Ryan Cotterell, and Jason Eisner. Weighting Sinite-State Transductions With Neural Context. In Proceedings of 2016.
14

---

[92] Steven J. Rennie, Etienme Marcheret, Youssef Mroueh, Jarret Ross, and Vaibhava Goel. Self-critical Sequence Training for Image Captioning. In Proceedings of CVPR, 2017.
[93] Alexander M. Rush. Torch-Struct: Deep Structured Prediction Library, In Proceedings of ACL (System Demonstrations), 2020.
[94] Jake Russin, Jason Jo, Randall C. O'Reilly, and Yoshua Bengio. Compositional Generalization in a Deep Seq2seq Model by Separating Syntax and Semantics, arXiv: (9XY::990,00708, 2019.
[95] Abigail See, Peter J. Liu, and Christopher D. Manning. Get To The Point: Summarization with Pointer- Generator Networks. In Proceedings of ACL, pages 1073-1083, 2017.
[96] Shiv Shankar, Siddhant Garg, and Sunita Sarawagi. Surprisingly Easy Hard-Attention for Sequence to Sequence Learning. In Proceedings of EMNLP. 2018.
[97] Jetie Guand Hassan S. Shavarani and Anoop Sarkar. Top-down Tree Structured Decoding with Syntactic Connections for Neural Machine Translation and Parsing. In Proceedings of EMNLP, 2018.
[98] Peter Shaw, Ming-Wey Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? In Proceedings of ACL, 2021.
[99] Xiaoyu Shen, Ernie Chang, Hui Su, Cheng Niu, and Dietrich Klakow. Neural Data-to- Text Generation via Jointly Learning the Segmentation and Corresoondecee. In Proceedings ACL, 2020.
[100] Haoyue Shi, Jiayuan Mao, Kevin Gimpel, and Karen Livescu. Visually Grounded Neural Syntax Acquisition. In Proceedings of ACL, 2019.
[101] Stuart M. Shieber and Yees Schabes. Synchronous Tree-Adjoining Grammars. COLING 1990 Volume
3: Papers presented to the 13th International Conference on Computational Linguistics, 1990.
[102] Khalil Sima' an. Computational Complexity of Prohabilistic Disambiguation by means of Tree-Grammars In Proceedings of COLING, 1996.
[103] David Smith and Jason Eisner. Quasi-Synchronous Grammars: Alignment by Soft Projection of Syntactic Dependencies. In Proceedings on the Workshop on Statistical Machine Translation, 2006.
[104] David Smith and Jason Eisner. Parser Adaptation and Projection with Quasi-Synchronous Grammar Features. In Proceedings of EMNLP, Singapore, 2009.
[105] Andreas Stoleke. An Efficient Prohabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities. Computational Linguistics, 21(2), 1995.
[106] Ilya Sutskever, Oriol Vinyals, and Quoc Le. Sequence Sequence Learning with Neural Networks. In Proceedings of NeurlPS, 2014.
[107] Kai Sheng Tai, Richard Socher. and Christopher D. Manning. Improved Semantic Representations From T're-SStrucure Long Short-Term Memory Networks. In Proceedings of ACL, 2015.
[108] Shawn Tan, Yikang Shen, Alessandro Sordoni, Aaron Courville, and Timothy J. O'Doneell. Recursive Top-Down Production for Sentence Generation with Latent Trees. In Findings of the Association for Computational I linguistics: EMNLP, 2020.
[109] Ke Tran, Yonatan Bisk, Ashish Vaswani, Daniel Mareu, and Kevin Knight. Unsupervised Neural Hidden Markov Models. In Proceedings of the Workshop on Structured Prediction for NLP, 2016.
[110] Ashish Vaswani. Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All You Need. In Proceedings of NeurlPS, 2017.
[111] Bailin Wang, Mirella Lapata, and Ivan Titov. Structured Reordering for Modeling Latent Alignments in Sequence Transduction. arXiv: 106.0:2.6 2021.
[112] Mengqiu Wang, Noah A. Smith, and Teruko Mitamura. What is the Jeopardy Model? A Quasi- Synchronous Grammar for QA. In Proceedings EMNLP, 2007.
[113] Sam Wiseman, Stuart M. Shieber, and Alexander M. Rush. Learning Neural Templates for Text Generation. In Proceedings of EMNLP, 2018.
[114] Sam Wiseman, Arturs Backurs, and Karl Stratos. Generating (Formulaic) Text by Splicing Together Nearest Neighbors. 4rX.v:2001.08248 2021.
15

---

[115] Yuk Wah Wong and Raymond Mooney, Learning Synchronous Grammars for Semantic Parsing with Lambda Calculus. In Proceedings of ACL, 2007.
[116] Kristian Woodsend and Mirella Lapata. Learning to Simplify Sentences with Quasi-Synchronous Grammar and Integer Programming. In Proceedings of EMNLP, 2011.
[117] Kristian Woodsend, Yansong Feng, and Mirella Lapata. Tide Generation with Quasi-Synchronous Grammar. In Proceedings of EMNLP, 2010.
[118] Dekai Wu. Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora. Computational Linguistics, 23(3):377-4033 1997.
[119] Shijie Wu, Pamela Shapiro, and Ryan Cotterell. Hard Non-Monotonic Attention for Character-Level Transduction. In Proceedings of EMNLP, 2018.
[120] Shijie Wu, Ryan Cotterell, and Mans Huiden. Applying the Transformer to Character-level Transduction. In Proceedingy of EACL, 2021.
[121] 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 Proceedings of ICML, 2015.
[122] Kenji Yamada and Kevin Knight. A Syntax-based Statistical Translation Model. In Proceedings of ACL, 2001.
[123] Songlin Yang. Yong Jiang, Wenjuan Han, and Kewei Tu. Sccond-Order Unsupervised Neural Dependeney Parsing, In Proceedings of the 28th International Conference on Computational Linguistics, 2020.
[124] Songlin Yang, Yanpeng Zhao, and Kewei Tu. Neural Bi-Lexicalized PCFG Induction. In Proceedings ACI., 2021.
[125] Songlin Yang, Yanpeng Zhao, and Kewei Tu. PCFGs Can Do Better: Inducing Probabilistic Context- Free Grammars with Many Symbols. Proceedings of NAACL, 2021.
[126] Pengcheng Yin and Graham Neubig. Syntactic Neural Model for General-Purpose Code Generation. Proceedings of ACI., 2017.
[127] Pengcheng Yin, Hao Fang, Graham Neubig, Adam Pauls, Emmanouil Antonios Platanios, Yu Su, Sam Thomson, and Jacob Andreas. Compositional Generalization for Neural Semantic Parsing via Span-level Supervised Attention. In Proceedings of NAACL, 2021.
[128] Lei Yu, Jan Buys, and Phil Blunsom. Online Segment to Segment Neural Transduction. In Proceedings of EMNLP, 2016.
[129] Songyang Zhang, Linfeng Song, Lifeng Jin, Kun Xu, Dong Yu, and Jieho Luo. Video-aided Unsupervised Grammar Induction. In Proceedings of NAACI, 2021.
(130) Yanpeng Zhao and Ivan Titov. Visually Grounded Compound PCFGs. Proceedings of EMNLP. 2020.
[131] Yanpeng Zhao and Ivan Titov. An Empirical Study Compound PCFGs. In Proceedings of the Second Workshop on Domain Adaptation for NLP, Association for Computational Linguistics, 2021.
[132] Qingyu Zhou, Nan Yang, Furu Wei, and Ming Zhou. Sequential Copying Networks. In Proceedings of AAAI, 2018.
[133] Hao Zhu, Yonatan Bisk, and Graham Neubig. The Return of Lexical Dependencies: Neural Lexicalized PCFGs. Transactions of the Association for Computational Linguistics, 8:647-661, 2020.
[134] Xiaodan Zhu, Parinaz Sobhani, and Hongyu Guo. Long Short-Term Memory Over Tree Structures. In Proceedings of ICML, 2015.
16


Reviews:
[{"review_id": "yNbMQiP1L55", "reviewer": "Reviewer_fSHR", "summary": "This paper investigates an neural approach of probabilistic quasi-synchronous context-free grammars (QCFG) and its application in various sequence-to-sequence applications.  QCFG is a type of very general tree-to-tree synchronous grammar where any subset of nodes in the source tree can be aligned to a node in the target tree.  This paper proposes an neural approach to QCFG, where the representation of tree nodes are parameterized with a TreeLSTM model. Further, the paper conducts a joint training of a source parser and the QCFG, where the source syntax tree is a binary tree without labels in the nodes.  A complex combination of techniques including Monte Carlo estimation, dynamic programming, MAP infrerence, approximate decoding is used to deal with the complexity in training and inference.  Further extensions are proplsed to deal with the phrase-to-phrase copying, domain specific constraints problems and adding autogressive language models.  Experimewnts are conducted in three tasks: natural language to commands, style transfer, and machine translation.  All experiments show significant improvement over previous work, especially seq2seq-LSTM models.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "Pro:\n\nA novel seq2seq neural model with latent syntax models.  The model can be trained solely in parallel texts without syntax treebanks.  Experiments show improvements on various tasks.\nCase studies demonstrate that the proposed method better model the structural alignents between the source and target texts and have better performance in compositional problems.  \n\nCons:\n\nThe experiments are all in quite small scale.  I wonder if it works the same well with large training data.  \nThe computational cost is rather high.  I hope to see the training time of these models.\n\n\nSuggestions:\n\nLine 148-153 Incorporating autogressive language models: not very clear to me.  More explanation or an example is needed.\nSection 3.3: The seq2seq-LSTM is a bit weak as a baseline.  Transformer should be added.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "X0pEbs3RfAc", "reviewer": "Reviewer_FyUp", "summary": "This paper describes a sequence-to-sequence model that models both source and target trees as latent variables; the target tree is related to the source tree “quasi-synchronously.” The model is trained using REINFORCE.\n", "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": "# Model\n\nThe model is a pretty original departure from existing translation models, even those that use trees. I think it's great to see something like this working.\n\nGiven the complexity of the training method, I would really like to see some discussion of training time and scalability, like how many hours it takes to run the experiments in the papers, or what the largest parallel text you're able to train on is.\n\n# Experiments\n\nThe model performs “respectably” on SCAN; compared with the other domain-agnostic methods, it’s clearly the best. What do the dashes in Table 1 mean? Is there any way to evaluate the methods above the line without SCAN-specific knowledge? Or to evaluate your method using comparable SCAN-specific knowledge?\n\nThe model also does well on several English rewriting tasks (e.g., active to passive). In Table 2 it might help to bold the best non-human score, which appears to almost always be your model. I think it would make sense to include a Transformer+copy baseline as well.\n\nThere is also an experiment on a *very* small machine translation task. Although the source for the data is cited, I think the size of the task should be stated more clearly: the sentences always begin with phrases like “I am,” “he is,” etc. and have at most 9 words each. Again, I think it would make sense to include a Transformer baseline here.\n\n# Other\n\nI feel that the introduction could be improved by being made more concise and getting more quickly to the really original part of the paper, the use of latent trees (currently not mentioned  until page 2). For example, “factorization of the output distribution via the chain rule coupled with a richly-parameterized neural network that models the local conditional distribution over the next element given the previous elements” seems to me like a very long way of saying “a neural model of p(y_t | y_1 \\cdots y_{t-1})”.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Given the complexity of the training method, I would like to see more discussion of training time and scalability. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "Rfk6jT6mHms", "reviewer": "Reviewer_6KbN", "summary": "The paper proposes a grammar-based method for sequence-to-sequence learning. The model is based on two latent grammars with neural parametrization. The source Probabilistic Context Free Grammar (PCFG) models the latent tree structure of the source sequence. The target Quasi (Probabilistic) Context Free Grammar jointly models the latent tree structure of the target sequence and the alignment between the source and the target tree. Both source and target parses need to be marginalized out in order to train the model. The proposed method performs approximate marginalization by sampling the source trees and then exactly marginalizing the target trees with an algorithm of a high yet polynomial computational complexity. The algorithm achieves high performance on the compositional tasks from SCAN, style-transfer and small-scale translation tasks. ", "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": "Quality: I find the presented results sufficient for publication. The quantitative results are better than adequately chosen baselines. The qualitative results give useful insights into the inner workings of the method. \n\nFurther quality improvements can be achieved:\n- More synthetic compositional generalization datasets could be used (COGS, CFQ, CLOSURE) \nIt would be nice to see semantic parsing experiments using natural data. In particular, a lot of similar methods (e.g. [46])  have recently been tested on GeoQuery. \n- Some ablation results would be nice to have. What if a linear source parse is used?\n- Error analysis for SCAN\n\nClarity: the paper is well-written and clear for people with a bit of background in grammars and computational linguistics. To make it more accessible for a wider audience, I would recommend including pseudocodes for the target parse marginalization and for the inference. \n\nOriginality: there is a fair amount of work on more compositional seq2seq transduction algorithms, some of which is using grammars (e.g. [46]). The paper appears sufficiently distinct for other works, but a deeper discussion on its similarities/differences with other grammar-based approaches would not hurt.\n\nSignificance: the fact that a grammar-based model with so many latent variables can be trained and can perform well is a significant result. More experiments could further increase significance. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is quite up-front about the limitations of the proposed method, such as conditional independence assumptions and computational complexity. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6M73M06zmCC", "reviewer": "Reviewer_e5Ff", "summary": "This paper proposes a framework for sequence-to-sequence learning with synchronous grammars. In this framework, both the source trees and target trees are modeled as latent variables, and each node in the target tree is transduced by a subset of nodes in the source tree. These latent trees are marginalized out during training and no extra supervision is required. The grammars are parameterized by neural parameters so that the model can be trained end-to-end without manual feature engineering. Such hierarchical, latent seq2seq modeling makes the generation process more interpretable than typical seq2seq models like LSTM or transformers, as well as providing an interface to add inductive bias easily, for which the paper has included several examples. The experiments are focused on settings where generalization is difficult (e.g. compositional generation or when the training data is small),  on language navigation, style transfer, and machine translation tasks the proposed model outperforms traditional seq2seq models substantially, demonstrating better sample efficiency. \n", "questions": "", "limitations": "", "rating": 9, "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": "I’ll detail the strengths, weaknesses, and questions below:\n### Strengths:\n\n1. I think the direction is very interesting and important. Currently, most neural models are data-driven without explicit inductive bias, which is uninterpretable and often with low sample efficiency. Therefore, in many domains/tasks generalization (e.g. compositional generalization) is of great interest to the community. While there are some methods like data augmentation to improve generalization, this paper proposes a more principled method and tackles the issue from the model framework itself. Therefore, I think this paper stands as a strong contribution to propose a new model class and show its effectiveness, and could potentially open a new path for future work to study generalization from a different perspective.\n\n\n2. The techniques are novel in modern seq2seq tasks. While the concept of QCFG is not new, the neural parameterization, implementation on recent seq2seq benchmarks, and strong results compared to traditional neural seq2seq models are non-trivial efforts.\n\n\n3. In Section 2.4, the examples on how to imbue inductive bias and connection to some common techniques in NN are very intriguing, there could be future interesting work on this aspect to add different inductive bias on various tasks/datasets.\n\n\n4. Empirical results are strong.\n\n\n5. The paper is very well-written, I enjoyed reading it a lot.\n\n\n### Weaknesses:\n\nThe main weaknesses are the complexity of the method and high time complexity due to the dynamic program, which could limit the method in large-scale settings as acknowledged by the authors. \n", "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": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a neural approach of probabilistic quasi-synchronous context-free grammars (QCFG) and evaluates its application to various sequence-to-sequence applications (natural language to command, style transfer, and machine translation). While tree-based, the approach doesn’t require any treebank or other linguistic annotation, and training is end-to-end without any manual feature engineering.

Overall, reviews find the paper to be quite strong. While there is prior work on quasi-synchronous grammars, the neural parameterization of the paper, the non-reliance on feature engineering, the application to recent benchmarks, and strong results are seen as significant contributions. The overall direction of this work is important compared to current fully data-driven models, which typically do not incorporate any inductive bias and can cause low sample efficiency and over-reliance on surface-form information. 

The only main weaknesses of the paper are high time complexity and experiments that are overall small scale. But I think it is reasonable to downplay these limitations, as one of the stated goals of the paper is sample efficiency rather than ability to efficiently train on large datasets.  

Decision: Accept (Spotlight)