1 Introduction↩︎

Sequence-to-sequence learning with neural networks [1]–[3] encompasses a powerful and general class of methods for modeling the distribution over an output target sequence \({\boldsymbol{y}}\) given an input source sequence \({\boldsymbol{x}}\). Key to its success is a 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 word given the previous words and the input. While architectural innovations such as attention [4], convolutional layers [5], and Transformers [6] have led to significant improvements, this word-by-word modeling remains core to 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 on diagnostic tasks designed to test for compositional generalization [8], [9]. This is partially attributable to the fact that standard sequence-to-sequence models have relatively weak inductive biases (e.g. for capturing hierarchical structure [10]), 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-sequence learning with latent neural grammars. This work departs from previous approaches in three ways. First, we model the distribution over the target sequence with a quasi-synchronous grammar [11] which assumes a hierarchical generative process whereby each node in the target tree is transduced by nodes in the source tree. Such node-level alignments provide provenance and a 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 compositional generalization compared to non-hierarchical models. Second, in contrast the existing line of work on incorporating (often observed) tree structures into sequence modeling with neural networks [12]–[20], 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 handcrafted/pipelined features [11], [21]–[26] we make use of neural features to parameterize the grammar’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 a larger pipelined system (e.g. to extract alignments) [27]–[29].

We apply our approach to a variety of sequence-to-sequence learning tasks—SCAN language navigation task designed to test for compositional generalization [8], style transfer on the English Penn Treebank [30], and small-scale English-French machine translation—and find that it performs respectably compared to baseline approaches.

2 Neural Synchronous Grammars for Sequence-to-Sequence Learning↩︎

We use \({\boldsymbol{x}}= x_1, \dots, x_S\), \({\boldsymbol{y}}= y_1, \dots, y_T\) to denote the source/target strings, and further use \({\boldsymbol{s}}\), \({\boldsymbol{t}}\) to refer to source/target trees, represented as a set of nodes including the leaves (i.e. \(\mathop{\mathrm{yield}}({\boldsymbol{s}}) = {\boldsymbol{x}}\) and \(\mathop{\mathrm{yield}}({\boldsymbol{t}}) = {\boldsymbol{y}}\)).

2.1 Quasi-Synchronous Grammars↩︎

Quasi-synchronous grammars, introduced by [11], define a monolingual grammar over target strings conditioned on a source tree, where the grammar’s rule set depends dynamically on the source tree \({\boldsymbol{s}}\). In this paper we work with probabilistic quasi-synchronous context-free grammars (QCFG), which can be represented as a tuple \(G[{\boldsymbol{s}}] = (S, \mathcal{N}, \mathcal{P}, \Sigma, \mathcal{R}[{\boldsymbol{s}}], \theta)\) where \(S\) is the distinguished start symbol, \(\mathcal{N}\) is the set of nonterminals which expand to other nonterminals, \(\mathcal{P}\) is the set of nonterminals which expand to terminals (i.e. preterminals), \(\Sigma\) is the set of terminals, and \(\mathcal{R}[{\boldsymbol{s}}]\) is a set of context-free rules conditioned on \({\boldsymbol{s}}\), where each rule is one of \[\begin{align} &S \to A[\alpha_i], &&\text{A \in \mathcal{N},\alpha_i \subseteq {\boldsymbol{s}}} \\ &A[\alpha_i] \to B[\alpha_j]C[\alpha_k], &&\text{A \in \mathcal{N},B, C \in \mathcal{N}\cup \mathcal{P}, \alpha_i, \alpha_j, \alpha_k \subseteq {\boldsymbol{s}}} \\ &D[\alpha_i] \to w, &&\text{D \in \mathcal{P}, w \in \Sigma,\alpha_i \subseteq {\boldsymbol{s}}}. \end{align}\] We use \(\theta\) to parameterize the rule probabilities \(p_\theta(r)\) for each \(r \in \mathcal{R}[{\boldsymbol{s}}]\). In the above, \(\alpha_i\)’s are subsets of nodes in the source tree \({\boldsymbol{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 [31] 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 common.³ Since the \(\alpha_i\)’s are elements of the power set of \({\boldsymbol{s}}\), the above formulation as presented is completely intractable. We follow prior work [11], [24] and restrict \(\alpha_i\)’s to be single nodes (i.e. \(\alpha_i, \alpha_j, \alpha_k \in {\boldsymbol{s}}\)), which amounts to assuming that each target tree node is aligned to exactly one source tree node.

In contrast to standard, “flat” sequence-to-sequence models where any hierarchical structure necessary for the task must be captured implicitly within a neural network’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.⁴ More generally, the grammar’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 [sec:copy]).

2.2 Parameterization↩︎

Since each source tree node \(\alpha_i\) is likely to occur only a 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 [11], [26]. In this work we instead use a 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[\alpha_i]\) as an embedding, \[\begin{align} \mathbf{e}_{A[\alpha_i]} = \mathbf{u}_{A} + \mathbf{h}_{\alpha_i}, \end{align}\] where \(\mathbf{u}_{A}\) is the embedding for \(A\), and \(\mathbf{h}_{\alpha_i}\) is the representation of node \(\alpha_i\) given by running a TreeLSTM over the source tree \({\boldsymbol{s}}\) [39], [40]. These embeddings are then combined to produce the probability of each rule, \[\begin{align} &p_\theta(S \to A[\alpha_i]) &&\propto \exp\left(\mathbf{u}_{S}^\top \mathbf{e}_{A[\alpha_i]}\right),\\ &p_\theta(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]) &&\propto \exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B[\alpha_j]}) + f_{\text{3}}(\mathbf{e}_{C[\alpha_k]}))\right), \\ &p_\theta(D[\alpha_i] \to w) && \propto \exp\left(f_4(\mathbf{e}_{D[\alpha_i]})^\top\mathbf{u}_{w} + b_w \right), \end{align}\] where \(f_1, f_2, f_3, f_4\) are feedforward networks with residual layers (see Appendix 7.1 for the exact parameterization). Therefore the learnable parameters in this model are the nonterminal embeddings (i.e. \(\mathbf{u}_A\) for \(A \in \{S\} \cup \mathcal{N}\cup \mathcal{P}\)), terminal embeddings/biases (i.e. \(\mathbf{u}_w, b_w\) for \(w \in \Sigma\)), and the parameters of the TreeLSTM and the feedforward networks.

2.3 Learning and Inference↩︎

The QCFG described above defines a distribution over target trees (and by marginalization, target strings) given a 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 a probabilistic source-side parser along with the QCFG. This parser is a monolingual PCFG with parameters \(\phi\) that defines a posterior distribution over binary parse trees given source strings, i.e. \(p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})\). Our PCFG uses the neural parameterization from [41]. With the parser in hand, we are now ready to define the log marginal likelihood, \[\begin{align} \log \,p_{\theta,\phi}({\boldsymbol{y}}\,\vert\,{\boldsymbol{x}}) = \log \left( \sum_{{\boldsymbol{s}}\in \mathcal{T}({\boldsymbol{x}})} \sum_{{\boldsymbol{t}}\in \mathcal{T}({\boldsymbol{y}})} p_\theta({\boldsymbol{t}}\,\vert\,{\boldsymbol{s}})p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}}) \right). \end{align}\] Here \(\mathcal{T}({\boldsymbol{x}})\) and \(\mathcal{T}({\boldsymbol{y}})\) are the sets of trees whose yields are \({\boldsymbol{x}}\) and \({\boldsymbol{y}}\) respectively. Unlike in synchronous context-free grammars, it is not possible to efficiently marginalize over both \(\mathcal{T}({\boldsymbol{y}})\) and \(\mathcal{T}({\boldsymbol{x}})\) due to the non-isomorphic assumption. However, we observe that the inner summation \(\sum_{{\boldsymbol{t}}\in \mathcal{T}({\boldsymbol{y}})} p_\theta({\boldsymbol{t}}\,\vert\,{\boldsymbol{s}}) = p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}})\) can be computed with the usual inside algorithm [42] in \(\mathcal{O}(\vert\mathcal{N}\vert (\vert \mathcal{N}\vert + \vert \mathcal{P}\vert )^2 S^3 T^3)\), where \(S\) is the source length and \(T\) is the target length. This motivates the following lower bound on the log marginal likelihood, \[\begin{align} \log p_{\theta, \phi}({\boldsymbol{y}}\,\vert\,{\boldsymbol{x}}) \ge \mathbb{E}_{{\boldsymbol{s}}\sim p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})}\left[\log p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}) \right], \end{align}\] which is obtained by the usual application of Jensen’s inequality (see Appendix 7.2).⁵

An unbiased Monte Carlo estimator for the gradient with respect to \(\theta\) is straightforward to compute given a sample from \(p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})\), since we can just backpropagate through the inside algorithm. For the gradient respect to \(\phi\), we use the score function estimator with a self-critical baseline [43], \[\begin{align} \nabla_\phi \, \mathbb{E}_{{\boldsymbol{s}}\sim p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})}\left[\log p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}) \right] \approx \left(\log p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}') - \log p_\theta({\boldsymbol{y}}\,\vert\,\widehat{{\boldsymbol{s}}}) \right) \nabla_\phi \log p_\phi({\boldsymbol{s}}' \,\vert\,{\boldsymbol{x}}), \end{align}\] where \({\boldsymbol{s}}'\) is a sample from \(p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})\) and \(\widehat{{\boldsymbol{s}}}\) is the MAP tree from \(p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})\). We also found it important to regularize the source parser by simultaneously training it as a monolingual PCFG, and therefore add \(\nabla_\phi \log p_\phi({\boldsymbol{x}})\) to the gradient expression above.⁶ Obtaining the sample tree \({\boldsymbol{s}}'\), the argmax tree \(\widehat{{\boldsymbol{s}}}\), and scoring the sampled tree \(\log p_\phi({\boldsymbol{s}}' \,\vert\,{\boldsymbol{x}})\) all require \(\mathcal{O}(S^3)\) dynamic programs. Hence the runtime is still dominated by the \(\mathcal{O}(S^3 T^3)\) dynamic program to compute \(\log p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}')\) and \(\log p_\theta({\boldsymbol{y}}\,\vert\,\widehat{{\boldsymbol{s}}})\).⁷ We found this to be manageable on modern GPUs with a vectorized implementation of the inside algorithm. Our implementation uses the \(\textsf{\fontsize{9}{10}\selectfont Torch-Struct}\) library [44].

2.3.0.1 Predictive inference

For decoding, we first run MAP inference with the source parser to obtain \(\widehat{{\boldsymbol{s}}} = \mathop{\mathrm{argmax}}_{{\boldsymbol{s}}} p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})\). Given \(\widehat{{\boldsymbol{s}}}\), finding the most probable sequence \(\mathop{\mathrm{argmax}}_{{\boldsymbol{y}}} p_\theta({\boldsymbol{y}}\,\vert\,\widehat{{\boldsymbol{s}}})\) (i.e. the consensus string of the grammar \(G[\widehat{{\boldsymbol{s}}}]\)) is still difficult, and in fact NP-hard [45]–[47]. We therefore resort to an approximate decoding scheme where we sample \(K\) target trees \({\boldsymbol{t}}^{(1)}, \dots {\boldsymbol{t}}^{(K)}\) from \(G[\widehat{{\boldsymbol{s}}}]\), rescore the yields of the sampled trees, and return the tree whose yield has the lowest perplexity.

2.4 Extensions↩︎

Here we show that the formalism of synchronous grammars provides a flexible interface with which to interact with the model.

2.4.0.1 Phrase-level copying

Incorporating copy mechanisms into sequence-to-sequence models has led to significant improvements for tasks where there is overlap between the source and target sequences [48]–[53]. 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-purpose nonterminal/preterminal that always copies the yield of the source subtree that it is combined with. Concretely, letting \(A_\mathrm{\small copy} \in \mathcal{N}\) be a copy nonterminal, we can expand the rule set \(\mathcal{R}[{\boldsymbol{s}}]\) to include rules of the form \(A_\mathrm{\small copy}[\alpha_i] \to v\) for \(v \in \Sigma^{+}\), and define the probabilities to be, \[\begin{align} p_\theta(A_\mathrm{\small copy}[\alpha_i] \to v) \, \mathrel{\overset{\makebox[0pt]{\normalfont\tiny \mathop{\mathrm{def}}}}{=}}\, \mathbb{1}\{v = \mathop{\mathrm{yield}}(\alpha_i)\}. \end{align}\] (The preterminal copy mechanism is similarly defined.) Computing \(p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}})\) in this modified grammar requires a straightforward modification of the inside algorithm.⁹ In our style transfer experiments in section [sec:styleptb] we show that this phrase-level copying is 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 [57], [58].

2.4.0.2 Adding constraints on rules

For some applications we may want to place additional restrictions on the rule set to operationalize domain-specific constraints and inductive biases. For example, setting \(\alpha_j, \alpha_k \in \mathop{\mathrm{descendant}}(\alpha_i)\) for rules of the form \(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]\) would constrain the target tree hierarchy to respect the source tree hierarchy, while restricting \(\alpha_i\) to source terminals (i.e. \(\alpha_i \in \mathop{\mathrm{yield}}({\boldsymbol{s}})\)) for rules of the form \(D[\alpha_i] \to w\) would enforce that each target terminal be aligned to a source terminal. We indeed make use of such restrictions in our experiments.

2.4.0.3 Incorporating autoregressive language models

Finally, we remark that simple extensions of the QCFG can incorporate standard autoregressive language models. Let \(p_{\mathrm{\small lm}}(w \,\vert\,\gamma)\) be a distribution over the next word given by a (potentially conditional) language model given arbitrary context \(\gamma\) (e.g. \(\gamma = {\boldsymbol{y}}_{<t}\) for a monolingual language model and \(\gamma = {\boldsymbol{x}}, {\boldsymbol{y}}_{<t}\) for a sequence-to-sequence model). One way to embed this language model into a QCFG would be to use a special lm preterminal \(D_{\mathrm{\small lm}} \in \mathcal{P}\) that is not combined with any source node, and define the emission probability to be, \[\begin{align} p_\theta(D_{\mathrm{\small lm}} \to w)\, \mathrel{\overset{\makebox[0pt]{\normalfont\tiny \mathop{\mathrm{def}}}}{=}}\, p_{\mathrm{\small lm}}(w \,\vert\,\gamma). \end{align}\] (The nonterminal probabilities \(p_\theta(A[\alpha_i] \to D_{\mathrm{\small lm}} C[\alpha_k])\) and \(p_\theta(A[\alpha_i] \to B[\alpha_j]D_{\mathrm{\small lm}})\) are computed with the associated symbol embedding \(\mathbf{u}_{D_{\mathrm{\small lm}}}\).) Both the QCFG and the language model can then be trained jointly.

For some cases we may want to make use of a conditional language model that condition on subparts of the source sentence. This may be appropriate for learning to translate non-compositional 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 \(A_{\mathrm{\small lm}} \in \mathcal{N}\) which is combined with source tree nodes to produce rules of the form \(A_\mathrm{\small lm}[\alpha_i] \to v\) for \(v \in \Sigma^{+}\). The associated probabilities are then defined to be, \[\begin{align} p_\theta(A_\mathrm{\small lm}[\alpha_i] \to v) \, \mathrel{\overset{\makebox[0pt]{\normalfont\tiny \mathop{\mathrm{def}}}}{=}}\, p_{\mathrm{\small lm}}(v \,\vert\,\mathop{\mathrm{yield}}(\alpha_i)). \end{align}\] While these extensions can embed flexible autoregressive models within a QCFG,¹⁰ 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 a variety of sequence-to-sequence learning tasks. These experiments are not intended to push the state-of-the-art 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 [8], a diagnostic dataset where a model has to learn to translate simple English commands to actions (e.g. \(\textsf{\fontsize{9}{10}\selectfont jump twice after walk} \rightarrow \textsf{\fontsize{9}{10}\selectfont WALK JUMP JUMP}\)). While conceptually simple, standard sequence-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,¹¹ (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.

In these experiments, the nonterminals \(A \in \mathcal{N}\) are only combined with source nodes that govern at least two nodes, and the preterminals \(P \in \mathcal{P}\) are only combined with source terminals. We set \(|\mathcal{N}| = 10\) and \(|\mathcal{P}| = 1\), and place two additional restrictions on the rule set. First, for rules of the form \(S \to A[\alpha_i]\) we restrict \(\alpha_i\) to always be the root of the source tree. Second, for rules of the form \(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]\) we restrict \(\alpha_j, \alpha_k\) either be a descendant of \(\alpha_i\), or \(\alpha_i\) itself (i.e. \(\alpha_j, \alpha_k \in \mathop{\mathrm{descendant}}(\alpha_i) \cup \{\alpha_i\}\)). These restrictions operationalize the constraint that the target tree hierarchy respects the source tree hierarchy, though still in a much looser sense than in an isomorphism. We found these constraints to be crucial in learning models that perform well on the compositional splits of the dataset. See Appendix 7.3.1 for the full experimental setup and hyperparameters.

3.1.0.1 Results

Table [tab:scan] 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 [tab:scan-rules] 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 “\(x \,\, \textsf{\fontsize{9}{10}\selectfont thrice}\)” in a grammar that only has unary and binary rules, the model uses the nonterminals \(N_1\) and \(N_8\) in different ways when combined with the same phrase. Figure 1 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\) {and,after} \(y\)” to “\(x \, x\)” (or “\(y \, y\)”) at the root node. When we manually disallowed such splits during decoding, performance increased by 1%-2% across the board, showcasing a 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 [30]. 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 to be rewritten to emphasize a particular verb/action (1201 examples).¹² 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 \(|\mathcal{N}| = |\mathcal{P}| = 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 a bidirectional LSTM before feeding to the TreeLSTM encoder.¹³ We further experiment with the phrase-level copy mechanism as described in section [sec:copy]. The original paper provides several strong baselines: finetuned GPT2, a standard sequence-to-sequence model, and the retrieve-and-edit model from [60]. We also train our own baseline sequence-to-sequence model with a word-level copy mechanism. See Appendix 7.3.2 for more details.

3.2.0.1 Results

Table 1 shows the results where we observe that the neural QCFG performs well compared to 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-to-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.¹⁶ 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 baselines 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.

3.3 Machine Translation↩︎

Our final experiment is on a small-scale English-French machine translation dataset from [8]. 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 see if it can systematically generalize to unseen combinations. To assess the latter, [8] add 1000 repetitions of \(\textsf{\fontsize{9}{10}\selectfont i am daxy} \rightarrow \textsf{\fontsize{9}{10}\selectfont je suis daxiste }\) to the training set and test on 8 new sentences that use daxy in novel combinations (e.g. \(\textsf{\fontsize{9}{10}\selectfont he is daxy} \rightarrow \textsf{\fontsize{9}{10}\selectfont il est daxiste}\) and \(\textsf{\fontsize{9}{10}\selectfont i am not daxy} \rightarrow \textsf{\fontsize{9}{10}\selectfont 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 is the “i am daxy” example), 631 examples for validation, and 583 for test.¹⁷

For these experiments, we set \(|\mathcal{N}| = |\mathcal{P}| = 14\) and combine all source tree nodes with all nonterminals/preterminals. We place two restrictions on the rule set: for rules of the form \(S \to A[\alpha_i]\) we restrict \(\alpha_i\) to be the root of the source tree (as in previous experiments), and for rules of the form \(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]\) we restrict \(\alpha_j, \alpha_k\) to be the direct children of \(\alpha_i\) such that \(\alpha_j \ne \alpha_k\) (or \(\alpha_i\) itself if \(\alpha_i\) has no children).¹⁸ 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 LSTM/Transformer models as well as approaches that explicitly target compositional generalization [61], [62].

l4.3cm

3.3.0.1 Results

Table [tab:mt] shows BLEU on the regular test set of 583 sentences and accuracy on the 8 daxy sentences.¹⁹ While the neural QCFG performs nontrivially, it is soundly outperformed by a well-tuned Transformer model, which performs impressively well even on the daxy test set.²⁰ We thus consider our results on machine translation 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.²¹ Figure 3 shows several examples of target tree derivations from the neural QCFG that does 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 of classic hierarchical phrase-based approaches to machine translation where the extracted phrases often do not correspond to linguistic phrases [21]. Finally, although the model does well on the daxy test set, it still incorrectly translates simple but unusual made-up examples such as “i m not a cat” (Figure 3, top right). This is despite the fact that examples of the form \(\textsf{\fontsize{9}{10}\selectfont i \{am,m\} not a x} \rightarrow \textsf{\fontsize{9}{10}\selectfont je ne suis pas \{un,une\} y}\) 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 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 \(\mathcal{O}(\vert\mathcal{N}\vert (\vert \mathcal{N}\vert + \vert \mathcal{P}\vert )^2 S^3 T^3)\) 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 it necessary to sample and score a large number of target trees to perform well on the non-synthetic datasets (see Appendix 7.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-sequence models, although this may be partially attributable to the availability of a robust set of hyperparameters for existing approaches.

At the start of this project, our initial hope was to show that classic, grammar-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 be 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-machine systems [64]. 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 [48], [65] or inducing structures with which to regularize/augment models [58], [66]–[68]. In this vein, it may be interesting to explore how induced structures from grammars (such as the tranduction rules in Table [tab:scan-rules]) can be used in conjunction with flexible neural models.

5 Related Work↩︎

5.0.0.1 Synchronous grammars

Synchronous grammars and tree transducers have a long and rich history in natural language processing [22], [23], [31], [32], [69]–[76]. In this work we focus on the formalism of quasi-synchronous grammars, which relaxes the requirement that source trees be isomorphic to target trees. Quasi-synchronous grammars have enjoyed applications across a wide range of domains including in machine translation [11], [26], [77], question answering [24], paraphrase detection [25], sentence simplification [78], [79], and parser projection [80]. 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 as latent.

5.0.0.2 Compositional sequence-to-sequence learning

[8] 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-sequence learning through various approaches including modifications to existing architectures [61], [81]–[84], grammars and neuro-symbolic models [62], [85]–[88], meta-learning [89], [90], and data augmentation [91]–[94]. Our approach is closely related to NQG-T5 [86] which uses a rules-based approach to induce a non-probabilistic QCFG and then backs off to a flexible sequence-to-sequence model during prediction if the grammar cannot parse the input sequence.

5.0.0.3 Deep latent variable models

There has much work on neural parameterizations of classic probabilistic latent variable models including hidden Markov models, [95]–[97], finite state transducers [98], [99] topic models [100]–[102], dependency models [103]–[107], and context-free grammars [41], [108]–[112]. These works essentially extend feature-based unsupervised learning [113] to the neural case with the use of neural networks over embedding parameterizations, which makes it easy to share parameters and additionally condition the generative model on side information such as auxiliary latent variables [41], [106], images [114]–[116], video and audio [117], and source-side context [96], [118]. Since we marginalize over unobserved trees during learning, our work is also related to the line of work on marginalizing out latent variables/structures for sequence transduction tasks [119]–[128].

6 Conclusion↩︎

In this paper we have studied sequence-to-sequence learning with latent neural grammars. We have shown that the formalism quasi-synchronous 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 [32]) with contemporary parameterizations, (2) conditioning on other modalities such as images/audio for grounded grammar induction [114], [115], [117], [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.

7 Appendix↩︎

7.1 Neural QCFG Parameterization↩︎

Each nonterminal is combined with a source node to produce a symbol \(A[\alpha_i]\), whose embedding representation is given by \(\mathbf{e}_{A[\alpha_i]} = \mathbf{u}_{A} + \mathbf{h}_{\alpha_i}\). Here \(\mathbf{u}_{A}\) is a randomly initialized embedding and \(\mathbf{h}_{\alpha_i}\) is the node representation for \(\alpha_i\) from a TreeLSTM. The rule probabilities are then given by, \[\begin{align} &p_\theta(S \to A[\alpha_i]) &&= \frac{\exp\left(\mathbf{u}_{S}^\top \mathbf{e}_{A[\alpha_i]}\right)}{\sum\limits_{A' \in \mathcal{N}}\sum\limits_{\alpha' \in {\boldsymbol{s}}}\exp\left(\mathbf{u}_{S}^\top \mathbf{e}_{A'[\alpha']}\right)},\\ &p_\theta(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]) &&= \frac{\exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B[\alpha_j]}) + f_{\text{3}}(\mathbf{e}_{C[\alpha_k]}))\right)}{\sum\limits_{B' \in \mathcal{M}} \sum\limits_{\alpha' \in {\boldsymbol{s}}} \sum\limits_{C'' \in \mathcal{M}}\sum\limits_{\alpha'' \in {\boldsymbol{s}}}\exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B'[\alpha']}) + f_{\text{3}}(\mathbf{e}_{C''[\alpha'']}))\right)}, \\ &p_\theta(D[\alpha_i] \to w) && = \frac{\exp\left(f_4(\mathbf{e}_{D[\alpha_i]})^\top\mathbf{u}_{w} + b_w \right)}{\sum\limits_{w' \in \Sigma}\exp\left(f_4(\mathbf{e}_{D[\alpha_i]})^\top\mathbf{u}_{w'} + b_{w'} \right)}, \end{align}\] where \(\mathcal{M}= \mathcal{N}\cup \mathcal{P}\). In the above \(f_i\)’s are feedforward networks with three residual blocks, \[\begin{align} f_i(\mathbf{x}) &= g_{i, 3}(g_{i, 2}(g_{i, 1}(\mathbf{W}_i\mathbf{x}+\mathbf{b}_i))), && i \in \{1,2,3,4\},\\ g_{i, j}(\mathbf{x}) &= \mathop{\mathrm{ReLU}}(\mathbf{V}_{i, j}(\mathop{\mathrm{ReLU}}(\mathbf{U}_{i,j} + \mathbf{c}_{i,j})) + \mathbf{d}_{i,j}) + \mathbf{x}, && j \in \{1,2,3\}. \end{align}\] We often place restrictions on the derivations to operationalize domain-specific constraints. For example, in our machine translation experiments we constrain \(\alpha_j, \alpha_k\) to be the immediate children of \(\alpha_j\) for rules of the form \(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]\) such that \(\alpha_j \ne \alpha_k\), unless \(\alpha_i\) is a leaf node in which case \(\alpha_i\) is always inherited. To calculate \(p_\theta(A[\alpha_i] \to B[\alpha_j]C[\alpha_k])\) with this restriction, we consider different cases. In the case where \(\alpha_j, \alpha_k\) are the immediate children of \(\alpha_i\), \(p_\theta(A[\alpha_i] \to B[\alpha_j]C[\alpha_k])\) is given by \[\begin{align} \frac{\exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B[\alpha_j]}) + f_{\text{3}}(\mathbf{e}_{C[\alpha_k]}))\right)}{\sum\limits_{B' \in \mathcal{M}} \sum\limits_{C'' \in \mathcal{M}}\exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B'[\alpha_j]}) + f_{\text{3}}(\mathbf{e}_{C''[\alpha_k]}))\right) + \exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B'[\alpha_k]}) + f_{\text{3}}(\mathbf{e}_{C''[\alpha_j]}))\right)}. \end{align}\] In the case where \(\alpha_i \in \mathop{\mathrm{yield}}({\boldsymbol{s}})\) (i.e. it has no children), we have \[\begin{align} p_\theta(A[\alpha_i] \to B[\alpha_j]C[\alpha_k]) = \begin{cases} \frac{\exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B[\alpha_j]}) + f_{\text{3}}(\mathbf{e}_{C[\alpha_k]}))\right)}{\sum\limits_{B' \in \mathcal{M}} \sum\limits_{C'' \in \mathcal{M}}\exp \left(f_{\text{1}}(\mathbf{e}_{A[\alpha_i]})^\top (f_{\text{2}}(\mathbf{e}_{B'[\alpha_i]}) + f_{\text{3}}(\mathbf{e}_{C''[\alpha_i]}))\right)},& \alpha_j = \alpha_k = \alpha_i, \\ 0, & \text{otherwise}. \end{cases} \end{align}\] All other \(p_\theta(A[\alpha_i] \to B[\alpha_j]C[\alpha_k])\)’s are assigned to 0. In practice these constraints are implemented by masking out the full third-order tensor of the rules’ (log) probabilities, which is of size \((2S-1)|\mathcal{N}| \times (2S-1)|\mathcal{N}\cup \mathcal{P}| \times (2S-1)|\mathcal{N}\cup \mathcal{P}|\). Here \((2S-1)\) is the number of nodes in the binary source tree. This masking strategy makes it possible to still utilize vectorized implementations of the inside algorithm.

7.2 Lower Bound Derivation↩︎

\[\begin{align} \log \, p_{\theta, \phi} ({\boldsymbol{y}}\,\vert\,{\boldsymbol{x}}) &= \log \left( \sum_{{\boldsymbol{s}}\in \mathcal{T}({\boldsymbol{x}})} \sum_{{\boldsymbol{t}}\in \mathcal{T}({\boldsymbol{y}})} p_\theta({\boldsymbol{t}}\,\vert\,{\boldsymbol{s}})p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}}) \right) \\ &= \log \left(\sum_{{\boldsymbol{s}}\in \mathcal{T}({\boldsymbol{x}})}p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}) p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})\right)\\ &= \log \, \mathbb{E}_{{\boldsymbol{s}}\sim p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})}\left[ p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}) \right] \\ &\ge \mathbb{E}_{{\boldsymbol{s}}\sim p_\phi({\boldsymbol{s}}\,\vert\,{\boldsymbol{x}})}\left[ \log p_\theta({\boldsymbol{y}}\,\vert\,{\boldsymbol{s}}) \right] \end{align}\]

7.3 Experimental Setup and Hyperparameters↩︎

For all experiments the source parser is a neural PCFG [41] with 20 nonterminals and 20 preterminals. Other model settings that are shared across the experiments include: (1) Adam optimizer with learning rate \(= 0.0005\), \(\beta_1 = 0.75\), \(\beta_2 = 0.999\), (2) gradient norm clipping at \(3\), (3) \(L_2\) penalty (i.e. weight decay) of \(10^{-5}\), (4) Xavier Glorot uniform initialization, and (5) training for 15 epochs with early stopping on the validation set (most models converged well before 15 epochs). The batch size is 4 for the SCAN and style transfer datasets, and 32 for the machine translation dataset. Due to memory constraints, in practice we use a batch size of 1 and simulate larger batch sizes through gradient accumulation. We observed training to be somewhat unstable and some datasets (e.g. SCAN and machine translation) needed training across 4 to 6 random seeds to perform well. In general we found it okay to overparameterize the grammar and use more nonterminals than seems necessary [130].

7.3.1 SCAN↩︎

For SCAN, all models and embeddings are 256-dimensional. The QCFG has 10 nonterminals and 1 preterminal (\(|\mathcal{N}| = 10, |\mathcal{P}| = 1\)).Since SCAN does not provide official validations sets, we use the test set of the simple split as the validation set for the add primitive (jump), add template (around right), length splits. For the simple split, we use the training set itself as the validation set for early stopping. For decoding we take 10 sample derivations from the grammar and take the yield that has the lowest perplexity after rescoring.

7.3.2 Style Transfer↩︎

On StylePTB, all models and embeddings with 512-dimensional. The QCFG has 8 nonterminals and 8 preterminals (\(|\mathcal{N}| = 8, |\mathcal{P}| = 8\)). We also contextualize the source embedding by passing it through a bidirectional LSTM, where the concatenation of the forward and backward hidden states for each word are projected down to 512 dimensions via an affine layer before they are fed to the TreeLSTM. For decoding we use 1000 samples and take the yield that has the lowest perplexity after rescoring. The adjective/verb emphasis tasks also provide a particular word in the source sentence to emphasize. We encode this information through a binary variable, whose embedding is added to the word embedding (before contexualization) in the encoder. Tokens which occur less than three times are replaced with the \(\langle\)unk\(\rangle\) token.

The baseline uses a bidirectional LSTM encoder and an LSTM decoder with soft attention [4] and a pointer copy mechanism [53]. We tune over the number of layers, hidden units, and dropout rate. For decoding we use beam search with beam size of 5 (larger beam sizes did not improve performance).

7.3.3 Machine Translation↩︎

In these experiments we use 512-dimensional models/embeddings. The QCFG has 14 nonterminals and 14 preterminals (\(|\mathcal{N}| = 14, |\mathcal{P}| = 14\)). As in the Style Transfer experiments, we also experiment with a variant where we contextualize the source word embeddings with a bidirectional LSTM before the TreeLSTM layer. For decoding we use 1000 samples and take the yield that has the lowest perplexity after rescoring. Tokens which occur less than two times are replaced with the \(\langle\)unk\(\rangle\) token.

The LSTM baseline uses a bidirectional LSTM encoder and a LSTM decoder with soft attention [4]. We tune over the number of layers, dimensions, and dropout rate. The Transformer baseline is from OpenNMT [131], where we tune over the number of layers, hidden units, dropout rate, warm-up steps, and batch size. Given the small size of our dataset, the Transformer was particularly sensitive to the number of warm-up steps and the batch size. For decoding we use beam search with beam size of 5 (larger beam sizes did not improve performance).

We calculate BLEU with the multi-bleu.perl script from mosesdecoder. For the daxy test set, the original paper [8] only considers the “tu” translation of “you” to be correct. We follow [61] and [62] and also count “vous” to be correct as well (e.g. both “tu n es pas daxiste .” and “vous n etes pas daxiste .” are considered to be valid translations of “you are not daxy .”).

References↩︎