Branch and Bound Algorithm for Dependency Parsing with Non-local Features
Graph based dependency parsing is inefficient when handling non-local features due to high computational complexity of inference. In this paper, we proposed an exact and efficient decoding algorithm based on the Branch and Bound (B{\&}B) framework where non-local features are bounded by a linear combination of local features. Dynamic programming is used to search the upper bound. Experiments are conducted on English PTB and Chinese CTB datasets. We achieved competitive Unlabeled Attachment Score (UAS) when no additional resources are available: 93.17{\%} for English and 87.25{\%} for Chinese. Parsing speed is 177 words per second for English and 97 words per second for Chinese. Our algorithm is general and can be adapted to non-projective dependency parsing or other graphical models.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Dependency Parsing with Bounded Block Degree and Well-nestedness via Lagrangian Relaxation and Branch-and-Bound
Transition-based Dependency Parsing with Selectional Branching
CCG Parsing Algorithm with Incremental Tree Rotation
The main obstacle to incremental sentence processing arises from right-branching constituent structures, which are present in the majority of English sentences, as well as optional constituents that adjoin on the right, …
SentenceDependency Graph Parsing as Sequence Labeling
Various linearizations have been proposed to cast syntactic dependency parsing as sequence labeling. However, these approaches do not support more complex graph-based representations, such as semantic dependencies or enh…
Dependency ParsingInvestigation of Transfer Languages for Parsing Latin: Italic Branch vs. Hellenic Branch
Choosing a transfer language is a crucial step in transfer learning. In much previous research on dependency parsing, related languages have successfully been used. However, when parsing Latin, it has been suggested that…
Dependency ParsingTransfer Learning