Minimum Description Length Recurrent Neural Networks (2022)

Abstract: We train neural networks to optimize a Minimum Description Length score, that is, to balance between the complexity of the network and its accuracy at a task. We show that networks optimizing this objective function master tasks involving memory challenges and go beyond context-free languages. These learners master languages such as anbn, anbncn, anb2n, anbmcn +m, and they perform addition. Moreover, they often do so with 100% accuracy. The networks are small, and their inner workings are transparent. We thus provide formal proofs that their perfect accuracy holds not only on a given test set, but for any input sequence. To our knowledge, no other connectionist model has been shown to capture the underlying grammars for these languages in full generality.

## introduction a successful learning system is one that makes appropriate generalizations. for example, after seeing the sequence 1,0,1,0,1 we might suspect that the next element will be 0. if we then see 0, we might be even more confident that the next input element will be 1. artificial neural networks have shown impressive results across a wide range of domains, including linguistic data, computer vision, and many more. they excel at generalizing when large training corpora and computing resources are available, but they face serious challenges that become particularly clear when generalizing from small input sequences like the one presented above. first, they tend to overfit the learning data. to avoid this, they require external measures to control their own tendency for memorization (such as regularization) as well as very large training * both authors contributed equally to this work. corpora. moreover, standard regularization techniques fall short in many cases, as we show below. second, even when successful, they tend to produce non-categorical results. that is, they output very high probabilities to target responses, but never 100%. adequate, human-like generalization, on the other hand involves having both a probabilistic guess (which neural networks can do) and, at least in some cases, a clear statement of a categorical best guess (which neural networks cannot do). third, these networks are often very big, and it is generally very hard to inspect a given network and determine what it is that it actually knows (though see @xcite , for a recent successful attempt to probe this knowledge in the context of linguistics). some of the challenges above arise from the reliance of common connectionist approaches on backpropagation as a training method, which keeps the neural architecture itself constant throughout the search. the chosen architecture must therefore be large enough to capture the given task, and it is natural to overshoot in terms of size. furthermore, it must allow for differentiable operations to be applied, which prevents certain categorical patterns from even being expressible. in this paper, we propose to investigate a training method that differs from common approaches in that its goal is to optimize a minimum description length objective function (mdl; @xcite . this amounts to minimizing error as usual, while at the same time trying to minimize the size of the network (a similar pressure to a bayesian size prior). as a result, the objective function offers a guide to determining the size of the network (a guide that error minimization alone does not provide), which means that the architecture itself can evolve during learning and typically can decrease in size. one potential side effect is that optimization cannot be done through backpropagation alone. we here use a genetic algorithm to search through the very large search space of neural networks of varying sizes. we find that mdl-optimized networks reach adequate generalizations from very small corpora, and they avoid overfitting. the mdl-optimized networks are all small and transparent; in fact, we provide proofs of accuracy that amount to infinite and exhaustive test sets. they can also provide deterministic outputs when relevant (expressing pure 100% confidence). we illustrate this across a range of tasks involving counters, stacks, and simple functions such as addition. ## previous work our primary concern in this paper is the objective function. the idea of applying a simplicity criterion to artificial neural networks dates back at least to @xcite , who minimize the encoding length of a network's weights alongside its error, and to @xcite , who use a simplicity metric that is essentially the same as the mdl metric that we use in the present work (and describe below). @xcite presents an algorithm for discovering networks that optimize a simplicity metric that is closely related to mdl. simplicity criteria have been used in a range of works on neural networks, including recent contributions (e.g., @xcite . outside of neural networks, mdl-and the closely related bayesian approach to induction-have been used in a wide range of models of linguistic phenomena, in which one is often required to generalize from very limited data (see @xcite @xcite @xcite , among others; and see @xcite @xcite , for recent proposals to learn full phonological grammars using mdl within two different representational frameworks). in the domain of program induction, @xcite have recently used a bayesian learner equipped with a simplicity prior to learn formal languages similar to the ones we present below. turning to the optimization algorithm that we use to search for the mdl-optimal network, our work connects with the literature on using evolutionary programming to evolve neural networks. early work that uses genetic algorithms for various aspects of neural network optimization includes @xcite , @xcite , @xcite , and @xcite . these works focus on feed-forward architectures, but @xcite present an evolutionary algorithm that discovers recurrent neural networks and test it on a range of sequential tasks that are very relevant to the goals of the current paper. evolutionary programming for neural networks remains an active area of research (see @xcite @xcite , among others, for relevant references). our paper connects also with the literature on using recurrent neural networks for grammar induction and on the interpretation of such networks in terms of symbolic knowledge (often formal-language theoretic objects). these challenges were already taken up by early work on recurrent neural networks (see @xcite , among others), and they remain the focus of recent work (see, e.g., @xcite . @xcite and @xcite provide discussion and further references. ## experiments we ran tasks based on several classical formal-language learning challenges. we use both deterministic and probabilistic expectations to test the ability of a learner to work on probabilistic and symbolic-like predictions. in addition to showing that the mdl learner performs well on test sets, we provide proofs that it performs well on the whole infinite language under consideration. ## conclusion classical rnns optimized for accuracy can partially recognize nonregular languages and generalize beyond the data up to a certain n @xcite . however large this n may be, the failure of these networks to fully generalize to arbitrary values of n reveals that they fail to lock in on the correct grammars that underlie these tasks. we found that an mdl-optimized learner arrives at networks that are reliably close to the true distribution with small training corpora, for classically challenging tasks. in several cases, the networks achieved perfect scores. beyond the usual evaluation in terms of performance on test sets, the networks lent themselves to direct inspection and showed an explicit statement of the pattern that generated the corpus.