Mova0.5 pre-release⌕
☰
home / docs / papers / English / Transition-based Bubble Parsing: Improvements on Coordination Structure Prediction

Transition-based Bubble Parsing: Improvements on Coordination Structure Prediction

What it is about

Standard dependency trees give coordination an awkward shape: one conjunct must be the head, and a shared modifier ("hot" in "hot coffee or tea and a bun") cannot be told apart from a private one. The authors use Kahane's bubble trees, in which a bubble groups the conjuncts and its coordinator, and the bubble takes part in ordinary dependency arcs. They give a transition system (Bubble-Hybrid) that extends Arc-Hybrid with three actions, open, attach and close a bubble, and prove it sound and complete for projective bubble trees. A neural scorer (bi-LSTM, or BERT features) picks the actions. On the Penn Treebank with coordination annotation and on GENIA, the parser beats earlier systems on coordination identification. With BERT, it reaches 95.81 UAS and 94.46 LAS on PTB after conversion back to UD. On GENIA, exact recall is 79.18 against 67.09 for the bi-LSTM version. The gain is largest on complex coordinations.

Ideas

For Mova

The chapter is 24. Coordination and subordination, with 22. Phrases: noun, adjective, adverb and prepositional phrases for the phrase and its shared modifier, and 25. Relative clauses for coordinated relatives. Code: en/src/parse.rs (bubble transitions, second-pass rescoring), en/src/lin.rs (linearization of bubble structures), prag (replaceability). Measure: exact match on coordination structures for simple and complex sentences, UAS on UD EWT dev, run twice for determinism. The training data are not ours to ship; test on our own UD sets.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/2021.acl-long.557

@inproceedings{shi2021transition,
  title = {{Transition-based Bubble Parsing: Improvements on Coordination Structure Prediction}},
  author = {Shi, Tianze and Lee, Lillian},
  booktitle = {Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)},
  year = {2021},
  doi = {10.18653/v1/2021.acl-long.557},
  url = {https://doi.org/10.18653/v1/2021.acl-long.557}
}

References

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

  1. Rajeev Agarwal and Lois Boggess. 1992. A simple but useful approach to conjunct identification. In Proceedings of the 30th Annual Meeting of the Association for Computational Linguistics, pages 15–21, Newark, Delaware, USA. Association for Computational Linguistics. find
  2. Ali Basirat and Joakim Nivre. 2021. Syntactic nuclei in dependency parsing – A multilingual exploration. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 1376–1387, Online. Association for Computational Linguistics. find
  3. Gosse Bouma, Djamé Seddah, and Daniel Zeman. 2020. Overview of the IWPT 2020 shared task on parsing into enhanced Universal Dependencies. In Proceedings of the 16th International Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies, pages 151–161, Online. Association for Computational Linguistics. find our card
  4. Michael Collins. 2003. Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4):589–637. find our card
  5. Miryam de Lhoneux, Miguel Ballesteros, and Joakim Nivre. 2019. Recursive subtree composition in LSTM-based dependency parsing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 1566–1576, Minneapolis, Minnesota, USA. Association for Computational Linguistics. find
  6. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota, USA. Association for Computational Linguistics. find
  7. Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency parsing. In Proceedings of the 5th International Conference on Learning Representations, Toulon, France. OpenReview.net. find our card
  8. Amit Dubey, Patrick Sturt, and Frank Keller. 2005. Parallelism in coordination as an instance of syntactic priming: Evidence from corpus-based modeling. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 827–834, Vancouver, British Columbia, Canada. Association for Computational Linguistics. find
  9. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015. Transition-based dependency parsing with stack long short-term memory. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 334–343, Beijing, China. Association for Computational Linguistics. find our card
  10. Jessica Ficler and Yoav Goldberg. 2016a. Coordination annotation extension in the Penn tree bank. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 834–842, Berlin, Germany. Association for Computational Linguistics. find
  11. Jessica Ficler and Yoav Goldberg. 2016b. A neural network for coordination boundary prediction. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 23–32, Austin, Texas, USA. Association for Computational Linguistics. find
  12. Jessica Ficler and Yoav Goldberg. 2017. Improving a strong neural parser with conjunction-specific features. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, pages 343–348, Valencia, Spain. Association for Computational Linguistics. find our card
  13. Lyn Frazier, Alan Munn, and Charles Clifton. 2000. Processing coordinate structures. Journal of Psycholinguistic Research, 29(4):343–370. find
  14. Lyn Frazier, Lori Taft, Tom Roeper, Charles Clifton, and Kate Ehrlich. 1984. Parallel structure: A source of facilitation in sentence comprehension. Memory & Cognition, 12(5):421–430. find
  15. Kim Gerdes and Sylvain Kahane. 2015. Non-constituent coordination and other coordinative constructions as dependency graphs. In Proceedings of the Third International Conference on Dependency Linguistics (Depling 2015), pages 101–110, Uppsala, Sweden. Uppsala University. find
  16. Aleksej V. Gladkij. 1968. "On describing the syntactic structure of a sentence" (in Russian with English summary). Computational Linguistics, 7:21–44. find
  17. Yoav Goldberg and Michael Elhadad. 2010. Inspecting the structural biases of dependency parsing algorithms. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 234–242, Uppsala, Sweden. Association for Computational Linguistics. find
  18. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the Association for Computational Linguistics, 1:403–414. find
  19. Alex Graves and Jürgen Schmidhuber. 2005. Frame-wise phoneme classification with bidirectional LSTM and other neural network architectures. Neural Networks, 18(5):602–610. find
  20. Stefan Grünewald, Prisca Piccirilli, and Annemarie Friedrich. 2021. Coordinate constructions in English enhanced Universal Dependencies: Analysis and computational modeling. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 795–809, Online. Association for Computational Linguistics. find our card
  21. Jan Hajič, Eduard Bejček, Jaroslava Hlavacova, Marie Mikulová, Milan Straka, Jan Štěpánek, and Barbora Štěpánková. 2020. Prague dependency treebank -consolidated 1.0. In Proceedings of the 12th Language Resources and Evaluation Conference, pages 5208–5218, Marseille, France. European Language Resources Association. find
  22. Jan Hajič, Barbora Vidová Hladká, Jarmila Panevová, Eva Hajičová, Petr Sgall, and Petr Pajas. 2001. Prague dependency treebank 1.0 (LDC2001T10). find
  23. Chung-hye Han and Anoop Sarkar. 2017. Coordination in TAG without the Conjoin Operation. In Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms, pages 43–52, Umeå, Sweden. Association for Computational Linguistics. find
  24. Atsushi Hanamoto, Takuya Matsuzaki, and Jun’ichi Tsujii. 2012. Coordination structure analysis using dual decomposition. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 430–438, Avignon, France. Association for Computational Linguistics. find
  25. Kazuo Hara, Masashi Shimbo, Hideharu Okuma, and Yuji Matsumoto. 2009. Coordinate structure analysis with global structural constraints and alignment-based local features. 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 967– 975, Suntec, Singapore. Association for Computational Linguistics. find
  26. Deirdre Hogan. 2007. Coordinate noun phrase disambiguation in a generative parsing model. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 680–687, Prague, Czech Republic. Association for Computational Linguistics. find
  27. Richard A. Hudson. 1984. Word Grammar. Blackwell, Oxford. find
  28. Timo Järvinen and Pasi Tapanainen. 1998. Towards an implementable dependency grammar. In Processing of Dependency-Based Grammars, pages 1–10, Montreal, Quebec, Canada. Association for Computational Linguistics. find
  29. Richard Johansson and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for English. In Proceedings of the 16th Nordic Conference of Computational Linguistics (NODALIDA 2007), pages 105–112, Tartu, Estonia. University of Tartu, Estonia. find our card
  30. Sylvain Kahane. 1997. Bubble trees and syntactic representations. In Proceedings of the 5th Meeting of Mathematics of Language, pages 70–76, Saarbrücken, Germany. find
  31. Ronald M. Kaplan and John T. Maxwell III. 1988. Constituent coordination in lexical-functional grammar. In Proceedings of International Conference on Computational Linguistics, pages 303–305, Budapest, Hungary. find
  32. Jin Dong Kim, Tomoko Ohta, Yuka Tateisi, and Jun’ichi Tsujii. 2003. GENIA corpus—a semantically annotated corpus for bio-textmining. Bioinformatics, 19(suppl_1):i180–i182. find
  33. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of the Association for Computational Linguistics, 4:313–327. find our card
  34. Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency parsing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool Publishers. find
  35. Marco Kuhlmann, Carlos Gómez-Rodríguez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 673–682, Portland, Oregon, USA. Association for Computational Linguistics. find
  36. Sadao Kurohashi and Makoto Nagao. 1994. A syntactic analysis method of long Japanese sentences based on the detection of conjunctive structures. Computational Linguistics, 20(4):507–534. find
  37. Vincenzo Lombardo and Leonardo Lesmo. 1998. Unit coordination and gapping in dependency theory. In Processing of Dependency-Based Grammars, pages 11–20, Montreal, Quebec, Canada. Association for Computational Linguistics. find
  38. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn treebank. Computational Linguistics, 19(2):313–330. ↗ our card
  39. Igor Mel’čuk. 1988. Dependency Syntax: Theory and Practice. State University Press of New York, Albany. find
  40. Igor Mel’čuk. 2003. Levels of dependency in linguistic description: Concepts and problems. In Vilmos Ágel, Ludwig M. Eichinger, Hans Werner Eroms, Peter Hellwig, Hans Jürgen Heringer, and Henning Lobin, editors, Dependency and Valency: An International Handbook of Contemporary Research, volume 1, pages 188–229. Walter de Gruyter, Berlin. find
  41. David Milward. 1994. Non-constituent coordination: Theory and practice. In Proceedings of the 15th International Conference on Computational Linguistics, volume 2, pages 935–941, Kyoto, Japan. find
  42. Alireza Mohammadshahi and James Henderson. 2020. Graph-to-graph Transformer for transition-based dependency parsing. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3278–3289, Online. Association for Computational Linguistics. find our card
  43. Jens Nilsson, Joakim Nivre, and Johan Hall. 2006. Graph transformations in data-driven dependency parsing. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 257–264, Sydney, Australia. Association for Computational Linguistics. find
  44. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. find our card
  45. Owen Rambow. 2010. The simple truth about dependency and phrase structure representations: An opinion piece. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 337–340, Los Angeles, California, USA. Association for Computational Linguistics. find
  46. Ines Rehbein, Julius Steen, Bich-Ngoc Do, and Anette Frank. 2017. Universal Dependencies are hard to parse — or are they? In Proceedings of the Fourth International Conference on Dependency Linguistics (Depling 2017), pages 218–228, Pisa, Italy. Linköping University Electronic Press. find
  47. Swarnadeep Saha and Mausam. 2018. Open information extraction from conjunctive sentences. In Proceedings of the 27th International Conference on Computational Linguistics, pages 2288–2299, Santa Fe, New Mexico, USA. Association for Computational Linguistics. find
  48. Swarnadeep Saha, Harinder Pal, and Mausam. 2017. Bootstrapping for numerical Open IE. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 317–323, Vancouver, Canada. Association for Computational Linguistics. find
  49. Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajič, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016. Universal Dependencies v1: A multilingual treebank collection. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16), pages 1659–1666, Portorož, Slovenia. European Language Resources Association. find our card
  50. Federico Sangati. 2010. A probabilistic generative model for an intermediate constituency-dependency representation. In Proceedings of the ACL 2010 Student Research Workshop, pages 19–24, Uppsala, Sweden. Association for Computational Linguistics. find
  51. Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Jan Hajič, Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman. 2020. Universal Dependencies v2: An evergrowing multilingual treebank collection. In Proceedings of the 12th Language Resources and Evaluation Conference, pages 4034–4043, Marseille, France. European Language Resources Association. find our card
  52. Anoop Sarkar and Aravind Joshi. 1996. Coordination in tree adjoining grammars: Formalization and implementation. In Proceedings of the 16th International Conference on Computational Linguistics, pages 610–615, Copenhagen, Denmark. find
  53. Joakim Nivre, Paola Marongiu, Filip Ginter, Jenna Kanerva, Simonetta Montemagni, Sebastian Schuster, and Maria Simi. 2018. Enhancing Universal Dependency treebanks: A case study. In Proceedings of the Second Workshop on Universal Dependencies (UDW 2018), pages 102–107, Brussels, Belgium. Association for Computational Linguistics. find our card
  54. Martin Popel, David Mareček, Jan Štěpánek, Daniel Zeman, and Zděněk Žabokrtský. 2013. Coordination structures in dependency treebanks. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 517–527, Sofia, Bulgaria. Association for Computational Linguistics. find our card
  55. Federico Sangati and Chiara Mazza. 2009. An English dependency treebank à la Tesnière. In Proceedings of the 8th International Workshop on Treebanks and Linguistic Theories, pages 173–184, Milan, Italy. find
  56. Yuya Sawada, Takashi Wada, Takayoshi Shibahara, Hiroki Teranishi, Shuhei Kondo, Hiroyuki Shindo, Taro Watanabe, and Yuji Matsumoto. 2020. Coordination boundary identification without labeled data for compound terms disambiguation. In Proceedings of the 28th International Conference on Computational Linguistics, pages 3043–3049, Barcelona, Spain (Online). International Committee on Computational Linguistics. find
  57. Sebastian Schuster, Matthew Lamm, and Christopher D. Manning. 2017. Gapping constructions in Universal Dependencies v2. In Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017), pages 123–132, Gothenburg, Sweden. Association for Computational Linguistics. find our card
  58. Sebastian Schuster and Christopher D. Manning. 2016. Enhanced English Universal Dependencies: An improved representation for natural language understanding tasks. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), pages 2371–2378, Portorož, Slovenia. European Language Resources Association. find our card
  59. Tianze Shi, Liang Huang, and Lillian Lee. 2017. Fast(er) exact decoding and global training for transition-based dependency parsing via a minimal feature set. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 12–23, Copenhagen, Denmark. Association for Computational Linguistics. find
  60. Masashi Shimbo and Kazuo Hara. 2007. A discriminative learning model for coordinate conjunctions. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 610–619, Prague, Czech Republic. Association for Computational Linguistics. find
  61. Mark Steedman. 1996. Surface Structure and Interpretation. Number 30 in Linguistic Inquiry Monograph. The MIT Press, Cambridge, Massachusetts. find
  62. Mark Steedman. 2000. The Syntactic Process. MIT Press, Cambridge, MA, USA. find
  63. Hiroki Teranishi, Hiroyuki Shindo, and Yuji Matsumoto. 2017. Coordination boundary identification with similarity and replaceability. In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 264–272, Taipei, Taiwan. Asian Federation of Natural Language Processing. find
  64. Hiroki Teranishi, Hiroyuki Shindo, and Yuji Matsumoto. 2019. Decomposed local models for coordinate structure parsing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 3394–3403, Minneapolis, Minnesota, USA. Association for Computational Linguistics. find
  65. Lucien Tesnière. 1959. Eléments de Syntaxe Structurale. Librairie C. Klincksieck, Paris. find
  66. Niina Ning Zhang. 2009. Coordination in Syntax. Cambridge Studies in Linguistics. Cambridge University Press, New York. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/shi-2021-transition-based-bubble-parsing-improvements/