Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length (2024)

Abstract: Neural networks offer good approximation to many tasks but consistently fail to reach perfect generalization, even when theoretical work shows that such perfect solutions can be expressed by certain architectures. Using the task of formal language learning, we focus on one simple formal language and show that the theoretically correct solution is in fact not an optimum of commonly used objectives — even with regularization techniques that according to common wisdom should lead to simple weights and good generalization (L1, L2) or other meta-heuristics (early-stopping, dropout). On the other hand, replacing standard targets with the Minimum Description Length objective (MDL) results in the correct solution being an optimum.

## introduction probing the capabilities of artificial neural networks (anns) in the domain of language learning has advanced in two complementary pathstheoretical and empirical. theoretical work tries to delineate the kinds of languages and phenomena that can be expressed by anns, and empirical work involves training networks on such tasks and inspecting their performance. these paths have still not converged: while theoretical work continues to provide findings regarding the expressivity of different architectures, empirical work keeps arriving at suboptimal solutions that fall short of the theoretically correct ones. for example, for formal languages such as a n b n or dyck-1, among many others, we are not aware of any network trained through gradient descent that was shown to perform well on strings that are orders of magnitudes longer than those seen during training, while failures to report generalization beyond low lengths are pervasive @xcite @xcite @xcite others; see @xcite for an overview). this stands in contrast to symbolic models, where the requirement for solution correctness across lengths is trivially met. why this would be the case is often either left unexplained or waved off as a shortcoming of the optimization method (most often, gradient descent using backpropagation). in this work we argue that these failures are not due to training misfortunes that could be overcome, for example, by using a more exhaustive hyper-parameter search, more training steps, or more training data. rather, they are due to inherent characteristics of the training objectives currently used for such tasks. our main contributions are: the full experimental materials and source code are available at https://github.com/0xnurl/ mdl-lstm . ## previous work we rely mainly on three recent works, which we extend in the following ways. first, the current work is similar to @xcite , who inspected the role of the objective function in formal language learning. they showed that for a simple recurrent neural network (rnn), which uses a single relu layer, the optimal counting solution does not align with optima of common loss functions (cross-entropy and mean squared error). this was done by providing necessary and sufficient conditions for implementing counting in a relu-rnn. we extend this work in the following ways. first, we move to the more commonly used lstm rnn. since this architecture is more complex, it is also harder to find such sufficient and necessary conditions for counting as done by @xcite . this leaves our results mostly empirical, compared to their analytical result. however, here we go beyond that work by also providing an alternative objective function (mdl), for which the optimal network becomes an optimum. second, in order to locate such an optimum of the objective, we build an optimal lstm that accepts a specific formal language. for this we rely on @xcite , who showed that an lstm can theoretically implement counting using specific weight configurations, so that the state vector holds a counter that can be incremented and decremented based on the input. here we implement their general recipe to build an optimum lstm that accepts the language a n b n . we focus on one language for simplicity, and the method can be easily extended to more languages. third and closest to the current work, @xcite applied the mdl principle to rnns for formal language learning. the resulting networks were shown to be correct for any string for languages such as a n b n , a n b m c n+m , and dyck-1. since this objective resulted in a non-differentiable loss function, @xcite used neuroevolution to search the hypothesis space, evolving free-form rnn cells. since our focus in this work is the objective, here we leave the search algorithm aside and use a single fixed architecture for which a theoretical target is known to exist (lstm). we then inspect the effect of the objective function on potential weight solutions. more broadly, empirical work using rnns for artificial grammar learning have been carried out at least since the introduction of simple rnns in @xcite . theoretical work regarding rnns' theoretical computational power go back at least to @xcite , who showed that rnns are turing-complete under certain permissive assumptions (unbounded activation precision and running time). the empirical success of anns in the practical field of natural language processing (nlp) has led to recent interest in the theoretical power of rnns under practical conditions, mainly real-time processing and finite precision @xcite . other recent work has applied similar methods to the transformer architecture (see survey in @xcite . in terms of empirical results, works since elman (1990) trained anns to recognize formal languages and most often tested for generalization using unseen string lengths and depths @xcite @xcite , among many others). @xcite provide an overview of such works; they show that common to these works is a failure to generalize beyond a certain tested length. @xcite also provide a standardized benchmark for formal language learning, and find that rnns trained to optimize standard losses fail to generalize well from reasonably small amounts of data, while an rnn variant trained to minimize mdl @xcite is able to generalize significantly better. applying the mdl criterion to anns also dates back to at least the early 1990's. @xcite for an overview of early attempts in this area, and @xcite for a review of more recent work.) @xcite minimized the encoding length of the weights alongside the prediction error, while leaving the architecture fixed. @xcite provided an algorithm that searches for networks that lie at 'flat minima' -regions of parameter space where error remains relatively similar; this preference is given an mdl justification. @xcite used a genetic algorithm to search for network architectures that minimize an mdl score, using a weight encoding similar to l2 regularization. @xcite presented an algorithm for discovering networks that optimize a runningtime based complexity metric that is closely related to mdl (levin complexity). more recently, @xcite used a bayesian method with an mdl justification for pruning and quantizing network units and weights. @xcite used a differentiable approximation of the l0 norm to encourage weight sparsity. as far as we can tell, these methods are still prone to the risk of overfitting through highly informative yet small-valued weights, explained in section 3.2 below. ## general setup we describe here the technical background leading to the experiments in section 4. ## discussion we presented a comparison between common overfitting-prevention techniques, among them some that equate simplicity with scalar magnitude, and the mdl objective accompanied with an encoding scheme for weights which favors an intuitive notion of simplicity. combined with a manually built lstm that optimally recognizes a n b n , we could measure the loss values of an optimal solution and check if they align with optimum points of the loss function. it was only when we used mdl that the optimal network aligned with the minimum of the loss. for the other loss functions, networks lying at minimum points had far from optimal performance. using meta-heuristics such as early stopping mitigated overfitting to some extent, but still did not lead to a fully general solution. we interpret these findings as an indicator that anns' failure to converge on provably existing, optimal solutions is not accidental, but rather an inherent and pathological property of the way that current models are trained. this is in line with a mounting list of generalization failures to learn formal languages, as well as more complicated natural language tasks. we focused here on rnns, mainly because they lend themselves easily to manual construction and inspection. however, we see no a priori reason why our results would not extend to other architectures such as transformers or convolutional networks, given the generality of the mdl principle, and the fact that it has been shown to be beneficial across various domains and learning tasks, including linguistic phenomena (see @xcite @xcite . ## limitations in section 4.4 we explored the loss surface around the golden network using different objectives, and found that using l1/l2 regularization leads to suboptimal networks lying at optimum points, while using the mdl objective leads to the golden network lying at an optimum point. however, since the loss exploration is not (and cannot be) exhaustive, caution is needed when making generalizations based on these results. first, when using l1/l2, it is still possible of course that better optima lie somewhere else in the loss spaces, and that the respective minimizing networks have perfect performance. given the discussion in section 3.1 about scalar magnitude vs. simplicity we find this possibility unlikely but admittedly still possible. conversely, when using the mdl objective, here it is conceivable that other networks would have better mdl scores and suboptimal performance. while this cannot be ruled out completely, we believe that using the mdl objective accompanied by a reasonable encoding scheme like the one used here makes over/under-fitting unlikely. this is arguably not the case for l1/l2. (another possibility, that of a network with a better mdl score but equivalent perfect performance, is more likely, given that the golden network was manually designed and can potentially be optimized further.) finally, a major practical limitation of the current work relates to the non-differentiability of the mdl objective. this is especially problematic for anns, given that current standard training methods rely almost exclusively on gradient descent. one could then consider l1/l2 as a differentiable proxy for a strict formalization of simplicity. however, the current work sheds light on the shortcomings of these compromises. this in turn could lead both to a more informed use of such proxies, and potentially to further research regarding better optimization techniques for mdl. stop after no improvement for number of epochs: none/2/10. weight initialization: uniform/normal. all simulations used the adam optimizer (kingma and ba, 2014) with learning rate 0.001, β 1 = 0.9, β 2 = 0.999, and ran for 20,000 epochs unless stopped by early stopping.