Fast and Accurate Non-Projective Dependency Tree Linearization (2020)

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 facilitate the decoding by solving the TSP for each subtree and combining the solution into a projective tree. We then design a transition system as post-processing, inspired by non-projective transition-based parsing, to obtain non-projective sentences. Our proposed method outperforms the state-of-the-art linearizer while being 10 times faster in training and decoding.

## introduction surface realization is the task of generating a sentence from a syntactic or semantic representation. in several shared tasks @xcite @xcite , the input representations are unordered dependency trees. the state-of-the-art system @xcite in the surface realization shared task 2019 (sr'19) takes a pipeline approach, where the first step is linearization, namely ordering the tokens in the dependency tree. they use a tree-lstm to encode each token with awareness of the whole tree, then apply the divide-andconquer 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 @xcite . in this work, we tackle linearization decoding in a different way, by casting it as a traveling salesman problem (tsp). @xcite first formulated 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, @xcite formulate the word ordering in phrase-based machine translation as a tsp, and show that it achieves better performance and speed than beam search decoding with the same bigram language model. horvat and byrne (2014) explore higher-order n-gram language 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 structure. much effort has been put into incorporating more powerful decoding algorithms such as integer programming @xcite and dynamic programming @xcite . 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 encoder to provide better representation of the tokens. in this paper, we solve the dependency tree linearization task as a tsp. with the help of tree-lstm to encode the tree and biaffine attention as a bigram language model, we can use a greedy tsp solver to linearize the tree effectively. furthermore, the divide-and-conquer strategy greatly reduces the search space but introduces the projectivity restriction, which we remedy with a transition-based reordering system. as a result, the proposed linearizer outperforms the previous state-of-the-art model both in quality and speed. ## conclusion in this paper, we revisit the idea of treating word ordering as a tsp, but unlike the common bagof-words scenario, the words have an underlying syntactic structure. we demonstrate that with the tree-lstm encoder, the biaffine scoring model, the divide-and-conquer strategy, and a transitionbased sorting system, we can linearize a dependency tree with high speed and quality and without the projectivity restriction. we show with various ablation experiments that all of the components are crucial for the success of the tsp-based linearizer. our work emphasizes the importance of syntax in the word ordering task. we discussed many connections and similarities between linearization and parsing. we believe that quite generally, systems for solving one task can benefit from the other task's view on syntactic structure. one possibility to capitalize on these synergies is to explore data augmentation methods to select beneficial extra training data in an unsupervised fashion.