Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2809 - 2821 December 7-11, 2022 ©2022 Association for Computational Linguistics Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation Xiang Hu† Haitao Mi†∗ Liang Li‡ Gerard de Melo§ Ant Group† {aaron.hx, haitao.mi}@alibaba-inc.com† School of Cyber Science and Technology, Shandong University, China / Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University / Quancheng Laboratory, China‡ li.liang@sdu.edu.cn‡ Hasso Plattner Institute / University of Potsdam§ gdm@demelo.org§ Abstract Chart-based models have shown great potential in unsupervised grammar induction, running recursively and hierarchically, but requiring O(n3) time-complexity. The Recursive Trans- former based on Differentiable Trees (R2D2) makes it possible to scale to large language model pretraining even with a complex tree encoder, by introducing a heuristic pruning method. However, its rule-based pruning pro- cess suffers from local optima and slow infer- ence. In this paper, we propose a unified R2D2 method that overcomes these issues. We use a top-down unsupervised parser as a model- guided pruning method, which also enables parallel encoding during inference. Our parser casts parsing as a split point scoring task by first scoring all split points for a given sentence and then using the highest-scoring one to recur- sively split a span into two parts. The reverse order of the splits is considered as the order of pruning in the encoder. We optimize the unsupervised parser by minimizing the Kull- back–Leibler distance between tree probabili- ties from the parser and the R2D2 model. Our experiments show that our Fast-R2D2 signifi- cantly improves the grammar induction quality and achieves competitive results in downstream tasks.1 1 Introduction Compositional, hierarchical, and recursive pro- cessing are widely believed to be essential traits ∗Work done while at Ant Group. To contact Haitao, haitaomi@global.tencent.com 1The code is available at: https://github.com/ alipay/StructuredLM_RTDT of human language across diverse linguistic the- ories (Chomsky, 1956, 2014). Chart-based mod- els (Maillard et al., 2017; Kim et al., 2019a; Droz- dov et al., 2019; Hu et al., 2021) have made promis- ing progress in both grammar induction and hier- archical encoding in recent years. The differen- tial CKY encoding architecture of Maillard et al. (2017) simulates the hierarchical and recursive pro- cess explicitly by introducing an energy function to combine all possible derivations when construct- ing each cell representation. However, this entails a cubic time complexity, which makes it impossi- ble to scale to large language model training like BERT (Devlin et al., 2018). Simultaneously, its cubic memory cost also limits the tree encoder’s ability to draw on huge parameter models as a back- bone. Hu et al. (2021) introduced a heuristic pruning method, successfully reducing the time complexity to a linear number of compositions. The experi- ments show that chart-based models exhibit great potential for grammar induction and representa- tion learning when applying a sophisticated tree encoder such as Transformers with large corpus pretraining, leading to a Recursive Transformer based on Differentiable Trees, or R2D2 …

Content truncated to 500 words