Incrementality in Deterministic Dependency Parsing

Summary

The paper studies how incremental a deterministic, left-to-right dependency parser can be, in the sense of keeping the partially built structure connected as words arrive. It formalises parsing as a transition system over a stack and an input buffer, and analyses the arc-standard style of transitions (shift, left-arc, right-arc) and its relation to an arc-eager variant. The author shows that strict incrementality cannot be achieved for all structures in a purely bottom-up arc-standard system, while the arc-eager strategy allows a higher degree of incrementality. The analysis connects parsing algorithms to questions of human sentence processing and provides the formal basis for many later transition-based parsers trained with classifiers and static oracles.

How Mova uses it

• en/src/parse.rs — the dependency parser is a table-driven arc-standard transition automaton: state = stack + buffer, actions SHIFT / LEFT(label) / RIGHT(label).
• Decisions come from tables "feature → action weight", trained with an averaged perceptron against a static oracle derived from UD trees (the transition framework from this paper; feature templates simplified from Zhang & Nivre 2011).
• Adapted into two stages, action type (3 classes) and then the UD label only for arcs, to keep tables small; features are integers (template number + word/tag codes).
• Extended with beam search (8 hypotheses) and early update (Zhang & Clark 2008).

Effectiveness in Mova

The transition system itself is not compared against alternatives (e.g. arc-eager), so its share is not measured separately. Parser results from the en README and en/src/parse.rs, UD English EWT test UAS/LAS: 86.9 / 83.8 with gold tags; 84.2 / 79.8 with Mova's own tags; greedy 83.4 / 79.0; greedy with TnT tags 82.3 / 77.3; PUD 81.5 / 76.3, GUM 81.5 / 76.2; about 58k tokens/s. Adding the beam raised EWT test LAS from 79.00 to 79.77 (dev 77.33 → 79.17, PUD 74.48 → 76.33).

👨‍🔬💥

More ideas (a second reading)

• I1. en/src/parse.rs: the arc-standard transitions are the current choice. Add an arc-eager transition set as a variant and compare LAS on EWT test (held out, LAS 79.8 with own tags today) and the share of configurations with at most one component. Decide on the two-fold check (en folds), not on test.
• I2. en parse-eval: report the incrementality share (configurations with at most one and at most three components) next to LAS, on EWT test and on the well-formed subset, as the paper does. This is a cheap diagnostic that costs no training.
• I3. Real-time mode: count the words whose head arc is final when the word is read. Measure this share on EWT test and PUD test (test only, as PUD is not ours to train on) against LAS, to see how much accuracy the streaming mode costs.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1613148.1613156

@inproceedings{nivre2004incrementality,
  title = {{Incrementality in Deterministic Dependency Parsing}},
  author = {Nivre, Joakim},
  booktitle = {Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together},
  year = {2004},
  doi = {10.3115/1613148.1613156},
  url = {https://doi.org/10.3115/1613148.1613156}
}

References

18 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Steven Abney and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20:233–250. find
2. Steven Abney. 1991. Parsing by chunks. In Principle-Based Parsing, pages 257–278. Kluwer. find
3. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings NAACL-2000. find
4. Michael Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annatual Meeting of the Association for Computational Linguistics, pages 16–23, Madrid, Spain. find
5. Walter Daelemans, Sabine Buchholz, and Jorn Veenstra. 1999. Memory-based shallow parsing. In Proceedings of the 3rd Conference on Computational Natural Language Learning (CoNLL), pages 77–89. find
6. Walter Daelemans, Jakub Zavrel, Ko van der Sloot, and Antal van den Bosch. 2003. Timbl: Tilburg memory based learner, version 5.0, reference guide. Technical Report ILK 03-10, Tilburg University, ILK. find
7. Jan Einarsson. 1976. Talbankens skriftspråks-konkordans. Lund University. find
8. Parser configurations Number Percent 928 9.2 7823 77.8 1000 10.0 248 2.5 41 0.4 8 0.1 1 0.0 8751 87.1 9999 99.5 10049 100.0 find
9. Lyn Frazier. 1987. Syntactic processing: Evidence from Dutch. Natural Language and Linguistic Theory, 5:519–559. find
10. Matthias Trautner Kromann. 2002. Optimality parsing and local cost functions in Discontinuous Grammar. Electronic Notes of Theoretical Computer Science, 52. find
11. William Marslen-Wilson. 1973. Linguistic structure and speech shadowing at very short latencies. Nature, 244:522–533. find
12. Igor Mel’cuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
13. George A. Miller and Noam Chomsky. 1963. Finitary models of language users. In R. D. Luce, R. R. Bush, and E. Galanter, editors, Handbook of Mathematical Psychology. Volume 2. Wiley. find
14. Glyn Morrill. 2000. Inremental processing and acceptability. Computational Linguistics, 26:319–338. find
15. Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of the 8th Conference on Computational Natural Language Learning (CoNLL), pages 49–56. find
16. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 149– 160. find our card
17. Mark Steedman. 2000. The Syntactic Process. MIT Press. find
18. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 195–206. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/nivre-2004-incrementality-deterministic-dependency-parsing/