Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time
We present a new cubic-time algorithm to calculate the optimal next step in shift-reduce dependency parsing, relative to ground truth, commonly referred to as dynamic oracle. Unlike existing algorithms, it is applicable if the training corpus contains non-projective structures. We then show that for a projective training corpus, the time complexity can be improved from cubic to linear.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingSimilar Papers 제목 키워드 기반
Calculating the optimal step of arc-eager parsing for non-projective trees
It is shown that the optimal next step of an arc-eager parser relative to a non-projective dependency structure can be calculated in cubic time, solving an open problem in parsing theory. Applications are in training of …
ARCEfficient Stacked Dependency Parsing by Forest Reranking
This paper proposes a discriminative forest reranking algorithm for dependency parsing that can be seen as a form of efficient stacked parsing. A dynamic programming shift-reduce parser produces a packed derivation fores…
ARCDependency ParsingRerankingSpan-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles
Parsing accuracy using efficient greedy transition systems has improved dramatically in recent years thanks to neural networks. Despite striking results in dependency parsing, however, neural models have not surpassed st…
Constituency ParsingDependency ParsingRerankingSentenceShift-Reduce CCG Parsing with a Dependency Model
A Gamification of Japanese Dependency Parsing
Gamification approaches have been used as a way for creating language resources for NLP. It is also used for presenting and teaching the algorithms in NLP and linguistic phenomena. This paper argues about a design of gam…
Dependency Parsing