Please Mind the Root: Decoding Arborescences for Dependency Parsing

• URL: http://arxiv.org/abs/2010.02550v2
• Date: Wed, 7 Oct 2020 08:12:11 GMT
• Title: Please Mind the Root: Decoding Arborescences for Dependency Parsing
• Authors: Ran Zmigrod, Tim Vieira, Ryan Cotterell
• Abstract summary: We analyze the output of state-of-the-arts on many languages from the Universal Dependency Treebank. The worst constraint-violation rate we observe is 24%.
• Score: 67.71280539312536
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The connection between dependency trees and spanning trees is exploited by the NLP community to train and to decode graph-based dependency parsers. However, the NLP literature has missed an important difference between the two structures: only one edge may emanate from the root in a dependency tree. We analyzed the output of state-of-the-art parsers on many languages from the Universal Dependency Treebank: although these parsers are often able to learn that trees which violate the constraint should be assigned lower probabilities, their ability to do so unsurprisingly de-grades as the size of the training set decreases. In fact, the worst constraint-violation rate we observe is 24%. Prior work has proposed an inefficient algorithm to enforce the constraint, which adds a factor of n to the decoding runtime. We adapt an algorithm due to Gabow and Tarjan (1984) to dependency parsing, which satisfies the constraint without compromising the original runtime.

Related papers

• Hexatagging: Projective Dependency Parsing as Tagging [63.5392760743851]
  We introduce a novel dependency, the hexatagger, that constructs dependency trees by tagging the words in a sentence with elements from a finite set of possible tags. Our approach is fully parallelizable at training time, i.e., the structure-building actions needed to build a dependency parse can be predicted in parallel to each other. We achieve state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set.
  arXiv  Detail & Related papers  (2023-06-08T18:02:07Z)
• Hierarchical Dependency Constrained Tree Augmented Naive Bayes Classifiers for Hierarchical Feature Spaces [0.0]
  We propose two novel Hierarchical dependency-based Tree Augmented Naive Bayes algorithms, i.e. Hie-TAN and Hie-TAN-Lite. Hie-TAN successfully obtained better predictive performance than several other hierarchical dependency constrained classification algorithms.
  arXiv  Detail & Related papers  (2022-02-08T19:16:51Z)
• Biaffine Discourse Dependency Parsing [0.0]
  We use the biaffine model for neural discourse dependency parsing and achieve significant performance improvement compared with the baselines. We compare the Eisner algorithm and the Chu-Liu-Edmonds algorithm in the task and find that using the Chu-Liu-Edmonds generates deeper trees.
  arXiv  Detail & Related papers  (2022-01-12T12:56:13Z)
• Efficient Sampling of Dependency Structures [39.5549669100436]
  We adapt two spanning tree sampling algorithms to faithfully sample dependency trees from a graph subject to a root constraint. We build upon Colbourn's algorithm and present a novel extension that can sample $K$ trees without replacement in $mathcalO(K N3 + K2 N)$ time.
  arXiv  Detail & Related papers  (2021-09-14T08:33:12Z)
• Learning compositional structures for semantic graph parsing [81.41592892863979]
  We show how AM dependency parsing can be trained directly on a neural latent-variable model. Our model picks up on several linguistic phenomena on its own and achieves comparable accuracy to supervised training.
  arXiv  Detail & Related papers  (2021-06-08T14:20:07Z)
• On Finding the $K$-best Non-projective Dependency Trees [39.5549669100436]
  We provide a simplification of the $K$-best spanning tree algorithm of Camerini et al. (1980). We present a novel extension of the algorithm for decoding the $K$-best dependency trees of a graph which are subject to a root constraint.
  arXiv  Detail & Related papers  (2021-06-01T20:23:41Z)
• Linguistic dependencies and statistical dependence [76.89273585568084]
  We use pretrained language models to estimate probabilities of words in context. We find that maximum-CPMI trees correspond to linguistic dependencies more often than trees extracted from non-contextual PMI estimate.
  arXiv  Detail & Related papers  (2021-04-18T02:43:37Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
  Parsing sentences into syntax trees can benefit downstream applications in NLP. Transition-baseds build trees by executing actions in a state transition system. Existing transition-baseds are predominantly based on the shift-reduce transition system.
  arXiv  Detail & Related papers  (2020-10-27T19:19:38Z)
• Efficient Second-Order TreeCRF for Neural Dependency Parsing [23.426500262860777]
  In the deep learning (DL) era, parsing models are extremely simplified with little hurt on performance. This paper presents a second-order TreeCRF extension to the biaffine. We propose an effective way to batchify the inside and Viterbi algorithms for direct large matrix operation.
  arXiv  Detail & Related papers  (2020-05-03T03:18:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.