Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers
We generalize Cohen, G\'omez-Rodr\'iguez, and Satta's (2011) parser to a family of non-projective transition-based dependency parsers allowing polynomial-time exact inference. This includes novel parsers with better coverage than Cohen et al. (2011), and even a variant that reduces time complexity to $O(n^6)$, improving over the known bounds in exact inference for non-projective transition-based parsing. We hope that this piece of theoretical work inspires design of novel transition systems with better coverage and better run-time guarantees. Code available at https://github.com/tzshi/nonproj-dp-variants-naacl2018
Code (1)
Similar Papers 제목 키워드 기반
Efficient Parsing for Head-Split Dependency Trees
Head splitting techniques have been successfully exploited to improve the asymptotic runtime of parsing algorithms for projective dependency trees, under the arc-factored model. In this article we extend these techniques…
ARCDependency ParsingHeaded-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 ParsingHeaded-Span-Based Projective Dependency Parsing
We propose a new paradigm for projective dependency parsing based on headed spans. In a projective dependency tree, the subtree rooted at each word covers a contiguous sequence (i.e., a span) in the surface order. We c…
Dependency Parsingglobal-optimizationLatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesis
Structured sequence generation often requires a model to satisfy several input-derived constraints in a single output. Standard decoding methods may assign high probability to fluent continuations while placing low mass …
Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling
Scheduling on dataflow graphs (also known as computation graphs) is an NP-hard problem. The traditional exact methods are limited by runtime complexity, while reinforcement learning (RL) and heuristic-based approaches st…
Combinatorial OptimizationReinforcement Learning (RL)Scheduling