(Adding categories) Tag: categoryselect |
(well-formedness) Tag: sourceedit |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
'''Original article:''' Nivre (2004)<ref>Nivre, J. (2004). Incrementality in Deterministic Dependency Parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together.</ref> |
'''Original article:''' Nivre (2004)<ref>Nivre, J. (2004). Incrementality in Deterministic Dependency Parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together.</ref> |
||
| + | |||
| + | '''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)<ref name=nivre14>Nivre, Joakim, and Daniel Fernández-González. "Arc-eager parsing with the tree constraint." Computational linguistics 40.2 (2014): 259-267.</ref>. |
||
'''Motivation:''' increase incrementality w.r.t. arc-standard. |
'''Motivation:''' increase incrementality w.r.t. arc-standard. |
||
| − | + | == Transitions == |
|
* 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) |
* 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) |
* 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) |
||
| Line 9: | Line 11: | ||
* Shift (SH) pushes the next input token wi onto the stack. |
* Shift (SH) pushes the next input token wi onto the stack. |
||
| + | == Training == |
||
| ⚫ | |||
| + | |||
| + | === Static oracle === |
||
| + | From Goldberg & Nivre (2012)<ref>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.</ref>, page 963: |
||
| + | |||
| + | i: top of stack, j: top of buffer<br/> |
||
| + | if there's a link j -> i then return LEFT-ARC<br/> |
||
| + | else if there's a link i -> j then return RIGHT-ARC<br/> |
||
| + | else if there's a link k <-/-> j, k < i then return REDUCE<br/> |
||
| + | else return SHIFT |
||
| + | |||
| + | === Dynamic oracle === |
||
| + | |||
| ⚫ | |||
{|class=wikitable |
{|class=wikitable |
||
| Line 45: | Line 60: | ||
| Turkish || - || 64.37 || Nivre (2008)<ref name=nivre08/> || |
| Turkish || - || 64.37 || Nivre (2008)<ref name=nivre08/> || |
||
|} |
|} |
||
| + | |||
| + | == Usage == |
||
| + | |||
| + | "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)<ref name=nivre14/> |
||
== References == |
== References == |
||
Latest revision as of 17:34, 13 May 2016
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[]
- 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[]
Static oracle[]
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[]
Performance[]
| 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[]
"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[]
- ↑ Nivre, J. (2004). Incrementality in Deterministic Dependency Parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together.
- ↑ 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.
- ↑ 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.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.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