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

1 Citation (Scopus)

9 Downloads (Pure)

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

Mark Jan Nederhof
- mn31st-andrews.acuk
- School of Computer Science - Senior Lecturer
Person: Academic

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

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

Fingerprint

Profiles

Mark Jan Nederhof

Cite this