Hexatagging: Projective Dependency Parsing as Tagging

What it is about

The paper turns projective dependency parsing into tagging. Each word receives a "hexatag" from a finite set that encodes the stack actions of a binarized version of its tree, and all words are tagged in parallel with two linear projections over a pretrained encoder. Because validity depends only on the number of stack elements at each step, a dynamic program over stack depth finds the best valid tag sequence exactly in linear time. On the English Penn Treebank the model reaches 96.4 LAS and 97.4 UAS, which the authors report as state of the art for their setting; decoding is about ten times faster than a biaffine parser with the same encoder. On UD 2.2 the trees are made projective with the pseudo-projective transformation. The main limit the authors name is that the model cannot produce non-projective trees.

Ideas

• I1. Stack-depth decoder beside Eisner: implement the stack-depth dynamic program as a second exact decoder for projective trees in gparse/src/eisner.rs's neighbourhood; the gate is byte-identical trees against Eisner on EWT dev, and then decoding time.
• I2. Tag head in gparse: add a linear head that predicts per-word action classes (a hexatag-like set) trained beside the biaffine arc scorer, with the from-scratch four-layer transformer and no pretrained weights; measure EWT test LAS against the current 85.6.
• I3. Projectivity ceiling: count the non-projective gold arcs in EWT test that a projective-only decoder cannot reproduce; this is the upper bound for any tag-based path in Mova and tells whether it is worth building.

For Mova

The code is gparse (the biaffine arc scorer, gparse/src/eisner.rs) and, for the rules, en/src/parse.rs. The chapter is 20. Syntax: the Universal Dependencies frame. The paper uses a pretrained encoder, which Mova does not use; only the decoding idea and the tag scheme carry over. Measure first: the decode time and the tree agreement on EWT dev.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/2023.acl-short.124

@inproceedings{amini2023hexatagging,
  title = {{Hexatagging: Projective Dependency Parsing as Tagging}},
  author = {Amini, Afra and Liu, Tianyu and Cotterell, Ryan},
  booktitle = {Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2023},
  doi = {10.18653/v1/2023.acl-short.124},
  url = {https://doi.org/10.18653/v1/2023.acl-short.124}
}

References

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

1. Armen Aghajanyan, Anchit Gupta, Akshat Shrivastava, Xilun Chen, Luke Zettlemoyer, and Sonal Gupta. 2021. Muppet: Massive multi-task representations with pre-finetuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 5799–5811, Online and Punta Cana,… find
2. Afra Amini and Ryan Cotterell. 2022. On parsing as tagging. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 8884–8900, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics. find
3. Srinivas Bangalore and Aravind K. Joshi. 1999. Supertagging: An approach to almost parsing. Computational Linguistics, 25(2):237–265. find
4. Danqi Chen and Christopher Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 740–750, Doha, Qatar. Association for Computational Linguistics. find our card
5. Kevin Clark, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. 2020. ELECTRA: pre-training text encoders as discriminators rather than generators. In International Conference on Learning Representations. find
6. Shay B. Cohen and Daniel Gildea. 2016. Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication. Computational Linguistics, 42(3):421–455. find
7. Marie-Catherine de Marneffe and Christopher D. Manning. 2008. The Stanford typed dependencies representation. In Coling 2008: Proceedings of the workshop on Cross-Framework and Cross-Domain Parser Evaluation, pages 1–8, Manchester, UK. find our card
8. Coling 2008 Organizing Committee. find
9. 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,… find
10. Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency parsing. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. Open-Review.net. find our card
11. Timothy Dozat, Peng Qi, and Christopher D. Manning. 2017. Stanford’s graph-based neural dependency parser at the CoNLL 2017 shared task. In Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 20–30, Vancouver, Canada. Association for Computa… find our card
12. Jason Eisner. 1996. Efficient normal-form parsing for combinatory categorial grammar. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL), pages 79–86, Santa Cruz. find
13. Jason Eisner and Giorgio Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pages 457–464, College Park, Maryland, USA. Association for Computational Linguistics. find
14. Mark Johnson. 1998. Finite-state approximation of constraint-based grammars using left-corner grammar transforms. In 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume 1, pages 619–623, Montreal, Quebec, Canada.… find
15. Eliyahu Kiperwasser and Miguel Ballesteros. 2018. Scheduled multi-task learning: From syntax to translation. Transactions of the Association for Computational Linguistics, 6:225–240. find
16. 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
17. Nikita Kitaev and Dan Klein. 2020. Tetra-tagging: Word-synchronous parsing with linear-time inference. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6255– 6261, Online. Association for Computational Linguistics. find our card
18. Taku Kudo and Yuji Matsumoto. 2002. Japanese dependency analysis using cascaded chunking. In COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002). find
19. 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. Asso… find
20. Kenton Lee, Mike Lewis, and Luke Zettlemoyer. 2016. Global neural CCG parsing with optimality guarantees. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2366–2376, Austin, Texas. Association for Computational Linguistics. find
21. Zuchao Li, Jiaxun Cai, Shexia He, and Hai Zhao. 2018. Seq2seq dependency parsing. In Proceedings of the 27th International Conference on Computational Linguistics, pages 3203–3214, Santa Fe, New Mexico, USA. Association for Computational Linguistics. find
22. 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. find our card
23. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 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 Columbi… find our card
24. Ryan McDonald and Giorgio Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of the Tenth International Conference on Parsing Technologies, pages 121–132, Prague, Czech Republic. Association for Computational Linguistics. find
25. Khalil Mrini, Franck Dernoncourt, Quan Hung Tran, Trung Bui, Walter Chang, and Ndapa Nakashole. 2020. Rethinking self-attention: Towards interpretability in neural parsing. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 731–742, Online. Association for Computational… find
26. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 149–160, Nancy, France. find our card
27. Joakim Nivre, Mitchell Abrams, Željko Agić, Lars Ahrenberg, Lene Antonsen, Maria Jesus Aranzabe, Gashaw Arutie, Masayuki Asahara, Luma Ateyah, Mohammed Attia, Aitziber Atutxa, Liesbeth Augustinus, Elena Badmaeva, Miguel Ballesteros, Esha Banerjee, Sebastian Bank, Verginica Barbu Mititelu, John Baue… find
28. Joakim Nivre and Jens Nilsson. 2005. Pseudo-projective dependency parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 99–106, Ann Arbor, Michigan. Association for Computational Linguistics. find
29. Michalina Strzyz, David Vilares, and Carlos Gómez-Rodríguez. 2019. Viable dependency parsing as sequence labeling. 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), page… find
30. Robert Vacareanu, George Caique Gouveia Barbosa, Marco A. Valenzuela-Escárcega, and Mihai Surdeanu. 2020. Parsing as tagging. In Proceedings of the Twelfth Language Resources and Evaluation Conference, pages 5225–5231, Marseille, France. European Language Resources Association. find
31. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc. find
32. Xinyu Wang and Kewei Tu. 2020. Second-order neural dependency parsing with message passing and end-to-end training. In Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Proces… find
33. Naiwen Xue, Fei Xia, Fu-dong Chiou, and Marta Palmer. 2005. The penn chinese treebank: Phrase structure annotation of a large corpus. Natural Language Engineering, 11(2):207–238. find
34. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 195–206, Nancy, France. find our card
35. Songlin Yang and Kewei Tu. 2022. Headed-span-based projective dependency parsing. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2188–2200, Dublin, Ireland. Association for Computational Linguistics. find
36. Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019. Xlnet: Generalized autoregressive pretraining for language understanding. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc. find
37. Yu Zhang, Zhenghua Li, and Min Zhang. 2020. Efficient second-order TreeCRF for neural dependency parsing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3295–3305, Online. Association for Computational Linguistics. find our card
38. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 562–571, Honolulu, Hawaii. Association for Computational Linguis… find our card
39. Junru Zhou and Hai Zhao. 2019. Head-Driven Phrase Structure Grammar parsing on Penn Treebank. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2396– 2408, Florence, Italy. Association for Computational Linguistics. find
40. Ran Zmigrod, Tim Vieira, and Ryan Cotterell. 2020. Please mind the root: Decoding arborescences for dependency parsing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4809–4819, Online. Association for Computational Linguistics. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/acl-2023-amini-hexatagging-projective-dependency-parsing-as/