Finding Optimal 1-Endpoint-Crossing Trees

2013-01-01 · TACL 2013 1 · Emily Pitler, Sampath Kannan, Mitchell Marcus

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{--}99.8{\%} of dependency parses in various natural language treebanks, whenever an edge is crossed, the edges that cross it all have a common vertex. The optimal dependency tree that satisfies this 1-Endpoint-Crossing property can be found with an O(n4) parsing algorithm that recursively combines forests over intervals with one exterior point. 1-Endpoint-Crossing trees also have natural connections to linguistics and another class of graphs that has been studied in NLP.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Dependency Parsing Machine Translation Question Answering

Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs

2017-09-01 · WS 2017 9 · Robin Kurtz, Marco Kuhlmann

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…

Dependency Parsing Sentence

A Crossing-Sensitive Third-Order Factorization for Dependency Parsing

2014-01-01 · TACL 2014 1 · Emily Pitler

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 Parsing

Quasi-Second-Order Parsing for 1-Endpoint-Crossing, Pagenumber-2 Graphs

2017-09-01 · EMNLP 2017 9 · Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan

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…

ARC Dependency Parsing

Recognizing and Eliciting Weakly Single Crossing Profiles on Trees

2016-11-13 · Palash Dey

We introduce and study the weakly single-crossing domain on trees which is a generalization of the well-studied single-crossing domain in social choice theory. We design a polynomial-time algorithm for recognizing prefer…

Open-Ended Question Answering

Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs

2017-07-01 · ACL 2017 7 · Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan

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 Parsing Semantic Dependency Parsing