Neural Networks and the Chomsky Hierarchy
This addresses the unsolved problem of reliable generalization in ML/AI, providing insights into architecture limitations for out-of-distribution inputs, though it is incremental as it focuses on a specific subset of tasks.
The authors investigated whether the Chomsky hierarchy can predict neural network generalization limits, finding that RNNs and Transformers fail on non-regular tasks, LSTMs handle regular and counter-language tasks, and only memory-augmented networks generalize on context-free and context-sensitive tasks, based on an empirical study of 20,910 models across 15 tasks.
Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study (20'910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.