Benchmarking Neural Network Generalization for Grammar Induction (2023)

Abstract: How well do neural networks generalize? Even for grammar induction tasks, where the target generalization is fully known, previous works have left the question open, testing very limited ranges beyond the training set and using different success criteria. We provide a measure of neural network generalization based on fully specified formal languages. Given a model and a formal grammar, the method assigns a generalization score representing how well a model generalizes to unseen samples in inverse relation to the amount of data it was trained on. The benchmark includes languages such as a^nb^n , a^nb^nc^n , a^nb^mc^{n+m} , and Dyck-1 and 2. We evaluate selected architectures using the benchmark and find that networks trained with a Minimum Description Length objective (MDL) generalize better and using less data than networks trained using standard loss functions. The benchmark is available at https://github.com/taucompling/bliss .

## introduction the extent to which artificial neural networks (anns) generalize beyond their training data is an open research question. in this work we approach this question from the perspective of grammar induction, that is, the learning of a formal grammar from a finite (often small) sample from the (typically infinite) language of that grammar. in order to succeed in this task, a model must strike a balance between fitting the training data and generalizing to a potentially infinite set of unseen strings. humans tested on such tasks show systematic generalization from small sets of examples @xcite . while a range of ann architectures have been shown to reach approximations for formal languages, the quality of this approximation remains an open matter, as we show below. here we build on previous probes of ann generalization for grammar induction and introduce a unified and general way to assess this capability, for a given pair of a learning model and a corpus drawn from a formal language. our main contributions are: the method assigns an index score representing a model's generalization performance in inverse relation to the size of the training data. we introduce the method and provide concrete datasets for well-studied formal languages. we find that equipping anns with memory devices such as differentiable stacks helps generalization, but generalization remains partial and slow. at the same time, training with mdl leads in some of the test cases that we examined to potentially perfect generalization with significantly less data. in other cases, training with mdl did not result in successful generalization, possibly because the optimization procedure we used for the architecture search failed to find the global optimum under the mdl objective function. ## background learning formal languages has long been used to probe various aspects of ann performance. these most often include inquiries about: (i) anns' ability to generalize beyond their training data, and lgck'22 @xcite . here we will focus on the generalization question. we will show how it might be related to another under-exploited line of inquiry regarding the training objective of anns. a long line of theoretical work has probed the computational power of anns. @xcite originally showed that rnns with a sigmoid activation can emulate multiple-stack turing machines under certain permissive conditions (infinite activation precision and unbounded running time). since these conditions cannot be met in practice, another line of work probed the computational power of rnns under practical conditions (finite precision and input-bound running time). @xcite have shown that under these conditions lstms are able to hold weight configurations that perform unbounded counting, and so they should be able to recognize counter languages (cl), a family of formal languages that can be recognized using one or more counting devices (following some formal restrictions, @xcite . recently, @xcite and @xcite have shown that two simpler rnn ar-chitectures, with linear-and relu-based cells, are also able to hold counting weight configurations, with similar consequences for recognizing cl. empirically, another line of work provided promising results regarding the capability of anns to learn formal languages. this was most often done by training networks on strings up to a certain length and then showing good performance on longer ones @xcite @xcite ; see however, other empirical results show that in practice anns generalize only to very restricted ranges. @xcite found that while lstms are theoretically able to hold counting solutions, these are not found through training: lstms trained on a n b n and a n b n c n with max n 100 and 50, respectively, start accepting illicit strings with n values as low as 256 and 100. as mentioned above, @xcite tested lstms on dyck-1 sequences but only up to length 100, and concluded that this language was learned by lstms. @xcite extended this work to longer sequences, and found that lstms fail to generalize in practice, outputting incorrect predictions at lengths under 1,000. this, despite dyck-1 being a cl and so theoretically learnable by lstms @xcite . apart from lstms, recent probes by el-naggar et al. (2023a) and el-naggar et al. (2023b) have shown that linear and relu rnns, theoretically capable of counting, fail to find the counting weight configurations in practice when trained using backpropagation and standard loss functions; el-naggar et al. (2023b) went further with determining the source of this discrepancy, showing that the counting weight configuration is not an optimum of these loss functions. moreover, even in works that report successful generalization to some degree beyond the training set, the fact that networks stop generalizing at an arbitrary point is often left unexplained @xcite @xcite . 1 the literature on the generalization abilities of anns has made use of a range of measures of success, making results difficult to compare. different probes of the same model often use different success criteria, and generate training and test sets using different sampling methods and of different orders of magnitude. ## the bliss index we present the benchmark for language induction from small sets (bliss). we provide a formal description of the method, followed by a concrete application to specific tasks. the current release consists of three parts: (i) a specification for the generalization index b, calculated for a given pair of formal language and ann; (ii) a dataset containing a set of formal languages for benchmarking; (iii) an evaluation of different ann architectures using this dataset. ## datasets we provide training and test datasets for a preliminary set of formal languages for evaluation using the b index. the dataset includes the languages a n b n , a n b n c n , a n b n c n d n , a n b m c n+m , dyck-1, and dyck-2. the source code, datasets, and specifications for the benchmark are available at https://github.com/taucompling/bliss . ## discussion we provided a simple index for how well a model generalizes: how much it can learn from how little data. we illustrated the usefulness of this index in a comparison of several current models over several formal languages. beyond showing which current models generalize better than others, the benchmark also highlights which aspects of artificial neural networks work well for grammar induction, and what is still missing. among languages that were learned with perfect accuracy (a n b n , a n b m c n+m , dyck-1), mdlrnns generalized best, but still failed on others (a n b n c n , a n b n c n d n , and dyck-2). previous work has shown that this model's search procedure, an evolutionary algorithm, fails to find networks that are manually shown to have better mdl scores @xcite . we take this to show that the optimization procedure limits the model and prevents it from taking full advantage of the mdl objective. the benefit of the mdl objective is nevertheless evident in the generalization performance for several languages. marnns clearly benefit from their memory devices and reach good generalization scores, but testing for perfect accuracy (ε = 0) reveals that their learning outcome is mostly approximate, and that they fail to maintain perfect accuracy for long stretches beyond their training data. this could be the result of an inadequate objective function (cross-entropy), limitations of the search (backpropagation/gradient descent), or both. we do not currently have results that help decide this matter, but recent results for other architectures @xcite hint that the problem lies at least in part in the objective function.