Elamur Research⌕
☰
home / papers / 2011 / PLCFRS Parsing of English Discontinuous Constituents

PLCFRS Parsing of English Discontinuous Constituents

Paper · 2011 · Kilian Evang and Laura Kallmeyer

Summary

The paper asks whether English parsing can treat non-local dependencies directly, without the usual practice of deleting traces before training. According to the abstract, about 20% of Penn Treebank sentences contain such constructions, including wh-movement, fronting, extraposition and right-node raising. The authors convert the PTB's trace-and-index annotation into trees with crossing branches, where discontinuous constituents are explicit. This conversion handles each null-element type (T, T-PRN, ICH, EXP, RNR) separately. From the converted treebank they extract a probabilistic LCFRS, binarize it, split categories, and parse with Kallmeyer and Maier's weighted CYK parser, originally built for German. Compared with a PCFG trained with the same techniques, the PLCFRS model scores slightly better overall. It recovers roughly 88% of T/T-PRN dependencies, and even its local attachments improve. The authors conclude that discarding non-local information hurts syntactic analysis as a whole, not only the long-distance cases. Data-driven discontinuous parsing is therefore viable for English, not just for free-word-order languages.

Key points

  • Table 1 counts 18,759 T instances and 21,738 reattachments overall. Of 49,208 trees, 32,021 needed no reattachment. After conversion, 8,996 trees have gap-degree 1 and 794 have gap-degree 2.
  • Unlabeled attachment scores on the dependency-converted test set are 82.14% for the parser trained without discontinuities (Tr) and 84.18% for the discontinuous version (Tr′). The table also lists MSTParser results around 90.2%.
  • Correct analyses by construction:
    • wh-movement: 108 of 129;
    • fronted quotations: 129 of 142;
    • surrounding arguments: 22 of 31;
    • ICH: only 2 of 30;
    • EXP: only 2 of 14.
  • Dropping ICH/EXP from the conversion (Tr′′) slightly raises EVALB scores and greatly cuts parsing time, but gives no gain in UAS (84.12%).
  • Identified weaknesses:
    • The model lacks lexical information, which hurts decisions such as PP attachment.
    • Continuous and discontinuous expansions of the same category are treated as independent, causing data sparsity.

Interesting ideas

  • I1. Rather than deleting traces, the authors turn them into explicit discontinuous structure, so the long-distance links survive training and even improve local decisions.
  • I2. The evaluation breaks results down per dependency type (T, ICH, EXP, RNR), which exposes construction types where the parser almost always fails even though the aggregate score looks fine.
  • I3. Annotating a hard phenomenon can hurt performance if the model cannot exploit it: the ICH/EXP rules triggered many false discontinuities, and removing them sped up parsing at no cost in accuracy.
  • I4. The authors propose splitting a rule into what it expands to and where the gap falls, so that continuous and gapped versions of a category share statistics.
  • I5. Fronted and interrupted quotations are recognized reliably thanks to punctuation patterns.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tree): When converting PTB-style or other treebanks to our UD dialect, map null elements and indices onto real dependency arcs instead of dropping them, so wh-moved and fronted phrases attach to their true heads.
  • I2 (learn): Report parser accuracy per non-local construction (wh-questions, fronted quotes, extraposition) on a fixed probe set, so regressions on rare but meaning-critical cases are not hidden by the overall LAS.
  • I3 (learn): Run ablations that switch off a newly annotated phenomenon in silver data, and keep it only if it measurably helps against such a control.
  • I4 (tree): The perceptron or gparse parser could score non-projective arcs with features shared with their projective counterparts, easing sparsity for rare long-distance attachments.
  • I5 (frames): Treat split quotations ("X," he said, "Y") as one speech act whose content spans both parts, linking the reporting verb to the whole quote for speaker attribution.

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

 Institutions

🎓University of GroningenGroningen · Netherlands49 works · 4,843 citations🎓Heinrich Heine University DüsseldorfDüsseldorf · Germany14 works · 1,132 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.English · 1,373 works

Cite

Cite as Kilian Evang and Laura Kallmeyer. 2011. PLCFRS Parsing of English Discontinuous Constituents. Proceedings of the 12th International Conference on Parsing Technologies.

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

@inproceedings{evang2011plcfrs,
  title = {{PLCFRS Parsing of English Discontinuous Constituents}},
  author = {Kilian Evang and Laura Kallmeyer},
  booktitle = {Proceedings of the 12th International Conference on Parsing Technologies},
  year = {2011},
  url = {https://aclanthology.org/W11-2913/}
}

References

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

  1. Ann Bies, Mark Ferguson, Karen Katz, and Robert MacIntyre. 1995. Bracketing Guidelines for Treebank II Style Penn Treebank Project. University of Pennsylvania. find
  2. Pierre Boullier. 1998. A Proposal for a Natural Language Processing Syntactic Backbone. Technical Report 3342, INRIA. find
  3. Pierre Boullier. 2000. Range Concatenation Grammars. In Proceedings of the Sixth International Workshop on Parsing Technologies (IWPT2000), pages 53–64, Trento, Italy, February. find
  4. Aoife Cahill, Michael Burke, Ruth O’Donovan, Josef Van Genabith, and Andy Way. 2004. Long-distance dependency resolution in automatically acquired wide-coverage PCFG-based LFG approximations. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 319–326, Barcelona, Spain, July. find
  5. Richard Campbell. 2004. Using linguistic principles to recover empty categories. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 645–652, Barcelona, Spain, July. find
  6. Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  7. Pétr Dienes and Amit Dubey. 2003. Deep syntactic processing by combining shallow methods. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 431–438, Sapporo, Japan, July. Association for Computational Linguistics. find
  8. Ryan Gabbard, Seth Kulick, and Mitchell Marcus. 2006. Fully parsing the Penn Treebank. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 184–191, New York City, USA, June. Association for Computational Linguistics.
  9. Carlos Gómez-Rodrı́guez, Marco Kuhlmann, Giorgio Satta, and David Weir. 2009. Optimal reduction of rule length in linear context-free rewriting systems. In Proceedings of the North American Chapter of the Association for Computational Linguistics - Human Language Technologies Conference (NAACL’09:HLT), pages 539–547, Boulder, Colorado. find
  10. Johan Hall and Joakim Nivre. 2008. Parsing discontinuous phrase structure with grammatical functions. In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL), pages 169–180. find
  11. Julia Hockenmaier. 2003. Data and models for statistical parsing with Combinatory Categorial Grammar. Ph.D. thesis, School of Informatics, University of Edinburgh. find
  12. Tom Holan, Vladislav Kubo, Karel Oliva, and Martin Pltek. 1998. Two useful measures of word order complexity. In Workshop on Processing of Dependency-Based Grammars, pages 21–29, Montreal, Canada. find
  13. Valentin Jijkoun and Maarten de Rijke. 2004. Enriching the output of a parser using memory-based learning. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 311– 318, Barcelona, Spain, July. find
  14. Mark Johnson. 2002. A simple pattern-matching algorithm for recovering empty nodes and their antecedents. In Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, pages 136–143, Philadelphia, Pennsylvania, USA, July. Association for Computational Linguistics. find
  15. Laura Kallmeyer and Wolfgang Maier. 2010. Data-driven parsing with probabilistic Linear Context-Free Rewriting Systems. In Proceedings of the 23rd International Conference on Computational Linguistics (COLING 2010), Beijing, China. find
  16. Laura Kallmeyer, Wolfgang Maier, and Giorgio Satta. 2009. Synchronous rewriting in treebanks. In Proceedings of IWPT 2009. find
  17. Laura Kallmeyer. 2010. Parsing Beyond Context-Free Grammars. Springer, Berlin. Textbook. ↗
  18. Yuki Kato, Hiroyuki Seki, and Tadao Kasami. 2006. Stochastic multiple context-free grammar for RNA pseudoknot modeling. In Proceedings of The Eighth International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+8), pages 57–64, Sydney, Australia, July. find
  19. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 423–430, Sapporo, Japan, July. Association for Computational Linguistics.
  20. Marco Kuhlmann and Giorgio Satta. 2009. Treebank grammar techniques for non-projective dependency parsing. In Proceedings of EACL. find
  21. Roger Levy and Christopher Manning. 2004. Deep dependencies from context-free statistical parsers: Correcting the surface dependency approximation. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 327– 334, Barcelona, Spain, July. find
  22. Roger Levy. 2005. Probabilistic models of word order and syntactic discontinuity. Ph.D. thesis, Stanford University. find
  23. Dekang Lin. 1995. A dependency-based method for evaluating broad-coverage parsers. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI 1995), Montreal, Quebec, Canada. find
  24. Wolfgang Maier and Laura Kallmeyer. 2010. Discontinuity and non-projectivity: Using mildly context-sensitive formalisms for data-driven parsing. In Proceedings of the Tenth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+10), New Haven. find
  25. Wolfgang Maier and Timm Lichte. 2009. Characterizing discontinuity in constituent treebanks. In Proceedings of Formal Grammar 2009, Bordeaux, France, July. To appear in Lecture Notes in Computer Science, Springer. find
  26. Wolfgang Maier and Anders Søgaard. 2008. Treebanks and mild context-sensitivity. In Philippe de Groote, editor, Proceedings of the 13th Conference on Formal Grammar (FG-2008), pages 61–76, Hamburg, Germany. CSLI Publications. find
  27. Wolfgang Maier. 2010. Direct parsing of discontinuous constituents in German. In Proceedings of the NAACL HLT 2010 First Workshop on Statistical Parsing of Morphologically-Rich Languages, pages 58–66, Los Angeles, CA, USA, June. Association for Computational Linguistics. find
  28. Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. 1994. The penn treebank: annotating predicate argument structure. In HLT ’94: Proceedings of the workshop on Human Language Technology, pages 114–119, Morristown, NJ, USA. Association for Computational Linguistics.
  29. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In 11th Conference of the European Chapter of the Association for Computational Linguistics.
  30. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523–530, Vancouver, British Columbia, Canada, October. Association for Computational Linguistics.
  31. Mark-Jan Nederhof. 2003. Weighted Deductive Parsing and Knuth’s Algorithm. Computational Linguistics, 29(1):135–143. ↗
  32. Joakim Nivre. 2006. Constraints on non-projective dependency parsing. In 11th Conference of the European Chapter of the Association for Computational Linguistics, pages 73– 80, Trento, Italy. Association for Computational Linguistics. find
  33. Joakim Nivre. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 351–359, Suntec, Singapore, August. Association for Computational Linguistics.
  34. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 404–411, Rochester, New York, April. Association for Computational Linguistics.
  35. Slav Petrov, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 433–440, Sydney, Australia, July. Association for Computational Linguistics.
  36. Oliver Plaehn. 2004. Computing the most probable parse for a discontinuous phrase-structure grammar. In New developments in parsing technology. Kluwer. ↗
  37. Hiroyuki Seki, Takahashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. On multiple context-free grammars. Theoretical Computer Science, 88(2):191–229. ↗
  38. K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proceedings of ACL, Stanford.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/evang-2011-plcfrs-parsing-english-discontinuous-constituents/