FANDOM


Original article: Nivre (2004)[1]

Well-formedness: Arc-eager system doesn't ensure well-formedness. A modified version uses Unshift transition to fix ill-formed tree (Nivre & Fernández-González, 2014)[2].

Motivation: increase incrementality w.r.t. arc-standard.

Transitions Edit

  • Left-Arc: adds an arc wj → wi from the next input token wj to the token wi on top of the stack and pops the stack. (wj is head)
  • Right-Arc: adds an arc wi → wj from the token wi on top of the stack to the next input token wj, and pushes wj onto the stack. (wi is head)
  • Reduce pops the stack.
  • Shift (SH) pushes the next input token wi onto the stack.

Training Edit

Static oracle Edit

From Goldberg & Nivre (2012)[3], page 963:

i: top of stack, j: top of buffer
if there's a link j -> i then return LEFT-ARC
else if there's a link i -> j then return RIGHT-ARC
else if there's a link k <-/-> j, k < i then return REDUCE
else return SHIFT

Dynamic oracle Edit

Performance Edit

Dataset UAS LAS Reference Notes
WSJ §22 89.35 86.61 Kong & Smith (2014)[4] MaltParser, libsvm
WSJ §23 89.20 86.46 Kong & Smith (2014)[4] MaltParser, libsvm
Arabic - 64.93 Nivre (2008)[5]
Bulgarian - 87.75 Nivre (2008)[5]
Chinese - 85.96 Nivre (2008)[5]
Czech - 76.34 Nivre (2008)[5]
Danish - 84.25 Nivre (2008)[5]
Dutch - 74.79 Nivre (2008)[5]
German - 84.23 Nivre (2008)[5]
Japanese - 90.83 Nivre (2008)[5]
Portuguese - 85.83 Nivre (2008)[5]
Slovene - 69.50 Nivre (2008)[5]
Spanish - 79.84 Nivre (2008)[5]
Swedish - 82.63 Nivre (2008)[5]
Turkish - 64.37 Nivre (2008)[5]

Usage Edit

"One of the most widely used transition systems for dependency parsing is the arceager system first described in Nivre (2003), which has been used as the backbone for greedy deterministic dependency parsers (Nivre, Hall, and Nilsson 2004; Goldberg and Nivre 2012), beam search parsers with structured prediction (Zhang and Clark 2008; Zhang and Nivre 2011), neural network parsers with latent variables (Titov and Henderson 2007), and delexicalized transfer parsers (McDonald, Petrov, and Hall 2011)." (Nivre & Fernández-González, 2014)[2]

References Edit

  1. Nivre, J. (2004). Incrementality in Deterministic Dependency Parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together.
  2. 2.0 2.1 Nivre, Joakim, and Daniel Fernández-González. "Arc-eager parsing with the tree constraint." Computational linguistics 40.2 (2014): 259-267.
  3. Goldberg, Y., & Nivre, J. (2012). A Dynamic Oracle for Arc-Eager Dependency Parsing. Proceedings of the 24th International Conference on Computational Linguistics (COLING), 2(December), 959–976.
  4. 4.0 4.1 Kong, Lingpeng, and Noah A. Smith. "An empirical comparison of parsing methods for stanford dependencies." arXiv preprint arXiv:1404.4314 (2014).
  5. 5.00 5.01 5.02 5.03 5.04 5.05 5.06 5.07 5.08 5.09 5.10 5.11 5.12 Nivre, J. (2008). Algorithms for Deterministic Incremental Dependency Parsing. Comput. Linguist., 34(4), 513–553. doi:10.1162/coli.07-056-R1-07-027