Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs
Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint-crossing (1ec) graphs, which has high coverage on standard data sets. Our main contribution is a characterization of 1ec graphs as a subclass of the graphs with pagenumber at most 3. Building on this we show how to extend an existing parsing algorithm for 1-endpoint-crossing trees to the full class. While the runtime complexity of the extended algorithm is polynomial in the length of the input sentence, it features a large constant, which poses a challenge for practical implementations.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingSentenceSimilar Papers 제목 키워드 기반
Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs
We study the Maximum Subgraph problem in deep dependency parsing. We consider two restrictions to deep dependency graphs: (a) 1-endpoint-crossing and (b) pagenumber-2. Our main contribution is an exact algorithm that obt…
Dependency ParsingSemantic Dependency ParsingQuasi-Second-Order Parsing for 1-Endpoint-Crossing, Pagenumber-2 Graphs
We propose a new Maximum Subgraph algorithm for first-order parsing to 1-endpoint-crossing, pagenumber-2 graphs. Our algorithm has two characteristics: (1) it separates the construction for noncrossing edges and crossing…
ARCDependency ParsingFinding Optimal 1-Endpoint-Crossing Trees
Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have traditionally been orders of magnitude slower than algorithms for projective trees. For 95.8{-…
Dependency ParsingMachine TranslationQuestion AnsweringA Crossing-Sensitive Third-Order Factorization for Dependency Parsing
Parsers that parametrize over wider scopes are generally more accurate than edge-factored models. For graph-based non-projective parsers, wider factorizations have so far implied large increases in the computational comp…
Dependency ParsingNeural Maximum Subgraph Parsing for Cross-Domain Semantic Dependency Analysis
We present experiments for cross-domain semantic dependency analysis with a neural Maximum Subgraph parser. Our parser targets 1-endpoint-crossing, pagenumber-2 graphs which are a good fit to semantic dependency graphs, …
Dependency ParsingSemantic Parsing