Elamur Research⌕
☰
home / papers / 1997 / A non-projective dependency parser

A non-projective dependency parser

Summary

Tapanainen and Järvinen present a rule-based English parser that produces labelled dependency links between words and does not require trees to be projective. The motivation was a limitation of the English Constraint Grammar (ENGCG). Its syntactic tags mark a word's function, such as subject or object, but not which word it attaches to, and much ambiguity was left unresolved. This made it unreliable for tasks like extracting verb arguments. The authors keep the ENGCG lexical analyser and morphological disambiguator and add a new rule formalism with roughly 2 500 rules. In it, rules explicitly connect dependents to heads through named valency slots, and partial links can serve as context for further rules. The result is an ambiguous dependency forest, which a language-independent global pruning step reduces to consistent trees. Compared with ENGCG, ambiguity falls to about a quarter with no loss of correctness. For subjects, precision is high, but some words remain unattached. The work shows that non-projective structures can be handled efficiently, which matters especially for free word-order languages.

Key points

  • The parser builds on the ENGCG pipeline and the CG-2 rule notation. It took over three person-years of work, not counting the reused lexical and morphological components.
  • Classic CG operations REMOVE and SELECT are extended with INDEX. INDEX proposes a possible dependency while keeping a word's other readings alive. Named slots, such as = subject, ensure a verb gets at most one filler of each kind.
  • The output follows Tesnière/Mel'čuk-style dependency syntax, in which every word has one head. The formalism has no built-in projectivity constraint, but grammar writers can forbid crossing links where needed.
  • The authors evaluated head-finding precision and recall, plus named dependencies for subject, object and predicative:
    • Subject precision was about 95–98%.
    • Roughly 10–15% of subjects were left without a link.
    • For context, they cite Lin (1996): 87%/78% precision/recall for subjects. They also cite Eisner (1996): 79.2% head accuracy. They note these figures are not strictly comparable.
  • Versus ENGCG, the authors report output that is richer, more explicit and more accurate, with ambiguity cut to about one quarter.

Interesting ideas

  • I1. Propose links cautiously instead of deleting readings. Rules suggest candidate dependencies and leave the choice to a later global step. This avoids early irreversible errors and could suit any pipeline where local evidence is weak.
  • I2. Global pruning driven by structure. The pruning step prefers large subtrees and trusts unambiguous subtrees more. It also discards a word's unlinked readings whenever a linked alternative exists. These heuristics need no language-specific statistics, so the approach could transfer to low-resource languages, including morphologically rich ones like Ukrainian.
  • I3. Iterate rules and pruning. Rules and pruning alternate, so each round of reduced ambiguity lets more rules fire. This "fixpoint" design suits other constraint-based or hybrid systems.
  • I4. Separate valency from subcategorisation. Valency slots state what arguments are possible, while lexical subcategorisation tags state which combinations are allowed. This split keeps grammar rules general and pushes specifics into the lexicon.
  • I5. Report precision and recall separately when attachment is optional. The parser may leave words unattached, so the authors report both measures rather than a single accuracy figure. This exposes the trade-off between abstaining and guessing, which is useful when high-precision extraction matters more than full coverage.

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: Natural language processing

Topics: Dependency parsing

Cited by

93 papers of our library cite it (of the 140884 whose bibliographies we read); 5 of them have a page here, 88 not yet.

Cite

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

@inproceedings{tapanainen1997non,
  title = {{A non-projective dependency parser}},
  author = {Tapanainen, Pasi and Jarvinen, Timo},
  booktitle = {Fifth Conference on Applied Natural Language Processing},
  year = {1997},
  doi = {10.3115/974557.974568},
  url = {https://doi.org/10.3115/974557.974568}
}

References

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

  1. Arto Anttila. 1995. How to recognise subjects in English. In Karlsson et al., chapt. 9, pp. 315-358. find
  2. Dekang Lin. 1996. Evaluation of Principar with the Susanne corpus. In John Carroll, editor, Workshop on Robust Parsing, pages 54-69, Prague. find
  3. Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In The 16th International Conference on Computational Linguistics, pages 340-345. Copenhagen. find our card
  4. David G. Hays. 1964. Dependency theory: A formalism and some observations. Language, 40(4):511-525. find
  5. Hans Jiirgen Heringer. 1993. Dependency syntax - basic ideas and the classical model. In Joachim Jacobs, Arnim von Stechow, Wolfgang Sternefeld, and Thee Venneman, editors, Syntax - An International Handbook of Contemporary Research, volume 1, chapter 12, pages 298-316. Walter de Gruyter, Berlin - N… find
  6. Richard Hudson. 1991. English Word Grammar. Basil Blackwell, Cambridge, MA. find
  7. Arvi Hurskainen. 1996. Disambiguation of morphological analysis in Bantu languages. In The 16th International Conference on Computational Linguistics, pages 568-573. Copenhagen. find
  8. Time J~rvinen. 1 9 9 4 . Annotating 200 million words: the Bank of English project. In The 15th International Conference on Computational Linguistics Proceedings, pages 565-568. Kyoto. Fred Karlsson, Atro Voutilainen, Juha Heikkil~, and Arto Anttila, editors. 1995. Constraint Grammar: a language-ind… find
  9. Fred Karlsson. 1990. Constraint grammar as a framework for parsing running text. In Hans Karlgren, editor, Papers presented to the 13th International Conference on Computational Linguistics, volume 3, pages 168-173, Helsinki, Finland. find
  10. Michael McCord. 1990. Slot grammar: A system for simpler construction of practical natural language grammars. In lq, Studer, editor, Natural Language and Logic: International Scientific Symposium, Lecture Notes in Computer Science, pages 118-145. Springer, Berlin. find
  11. Igor A. Mel'~uk. 1987. Dependency Syntax: Theory and Practice. State University of New York Press, Albany. find
  12. Christer Samuelsson, Pasi Tapanainen, and Atro Voutilainen. 1996. Inducing constraint grammars. In Laurent Miclet and Colin de la Higuera, editors, Grammatical Inference: Learning Syntax from Sentences, volume 1147 of Lecture Notes in Artificial Intelligence, pages 146-155, Springer. find
  13. Daniel Sleator and Davy Temperley. 1991. Parsing English with a link grammar. Technical Report CMU-CS-91-196, Carnegie Mellon University. find our card
  14. Pasi Tapanainen and Time J/irvinen. 1994. Syntactic analysis of natural language using linguistic rules and corpus-based patterns. In The 15th International Conference on Computational Linguistics Proceedings, pages 629-634. Kyoto. find
  15. Pasi Tapanainen. 1996. The Constraint Grammar Parser CG-2. Number 27 in Publications of the Department of General Linguistics, University of Helsinki. find
  16. Lucien TesniSre. 1959. l~ldments de syntaxe stvuc-turale, l~ditions Klincksieck, Paris. find
  17. Atro Voutilainen. 1995. Morphological disambiguation. In Karlsson et al., chapter 6, pages 165-284. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/tapanainen-1997-non-projective-dependency-parser/