Elamur Research⌕
☰
home / papers / 2004 / Memory-Based Dependency Parsing

Memory-Based Dependency Parsing

Summary

The paper investigates whether a deterministic, linear-time dependency parser can be made accurate by letting a learned classifier choose its next move. The authors take the shift-reduce-style parser from Nivre (2003), which has four transitions (Left-Arc, Right-Arc, Reduce, Shift), and train memory-based (k-nearest-neighbour) classifiers with TiMBL. The training data is a small Swedish treebank. At each step the classifier predicts both the transition and, for arc-building transitions, the dependency label. It uses features of the stack top, the next input token, their already-built dependents, and a part-of-speech lookahead. Two variants are compared: one using only part-of-speech and dependency-type features, and one that also uses word forms. Both are evaluated against an earlier probabilistic model (MCLE) that relies on a fixed back-off scheme. Memory-based guidance beats MCLE even with identical features, and adding lexical features gives the best results (labeled attachment score 81.7 per sentence). This matters because it shows that labeled, efficient dependency parsing is feasible with modest training data.

Key points

  • The parser needs at most 2n transitions for n words, so it runs in linear time if each classification takes constant time. Its output is always acyclic and projective.

  • The best TiMBL settings differed from the defaults in four ways:

    • MVDM distance instead of the overlap metric
    • no feature weighting
    • k = 5
    • inverse-distance-weighted class voting

  • Next-action prediction accuracy:

    • non-lexical model: 86.8 with defaults, 87.4 after tuning
    • lexical model: 88.4 with defaults, 89.7 after tuning

  • Parsing accuracy, per sentence (per word in parentheses):

    ModelLASUAS
    MCLE74.7 (72.3)81.5 (79.7)
    MBL non-lexical76.5 (74.7)82.9 (81.7)
    MBL lexical81.7 (80.6)85.7 (84.7)

    All differences are significant at the .0001 level.

  • The training set is roughly 10% of the size of the standard Penn Treebank training set. Unlabeled results nonetheless fall between reported English (>90%) and Czech figures.

  • Per-type analysis:

    • Subjects are parsed most accurately.
    • Objects and predicative complements attach about as well as each other but are more often given the wrong label.
    • Adverbials attach worst, largely because of PP-attachment ambiguity.

Interesting ideas

  • I1. Learned guide for a deterministic parser. A nondeterministic transition system becomes deterministic by letting a classifier settle every choice point. This keeps parsing linear and robust, and the same recipe fits any incremental structure builder, such as a chunker or tagger, in a low-resource language.
  • I2. Similarity-based smoothing instead of fixed back-off. Nearest-neighbour extrapolation handled unseen parser states better than a hand-ordered back-off chain, even with the same features. This is worth trying whenever sparse feature combinations defeat count-based estimates.
  • I3. Predicting the label together with the transition. The label is folded into the action, and labels already assigned are reused as features for later decisions. The paper suggests this history helps accuracy, so it is a cheap design choice for labeled parsing, for example with UD relations.
  • I4. Separating where gains come from. The authors compare classifier accuracy, LAS and UAS side by side. The lexical model's advantage is much smaller on UAS, which shows that word forms mainly help label choice rather than attachment. Reporting labeled and unlabeled scores together is a simple way to diagnose such effects.
  • I5. Per-relation breakdown. Listing labeled precision/recall and attachment per dependency type exposes specific weaknesses, such as PP attachment for adverbials. This is useful for targeting annotation or feature work in a new treebank.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Linguistics & languages

Topics: Dependency parsing · Treebanks · Part-of-speech tagging

Cited by

102 papers of our library cite it (of the 140673 whose bibliographies we read); 17 of them have a page here, 85 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{nivre2004memory,
  title = {{Memory-Based Dependency Parsing}},
  author = {Nivre, Joakim and Hall, Johan and Nilsson, Jens},
  booktitle = {Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004},
  year = {2004},
  url = {https://aclanthology.org/W04-2407/}
}

References

33 references, 7 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. 1997. Lazy Learning. Dordrecht: Kluwer. find
  3. A. V. Aho, R. Sethi and J. D. Ullman. 1986. Compilers: Principles Techniques, and Tools. Addison Wesley. find
  4. P. Boullier. 2003. Guided Earley Parsing. In G. van Noord (ed.) Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), Nancy, France, pp. 43–54. find
  5. E. Charniak. 2000. A Maximum-Entropy-Inspired Parser. In Proceedings NAACL-2000. find our card
  6. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. PhD Thesis, University of Pennsylvania. find
  7. M. Collins, J. Hajic, E. Brill, L. Ramshaw and C. Tillmann. 1999. A Statistical Parser of Czech. In Proceedings of 37th ACL Conference, University of Maryland, College Park, USA, pp. 505–512. find
  8. S. Cost and S. Salzberg. 1993. A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features. Machine Learning 10, 57–78. find
  9. Dependency type SUB OBJ PRD ADV Table 5: Dependency type accuracy, MBL lexical model; labeled precision, labeled recall, unlabeled attachment score W. Daelemans. 1999. Memory-Based Language Processing. Introduction to the Special Issue. Journal of Experimental and Theoretical Artificial Intelligence… find
  10. W. Daelemans, A. van den Bosch, J. Zavrel. 2002. Forgetting Exceptions is Harmful in Language Learning. Machine Learning 34, 11–43. find
  11. 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. find
  12. S. A. Dudani. 1976. The Distance-Weighted K-nearest Neighbor Rule. IEEE Transactions on Systems, Man, and Cybernetics SMC-6, 325–327. find
  13. J. Einarsson. 1976. Talbankens skriftsprkskonkordans. Lund University. find
  14. J. M. Eisner. 1996. Three New Probabilistic Models for Dependency Parsing: An Exploration. In Proceedings of COLING-96, Copenhagen. find our card
  15. E. Fix and J. Hodges. 1952. Discriminatory Analysis: Nonparametric Discrimination: Consistency Properties. Technical Report 21-49-004-11, USAF School of Aviation Medicine, Randolph Field, Texas. find
  16. R. A. Hudson. 1990. English Word Grammar. Blackwell. find
  17. M. Kay. 2000. Guides and Oracles for Linear-Time Parsing. In Proceedings of the 6th International Workshop on Parsing Technologies (IWPT 00), Trento, Italy, pp. 6–9. find
  18. M. P. Marcus, B. Santorini and M. A. Marcinkiewics. 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics 19, 313–330. find our card
  19. I. Mel’čuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
  20. J. Nivre. 2003. An Efficient Algorithm for Projective Dependency Parsing. In G. van Noord (ed.) Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), Nancy, France, pp. 149–160. find our card
  21. J. Nivre. 2004. Inductive Dependency Parsing. Technical Report, Växjö University. find
  22. T. Obrebski. 2003. Dependency Parsing Using Dependency Graph. In G. van Noord (ed.) Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), Nancy, France, pp. 217–218. find
  23. Precision 84.3 74.7 75.1 76.2 Recall 82.7 78.8 71.4 74.6 Attachment 89.2 87.0 84.2 78.3 find
  24. J. R. Quinlan. 1993. C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann. find our card
  25. P. Sgall, E. Hajicová and J. Panevová. 1986. The Meaning of the Sentence in Its Pragmatic Aspects. Reidel. find
  26. R. Skousen. 1989. Analogical Modeling of Language. Dordrecht: Kluwer. find
  27. R. Skousen. 1992. Analogy and Structure. Dordrecht: Kluwer. find
  28. C. Stanfill and D. Waltz. 1986. Toward Memory-Based Reasoning. Communications of the ACM 29(12), 1213–1228. find
  29. SUC 1997. Stockholm Umeå Corpus. Version 1.0. Produced by Department of Linguistics, Umeå University and Department of Linguistics, Stockholm University. find
  30. U. Teleman. 1974. Manual för grammatisk beskrivning av talad och skriven svenska. Studentlitteratur. find
  31. L. Tesnière. 1959. Eléments de syntaxe structurale. find
  32. Editions Klincksieck J. Veenstra and W. Daelemans. 2000. A Memory-Based Alternative for Connectionist Shift-Reduce Parsing. Technical Report ILK-0012, University of Tilburg. find
  33. H. Yamada and Y. Matsumoto. 2003. Statistical Dependency Analysis with Support Vector Machines. In G. van Noord (ed.) Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), Nancy, France, pp. 195–206. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/nivre-2004-memory-based-dependency-parsing/