TL;DR
Recurrent Neural Network Grammars (RNNGs) are powerful for modeling language structure but notoriously slow to train due to difficulties in batching. This paper introduces an effective batching strategy for RNNGs that allows for parallel computation across multiple sentences, leading to significant speedups in both training and inference. This work makes RNNGs more practical and scalable, potentially enabling them as a viable alternative to unstructured models like LSTMs.
What Problem Does This Paper Address?
Neural language models are excellent at predicting words, but understanding their deeper linguistic capabilities, especially syntactic understanding, is crucial. While traditional models like LSTMs and Transformers can learn some syntactic behaviors, explicitly modeling syntax with architectures like Recurrent Neural Network Grammars (RNNGs) offers a distinct advantage. RNNGs generate parse trees and sentences jointly, providing a richer representation of linguistic structure. However, a major hurdle for RNNGs has been their poor scalability, primarily due to the challenge of efficiently batching training data. Unlike LSTMs and Transformers, where operations are token-wise and easily parallelizable across sentences, RNNG computations are structure-sensitive, making standard mini-batching difficult. This has limited their practical adoption despite their theoretical advantages.
Methods
The core contribution of this paper is an effective batching strategy for RNNGs. The authors leverage the observation that many core operations within RNNGs, particularly those involving the stack LSTM (a key component of RNNGs), can be computed in parallel across multiple sentences.
Key aspects of their method include:
- Parallelizing Stack LSTM Operations: They devise techniques to compute stack LSTM updates and pointer movements in a batched manner, even when sentences have variable stack depths and internal operations differ. This is achieved by using tensor operations and carefully managing stack pointers.
- Action-Specific Batching: Instead of trying to unify all RNNG actions into a single batched operation, they group operations by type (e.g., NT, GEN, REDUCE) and optimize batching for each type. This pragmatic approach allows for significant speedups without oversimplifying the model's structure.
- Tensor Representations for Stacks: They extend the idea of batched stack LSTMs by representing stacks (both hidden states and elements) as tensors with an added "batch" dimension. This enables parallel processing of multiple sentences' stack states.
- Batched Beam Search: As a byproduct of their batched training approach, they also implement a fully batched beam search for inference, significantly accelerating the parsing process.
Datasets
- Training:
- BLLIP corpus (approx. 42 million tokens)
- English Wikipedia (100 million tokens)
- Evaluation:
- SyntaxGym test circuits (for syntactic generalization)
- Penn Treebank (PTB) development set (for parsing accuracy)
The authors note that the BLLIP corpus is used for its larger size compared to the commonly used Penn Treebank, which helps in demonstrating the effects of large batch sizes. They also use a large dataset from English Wikipedia to evaluate syntactic generalization.
Key Insights and Ideas
- Batching is Key to RNNG Scalability: The paper convincingly demonstrates that the primary bottleneck for RNNGs is not their inherent complexity but the lack of efficient batching. Their method unlocks significant speedups, making RNNGs much more practical.
- Structure-Sensitive Models Can Be Batched: Contrary to the intuition that structure-sensitive models are inherently difficult to batch, this work shows that with careful tensor manipulation and action-specific optimization, parallel computation is achievable.
- Data Scale Matters for Syntactic Generalization: Even for models with strong inductive biases like RNNGs, increasing the amount of training data (from 42M to 100M tokens) consistently improves syntactic generalization abilities.
- RNNGs May Outperform LSTMs with More Data: While LSTMs can exploit surface-level heuristics, RNNGs, when scaled with more data, tend to develop stronger reliance on structural understanding, potentially leading to better generalization.
- Subword Modeling is Beneficial but Needs Careful Tuning: Using subwords improves parsing accuracy, but the optimal number of subword units depends on the model size, suggesting a trade-off between vocabulary size and model capacity.
Key Results
- Training Speedup: Achieved a 6x speedup compared to the existing C++ DyNet implementation with model-independent auto-batching.
- Inference Speedup: Achieved x20-150 speedup for beam search depending on beam sizes.
- Syntactic Generalization: RNNG trained on 100M Wikipedia tokens showed consistent improvement in syntactic generalization scores on SyntaxGym circuits compared to a smaller dataset.
- Parsing Accuracy: Subword models consistently improved parsing accuracy (F1 scores) on the PTB development set compared to fixed vocabulary models.
- Model Convergence: Larger batch sizes (up to 512) led to faster model convergence and better final parameters.
Limitations and Future Work
- Memory Overhead: While the authors argue that the extra memory for stack tensors is not a bottleneck compared to the computational graph, large batch sizes with large models still require significant GPU memory.
- Action-Specific Separation: The algorithm separates actions, which is seen as a "deficiency" but necessary for broader applicability beyond very simple models.
- Future Work: The authors suggest further research into developing better syntactic representations as supervision for structured language models. They also propose exploring alternative inference methods beyond word-synchronous beam search to further improve efficiency. The paper opens doors for more extensive research into structured neural language models due to the reduced training costs.
Summary updated