An Efficient Algorithm for Projective Dependency Parsing

What it is about

Nivre defines a deterministic shift-reduce parser for projective dependency grammar. It runs in time linear in the sentence length and always returns a graph that is projective and acyclic. Its transitions are Left-Arc, Right-Arc, Reduce and Shift, and a scheduling policy decides between them. In a pilot on about 4,000 words (257 sentences) of hand-annotated Swedish, parsed with a hand-written grammar of 126 rules, the mean attachment score is 80.0 with a fixed priority order, 87.8 with a rule that shifts when the stack top can still head the next token, and 89.0 with a further lookahead for shift/right-arc conflicts. The author gives a 95% interval of 85–93% and calls the evidence small.

Ideas

• I1. en/src/parse.rs: in the static oracle, add the shift-or-reduce rule of the paper (shift when the stack top can still take the next word as a dependent, from the UD grammar of the en tables); measure cv LAS on the train folds, EWT test once per release.
• I2. en/src/parse.rs: the lookahead for shift against right-arc: when the stack top is a verb and the next word could be its post-modifier or the pre-modifier of the word after it, prefer shift; measure the share of such conflicts in EWT train and the cv LAS with and without the rule.
• I3. en beam-curve: measure parse time per sentence for greedy arc-standard against beam 8 on EWT test, to see how much time the beam costs against the LAS it buys, using the linear-time claim as the baseline.

For Mova

The shift/reduce conflict rules are the part that transfers to en/src/parse.rs, which is arc-standard with a static oracle. The relevant chapters are 20-syntax-overview and 21-clause-structure, where the verb-modifier ambiguity is discussed. Measure first: how often the conflict in idea I2 occurs in EWT train, since the paper's pilot is too small to show a gain on its own.

Topics: Dependency parsing

Cite

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

@inproceedings{nivre2003efficient,
  title = {{An Efficient Algorithm for Projective Dependency Parsing}},
  author = {Nivre, Joakim},
  booktitle = {Proceedings of the Eighth International Workshop on Parsing Technologies},
  year = {2003},
  url = {https://aclanthology.org/W03-3017/}
}

References

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

1. Alfred V. Aho, Ravi Sethi, and Jerey D. Ullman. Compilers: Principles Techniques, and Tools . Addison Wesley, 1986. find
2. Cristina Barbero, Leonardo Lesmo, Vincenzo Lombardo, and Paola Merlo. Integration of syntactic and lexical information in a hierarchical dependency grammar. In Sylvain Kahane and Alain Polguère, editors, Proceedings of the Workshop on Processing of Dependency-Based Grammars , pages 5867, Université… find
3. Glenn Carroll and Eugene Charniak. Two experiments on learning probabilistic dependency grammars from corpora. Technical Report TR-92, Department of Computer Science, Brown University, 1992. find
4. Michael Collins. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Annatual Meeting of the Association for Computational Linguistics , pages 184191, Santa Cruz, CA, 1996. find
5. Michael Collins. 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, 1997. find
6. Michael Collins. Head-Driven Statistical Models for Natural Language Parsing . PhD thesis, University of Pennsylvania, 1999. find
7. Michael Collins, Jan Haji£, Eric Brill, Lance Ramshaw, and Christoph Tillmann. A Statistical Parser of Czech. In Proceedings of 37th ACL Conference , pages 505512, University of Maryland, College Park, USA, 1999. find
8. Jacques Courtin and Damien Genthial. parsing. In Sylvain Kahane and Alain Polguère, editors, Proceedings of the Workshop on Processing of Dependency-Based Grammars , pages 95101, Université de Montréal, Quebec, Canada, August 1998. find
9. Michael A. Covington. A dependency parser for variable-word-order languages. Technical Report AI-1990-01, University of Georgia, Athens, GA, 1990. find
10. Michael A. Covington. Discontinuous dependency parsing of free and xed word order: Work in progress. Technical Report AI-1994-02, University of Georgia, Athens, GA, 1994. find
11. Ralph Debusmann. A declarative grammar formalism for dependency grammar. Master's thesis, Computational Linguistics, Universität des Saarlandes, November 2001. find
12. Denys Duchier. Axiomatizing dependency parsing using set constraints. In Sixth Meeting on Mathematics of Language , pages 115126, Orlando, Florida, July 1999. find
13. Denys Duchier. Lexicalized syntax and topology for non-projective dependency grammar. In Joint Conference on Formal Grammars and Mathematics of Language FGMOL'01 , Helsinki, August 2001. find
14. Denys Duchier. Conguration of labeled trees under lexicalized constraints and principles. Journal of Language and Computation , 1, 2002. find
15. Jason M. Eisner. An empirical comparison of probability models for dependency grammar. Technical Report IRCS-96-11, Institute for Research in Cognitive Science, University of Pennsylvania, 1996. find
16. Jason M. Eisner. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING-96 , Copenhagen, 1996. find our card
17. Jason M. Eisner. Bilexical grammars and their cubic-time parsing algorithms. In Harry Bunt and Anton Nijholt, editors, Advances in Probabilistic and Other Parsing Technologies . Kluwer, 2000. find
18. Haim Gaifman. Dependency systems and phrase-structure systems. Information and Control , 8:304337, 1965. find
19. David G. Hays. Dependency theory: 40:511525, 1964. find
20. Richard A. Hudson. English Word Grammar . Blackwell, 1990. find
21. Mitchell P. Marcus. A Theory of Syntactic Recognition for Natural Language . MIT Press, 1980. find
22. Hiroshi Maruyama. Structural disambiguation with constraint propagation. In Proceedings of the 28th ACL , pages 3138, Pittsburgh, PA, 1990. find
23. Igor Mel'cuk. Dependency Syntax: Theory and Practice . Press, 1988. Parsing with dependency relations and robust A formalism and some observations. Language , State University of New York find
24. Wolfgang Menzel and Ingo Schröder. ing graded constraints. In Sylvain Kahane and Alain Polguère, editors, Proceedings of the Workshop on Processing of Dependency-Based Grammars , pages 7887, Université de Montréal, Quebec, Canada, August 1998. find
25. Christer Samuelsson. A statistical theory of dependency syntax. In Proceedings COLING-2000 . Morgan Kaufmann, 2000. find
26. Petr Sgall, Eva Hajicova, and Jarmila Panevova. Pragmatic Aspects . Reidel, 1986. find
27. Daniel Sleator and Davy Temperley. Report CMU-CS-91-196, Carnegie Mellon University, Computer Science, 1991. find
28. Daniel Sleator and Davy Temperley. International Workshop on Parsing Technologies , 1993. find
29. Stockholm Umeå Corpus. Version 1.0. University and Department of Linguistics, Stockholm University. ISBN 91-7191-348-3., August 1997. find
30. Lucien Tesnière. Éléments de syntaxe structurale . Editions Klincksieck, 1959. Decision procedures for dependency parsing us-The Meaning of the Sentence in Its Parsing English with a link grammar. Technical Parsing English with a link grammar. In Third Produced by Department of Linguistics, Umeå find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/