Minimum Description Length Recurrent Neural Networks

Minimum Description Length Recurrent Neural Networks Nur Lan1,2, Michal Geyer2, Emmanuel Chemla1,3∗, Roni Katzir2∗ 1Ecole Normale Sup´erieure, France 2Tel Aviv University, Israel 3EHESS, PSL University, CNRS {nlan,chemla}@ens.fr michalgeyer@mail.tau.ac.il rkatzir@tauex.tau.ac.il Abstract We train neural networks to optimize a Min- imum Description Length score, that is, to balance between the complexity of the net- work and its accuracy at a task. We show that networks optimizing this objective func- tion 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 accu- racy 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. 1 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 con- trol 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 tech- niques fall short in many cases, as we show below. Second, even when successful, they tend to produce non-categorical results. That is, they out- put very high probabilities to target responses, but never 100%. Adequate, human-like general- ization, 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 Lakretz et al., 2019, 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 train- ing …

Content truncated to 500 words