Fast and Accurate Non-Projective Dependency Tree Linearization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees
The syntactic structure of a sentence is often represented using syntactic dependency trees. The sum of the distances between syntactically related words has been in the limelight for the past decades. Research on depend…
SentenceBracketing Encodings for 2-Planar Dependency Parsing
We present a bracketing-based encoding that can be used to represent any 2-planar dependency tree over a sentence of length n as a sequence of n labels, hence providing almost total coverage of crossing arcs in sequence …
Dependency ParsingPOSSentenceThe expected sum of edge lengths in planar linearizations of trees. Theory and applications
Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges connect syntactically-dependent words. Th…
SentenceHeaded-Span-Based Projective Dependency Parsing
We propose a new method for projective dependency parsing based on headed spans. In a projective dependency tree, the largest subtree rooted at each word covers a contiguous sequence (i.e., a span) in the surface order. …
Constituency ParsingDependency ParsingGlobal Greedy Dependency Parsing
Most syntactic dependency parsing models may fall into one of two categories: transition- and graph-based models. The former models enjoy high inference efficiency with linear time complexity, but they rely on the stacki…
ARCDependency ParsingRe-RankingSentence