Transition-based Parsing with Stack-Transformers (2020)

Abstract: Modeling the parser state is key to good performance in transition-based parsing. Recurrent Neural Networks considerably improved the performance of transition-based systems by modelling the global state, e.g. stack-LSTM parsers, or local state modeling of contextualized features, e.g. Bi-LSTM parsers. Given the success of Transformer architectures in recent parsing systems, this work explores modifications of the sequence-to-sequence Transformer architecture to model either global or local parser states in transition-based parsing. We show that modifications of the cross attention mechanism of the Transformer considerably strengthen performance both on dependency and Abstract Meaning Representation (AMR) parsing tasks, particularly for smaller models or limited training data.

## introduction transition-based parsing transforms the task of predicting a graph from a sentence into predicting an action sequence of a state machine that produces the graph @xcite @xcite . these parsers are attractive for their linear inference time and interpretability, however, their performance hinges on effective modeling of the parser state at every decision step. parser states typically comprise two memories, a buffer and a stack, from which tokens can be pushed or popped @xcite . traditionally, parser states were modeled using hand selected local features pertaining only to the words on the top of the stack or buffer @xcite . with the widespread use of neural networks, global models of the parser state such as the stack-lstm @xcite allowed encoding the entire buffer and stack. it was later shown that local features of the stack and buffer extracted from contextual word representations, such as bi-lstms, could outperform global modeling @xcite . with the rise of the transformer model @xcite , various approaches have been proposed that leverage this architecture for parsing @xcite @xcite @xcite . in this work we revisit the local versus global paradigms of state modeling in the context of sequence-to-sequence transformers applied to action prediction for transition-based parsing. similarly to previous works for rnn sequence to sequence @xcite , we propose a modification of the cross-attention mechanism of the transformer to provide global parser state modeling. we analyze the role of local versus global parser state modeling, stack and buffer modeling, effects model size as well as task complexity and amount of training data. results show that local and global state modeling of the parser state yield more than 2 percentage points absolute improvement over a strong transformer baseline, both for dependency and abstract meaning representation (amr) parsing. gains are also particularly large for smaller train sets and smaller model sizes, indicating that parser state modeling, can compensate for both. finally, we improve the amr transition-based oracle (ballesteros and al-onaizan, 2017a), yielding best results for a transition-based system and second overall. ## global versus local parser state given pair of sentence @xmath0, w 2 • • • w n and graph g, transition-based parsers learn an action sequence @xmath1, a 2 • • • a t , that applied to a state machine yields the graph @xmath2, w). actions of the state machine generally move words from a buffer, that initially contains the entire sentence, to a stack. components of the graph, such as edges or nodes, are created by applying transformations to words in the stack. the correct action sequence is given by an oracle @xmath3, g), which is generally rule-based. in principle, one could learn the sentence to action mapping @xmath4 the transition-based formalism relies heavily on the explicit representation of the state i.e. buffer and stack configurations. prior to widespread use of neural networks, local features limited to top of the stack and buffer already achieved good performances @xcite . the introduction of stack-lstms @xcite made possible modeling the global state of the parser by separately encoding action history @xmath5, and the dynamically changing stack and buffer with lstms @xcite . in addition to this, stack-lstms used the transition-based formalism to recursively build vector representations of sub-graphs, similarly to a graph neural network. another well known lstm model is the bi-lstm feature parser @xcite . in this case, a contextual representation of the sentence is first built with a bi-lstm @xmath6. at each time step t the stack configuration determined by @xmath7. although the features utilize local information of the buffer and stack, the use of a strong contextual representation proved to be sufficient and this remains one of the most widely used forms of parsing today. ## experiments and results to test the proposed approach, different parsing tasks were selected. dependency parsing in the english-treebank, is well known and well resourced (40k sentences). the amr2.0 semantic parsing task is more complex, encompassing named entity recognition, word sense disambiguation and co-reference among other sub-tasks, also well resourced (36k sentences). amr1.0 has around 10k sentences and can be considered as amr with limited train data. the dependency parsing setup followed @xcite , in the setting with no pos tags. this has only shift, left-arc(label), and right-arc(label) base action with a total of 82 different actions. results were measured in terms of (un)labeled attachment scores (uas/las). the amr setup followed ballesteros and al-onaizan (2017a), which introduced new actions to segment text and derive nodes or entity sub-graphs. in addition, we use the alignments and wikification from @xcite . unlike previous works, we force-aligned the unaligned nodes to neighbouring words and allowed attachment to the leaf nodes of entity sub-graphs, this increased oracle smatch from 93.7 to 98.1 and notably improved model performance. we therefore provide results for the @xcite oracle for comparison. both previous works predict a node creation action and then a node label, or call a lemmatizer if no label is found. instead, we directly predicted the label and added copy actions to construct node names from lemmas foot_0 or surface words, resulting in a maximum of 9k actions. node label predictions were limited to those seen during training for the word on the top of the stack. results were measured in smatch @xcite using the latest version 1.0.4 foot_1 . regarding model implementation, all models were implemented on the fairseq toolkit and trained with only minor modifications over the mt model hyper-parameters @xcite . this used crossentropy training with learning rate 5e -4 , inverse square root scheduling with min. 1e -9 , 4000 warmup updates with learning rate 1e -7 , and maximum 3584 tokens per batch. adam parameters 0.9 and 0.98, label smoothing was reduced to 0.01 foot_2 . all models used 6 layers of encoding and decoding with size 256 and 4 attention heads, except the normal transformers in amr, which performed better on a 3/8 layer configuration instead of 6/6. to study the effect of model size, small versions of all models using a 2/2 configuration were also tested. we used roberta-base @xcite embeddings without fine-tuning as input, averaging wordpieces to obtain word representations. weight averaging of the best 3 checkpoints @xcite and beam 10 were used in all models. this improves results at most by 0.4/0.8 points for amr2.0/amr1.0 with no significant differences across models. models were trained for a fixed number of epochs, selecting the best model on validation by either las or smatch. a maximum epoch number of 80 -120 was set to guarantee a margin of 5 epochs from best model to last epoch. no other hyper-parameters were changed across models or tasks. training took at most 6h on a nvidia tesla v100 gpu. it should be noted that this is around 10 times faster than our pytorch stack-lstm implementation for the same data. the labeled shift strategy used the 100 most frequent words. ## analysis of results regarding ablation of the stack-transformer components, the use of stack/buffer positions seems clearly detrimental (d) in all scenarios. this was a consistent pattern across various variants for which we do not report numbers such as sinusoidal versus learnable positions and reducing the position range to top three of the stack and buffer. one possible explanation is that positions varying after each time step may be hard to learn, particularly if injected directly in the decoder. it is also worth noting, than the combination of multi-task and stack-transformer produced little improvement or was even detrimental pointing to their similar role. re-model amr1.0 amr2.0 @xcite sults for the weakest of the stack-transformer variants are provided (h). comparing across different attention modifications (e-h), most methods perform similarly although there seems to be some evidence for global (full buffer, full stack) variants being more performant. modeling of the buffer seems also more important than modeling of the stack. one possible explanation for this is that, since the total number of heads is kept fixed, it may be more useful to gain an additional free head than modeling the stack content. furthermore without recursive representation building, as in stack-lstms, the role of the stack can be expected to be less important. tables 2 and 3 compare with prior works. pretrained embeddings used are indicated as xlnet-large x @xcite , bert base β and large b @xcite , graph recategorization, which utilizes an external entity recognizer @xcite overall, the stack-transformer is competitive against recent works particularly for amr, likely due to the higher complexity of the task. compared to prior amr systems, it is worth noting the large performance increase against stack-lstm @xcite , while sharing a similar oracle and embeddings and not using reinforcement learning fine-tuning. the stack-transformer also matches the best reported amr system (cai and lam, 2020) on amr1.0 without graph recategorization, but using roberta instead of bert embeddings and provided the second best reported scores on the higher resourced amr2.0 foot_3 . ## related works while inspired by stack-lstms @xcite , the stack-transformer lacks their elegant recursive composition, where representations for partial graph components are added to the stack and used in subsequent representations. it allows, however, to model the global parser state in a simple way that is easy to parallelize, and shows large performance gains against stack-lstms on amr. the proposed modified attention mechanism, could also be interpreted as a form of feature-based parser (kiperwasser and goldberg, 2016), where the parser state is used to select encoder representations, integrated into a transformer sequence to sequence model. the modification of the attention mechanism to reflect the parse state has been applied in the past to rnn sequence-to-sequence models. @xcite propose the use of a boundary to separate stack and buffer attentions. while simple, this precludes the use of swap actions needed for amr parsing and non-projective parsing. @xcite mask out reduced words and add a bias to the attention weights for words in the stack. while being the closest to the proposed technique, this method does not separately model stack and buffer nor retains free attention heads, which we consider a fundamental advantage. we also provide evidence that modeling the parser state still produces gains when using pre-trained transformer embeddings and provide a detailed analysis of components. finally, rnn @xcite and selfattention @xcite stack-pointer networks sum encoder representations based on local graph structure, which can be interpreted as masked uniform attention over 3 words and is related to the previous methods. ## conclusions we have explored modifications of sequence-tosequence transformers to encode the parser state for transition-based parsing, inspired by stack-lstm's global modeling of the parser state. while simple, these modifications consistently provide improvements against a normal sequence to sequence transformer in transition-based parsing, both for dependency parsing and amr parsing tasks. results also point to the benefits of modeling the parser state as a way to compensate for limited training resources or limitation in model sizes.