Abstract
Pre-trained language models have been shown to encode linguistic structures like parse trees in their embeddings while being trained unsupervised. Some doubts have been raised whether the models are doing parsing or only some computation weakly correlated with it. Concretely: (a) Is it possible to explicitly describe transformers with realistic embedding dimensions, number of heads, etc. that are capable of doing parsing — or even approximate parsing? (b) Why do pre-trained models capture parsing structure? This paper takes a step toward answering these questions in the context of generative modeling with PCFGs. We show that masked language models like BERT or RoBERTa of moderate sizes can approximately execute the Inside-Outside algorithm for the English PCFG. We also show that the Inside-Outside algorithm is optimal for masked language modeling loss on the PCFG-generated data. We conduct probing experiments on models pre-trained on PCFG-generated data to show that this not only allows recovery of approximate parse tree, but also recovers marginal span probabilities computed by the Inside-Outside algorithm, which suggests an implicit bias of masked language modeling towards this algorithm.
Introduction
For years, researchers have noticed that "probing" the embeddings of models like BERT reveals a surprising amount of syntactic information, such as parse trees. However, two major questions remained:
- Feasibility: Could a Transformer with a "realistic" number of heads and layers actually perform a formal parsing algorithm? Previous theoretical proofs suggested you would need an impractically large number of attention heads.
- Motivation: Why would a model trained simply to predict masked words bother to learn complex syntax? Is it actually "parsing," or just using semantic shortcuts?
This research bridges the gap between modern Transformers and classical linguistics by investigating the relationship between Transformers, Probabilistic Context-Free Grammars (PCFGs), and the Inside-Outside algorithm—a recursive method used to calculate the probability of different spans in a sentence.
Methodology
The authors employ a two-pronged approach combining theoretical construction and empirical validation.
Theoretical Construction and Mathematical Link
The authors prove that a Transformer can be constructed to simulate the Inside-Outside algorithm under "realistic" constraints. By utilizing the inherent sparsity of English PCFGs and low-rank structures across non-terminals, they demonstrate that a moderate-sized Transformer (similar to BERT-base) can approximate the algorithm effectively.
Furthermore, they establish a formal link through Theorem 3.3, which states that if a language is generated by a PCFG, the Inside-Outside algorithm is the mathematically optimal way to minimize the Masked Language Modeling (MLM) loss. This suggests that syntax is not just a "bonus" feature but the most efficient strategy for solving the MLM task.
Empirical Probing
To test these theoretical findings, the authors pre-trained RoBERTa models on synthetic data generated from an English-based PCFG. They then used "probes" (simple classifiers) to determine if the model's internal representations correlate with the intermediate values calculated by the Inside-Outside algorithm, specifically marginal span probabilities.
Datasets
- Synthetic PCFG Data: A dataset of 10 million sentences generated from a PCFG tailored to mimic English syntax, allowing for the isolation of syntax from semantic cues.
- Penn Treebank (PTB): A standard real-world benchmark for constituency parsing. The authors used the PCFG learned from PTB sections 02-21 to guide their synthetic data generation and evaluated their constructed models on section 22.
Key Results and Insights
Realistic Parsing Performance
The study demonstrates that a Transformer with only 15 attention heads and 40L embedding dimensions can achieve over 70% F1 score for constituency parsing on the PTB dataset. Probing experiments across different settings (PCFG, PTB, and Out-of-Distribution) confirm that both linear and neural network probes can recover significant syntactic information from the model's best layers.
High Correlation with Inside-Outside Probabilities
Probes on pre-trained RoBERTa models showed a high Pearson correlation (up to 0.93 for short spans) between the model's embeddings and the actual probabilities computed by the Inside-Outside algorithm. This correlation is particularly strong in the deeper layers of the model, suggesting that the model is performing a form of soft, probabilistic parsing as it processes text.
Layer-wise Emergence
Syntactic information is captured even in the lower layers of the model, with performance typically saturating around layer 3 or 4. This indicates that parsing is a fundamental, early-stage computation in MLMs.
Discussion and Future Work
The most profound insight is that hierarchical structure is the most efficient way for a model to predict masked words. However, some limitations remain:
- Context-Free Limitation: The study focuses on PCFGs, which are context-free. Real-world natural language often involves context-sensitive dependencies.
- Encoder Focus: The research specifically looks at Masked Language Models (like BERT/RoBERTa). Future work could explore if these findings translate to auto-regressive "decoder-only" models like GPT.
- Model Size: While the results are promising for moderate-sized models, testing on much larger architectures remains for future investigation.
Summary updated