Fast- R 2 D 2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation (2022)

Abstract: Chart-based models have shown great potential in unsupervised grammar induction, running recursively and hierarchically, but requiring O(n³) time-complexity. The Recursive Transformer 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 process suffers from local optima and slow inference. 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 recursively 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 Kullback–Leibler distance between tree probabilities from the parser and the R2D2 model.Our experiments show that our Fast-R2D2 significantly improves the grammar induction quality and achieves competitive results in downstream tasks.

## introduction compositional, hierarchical, and recursive processing are widely believed to be essential traits * work done while at ant group. to contact haitao, haitaomi@global.tencent.com 1 the code is available at: https://github.com/ alipay/structuredlm_rtdt of human language across diverse linguistic theories @xcite . chart-based models @xcite @xcite have made promising progress in both grammar induction and hierarchical encoding in recent years. the differential cky encoding architecture of @xcite simulates the hierarchical and recursive process explicitly by introducing an energy function to combine all possible derivations when constructing each cell representation. however, this entails a cubic time complexity, which makes it impossible to scale to large language model training like bert @xcite . simultaneously, its cubic memory cost also limits the tree encoder's ability to draw on huge parameter models as a backbone. @xcite introduced a heuristic pruning method, successfully reducing the time complexity to a linear number of compositions. the experiments show that chart-based models exhibit great potential for grammar induction and representation 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 for short. however, r2d2's heuristic pruning approach is rule-based and only considers certain composition probabilities. thus, trees constructed in this way are not guaranteed to be globally optimal. moreover, as each step during pruning is based on previous decisions, the entire encoding process is sequential and thus slow in the inference stage. in this work, we resolve these issues by proposing a unified method with a new global pruning strategy based on a lightweight and fast top-down parser. we cast parsing as split point scoring, where we first encode the input sentence with a bi-directional lstm, and score all split points in parallel. specifically, for a given sentence, the parser first scores each split point between words in parallel by looking at its left and right contexts, and then recursively splits a span (starting with the whole sentence) into two sub-spans by picking the highest-scoring split point among the current split candidates. subsequently, the reverse order of the sorted split points can serve as the merge order to guide the pruning of the cky encoder, which enables the encoder to search for more reasonable trees. as the gradient of the pretrained component cannot be back-propagated to the parser, inspired by urnng @xcite , we optimize the parser by taking trees sampled from the cky chart table generated by the encoder as ground truth. thus, the parser and the chart-based encoder promote each other in this way back and force just like the strategy and value networks in alphazero @xcite . additionally, the pretrained tree encoder can compose sequences recursively in parallel according to the trees generated by the parser, which makes fast-r2d2 a recursive neural network @xcite variant. in this paper, we make the following main contributions: ## related work many attempts have been done in grammar induction and hierarchical encoding. @xcite and @xcite provided some of the first successful statistical approaches to grammar induction. there have been multiple recent papers that focus on structure induction based on language modeling objectives @xcite @xcite . @xcite proposed to use rvnn as a recursive architecture to encode text hierarchically, and @xcite showed the effectiveness of rvnns with gold trees for sentiment analysis. in this work, we focus on models that are capable of learning meaningful structures in an unsupervised way and encoding text over the induced tree hierarchically. in the line of work on learning a sentence representation with structures, @xcite jointly train their shift-reduce parser and sentence embedding components without gold trees. as their parser is not differentiable, they have to resort to reinforcement training, resulting in increased variance, which may easily collapse to trivial left or right branching trees. gumbel-tree-lstms @xcite construct trees by recursively selecting two terminal nodes to merge and learning the composition probability via downstream tasks. crvnn (chowdhury and caragea, 2021) makes the entire process end-to-end differentiable and parallel by introducing a continuous relaxation. urnng @xcite propose the first architecture to jointly pretrain parser and encoder based on rnng @xcite . however, it has o(n 3 ) complexity and remains unable to improve upon a right-branching baseline when punctuation is removed. @xcite propose an alternative approach, based on a differentiable cky encoding. the algorithm is differentiable due to a soft-gating approach, which approximates discrete candidate selection by a probabilistic mixture of the constituents available in a given cell of the chart. while their work relies on annotated downstream tasks to learn structures, @xcite propose a novel auto-encoder-like pretraining objective based on the inside-outside algorithm @xcite . ## conclusion in this paper, we have presented fast-r2d2, which improves the performance and inference speed of r2d2 by introducing a fast top-down parser to guide the pruning of the r2d2 encoder. pretrained on the same corpus, fast-r2d2 significantly outperforms sequential transformers with a similar scale of parameters on classification tasks. experimental results show that fast-r2d2 is a promising and feasible way to learn hierarchical text representations, which is different from layer stacking models and can also generate interpretable intermediate representations. as future work, we are investigating leveraging the intermediate representations in additional downstream tasks.