Deep networks learn to parse uniform-depth context-free languages from local statistics

Understanding how the structure of language can be learned from sentences alone is a central question in both cognitive science and machine learning. Studies of the internal representations of Large Language Models (LLMs) support their ability to parse text when predicting the next word, while representing semantic notions independently of surface form. Yet, which data statistics make these feats possible, and how much data is required, remain largely unknown. Probabilistic context-free grammars (PCFGs) provide a tractable testbed for studying these questions. However, prior work has focused either on the post-hoc characterization of the parsing-like algorithms used by trained networks; or on the learnability of PCFGs with fixed syntax, where parsing is unnecessary. Here, we (i) introduce a tunable class of PCFGs in which both the degree of ambiguity and the correlation structure across scales can be controlled; (ii) provide a learning mechanism---an inference algorithm inspired by the structure of deep convolutional networks---that links learnability and sample complexity to specific language statistics; and (iii) validate our predictions empirically across deep convolutional and transformer-based architectures. Overall, we propose a unifying framework where correlations at different scales lift local ambiguities, enabling the emergence of hierarchical representations of the data.

How do modern deep learning models acquire the structure of language? In particular, how do they learn to parse text? This is an essential element of processing language, which as humans we do all the time: given a sentence, we need to understand how to split it into blocks, think of the subject, the action and its object. A deep network needs to acquire these grammatical skills purely from example sentences. In our paper we propose a synthetic language, which allows control over all statistical properties, but retains key aspects of natural language such as ambiguity, context-freeness and varying tree topology. We show how learning can proceed from local statistics alone, by exploiting the clustering of grammar rules sharing the same parent symbol. We confirm our theoretical prediction for the number of data required to learn on real deep network architectures, showing that they exploit our proposed mechanism. Our findings are a step towards clarifying the seemingly miraculous success of modern language models. Even a complex task such as parsing can be learned from the statistics of examples alone, and our synthetic language shines a light onto the mechanisms by which this can be achieved.