Fast and Accurate Non-Projective Dependency Tree Linearization

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1451–1462 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 1451 Fast and Accurate Non-Projective Dependency Tree Linearization Xiang Yu, Simon Tannert, Ngoc Thang Vu, Jonas Kuhn Institut f¨ur Maschinelle Sprachverarbeitung University of Stuttgart, Germany firstname.lastname@ims.uni-stuttgart.de Abstract We propose a graph-based method to tackle the dependency tree linearization task. We formulate the task as a Traveling Salesman Problem (TSP), and use a biaffine attention model to calculate the edge costs. We fa- cilitate the decoding by solving the TSP for each subtree and combining the solution into a projective tree. We then design a transi- tion system as post-processing, inspired by non-projective transition-based parsing, to ob- tain non-projective sentences. Our proposed method outperforms the state-of-the-art lin- earizer while being 10 times faster in training and decoding. 1 Introduction Surface realization is the task of generating a sen- tence from a syntactic or semantic representation. In several shared tasks (Belz et al., 2011; Mille et al., 2018, 2019), the input representations are unordered dependency trees. The state-of-the-art system (Yu et al., 2019a) in the Surface Realiza- tion Shared Task 2019 (SR’19) takes a pipeline ap- proach, where the first step is linearization, namely ordering the tokens in the dependency tree. They use a Tree-LSTM to encode each token with aware- ness of the whole tree, then apply the divide-and- conquer strategy to split the full tree into subtrees and find the optimal order for each subtree using beam search. Finally, the linearized subtrees are combined into a full projective tree. The general strategy is adapted from Bohnet et al. (2010). In this work, we tackle linearization decoding in a different way, by casting it as a Traveling Sales- man Problem (TSP). Knight (1999) first formu- lated the word ordering of the target language in word-based machine translation as a TSP, where the words are the nodes to traverse, and the log probabilities of the bigrams are the edge costs. Several works have followed this formulation. Among others, Zaslavskiy et al. (2009) formulate the word ordering in phrase-based machine trans- lation as a TSP, and show that it achieves better performance and speed than beam search decod- ing with the same bigram language model. Horvat and Byrne (2014) explore higher-order n-gram lan- guage models for TSP-based word ordering, which transforms into a much larger TSP graph. All of the aforementioned works operate on a bag of words without syntax, which is a TSP graph of non-trivial size with little information about the internal struc- ture. Much effort has been put into incorporating more powerful decoding algorithms such as Integer Programming (Germann et al., 2001) and Dynamic Programming (Tillmann and Ney, 2003). Our work differs from the previous work on TSP-based word ordering in several aspects. (1) Linearization is a special case of word ordering with syntax, where we can use a tree-structured en- coder to provide better representation of the tokens. (2) We adopt the divide-and-conquer strategy to …

Content truncated to 500 words