Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference

What it is about

The paper parses constituency trees by labeling each word with one of four "tetra-tags" that encode two binary structural decisions and two labels. All words are tagged in parallel by a simple classification layer over BERT, and a left-to-right reconciliation step rebuilds the tree in, empirically, linear time. Validity of a tag sequence depends only on the stack depth, so the best valid sequence is found by a dynamic program over action count and stack depth. The model reaches 95.4 F1 on the WSJ test set, close to the best fine-tuned BERT models, and is much faster than them. The paper also shows that a modest maximum stack size covers almost all development trees, and that the parser's score tracks that coverage.

Ideas

• I1. Stack-bounded en beam: give the arc-standard beam in en/src/parse.rs (beam 8) a stack-depth limit, taken from the coverage curve, and measure EWT test LAS and parse time; the paper's point is that a bounded stack costs little when the bound is chosen from data.
• I2. Coverage curve for the mova trees: for each bank, report the share of gold trees that a stack-bounded transition system can represent at depth d; use it to choose the depth before any tag-based decoder is built, and report it on EWT dev and GUM (test only).
• I3. Legal-sequence decoding for gparse tags: where any tag head is added (see the hexatagging card), use the same depth dynamic program to pick the best legal sequence, and count how often greedy output is illegal on EWT dev.

For Mova

The code is en/src/parse.rs (the transition system and its beam), gparse/src/eisner.rs (the decoder) and tools/treeagree (projectivity gate). The chapter is 20. Syntax: the Universal Dependencies frame. Measure first: the coverage curve on EWT dev, which costs one run and says whether a stack bound is safe.

Cite

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

@inproceedings{kitaev2020tetra,
  title = {{Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference}},
  author = {Kitaev, Nikita and Klein, Dan},
  booktitle = {Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.557},
  url = {https://doi.org/10.18653/v1/2020.acl-main.557}
}

References

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

1. Steven P. Abney and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20(3):233–250. find
2. Srinivas Bangalore and Aravind K. Joshi. 1999. Supertagging: An approach to almost parsing. Computational Linguistics, 25(2):237–265. find
3. John Cocke. 1970. Programming languages and their compilers: Preliminary notes. find
4. 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
5. Greg Durrett and Dan Klein. 2015. Neural CRF parsing. 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 302–312, Beijing, China. Association for Computati… find
6. Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. 2016. Recurrent neural network grammars. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 199–209, San Diego, California. Assoc… find
7. Carlos Gómez-Rodrı́guez and David Vilares. 2018. Constituent parsing as sequence labeling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1314– 1324, Brussels, Belgium. Association for Computational Linguistics. find
8. James Henderson. 2003. Inducing history representations for broad coverage statistical parsing. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pages 103– 110. find
9. Mark Johnson. 1998. Finite-state approximation of constraint-based grammars using left-corner grammar transforms. In COLING 1998 Volume 1: The 17th International Conference on Computational Linguistics. find
10. Tadao Kasami. 1966. An efficient recognition and syntax-analysis algorithm for context-free languages. Coordinated Science Laboratory Report no. R-257. find
11. Nikita Kitaev, Steven Cao, and Dan Klein. 2019. Multilingual constituency parsing with self-attention and pre-training. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3499–3505, Florence, Italy. Association for Computational Linguistics. find
12. 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
13. Jiangming Liu and Yue Zhang. 2017. In-order transition-based constituent parsing. Transactions of the Association for Computational Linguistics, 5:413–424. find
14. 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
15. Anton Nijholt. 1979. Structure preserving transformations on non-left-recursive grammars. In International Colloquium on Automata, Languages, and Programming, pages 446–459. Springer. find
16. Hiroshi Noji, Yusuke Miyao, and Mark Johnson. 2016. Using left-corner parsing to encode universal structural constraints in grammar induction. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 33–43, Austin, Texas. Association for Computational Linguist… find
17. Daniel J. Rosenkrantz and Philip M. Lewis. 1970. Deterministic left corner parsing. In Switching and Automata Theory, 1970., IEEE Conference Record of 11th Annual Symposium On, pages 139–152. IEEE. find
18. Kenji Sagae and Alon Lavie. 2005. A classifier-based parser with linear run-time complexity. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 125–132, Vancouver, British Columbia. Association for Computational Linguistics. find
19. William Schuler, Samir AbdelRahman, Tim Miller, and Lane Schwartz. 2010. Broad-coverage parsing using human-like memory constraints. Computational Linguistics, 36(1):1–30. find
20. Cory Shain, William Bryce, Lifeng Jin, Victoria Krakovna, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. 2016. Memory-bounded left-corner unsupervised grammar induction on child-directed input. In Proceedings of COLING 2016, the 26th International Conference on Computational… find
21. The COLING 2016 Organizing Committee. find
22. Mitchell Stern, Jacob Andreas, and Dan Klein. 2017. A minimal span-based neural constituency parser. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 818–827, Vancouver, Canada. Association for Computational Linguistics. find
23. Marten van Schijndel, Andy Exley, and William Schuler. 2013. A model of language processing as hierarchic sequential prediction. Topics in Cognitive Science, 5(3):522–540. find
24. David Vilares, Mostafa Abdou, and Anders Søgaard. 2019. Better, faster, stronger sequence tagging constituent parsers. 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),… find
25. Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a Foreign Language. In Advances in Neural Information Processing Systems 28, pages 2755– 2763. Curran Associates, Inc. find
26. Daniel H. Younger. 1967. Recognition and parsing of context-free languages in time n3. Information and control, 10(2):189–208. find
27. Yue Zhang and Stephen Clark. 2009. Transition-based parsing of the Chinese treebank using a global discriminative model. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09), pages 162–171, Paris, France. Association for Computational Linguistics. find
28. 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
29. Muhua Zhu, Yue Zhang, Wenliang Chen, Min Zhang, and Jingbo Zhu. 2013. Fast and accurate shift-reduce constituent parsing. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 434–443, Sofia, Bulgaria. Association for Computational… find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/acl-2020-kitaev-tetra-tagging-word-synchronous-parsing/