Do Transformers Parse while Predicting the Masked Word? (2023)

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 (Marcus et al., 1993). 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 one of the surprising discoveries about transformerbased language models like bert @xcite and roberta @xcite was that contextual word embeddings encode information about parsing, which can be extracted using a simple "linear probing" to yield approximately correct dependency parse trees for the text @xcite . subsequently, @xcite ; @xcite ; @xcite employed linear probing also to recover information about constituency parse trees. ## parsing using transformers we design transformers with moderate layers and heads for parsing and masked language modeling. in section 3.1, we prove that transformers can execute the inside-outside algorithm for bounded-length sentences with any pcfg. in section 3.2, we connect our construction with masked language modeling and demonstrate the optimality of the inside-outside algorithm for mlm on pcfggenerated data. finally, in section 3.3, we demonstrate the ability to reduce the size of these constructions while retaining their parsing performance. ## probing masked language models for parsing information section 3 shows that transformers can execute the inside-outside algorithm and contain syntactic information in their intermediate states. these results are existential, and it is unclear if models pretrained under mlm possess similar information. one difficulty in answering this question is that syntactic probes on bert-like models may leverage semantic cues to parse. to address this concern, we pre-train multiple roberta models on synthetic datasets derived from english pcfg (section 4.1), which eliminates semantic dependencies. we then probe the models for parse tree construction (section 4.2) and marginal probabilities (section 4.3) to verify if they capture information computed by the inside-outside algorithm. ## conclusion in this work, we show that mlm with moderate size has the capacity to parse decently well. we probe bert-like models pre-trained (with mlm loss) on the synthetic text generated using pcfgs to verify that these models capture syntactic information. furthermore, we show that the models contain the marginal span probabilities computed by the inside-outside algorithm, thus connecting mlm and parsing. we hope our findings may yield new insights into large language models and mlm.