Nucleus Composition in Transition-based Dependency Parsing

What it is about

Following Tesnière, the paper takes the syntactic nucleus, a unit that can be one word or several (for example an auxiliary with its verb, or a case marker with its noun), as the elementary unit of parsing. The authors show how UD defines nuclei, and how composition functions build one vector per nucleus, which a neural transition-based parser then reads. They test this on 20 languages with ablation, mixed-effects models and diagnostic classifiers. Nucleus composition gives small but consistent gains: up to about one LAS point, significant for nine languages (English is not among them), with the gains concentrated on main predicates, nominal and clausal dependents, and coordination. The size of the gain depends on coordination entropy and on the frequency of function words, especially determiners.

Ideas

• I1. Nucleus features in en/src/parse.rs: for each stack and buffer item add the composed nucleus of its head (the head with its aux, cop, case and mark dependents) as extra feature templates; measure EWT dev LAS and per-relation F1 for conj, nsubj and root, and keep the change only if it wins on dev in two deterministic runs.
• I2. Coordination nucleus: treat a coordinator with its first conjunct as one unit in the transition features; measure F1 of conj and cc on EWT dev, and on GUM as a test only, since the paper finds its largest gains there.
• I3. Ablation under the value-ablation rule: a copy of en without the nucleus features, measured on the same dev set, reports how much of any gain the features carry; delete the copy after recording the numbers.

For Mova

The code is en/src/parse.rs (the features and the transition system) and en/src/ud.rs (the UPOS and FEATS backoff used to build the nuclei). The chapters are 22. Phrases: noun, adjective, adverb and prepositional phrases, 24. Coordination and subordination and 13. Verbs. Measure first the per-relation F1 on EWT dev for conj and nsubj, where the paper's effect is largest.

Topics: Dependency parsing

Cite

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

@article{nivre2022nucleus,
  title = {{Nucleus Composition in Transition-based Dependency Parsing}},
  author = {Nivre, Joakim and Basirat, Ali and Dürlich, Luise and Moss, Adam},
  journal = {Computational Linguistics},
  year = {2022},
  doi = {10.1162/coli\_a\_00450},
  url = {https://doi.org/10.1162/coli_a_00450}
}

References

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

1. Abney, Steven. 1991. Parsing by chunks. In Robert Berwick, Steven Abney, and Carol Tenny, editors, Principle-Based Parsing. Kluwer, pages 257–278. find
2. Ballesteros, Miguel and Joakim Nivre. 2013. Getting to the roots of dependency parsing, 39:5–13. Bārzdin , š, Guntis, Normunds Grūzı̄tis, Gunta Nešpore, and Baiba Saulı̄te. 2007. Dependency-based hybrid model of syntactic analysis for the languages with a rather free word order. In Proceedings of… find
3. Basirat, Ali 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. find
4. Bates, Douglas, Martin Mächler, Ben Bolker, and Steve Walker. 2015. Fitting linear mixed-effects models using lme4. Journal of Statistical Software, 67(1):1–48. find
5. Wolof Belinkov, Yonatan. 2018. On Internal Language Representations in Deep Learning: An Analysis of Machine Translation and Speech Recognition. Ph.D. thesis, Massachusetts Institute of Technology. find
6. Bharati, Akshar, Samar Husain, Dipti Misra, and Rajeev Sangal. 2009. Two stage constraint based hybrid approach to free word order language dependency parsing. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT), pages 77–80. https://doi.org/10.3115 /1697236.1697251 Bh… find
7. Buchholz, Sabine, Jorn Veenstra, and Walter Daelemans. 1999. Cascaded grammatical relation assignment. In Proceedings of the Joint SIGDAT Conference on Empirical Methods in NLP and Very Large Corpora, pages 239–246. find
8. Dyer, Chris, 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 (ACL), pages 334–343. https://doi.org/10.3115/v1/P15… ↗ our card
9. Falenska, Agnieszka and Jonas Kuhn. 2019. The (non-)utility of structural features in BiLSTM-based dependency parsers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), pages 117–128. https://doi.org /10.18653/v1/P19-1012 Finlayson, Matthew, Aaron Muel… ↗
10. Han, Ji Yoon, Tae Hwan Oh, Lee Jin, and Hansaem Kim. 2020. Annotation issues in Universal Dependencies for Korean and Japanese. In Proceedings of the Fourth Workshop on Universal Dependencies (UDW 2020), pages 99–108. find
11. Hewitt, John and Percy Liang. 2019. Designing and interpreting probes with control tasks. arXiv preprint arXiv:1909.03368. find
12. Hupkes, Dieuwke, Sara Veldhoen, and Willem Zuidema. 2018. Visualisation and ‘diagnostic classifiers’ reveal how recurrent and recursive neural networks process hierarchical structure. Journal of Artificial Intelligence Research, 61:907–926. https://doi.org/10.1613/jair.1 .11196 Järvinen, Timo and Pa… — [doi:10.1613/jair.1](https://doi.org/10.1613/jair.1) ↗
13. Johnson, Paul and Holger Schielzeth. 2017. The coefficient of determination r2 and intra-class correlation coefficient from generalized linear mixed-effects models revisited and expanded. Journal of the Royal Society Interface, 14:20170213. find
14. Kahane, Sylvain. 1997. Bubble trees and syntactic representations. In Proceedings of the 5th Meeting of Mathematics of Language, pages 70–76. find
15. Kiperwasser, Eliyahu and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of the Association for Computational Linguistics, 4:313–327. https://doi.org/10 .1162/tacl\_a\_00101 find our card
16. Kudo, Taku and Yuji Matsumoto. 2002. Japanese dependency analysis using cascaded chunking. In Proceedings of the 6th Workshop on Computational Language Learning (CoNLL), pages 63–69. https:// doi.org/10.3115/1118853.1118869 Kuhlmann, Marco, Carlos Gómez-Rodríguez, and Giorgio Satta. 2011. Dynamic pr… find
17. Van der Maaten, Laurens and Geoffrey Hinton. 2008. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(11):2579–2605. de Marneffe, Marie, Christopher D. Manning, Joakim Nivre, and Daniel Zeman. 2021. Universal dependencies. Computational Linguistics, 47:255–308. https://doi.org/10.… find our card
18. Mohammadshahi, Alireza 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. find our card
19. Nespore, Gunta, Baiba Saulite, Guntis Barzdins, and Normunds Gruzitis. 2010. Comparison of the SemTi-Kamols and Tesnière’s dependency grammars. In Proceedings of the 4th International Conference on Human Language Technologies—the Baltic Perspective, pages 233–240. find
20. Nivre, Joakim. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 149–160. find our card
21. Nivre, Joakim. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL), pages 50–57. find our card
22. Nivre, Joakim. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553. https://doi.org /10.1162/coli.07-056-R1-07-027 Nivre, Joakim. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th A… ↗ our card
23. Nivre, Joakim, Johan Hall, and Jens Nilsson. 2006. Maltparser: A data-driven parser-generator for dependency parsing. In Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC), pages 2216–2219. Nivre, Joakim, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldbe… find
24. Samuelsson, Christer. 2000. A statistical theory of dependency syntax. In Proceedings of the 18th International Conference on Computational Linguistics (COLING), pages 684–690. https:// doi.org/10.3115/992730.992745 Sangati, Federico and Chiara Mazza. 2009. An English dependency treebank à la Tesniè… find
25. Reidel. Shi, Tianze, 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 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 12–23. https://doi .org/10.18653… find
26. Stenetorp, Pontus. 2013. Transition-based dependency parsing using recursive neural networks. In NIPS Workshop on Deep Learning. find
27. Tesnière, Lucien. 1959. Éléments de syntaxe structurale. find
28. Editions Klincksieck. Yamada, Hiroyasu and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 195–206. Zeman, Daniel, Joakim Nivre, Mitchell Abrams, Elia Ackermann, Noëmi Aepli, Ha… find our card
29. Zhang, Yue and Joakim Nivre. 2011. Transition-based parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL), pages 188–193. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2022-nivre-nucleus-composition-transition-based-dependency/