17 papers · 1 filter
Generating in the Limit with Infinitely Many Hallucinations
Irene Strauss, Alexandra Butoi, Ryan Cotterell
The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner task…
Causally Evaluating the Learnability of Formal Language Tasks
Vésteinn Snæbjarnarson, Anej Svete, Josef Valvoda +3
Language models, as multi-task learners, acquire a wide range of abilities during training. A fundamental question is how much task-specific data is needed to learn a given task. A…
Probability Distributions Computed by Autoregressive Transformers
Andy Yang, Anej Svete, Jiaoda Li +4
Most expressivity results for transformers treat them as language recognizers -- devices that accept or reject strings -- rather than as they are used in practice: as language mode…
Characterizing the Expressivity of Fixed-Precision Transformer Language Models
Jiaoda Li, Ryan Cotterell
Transformer-based language models (LMs) have achieved widespread empirical success, but their theoretical expressive power remains only partially understood. In this work, we analy…
Information Locality as an Inductive Bias for Neural Language Models
Taiga Someya, Anej Svete, Brian DuSell +3
Inductive biases are inherent in every machine learning system, shaping how models generalize from finite data. In the case of neural language models (LMs), debates persist as to w…
Training Neural Networks as Recognizers of Formal Languages
Alexandra Butoi, Ghazal Khalighinejad, Anej Svete +3
Characterizing the computational power of neural network architectures in terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds…