Graph-to-Graph Transformer for Transition-based Dependency Parsing

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3278–3289 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 3278 Graph-to-Graph Transformer for Transition-based Dependency Parsing Alireza Mohammadshahi Idiap Research Institute and EPFL / Switzerland James Henderson Idiap Research Institute / Switzerland {alireza.mohammadshahi, james.henderson}@idiap.ch 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 Trans- former 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 lan- guages 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. 1 Introduction In recent years, there has been a huge amount of research on applying self-attention models to NLP tasks. Transformer (Vaswani et al., 2017) 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 struc- ture of sentences, typically absolute position embed- dingsareinputtoeachvectorintheset, butrecentlya mechanism has been proposed for inputting relative positions (Shaw et al., 2018). For each pair of vec- tors, 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 pro- posals in that it inputs graph relations as continuous embeddings, instead of discrete model structure (e.g. (Henderson, 2003; Henderson et al., 2013; Dyer et al., 2015)) or predefined discrete attention heads (e.g. (Ji et al., 2019; Strubell et al., 2018)). An explicit representation of binary relations is sup- ported 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 …

Content truncated to 500 words