Graph-to-Graph Transformer for Transition-based Dependency Parsing (2020)

Abstract: We propose the Graph2Graph Transformer architecture for conditioning on and predicting arbitrary graphs, and apply it to the challenging task of transition-based dependency parsing. After proposing two novel Transformer models of transition-based dependency parsing as strong baselines, we show that adding the proposed mechanisms for conditioning on and predicting graphs of Graph2Graph Transformer results in significant improvements, both with and without BERT pre-training. The novel baselines and their integration with Graph2Graph Transformer significantly outperform the state-of-the-art in traditional transition-based dependency parsing on both English Penn Treebank, and 13 languages of Universal Dependencies Treebanks. Graph2Graph Transformer can be integrated with many previous structured prediction methods, making it easy to apply to a wide range of NLP tasks.

## introduction in recent years, there has been a huge amount of research on applying self-attention models to nlp tasks. transformer @xcite is the most common architecture, which can capture long-range dependencies by using a self-attention mechanism over a set of vectors. to encode the sequential structure of sentences, typically absolute position embeddings are input to each vector in the set, but recently a mechanism has been proposed for inputting relative positions @xcite . for each pair of vectors, an embedding for their relative position is input to the self-attention function. this mechanism can be generalised to input arbitrary graphs of relations. we propose a version of the transformer architecture which combines this attention-based mechanism for conditioning on graphs with an attention-like mechanism for predicting graphs and demonstrate its effectiveness on syntactic dependency parsing. we call this architecture graph2graph transformer. this mechanism for conditioning on graphs differs from previous proposals in that it inputs graph relations as continuous embeddings, instead of discrete model structure (e.g. @xcite @xcite ) or predefined discrete attention heads (e.g. @xcite ). an explicit representation of binary relations is supported by inputting these relation embeddings to the attention functions, which are applied to every pair of tokens. in this way, each attention head can easily learn to attend only to tokens in a given relation, but it can also learn other structures in combination with other inputs. this gives a bias towards attention weights which respect locality in the input graph but does not hard-code any specific attention weights. we focus our investigation on this novel graph input method and therefore limit our investigation to models which predict the output graph one edge at a time, in an auto-regressive fashion. in auto-regressive structured prediction, after each edge of the graph has been predicted, the model must condition on the partially specified graph to predict the next edge of the graph. thus, our proposed graph2graph transformer parser is a transition-based dependency parser. at each step, the model predicts the next parsing decision, and thereby the next dependency relation, by conditioning on the partial parse structure specified by the previous decisions. it inputs embeddings for the previously specified dependency relations into the graph2graph transformer model via the self-attention mechanism. it predicts the next dependency relation using only the vectors for the tokens involved in that relation. to evaluate this architecture, we also propose two novel transformer models of transition-based dependency parsing, called sentence transformer, and state transformer. sentence transformer computes contextualised embeddings for each token of the input sentence and then uses the current parser state to identify which tokens could be involved in the next valid parse transition and uses their contextualised embeddings to choose the best transition. for state transformer, we directly use the current parser state as the input to the model, along with an encoding of the partially constructed parse graph, and choose the best transition using the embeddings of the tokens involved in that transition. both baseline models achieve competitive or better results than previous state-of-the-art traditional transition-based models, but we still get substantial improvement by integrating graph2graph transformer with them. we also demonstrate that, despite the modified input mechanisms, this graph2graph transformer architecture can be effectively initialised with standard pre-trained transformer models. initialising the graph2graph transformer parser with pretrained bert @xcite parameters leads to substantial improvements. the resulting model significantly improves over the state-of-the-art in traditional transition-based dependency parsing. this success demonstrates the effectiveness of graph2graph transformers for conditioning on and predicting graph relations. this architecture can be easily applied to other nlp tasks that have any graph as the input and need to predict a graph over the same set of nodes as output. in summary, our contributions are: ## transition-based dependency parsing our transition-based parser uses arc-standard parsing sequences @xcite , which makes parsing decisions in bottom-up order. the main data structures for representing the state of an arc-standard parser are a buffer of words and a stack of partially constructed syntactic sub-trees. at each step, the parser chooses between adding a leftward or rightward labelled arc between the top two words on the stack (left-arc(l) or right-arc(l), where l is a dependency label) or shifting a word from the buffer onto the stack (shift). to handle non-projective dependency trees, we allow the swap action proposed in @xcite , which shifts the second-from-top element of the stack to the front of the buffer, resulting in the reordering of the top two elements of the stack. ## graph2graph transformer we propose a version of the transformer which is designed for both conditioning on graphs and predicting graphs, which we call graph2graph transformer (g2gtr), and show how it can be applied to transition-based dependency parsing. g2gtr supports arbitrary input graphs and arbitrary edges in the output graph. but since the nodes of both these graphs are the input tokens, the nodes of the output graph are limited to the set of nodes in the input graph. inspired by the relative position embeddings of @xcite , we use the attention mechanism of transformer to input arbitrary graph relations. by inputting the embedding for a relation label into the attention functions for the related tokens, the model can more easily learn to pass information between graph-local tokens, which gives the model an appropriate linguistic bias, without imposing hard constraints. given that the attention function is being used to input graph relations, it is natural to assume that graph relations can also be predicted with an attention-like function. we do not go so far as to restrict the form of the prediction function, but we do restrict the vectors used to predict graph relations to only the tokens involved in the relation. ## parsing models in this section, we define two transformer-based models for transition-based dependency parsing, and integrate the graph2graph transformer architecture with them, as illustrated in figure 1 . ## conclusion we proposed the graph2graph transformer architecture, which inputs and outputs arbitrary graphs through its attention mechanisms. each graph relation is input as a label embedding to each attention function involving the relation's tokens, and each graph relation is predicted from its token's embeddings like an attention function. we demonstrate the effectiveness of this architecture on transition-based dependency parsing, where the input graph is the partial dependency structure specified by the parse history, and the output graph is predicted one dependency at a time by the parser actions. to establish strong baselines, we also propose two transformer-based models for this task, called state transformer and sentence transformer. the former model incorporates history and composition models, as proposed in previous work. despite the competitive performance of these extended-transformer parsers, adding our graph input and output mechanisms results in significant improvement. also, the graph inputs are effective replacements for the composition models. all these results are preserved with the incorporation of bert pre-training, which results in substantially improving the state-of-the-art in traditional transition-based dependency parsing. as well as the generality of the graph input mechanism, the generality of the graph output mechanism means that graph2graph transformer can be integrated with a wide variety of decoding algorithms. for example, mohammadshahi and henderson (2020) investigate non-autoregressive decoding, which addresses the computational cost of running the g2gtr model once for every dependency edge. graph2graph transformer can also easily be applied to a wide variety of nlp tasks, such as semantic parsing tasks, which we hope to demonstrate in future work.