Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time

Mark Jan Nederhof

doi:10.1162/tacl_a_00268

Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time

Mark Jan Nederhof

School of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	283-296
Number of pages	14
Journal	Transactions of the Association for Computational Linguistics
Volume	7
DOIs	https://doi.org/10.1162/tacl_a_00268
Publication status	Published - 31 May 2019

Keywords

Formal language theory
Automata theory

Access to Document

10.1162/tacl_a_00268Licence: CC BY

Nederhof-2019-Calculating-optimal-TACL-283-CC
© 2019 Association for Computational Linguistics. This is an open-access article distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. For a full description of the license, please visit https://creativecommons.org/licenses/by/4.0/legalcode.
Final published version, 826 KBLicence: CC BY

Cite this

@article{309939cb52534ef391c8bda773cea8f2,

title = "Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time",

abstract = "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.",

keywords = "Formal language theory, Automata theory",

author = "Nederhof, \{Mark Jan\}",

year = "2019",

month = may,

day = "31",

doi = "10.1162/tacl\_a\_00268",

language = "English",

volume = "7",

pages = "283--296",

journal = "Transactions of the Association for Computational Linguistics",

issn = "2307-387X",

publisher = "MIT Press Journals",

}

TY - JOUR

T1 - Calculating the optimal step in shift-reduce dependency parsing

T2 - from cubic to linear time

AU - Nederhof, Mark Jan

PY - 2019/5/31

Y1 - 2019/5/31

N2 - 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.

AB - 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.

KW - Formal language theory

KW - Automata theory

UR - https://www.scopus.com/pages/publications/85107273555

U2 - 10.1162/tacl_a_00268

DO - 10.1162/tacl_a_00268

M3 - Article

SN - 2307-387X

VL - 7

SP - 283

EP - 296

JO - Transactions of the Association for Computational Linguistics

JF - Transactions of the Association for Computational Linguistics

ER -

Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Mark Nederhof

Cite this

Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Profiles

Mark Nederhof

Cite this