Expressivity and learnability of sequence models

Thesis

In this thesis, we study the representational capabilities and learnability of sequence models, with a focus on Transformers, the backbone of modern large language models. We first investigate expressivity: whether and how efficiently an architecture can represent a target function. For a range of algorithmic tasks, we prove exponential separations between Transformers and recurrent/state-space architectures, in the sense that one architecture can compute a function with exponentially smaller model size than the other. We further establish exponential separations between one-layer and two-layer Transformers. We then study empirical learnability in stylised in-context learning settings, treating sequence models as learning algorithms. Using a controlled test-bed of Boolean function classes with well-understood learning-theoretic properties, we identify differences in the performance of Transformers, modern recurrent models, and longconvolutional architectures. We further analyse learnability in additional settings, and demonstrate connections between in-context learning in pretrained large language models and the nearest-neighbour algorithm.

We theoretically analyse the learnability of sequence models under richer forms of supervision, focusing on query models where a learner can request labels of desired inputs. We provide new algorithms for learning singlehead attention-based models via queries in different oracle models and parameter regimes. We then turn to deterministic finite automata (DFAs) and study their learnability in a new supervision model relevant to the identification of the support of language models. We first characterise the identifiability of DFAs in this setting and establish hardness barriers for learning from examples or from membership queries alone. Finally, we introduce a query model inspired by the information one can obtain from language models and give an efficient learning algorithm by extending Angluin’s L ⋆ algorithm. We validate this approach through a systematic empirical study that extracts DFAs from Transformer-based language models trained on regular languages.

Authors: Bhattamishra, S

• DOI: 10.5287/ora-yjr0q8g5b
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: representational capabilities; Transformers; automata learning; provable learning; query learning; RNNs/SSMs
• Subjects: Deep learning (Machine learning); Machine learning; Computational learning theory