Enhancing the Transformer Decoder with Transition-based Syntax (2022)

Abstract: Notwithstanding recent advances, syntactic generalization remains a challenge for text decoders. While some studies showed gains from incorporating source-side symbolic syntactic and semantic structure into text generation Transformers, very little work addressed the decoding of such structure. We propose a general approach for tree decoding using a transition-based approach. Examining the challenging test case of incorporating Universal Dependencies syntax into machine translation, we present substantial improvements on test sets that focus on syntactic generalization, while presenting improved or comparable performance on standard MT benchmarks. Further qualitative analysis addresses cases where syntactic generalization in the vanilla Transformer decoder is inadequate and demonstrates the advantages afforded by integrating syntactic information.

## introduction in parallel to the impressive achievements of large neural networks in a variety of nlp fields, more and more work emphasizes the importance of the inductive biases models possess and the types of generalizations they make @xcite @xcite . syntactic generalization has been repeatedly identified as a problem in text generation @xcite , an issue that we address here. importantly, language models may fail, sometimes unexpectedly, on constructions that can be reliably parsed using standard syntactic parsers. in this work, we propose a method for incorporating syntax into the decoder to assist in mitigating these challenges, focusing on nmt as a test case. the use of (mostly syntactic) structure in machine translation dates back to the early days of the field @xcite . while focus has shifted to string-to-string methods since the introduction of neural methods, considerable work has shown gains from integrating linguistic structure into nmt and text generation technologies. we briefly survey such methods in §7. incorporating target-side syntax has been less frequently addressed than source-side syntax, possibly due to the additional conceptual and technical complexity it entails, as it requires to jointly generate the translation and its syntactic structure. in addition to linearizing the structure into a string, that allows to easily incorporate source and target structure @xcite , several works generated the nodes of the syntactic tree using rnns @xcite @xcite . others have shown gains from multi-task training of a decoder with a syntactic parser @xcite . however, we are not aware of any transformer-based architecture to support the integration of target-side structure in the form of a tree or a graph. addressing this gap, we propose a flexible architecture for integrating graphs into a transformer decoder. our approach is based on predicting the output tree as a sequence of transitions ( §3), following the transition-based tradition in parsing @xcite . the method (presented in §4) is based on generating the structure incrementally, as a sequence of transitions, as is customary in transition-based parsers. however, unlike standard linearization approaches, our proposed decoder re-encodes the intermediate graph (and not only the generated tokens), thus allowing the decoder to take advantage of the hitherto produced structure in its further predictions. in §2, we discuss the possibilities offered by such decoders, that do not only auto-regress on their previous outputs, but also on (symbolic) structures defined by those outputs. indeed, a decoder thus built can condition both on information it did not predict (e.g., external knowledge bases) and information predicted later on. we introduce bidirectional attention into the decoder, that allows token representations to encode the following tokens that were predicted. this is similar to the bidirectional attention in the encoder, where any token can attend to any token, and not only to preceding ones. our architecture is flexible, supporting decoding not only into trees, but into any graph structure for which a transition system exists. we test two architectures for incorporating the syntactic graph. one inputs the graph into a graph convolutional network (gcn; @xcite , and another dedicates an attention head to point at the syntactic parent of each token, which does not yield any increase in the number of parameters. we assess in §6 the impact of the proposed architecture on syntactically challenging translation cases @xcite and in general. we experiment with a 4 layered model in three target languages, and a 6 layered on en-de. due to the high computational cost, we experiment with the model on a single language pair only. we find that on the syntactic challenge sets proposed by @xcite , the proposed decoder achieves substantial improvements over the vanilla decoder, which do not diminish (and even slightly improve) when increasing the size of the model. in addition, evaluating on the standard mt benchmarks, we find that the syntactic decoders outperform the vanilla transformer for the smaller model size on all examined language pairs: on the english-german (en-de) and german-english (de-en) challenge sets and on en-de, de-en and english-russian (en-ru) test sets, and obtain comparable results to the vanilla when experimenting with a larger model on en-de. finally, we analyse the different modifications in isolation, finding that the ablated versions' performance resides between the full model and the vanilla decoder. ## decoding approach jo@@ hn put the coals out root nsubj det obj compound:prt example 1: target-side structure reduces the ambiguity of "put". de source: "john löschte die kohlen" (lit. john put-out the coals). disambiguating and connecting distant words is a known challenge in nmt @xcite . in example 1 to disambiguate "put" as not having the sense "lay" but "extinguish", "out" must be considered. to achieve this from the autoregressed output, the decoder's representation may need to be re-computed after predicting "out". we note that while source-side information can potentially be used to disambiguate "put", it may still be beneficial to enhance the auto-regressive decoder with disambiguating information. current implementations impose an architectural bias, namely, a decoded token's representation may not attend to future tokens. transformer models mask attention in the following manner (we did not find any alternative methods): token embeddings attend only to previously generated tokens, even when the following tokens are already known. this practice "ensures that the predictions for position i can depend only on the known outputs at positions less than i" @xcite . we propose to allow attending to any known token (fig. 1 ), as done on the encoder side. due to its conceptual resemblance to bidirectional rnn, we name this bidirectional transformer or bitran. formally, let o 1 . . . o n be a hitherto predicted sequence and d max sentence length. attention is sof tmax (l + m ) where @xmath0. hence, m (i, j) = -∞ masks a token j from representation i. this change does not introduce any new parameters or hyperparameters, but still increases the expressivity of the model. we note, however, that this modification does prevent some commonly implemented speed-ups relying on unidirectionality (e.g., in nematus; @xcite . apart from the technical contribution, we emphasize that this and the following approaches take advantage of attention-based models being stateless. transformers can, therefore, be viewed as conditional language models, namely as models for producing a distribution for the next word, given the generated prefix and source sentence. viewing them as such opens possibilities that were not native to rnns, such as predicting only partial outputs and conditioning on per-token or nonautoregressed context (see app. a). ## transition-based structure generation we turn to describe how we represent structure within the proposed decoder. we generate the target-side structure with a transition-based approach, motivated by the practical strength of such methods, as well as their sequential nature, which fits neural decoders well. we therefore augment the vocabulary with transitions. our work is inspired by rnng @xcite , a conceptually similar architecture that was developed for rnns. at each step, the input to the decoder includes the tokens and the parse graph that was generated thus far. as edges and their tokens are not generated simultaneously (but rather by different transitions; see below), we rely on bidirectional attention to update the past embeddings when a new edge connects previously generated tokens. in this section, we present the syntactic transitions and in the next ( §4), the ways we incorporate it back into the model. in this work, we represent syntax through universal dependencies (ud; @xcite , but note that other syntactic and semantic formalisms that have transition-based parsers @xcite @xcite fit the framework as well. we select ud due to its support for over 100 languages and its status as the de facto standard for syntactic representation. we base our transition system on arc-standard @xcite , which can produce any projective tree. both contain a transition connecting two words by a labeled edge. however, we replace shift that reads the next word by subword t generating a new sub-word t. sub-words are generated successively until a full word is formed. to avoid suboptimal representation of transition tokens, we add the edges going through them to the graph (e.g., the edge left-arc:det det -→ the). we denote with f the transition functions updating a word stack σ and the labeled graph g. if a, b are the top and second words in σ respectively, and x a transition, then f (x; σ) is defined as: for brevity, we denote an edge from/to every subword of a as an edge from/to a. overall, the translation sequence to create the graph in example 1 is: jo@@ hn put left-arc:nsubj the coals left-arc:det right-arc:obj out right-arc:compound:prt (more details in app. b) ## regressing on generated structure as discussed in §2, the state-less nature of the transformer allows re-encoding not only the previous predictions, but any information that can be computed based on them. so far, we proposed to autoregress on the syntactic structure, token by token. however, as f is deterministic, learning to emulate it, is pointless. instead, we can autoregress on the generated graph itself, our approach is modular and works with any graph encoding method. we experiment with two prominent methods for source-side graph encoding. ## results we compare the syntactic generalization abilities of the different decoders in §6.1, and continue by examining their overall performance ( §6.2). we then assess the contribution of the components of the system through ablation experiments ( §6.3) and evaluate the effects of noisy training data ( §6.4). ## related work while there are indications that transformers implicitly learn some syntactic structure when trained as language models or as nmt (e.g., @xcite @xcite , it is not at all clear whether such information replaces the utility of incorporating syntactic structure. indeed, a considerable body of work suggests the contrary. much previous work tested rnn-based and attention-based systems for their ability to make structural generalizations @xcite @xcite . syntactic generalizations seem to pose a particularly difficult challenge @xcite . moreover, while nmt often succeeds in translating inter-dependent linearly distant words, their performance is unstable: the same systems may well fail on other "obvious" cases of the same phenomena @xcite . this evidence provides motivation for efforts such as ours, to incorporate linguistic knowledge into the architecture. syntactic structure was used to improve various tasks, including code generation @xcite , question answering @xcite , automatic proof generation @xcite language modelling @xcite and grammatical error correction @xcite . such approaches, however, are task specific. e.g., the latter makes strong conditional independence assumptions, and is less suitable for mt where the source and target syntax may diverge considerably. in nmt, some works used structural cues by reinforcement learning @xcite , but the gain from such methods seems to be limited @xcite . @xcite and @xcite proposed to replace the source and target tokens with a linearized constituency graph or ccg parses. @xcite proposed an rnn to encode the source syntax. some works suggested modifying rnns to encode source-side syntax @xcite @xcite . @xcite used a graph rnn to encode source-side amr structures. few works suggested changes in the transformer to incorporate source-side syntax: @xcite and @xcite proposed a tree-based attention mechanism to encode syntax; @xcite incorporated the first layers of a parser in addition to the token embeddings. relatedly, previous work showed gains from using syntactic information for preprocessing @xcite . much fewer works focused on structure-based decoding. @xcite , building on @xcite , train a decoder in a multi-task setting of translation and parsing. notably, unlike in the method we propose, their generated translation is not constrained by the parse during the decoding. few works proposed alternating between two connected rnns one translating and one creating a linearized graph using a tree-based rnn @xcite or transition-based parsing @xcite . @xcite both parse and generate, using a recursive rnn representation. other work changed rnns @xcite or transformers to include structural inductive biases, but without explicit syntactic information. @xcite suggested an unsupervised way to train transformers that learn tree-like structures following the intuition that such representations are more similar to syntax. @xcite encoded tree-structured data in the positional embeddings. ## discussion the work we presented is motivated from several angles. first, we note that transformers are trained in the same way that former sequence to sequence models are trained (e.g., rnns) and to many, they are just a better architecture for the same task. instead, our work emphasizes the possibility of conditional training using transformers; namely, transformers should be able to predict the third token given the first two, even without previously predicting them. although generally not implemented this way, transformers are already conditional networks, and allow for flexibility not found in rnns. the finding that mt quality changes between beginnings and ends of predicted sentences both in rnns and in transformers @xcite , further motivates conditional translation. this is often explained by lack of context and disregard for the future tokens. such future context is used by humans @xcite and can potentially improve nmt @xcite . moreover, as the encoded input is constant throughout the prediction, the varying performance is likely due to the decoder. attending to all predictions from lower layers, as we propose here, aims to provide more of this required information. 2 finally, previous work investigated the reasons why incorporating source syntax helps rnns @xcite and transformers @xcite . these works show evidence that similar gains can be obtained when incorporating either syntactic trees or non-syntactic, syntactically uninformative, ones. a hypothesis followed, that graph-like architectures are helpful, but that syntactic information is redundant. while gcn creates such an architecture, linearized syntax, arguably parent and to some extent the labels gcn component, do not. still, they allow gains over the vanilla decoder, which challenges this hypothesis. ## conclusion we presented a flexible method for constructing decoders capable of outputting trees and graphs. we show that the improved decoder achieves notable gains in syntactic generalization, and in some settings improves overall performance as well. our proposal is based on two main modifications to the standard transformer decoder: (1) autoregression on structure; (2) bidirectional attention in the decoder, which allows recomputing token embeddings in light of newly decoded tokens. testing on two variants for the decoder, we find that they both show superior syntactic generalization abilities over the vanilla transformer, and that the gap does not diminish with model size. the method is flexible enough to allow decoding into a wide variety of graph and tree structures. our work opens many avenues for future work. one direction would be to focus on conditional networks, training with (intentionally) noisy prefixes, randomly masking "predicted" spans during training (as done in masked language models, @xcite , and data augmentation through hard words or phrases rather than full sentences. another direction might enhance bidirectionality by allowing "regretting" and changing past predictions. finally, the work opens possibilities for better incorporating structure into language generators, of incorporating semantic structure and of enforcing meaning preservation (thus targeting hallucinations, @xcite , by incorporating source and target structure together.