Deterministic Dependency Parsing of English Text

What it is about

The paper presents one of the first deterministic, linear-time labeled dependency parsers for English, trained on the Wall Street Journal part of the Penn Treebank. The parser uses a shift-reduce transition system (left-arc, right-arc, reduce, shift) that builds projective trees in one pass, and a memory-based learner (TiMBL, k = 5) that predicts the next transition and arc label. Features are the stack top, the next input token, their heads and leftmost or rightmost dependents, and three lookahead tags. The treebank is converted to dependencies by head rules, with arc labels taken from the Penn function tags (7 labels) or from bracket plus function labels (50 labels). The best model reaches 87.1% unlabeled attachment; labeled accuracy is 86.0% on the 7-label set, while root accuracy is clearly weaker than dependency accuracy and falls for longer sentences.

Ideas

• I1. Root accuracy as a reported metric in en parse-eval: add root accuracy and complete-match rate, by sentence-length bins of 10 words, on EWT test; the paper locates the largest weakness at the root of long sentences.
• I2. Clause pre-split probe: split sentences over 20 words at clause boundaries before en parsing, then measure LAS and root accuracy on EWT test for that subset; the paper suggests clausing as a fix for root errors.
• I3. Label granularity study: train the en perceptron with coarse labels (function-tag level, as in the 7-label set) and with the full mova labels, and compare LAS on EWT test and root accuracy; the paper finds the coarser set easier and the unlabeled score higher with more labels.
• I4. Label-source check: count how many gold labels in the converted mova corpus come from function-like tags versus default labels, and how many errors fall on the default; test only on GUM, which is NC.

For Mova

The code is en/src/parse.rs (the arc-standard parser and its features) and the en parse-eval command. The chapter is 21. The simple clause. Measure first: root accuracy and LAS by sentence length on EWT test against the current LAS 80.24, because the paper shows that a good LAS can hide a poor root.

Topics: Dependency parsing

Cite

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

@inproceedings{nivre2004deterministic,
  title = {{Deterministic Dependency Parsing of English Text}},
  author = {Nivre, Joakim and Scholz, Mario},
  booktitle = {COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics},
  year = {2004},
  doi = {10.3115/1220355.1220365},
  url = {https://doi.org/10.3115/1220355.1220365}
}

References

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

1. D. W. Aha, D. Kibler, and M. Albert. 1991. Instance-based learning algorithms. Machine Learning, 6:37–66. find our card
2. D. Aha, editor. 1997. Lazy Learning. Kluwer. find
3. A. Bies, M. Ferguson, K. Katz, and R. MacIntyre. 1995. Bracketing guidelines for Treebank II style, Penn Treebank project. University of Pennsylvania, Philadelphia. find
4. E. Black, F. Jelinek, J. Lafferty, D. Magerman, R. Mercer, and S. Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. In Proceedings of the 5th DARPA Speech and Natural Language Workshop. find
5. D. Blaheta and E. Charniak. 2000. Assigning function tags to parsed text. In Proceedings of NAACL, pages 234–240. find
6. S. Buchholz. 2002. Memory-Based Grammatical Relation Finding. Ph.D. thesis, University of Tilburg. find
7. J. Carroll, E. Briscoe, and A. Sanfilippo. 1998. Parser evaluation: A survey and a new proposal. In Proceedings of LREC, pages 447–454, Granada, Spain. find
8. E. Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL. find
9. M. Collins, J. Hajič, E. Brill, L. Ramshaw, and C. Tillmann. 1999. A Statistical Parser of Czech. In Proceedings of ACL, pages 505–512, University of Maryland, College Park, USA. ≤ 10 11–20 21–30 31–40 ≥ 41 Table 3: Accuracy in relation to sentence length (number of words) find
10. M. Collins. 1996. A new statistical parser based on bigram lexical dependencies. In Proceedings of ACL, pages 184–191, Santa Cruz, CA. find
11. M. Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of ACL, pages 16–23, Madrid, Spain. find
12. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find our card
13. S. Cost and S. Salzberg. 1993. A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 10:57–78. find
14. W. Daelemans, A. van den Bosch, and J. Zavrel. 2002. Forgetting exceptions is harmful in language learning. Machine Learning, 34:11–43. find
15. W. Daelemans, J. Zavrel, K. van der Sloot, and A. van den Bosch. 2003. Timbl: Tilburg memory based learner, version 5.0, reference guide. Technical Report ILK 03-10, Tilburg University, ILK. find
16. W. Daelemans. 1999. Memory-based language processing. Introduction to the special issue. Journal of Experimental and Theoretical Artificial Intelligence, 11:287–292. find
17. S. A. Dudani. 1976. The distance-weighted knearest neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics, SMC-6:325–327. find
18. J. Einarsson. 1976. Talbankens skriftspråkskonkor-dans. Lund University. find
19. J. M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING, Copenhagen, Denmark. find our card
20. E. Fix and J. Hodges. 1952. Discriminatory analysis: Nonparametric discrimination: Consistency properties. Technical Report 11, USAF School of Aviation Medicine, Randolph Field, Texas. find
21. J. Hajic. 1998. Building a syntactically annotated corpus: The prague dependency treebank. In Issues of Valency and Meaning, pages 106–132. Karolinum. find
22. M. T. Kromann. 2003. The Danish dependency treebank and the DTAG treebank tool. In Proceedings of the Second Workshop on Treebanks DA 93.7 88.8 87.4 86.8 84.6 RA 96.6 86.4 83.4 78.1 74.9 CM 83.6 39.5 20.8 9.9 1.8 and Linguistic Theories, pages 217–220, Växjö, Sweden. find
23. T. Kudo and Y. Matsumoto. 2000. Japanese dependency structure analysis based on support vector machines. In Proceedings of EMNLP/VLC, Hongkong. find
24. D. Lin. 1998. Dependency-based evaluation of MINIPAR. In Proceedings of LREC. find
25. D. M. Magerman. 1995. Statistical decision-tree models for parsing. In Proceedings of ACL, pages 276–283, Boston, MA. find
26. M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19:313–330. find our card
27. J. Nivre, J. Hall, and J. Nilsson. 2004. Memory-based dependency parsing. In Proceedings of CoNLL, pages 49–56. find
28. J. Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of IWPT, pages 149–160, Nancy, France. find our card
29. K. Oflazer. 2003. Dependency parsing with an extended finite-state approach. Computational Linguistics, 29:515–544. find
30. R. Skousen. 1989. Analogical Modeling of Language. Kluwer. find
31. R. Skousen. 1992. Analogy and Structure. Kluwer. find
32. C. Stanfill and D. Waltz. 1986. Toward memory-based reasoning. Communications of the ACM, 29:1213–1228. find
33. V. N. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer-Verlag. find
34. J. Veenstra and W. Daelemans. 2000. A memory-based alternative for connectionist shift-reduce parsing. Technical Report ILK-0012, University of Tilburg. find
35. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, pages 195–206, Nancy, France. find our card

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