Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement (2021)

Abstract: We propose the Recursive Non-autoregressive Graph-to-Graph Transformer architecture (RNGTr) for the iterative refinement of arbitrary graphs through the recursive application of a non-autoregressive Graph-to-Graph Transformer and apply it to syntactic dependency parsing. We demonstrate the power and effectiveness of RNGTr on several dependency corpora, using a refinement model pre-trained with BERT. We also introduce Syntactic Transformer (SynTr), a non-recursive parser similar to our refinement model. RNGTr can improve the accuracy of a variety of initial parsers on 13 languages from the Universal Dependencies Treebanks, English and Chinese Penn Treebanks, and the German CoNLL2009 corpus, even improving over the new state-of-the-art results achieved by SynTr, significantly improving the state-of-the-art for all corpora tested.

## introduction self-attention models, such as transformer @xcite , have been hugely successful in a wide range of natural language processing (nlp) tasks, especially when combined with language-model pre-training, such as bert @xcite . these architectures contain a stack of self-attention layers that can capture long-range dependencies over the input sequence, while still representing its sequential order using absolute position encodings. alternatively, @xcite propose to define sequential order with relative position encodings, which are input to the self-attention functions. recently, @xcite extended this sequence input method to the input of arbitrary graph relations via the selfattention mechanism, and combined it with an attention-like function for graph relation prediction, resulting in their proposed graph-to-graph transformer architecture (g2gtr). they demonstrated the effectiveness of g2gtr for transitionbased dependency parsing and its compatibility with pre-trained bert @xcite . this parsing model predicts one edge of the parse graph at a time, conditioning on the graph of previous edges, so it is an autoregressive model. the g2gtr architecture could be used to predict all the edges of a graph in parallel, but such predictions are non-autoregressive. they thus cannot fully model the interactions between edges. for sequence prediction, this problem has been addressed with non-autoregressive iterative refinement @xcite @xcite . interactions between different positions in the string are modeled by conditioning on a previous version of the same string. in this paper, we propose a new graph prediction architecture that takes advantage of the full graphto-graph functionality of g2gtr to apply a g2gtr model to refine the output graph recursively. this architecture predicts all edges of the graph in parallel, and is therefore non-autoregressive, but can still capture any between-edge dependency by conditioning on the previous version of the graph, like an auto-regressive model. this proposed recursive non-autoregressive graph-to-graph transformer (rngtr) architecture has three components. first, an initialization model computes an initial graph, which can be any given model for the task, even a trivial one. second, a g2gtr model takes the previous graph as input and predicts each edge of the target graph. third, a decoding algorithm finds the best graph given these edge predictions. the second and third components are applied recursively to do iterative refinement of the output graph until some stopping criterion is met. the final output graph is the graph output by the final decoding step. the rng transformer architecture can be applied to any task with a sequence or graph as input and a graph over the same set of nodes as output. we evaluate rngtr on syntactic dependency parsing because it is a difficult structured prediction task, state-of-the-art initial parsers are extremely competitive, and there is little previous evidence that non-autoregressive models (as in graph-based dependency parsers) are not sufficient for this task. we aim to show that capturing correlations between dependencies with non-autoregressive iterative refinement results in improvements, even in the challenging case of state-of-the-art dependency parsers. the evaluation demonstrates improvements with several initial parsers, including previous state-of-the-art dependency parsers, and the empty parse. we also introduce a strong transformerbased dependency parser pre-trained with bert @xcite , called syntactic transformer (syntr), using it both for our initial parser and as the basis of our refinement model. results on 13 languages from the universal dependencies treebanks @xcite , english and chinese penn treebanks @xcite , and the german conll 2009 corpus @xcite show significant improvements over all initial parsers and the stateof-the-art. 1 in this paper, we make the following contributions: ## dependency parsing syntactic dependency parsing is a critical component in a variety of natural language understanding tasks, such as semantic role labeling @xcite , machine transla-1 our implementation is available at: https://github .com/idiap/g2g-transformer . there are several approaches to capture correlations between dependency edges in graph-based models. in first-order models, such as maximum spanning tree (mst) @xcite @xcite , the score for an edge must be computed without being sure what other edges the model will choose. the model itself only imposes the discrete tree constraint between edges. higher-order models @xcite @xcite @xcite keep some between-edge information, but require more decoding time. in this paper, we apply first-order models, specifically the mst algorithm, and show that it is possible to keep correlations between edges without increasing the time complexity by recursively conditioning each edge score on a previous prediction of the complete dependency graph. ## rng transformer the rng transformer architecture is illustrated in figure 1 , in this case, applied to dependency parsing. the input to a rngtr model specifies the input nodes @xmath0, w 2 , . . . , w n ) (e.g., a sentence), and the output is the final graph g t (e.g., a parse tree) over this set of nodes. the first step is to compute an initial graph of g 0 over w , which can be done with any model. then each recursive iteration takes the previous graph g t-1 as input and predicts a new graph g t . the rngtr model predicts g t with a novel version of a graph-to-graph transformer @xcite . unlike in the work of @xcite , this g2gtr model predicts every edge of the graph in a single non-autoregressive step. as previously, the g2gtr first encodes the input graph g t-1 in a set of contextualized vector representations @xmath1, z 2 , . . . , z n ), with one vector for each node of the graph. the decoder component then predicts the output graph g t by first computing scores for each possible edge between each pair of nodes and then applying a decoding algorithm to output the highest-scoring complete graph. the rngtr model can be formalized in terms of an encoder e rng and a decoder d rng : in the case of dependency parsing, w are the words and symbols, p are their part-of-speech tags, and the predicted graph at iteration t is specified as: each word w j has one head (parent) w i with dependency label l from the label set l, where the parent can also be the root symbol w 2 (see section 3.1.1). the following sections describe in more detail each element of the proposed rngtr dependency parsing model. ## initial parsers the rngtr architecture requires a graph g 0 to initialize the iterative refinement. we consider several initial parsers to produce this graph. to leverage previous work on dependency parsing and provide a controlled comparison to the stateof-the-art, we use parsing models from the recent literature as both baselines and initial parsers. to evaluate the importance of the initial parse, we also consider a setting where the initial parse is empty, so the first complete dependency tree is predicted by the rngtr model itself. finally, the success of our rngtr dependency parsing model leads us to propose an initial parsing model with the same design, so that we can control for the parser design in measuring the importance of the rng transformer's iterative refinement. ## results and discussion after some initial experiments to determine the maximum number of refinement iterations, we report the performance of the rng transformer model on the ud treebanks, penn treebanks, and german conll 2009 treebank. 5 the rngtr models perform substantially better than previously proposed models on every dataset, and rngtr refinement improves over its initial parser for almost every dataset. we also perform various analyses to understand these results better. ## conclusion in this paper, we propose a novel architecture for structured prediction, recursive non-autoregressive graph-to-graph transformer (rng transformer), to iteratively refine arbitrary graphs. given an initial graph, rng transformer learns to predict a corrected graph over the same set of nodes. each iteration of refinement predicts the edges of the graph in a non-autoregressive fashion, but conditions these predictions on the entire graph from the previous iteration. this graph conditioning and prediction are made with the graph-to-graph transformer architecture @xcite , which can capture complex patterns of interdependencies between graph edges and can exploit bert @xcite pre-training. we evaluate the rng transformer architecture by applying it to the problematic structured prediction task of syntactic dependency parsing. in the process, we also propose a graph-based dependency parser (syntr), which is the same as one iteration of our rng transformer model but without graph inputs. evaluating on 13 languages of the universal dependencies treebanks, the english and chinese penn treebanks, and the german conll 2009 shared task treebank, our syntr model already significantly outperforms previous state-of-the-art models on all these treebanks. even with this powerful initial parser, rng transformer refinement almost always improves accuracies, setting new state-of-the-art accuracies for all treebanks. rng transformer consistently results in improvement regardless of the initial parser, reaching around the same level of accuracy even when it is given an empty initial parse, demonstrating the power of this iterative refinement method. error analysis suggests that rng transformer refinement is particularly useful for complex interdependencies in the output structure. the rng transformer architecture is a very general and powerful method for structured prediction, which could easily be applied to other nlp tasks. it would especially benefit tasks that require capturing complex structured interdependencies between graph edges, without losing the computational benefits of a non-autoregressive model.