Minimum Description Length Recurrent Neural Networks
Authors: Nur Lan
Emmanuel Chemla
Roni Katzir
Venue:  (2021)
Keywords: recurrent neural network
neural network
language modeling
minimum description length
genetic algorithm
semantics
syntax

Abstract: Recurrent neural networks (RNNs) face two well-known challenges: (a) the difficulty of such networks to generalize appropriately as opposed to memorizing, especially from very short input sequences (generalization); and (b) the difficulty for us to understand the knowledge that the network has attained (transparency). We explore the implications to these challenges of employing a general search through neural architectures using a genetic algorithm with Minimum Description Length (MDL) as an objective function. We find that MDL leads the networks to reach adequate levels of generalization from very small corpora, improving over backpropagation-based alternatives. We demonstrate this approach by evolving networks which perform tasks of increasing complexity with absolute correctness. The resulting networks are small, easily interpretable, and unlike classical RNNs, are provably appropriate for sequences of arbitrary length even when trained on very limited corpora. One case study is addition, for which our system grows a network with just four cells, reaching 100% accuracy (and at least .999 certainty) for arbitrary large numbers.

Under review as a conference paper at ICLR 2021
MINIMUM DESCRIPTION LENGTH RECURRENT NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Recurrent neural networks (RNNs) face two well-known challenges: (a) the dif- ficulty of such networks to generalize appropriately opposed to memorizing, especially from very short input sequences (generalization); and (b) the difficulty for understand the knowledge that the network has attained (transparency). We explore the implications to these challenges of employing a general search through neural architectures using a genetic algorithm with Minimum Description Length (MDL) as an objective function. We find that MDL leads the networks to reach adequate levels of generalization from very small corpora, improving over backpropagation-ben -ased alternatives. We demonstrate this approach by evolving networks which perform tasks of increasing complexity with absolute correctness. The resulting networks are small, easily interpretable, and unlike classical RNNs, are provably appropriate for sequences of arbitrary length even when trained on very limited corpora. One case study is addition, for which system grows network with just four cells, reaching 100% accuracy (and at least .999 certainty) for arbitrary large numbers.
INTRODUCTION
The modeling of sequential knowledge and learning requires making appropriate generalizations from input sequences that are often quite short. This holds both for language capabilities and for other sequential tasks such as counting. Moreover, the acquired knowledge and reason about its properties. Neural networks, despite their impressive results and popularity in a wide range of domains, still face some challenges in these respects: they tend to overfit the learning data and require regularization other special measures, well very large training corpora, to avoid this problem. In terms of knowledge, networks are often very big, and is generally very hard inspect a given network and determine what it that it actually knows (see Papernot& & McDaniel 2018 among others, for a recent attempt to probe this knowledge).
often helpful for the modeler to inspect
Some of the challenges above arise from the reliance of common connectionist approaches on back- propagation as a training method, and in this paper we explore the implications to sequential mod- eling of well-known alternative perspectives on neural network design. Speeifically, we consider replacing backpropagation with general search using a genetic algorithm through a large space of possible networks using Minimum Description Length (MDL; |Rissanen 1978) as an objective function. In essence, this amounts to minimizing error as usual, while at the same time trying to minimize the size of the network. We find that MDL helps the networks reach adequate levels of generalization from very small corpora, avoiding overfitting and performing significantly better than backpropagation- based alternatives. The MDL search converges on networks that are often small, transparent, and provably correct. We illustrate this across range of sequential tasks.
2 PREVIOUS WORK
Our work follows several lines of work in the literature. Evolutionary programming has been used to evolve neural networks in range of studies. Early work that uses genetic algorithms for various aspects of neural network optimization includes Miller et al. (1989), Montana & Davis (1989) Whitley et al.) (1990), and /Zhang & Mühlenbein (1993 1995). These works focus on feed-forwart architectures, but Angeline al. (1994) present an evolutionary algorithm that discovers recurrent

---

Under review as a conference paper at ICLR 2021
neural networks and test it 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 (Schmidhuber, 2013 and Gaier & Ha 2019 among others, for relevant references).
In terms of objective function, Zhang & Mühlenbein (993; 1995) use a simplicity metric that is essentially the same the MDL metric that
(and describe below). [Schmidhuber (1997) presents an algorithm for discovering networks that optimize a simplicity metric that is closely related to MDL. Simplicity criteria have been used in range of works on neural networks, including recent contributions (e.g., Ahmadizar et al. 2015 and Gaier & Ha 2019).
Our paper connects also with the literature 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 net- works (see Giles et al., 1990 and Elman 1990] among others), and they remain the focus of recent work (see, e.g.. Wang et al., 2018 and Weiss et al., 2018). See See Jacobssoon (2005) and Waan et al. 2018 for discussion and further references.
In a continuation these efforts, our contribution twofold. First, we put together minimal, out- of-the-box combination of the core of these ideas: evaluate the performance that can be achieved by a learner that seeks to optimize MDL. measures. The search and optimization itself done through standard genetic algorithm. From there, we benchmark the performance obtained through MDL optimization against the performance obtained by a set of 3 classic RNN architectures of different sizes. Second, show the benefit of optimizing networks not only for performance but also for their own architecture size, in that makes the black box much more permeable; for current tasks, are able to provide full proofs of accuracy (above and beyond test set).
LEARNER
3.1
MDL
Consider a hypothesis space G of possible grammars, and a corpus of input data D. our case, G is the set of all possible network architectures expressible using our representations, and D is a set of input sequences. For given G we may consider the ways which we can encode the data D given that G. The MDL principle (Rissanen, 1978), computable approximation of Kolmogorov Complexity (Solomonoff 1964 Kolmogorov 1965 Chaitin 1966), aims at the G that minimizes | + D G). where G is the size of G and D Gl the length of the shortest encoding of D given G (with both components typically measured in bits). Minimizing |G| favors small, general grammars that often fit the data poorly. Minimizing [D : G| favors large, overly specific grammars that overfit the data. By minimizing the sum, MDL aims at an intermediate level of generalization: reasonably small grammars that fit the data reasonably well. 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 generalize from very limited data (see Horning 1969
Berwick 1982 Stolcke 1994 Grünwald 1996] and de Marcken 1996. among others).
The term D G| corresponds to the surprisal of the data D according to the probability distribution defined by G' and is closely related to the cross-entropy between the distribution defined by G and the true distribution that generated We provide the details of such an encoding scheme in Appendix A and now turn to describe the space of networks that will be considered.
The term |G] depends on an encoding scheme for network.
3.2 REPRESENTATIONS
A network is represented as a directed graph which contains nodes, weighted edges, and activation functions for each node. Since we do not use backpropagation to train the network, the set of possible networks is larger here than what is usually allowed; for example, output units can have outgoing edges which feed hidden units, and input units can feed into other input units, thus saving intermediate hidden units. Beyond the topological flexibility, the activation functions also allow for more diversity in the possible networks, they can vary freely from one unit to the next, and they can be chosen from any of possible activation functions, including non-differentiable ones
2

---

Under review as a conference paper at ICLR 2021
since training does not rely backpropagation. Currently, only allow four possible activation functions: identity (i.e., no activation function), square function, ReLU, and sigmoid.
Since ultimately interested in sequential tasks, add second type of edges recurrent edges which cross time steps and feed a unit with the value of another unit at the previous step. Such edges are required in order to create memory cells and counters for various sequential tasks
3.3 SEARCH
Given our use of MDL as an objective function, which is not diffcrentiable, and our aim of optimiz- ing the network structure itself rather than just the weights of fixed architecture, gradient-based training methods such as backpropagation would not naturally support this objective.
Instead, we use Genetic Algorithm (GA: (olland 1975) which frees us from the constraints com- ing from backpropagation and fulfills the two requirements at once. For simplicity and to highlight the utility of the MDL metric standalone objective, we use a vanilla implementation of GA. The GA advances by incrementally evolving networks (e.g. add an edge, adjust a weight, remove a unit, etc.), and ranks them by their MDL score. Full implementation details are given Appendix B
3.4 INPUT AND OUTPUT
In all tasks, the learner is fed with inputs from a sequence, one input after the next, and at each time step its outputs are interpreted as determining the probability obtain a particular output. Depending on the task, this output is deterministically or probabilistically derivable from the inputs up to this point, and it may or may not correspond to the next input in the sequence.
If the vocabulary contains n letters, the inputs are one-hot encoded over n input cells (in yellow in the figures), and the outputs are given n cells (in blue). To interpret these n outputs as a probability distribution degenerate network that outputs all O's, the probabilities are set to the uniform value 1/n. When the vocabulary is binary, we use single 0/1 input cell and a single output cell whose value is interpreted as the probability to obtain 1, clipping it to the [o, 1] range if necessary.
zero negative values and normalize the rest to sum to 1. In case of
3.5 ILLUSTRATION WITH ELEMENTARY, DETERMINISTIC TASKS
First, let us provide a simple illustration, the identity task: the network is fed with a random quence of binary digits, and the target output is identical to the input at each time step. The network developed by the MDL learner is given in Fig. aa); this network is transparent and shows that this very simple task is learned perfectly well. Anticipating on a number of baselines, more results are given visually in Appendix and numerically in Appendix F. where can be seen that though some (but not all) classic RNNs may perform this task well, they do not achieve a perfect performance, only a statistically good one (that is, assigning a high probability to the appropriate value, but not necessarily assigning it a probability of 1).
X
Lineur
1.0
Lincur
P()))
X
Lincar
1.0
Linear
P((1)
(a)
(b)
Figure 1: The networks found by the MDL. learner for (a) the identity task and (b) the previous character task (same result for all training sets of length 10, 20, 50, and 100). The input (arriving to the yellow cell on the left) is directly fed into the output (blue cell the right) with weight of 1, either through direct, "contemporary" connection (a), or through a cross-time connection (b).
Second, consider the previous character task: the network is fed with random sequence of binary digits, and the output is identical to the previous input at each time step. This requires the learner
Another specificity of this representation that cells may have input all (which potentially benefi- cial terms of the grammar length part of the MDL score). In such cases, the cell hehaves as it received a total input of 0. So for instance if the activation function is a sigmoid, the output is constantly 0.5. The model source code and experimental material will he published once the paper can be de-anonymized.
3

---

Under review as a conference paper at ICLR 2021
to develop some kind of memory. The network developed by the MDL learner is given in Fig. [b). Again, one can comprehend how this network produces its output, and the classic RNNs tested do not perform well (and aren't 't transparent).
4 ARTIFICIAL LANGUAGE EXPERIMENTS
4.1 SETUP
A convenient choice test MDLL learner and its generalization capabilities comes from language induction tasks, in which the corpus is generated from a formally well-identified generalization. We ran tasks based on several classical cormal-lnguuage learning challenges from the linguistic domains of syntax and semantics. Let us mention two aspects in which these tasks differ from deterministic tasks as the ones above. First, they concern the prediction of the next character about predicting an independent output based on the input). Second, the next character that is, the target output- - was not deterministic function of the input (or all inputs so far). but followed in the training and test set from more general probability distribution. Given the results above, this could be seen as a challenge for the MDL learner which seems to make categorical decisions.
sequence (not
4.2 BASELINES
To compete with MDL learner, we trained 12 standard RNNs, varying in their architecture
(GRU cells, LSTM cells, Elman cells) and the size of their hidden state vector (2, 4, 32, 128). As usual, final softmax, derivable layer was plugged the end of these networks for them to output well-formed probability distribution. These RNNs were trained with a cross-entropy loss
Additionally, we added two abstract baselines: a uniform baseline corresponding to predicting all outputs with equal probability in all cases, and an optimal baseline, corresponding to predicting the actual probability distribution, that is the one determined by how the task was set up.
4.3 EXPERIMENTS
In each of the tasks below the training corpora consist of several sequences of the form 51 #82# where the s 'ss are strings over an alphabet that does not include #. As before, the task is to read each character in sequence and to predict the next character. The structure of the corresponds to various formal language-theorent
regularities, as described below. In sections 4.3. to 4.3.3 these regularities come from the domain of the semanties of quantificational determiners (Barwise & Cooper 1981] see Tiede 1999 and Paperno| |01|| among others, for a discussion of the Icarnability of such patterns). The formal languages in these tasks are regular and can be dealt with by finite- state automata. In sections 4.3.4 and 4.3.5 we consider patterns of unbounded counting based on classic syntactic challenge (Gers & Schmidhuber 2001) and correspond context-free and context- sensitive languages, which require more expressive frameworks. All results are given visually in Appendix and numerically Appendix F
4.3.1 EXACTLY n2
In this task, each s; is made of zero or more O's, and of exactly n I's: at each time step, the next input is 0 or 1 with equal probability if the current has fewer than n 1's and it is 0 or # if there are exactly n I's already. The order of the 0's and I's thus random. For "exactly 3', for example, one possible would be 00101 1000. The model trained on sequences of length 100, 200, 500, and 1,000, and tested on an unseen sequence of length 1,000.
The MDL learner achieves a test cross-entropy of 1 1580, 1293, 997.2, 997.2 for the four training sets, the lowest possible cross-entropy being 997. Against the RNN alternatives, the MDL networks are ranked 2/13, 2/13, 1/13, 1/13. Fig. 2 shows the network found for 1 and the largest training set of length 1,000.
All RNNs were trained using the Adam optimizer (Kingma & Ba 2015 with learning rate 0.01, 31 0.9, and 82 0.999. The networks were trained by feeding the full batch of training data for 1,000 epochs.
4

---

Under review as a conference paper at ICLR 2021
Liteer
Sigaoid
-100
Sigmood
Lincar
0.5
X
Lincar
Figure 2: The network found by the Ieanear for the exactly task. The network keeps track of the number of I's seen so far in the middle input cell (see the recurent connection that makes it persists in memory), and resets when a # input (see the -1 connection from the top input cell).
4.3.2 AT LEAST y
In this task, each 8; is made of zero or more O's, and of n or more I's: at each time step, the next input is with equal probability if the current s; has fewer than n I's, and it is 0, I # if there are exactly I's already, also with equal probability. The order of the O's and I's is thus random. For 'at least 3", for example, one possible s; would be 01010110010.
The model trained on sequences of length 200, 500, and 1,000, and tested on a single unseen se- quence of length 1,000. For n 1, the MDL learner achieves test cross-entropy of 1582, 1458, 1346 for the three training sets (lowest possible cross-entropy is 1345). Against the RNN alterna- tives, the networks are ranked 2/13, 3/13, 1/13. Fig-3(a) shows the network found for and the largest training set.
4.3.3 BETWEEN IT AND 72
Here each has zero or more O's, and between m and n I's: at each time step, the next input is 0 or with equal probability the current s; has less than m 1's, it is O, 1 or # if there are between m and n - 1 I's already. also with equal probability, and it is 0 or 1 if the number of I's has reached n. The order of the 0's and I's is thus random. For 'between and 6', for example, one possible 8; would be 0101011000 10010.
This was tested with (m, n) (3,6), 6). The model trained on sequences length 100, 200, 500, and 1,000, and tested of 1580, 1394, 175, 176 for the four training sets (lowest possible cross-entropy is 159). Against the RNN alternatives, the MDL networks are ranked I/13, 2/13, 1/13, 1/13. Fig. 3b) shows the network found for the largest training set.
unseen sequence of length 1,000. The MDL learner achieves cross-entropy
Sigmoul
Poi('O))
Sigmuai
Linese
Sigmooi
Psi(11))
Signooal
Poor"17)
1.0
X
Reln
Sigmnid
Pai('a")
Signod
Pai(
Litese
Linesr
(
(b)
Figure 3: The network found by the MDL leanner for (a) the at least 1 task and (b) the between 3 and 6 task for the largest training set.
5

---

Under review as a conference paper at ICLR 2021
4.3.4 a"b"
Here, each 8; belongs the context-free language a"b", where 2 0. In order recognize the language, an unbounded counter needs to be developed.
When generating the sequences, the next character is a with probability 99 after series of a's the sequence switches to b's with probability .1, and all remaining symbols are deterministically fixed by the fact that aim for abb" # sequence.
The model trained on sets consisting of 10 or 100 sequences and tested on an unseen set of 1,000 sequences. The MDL learner achieves a test cross-entropy of 9829 and 4755 for the two training sets (lowest possible cross-entropy is 4680). Against the RNN alternatives, the networks are ranked 4/13 and 1/13. In Fig. 4a) we show the network found for the larger training set.
4.3.5 c"
Each 8; belongs to the context-sensitive language b","e", where n 2 In order to succeed, the network needs to keep in memory the number of a's seen that it can deterministically predict the moment to switch from b's to c's, and from c's to the end of sequence symbol. The model was trained on sets consisting of 10 or 100 sequences, randomized similarly to the previous task. The final network was tested on an unseen set 1,000 sequences. Fig. 4bb) shows the network found for the larger training set. In Appendix C we show more precisely that the network assigns a probability of .91 or above to the correct output at any deterministic time step for any value of n. The MDL learner thus achieves a stable accuracy of 100% (on the test set and in fact for any relevant sequence), and test cross-entropy of 4987 (when the lowest possible cross-entropy is 4680). Against the RNN alternatives, the network is ranked 3/13.
4
Square
X
Sigrzoud
.6.B
Signoidi
-16.001
Signooal
.0.17
1,00
Sigmoid
PHil7a))
2,07
Luear
PwcCe))
1.1
1.0
.0.30
PHIlF)
11:25
Squar
Poi(bb
(a)
(b)
Figure 4: The network found by the MDL learner for (a) the a ab"", and (b) the 8" task for the largest training set. In (a), the bottom right cell takes care of the counting: it decreases at each new input a (by increments of 3). and decreases at each new increment of b (by increment of 3: +6 directly from the middle input cell and -3 indirectly through the bottom left input cell). network (b), the self-loop cell handles counting of all three symbols, first by decrcasing by the number a's, then increasing for each then decreasing again for c's; the output cell values at each time step align with the counter's 's value to create the correct probability distribution.
"The end of the initial sequence of a's cannot be deterministically predicted.

---

Under review as a conference paper at ICLR 2021
4.4
OVERVIEW OF THE RESULTS
Optimal
MDL
Best RNN,
Best RNN cross-entropy
MDL rank
Task
cross-yntropy
cross-entropy
no. hidden units
vs. RNN
Exactly 1
997
997.2
Elman,
1009
1/13
At least 1
1345
1346
Elman, 2
1366
1/13
Between 3-6
1159
1176
GRU,
1178
1/13
a"b"
4680
4755
LSTM,
4805
1/13
c"
4680
4987
LSTMM 128
4830
3/13
Addition
173
Elman, 4
9050
1/13
Table I: Results overview: cross-entropy and ranking of the MDL learner compared to the RNN alternatives (here for the largest training set each task, see details Appendices) and
Table D provides an overview of the results, full details are given visually in Appendix E and numer- ically Appendix As illustrated in the figures above, the networks that the MDL learner finds are sufficiently small and transparent that their workings can be inspected directly. In each case, this network expresses pattern that either identical the one that was used to generate the corpus or is very close to it.
Not surprisingly, this translates to good performance in terms of cross-entropy. Even though the learner did not attempt to optimize cross-entropy directly, the cross-entropy of the MDL network close to the entropy of the true distribution across several corpus sizes. Sometimes the two are almost the same, but typically much better) than the random baseline.
when this is not the case the MDL network performs no worse (and
Things different with the comparison RNNs from the literature. These networks large and opaque, and they perform unreliably: occasionally one of them performs well for particular corpus size, but others will typically perform much worse than chance, and which architecture does what can change significantly for the next corpus size or the next task. Overall, the MDL. learner performs best on the learner wins only of the remaining tasks.
in 21 of the 40 tasks and training conditions presented here while the next best
To the extent that can identify trend in the performance of the RNNs it is that the best per- formance generally comes from small networks, with few hidden units (for 26 tasks out of 40, the winner among the RNNs has hidden units, the minimal number possible here). Smaller networks may perform worse than bigger ones the training corpus, but they generalize better and perform better at test This is of course in line with the intuition behind our own learner and the MDLI approach more broadly.
CASE STUDY: GENERAL ADDITION
Recent advancements in large-scale language models such as GPT-3 (Brown et al. 2020) have
brought attention the capability of such models generalize opposed memorize. One partic- ular test case is that of general addition, which humans tackle with relative ease using few examples, but that is not picked up full generality by any deep learning learner to our knowledge
'Even in where the MDL. learner is the winner its cross-entropy is close that of the winner the optimal baseline; in fact, sometimes the RNN winner has cross-entropy below that of the optimal baseline, which makes it suspicious winner.
"A result, it means that picking the right RNN architecture is not easy task (without tripartite training/dev/test set), and performance at training not a good predictor performance at test.
"In other people's words: "As far as know there is no neural network that is capable of doing basic arithmetic like addition and multiplication
large number of digits based training data rather than hard- coding.". Kevin Lacker, 'Giving GPT-3 Turing Test'.
https::/lacckr: wttp:/aaaaaaaa////
http//////vv/igg//eeee gptt--ppt333 3-a- teraaturrii sotriingtesss ---a-turing--est. html
*GPT-3, one of the most recent and ambitious models, succeeds at many tasks but not quite addition: "One particularly interesting case arithmetic calculation: the model gives perfect score for 2-digit addition and
7

---

Under review as a conference paper at ICLR 2021
In the setting explore, the network is fed with sequences of pairs of binary digits, representing the digits of two binary numbers to be added up. The output at each step is the corresponding digit of the sum of these two numbers. With small training set of all pairs of integers up to 10 (total 100 samples), the MDL learner fails because in some cases it predicts a categorical probability (a plain 0 or 1) for the wrong output. With a larger training set of 400 samples (all pairs up 20), the MDL learner develops the network given in Fig. 5 The network achieves 100% accuracy on any test set, with cross-entropy 173 compared an optimal 0.
Dight
Linear
1.0
Linzre
Digh
Squar
-16.0
1.0
Sigmold
Figure 5: The network found by the MDL learner for the addition task, trained on 400 pairs of numbers. The
first digit is added to the second digit, and the sum is squared in place. Next, hidden cell (in yellow) with recurrent connection was evolved to take care the carry-over. The network reaches 100% accuracy on a test set consisting of all pairs of numbers up to 250, and is in fact provably correct for any arbitrary pair of numbers.
Here again, this network is quite transparent. In short, the output h of the hidden cell (in yellow) at any given time step corresponds the carry-over. (With in and jn the inputs, hn = sigmoid(7 + Jn + h 16), and this goes to - that is, there is a carry-over if the sum of the inputs and the carry-over from the previous time step is large enough). In Ap- pendix D we show more precisely that the network assigns a probability of ,999 or above to the correct output under all cireumstances.
Again, the task is learned very well and in a readable fashion. None of the comparison RNNs that we consider do as well, coherent with observations made above. To our knowledge no other RNN has been proven to hold a carry-over in memory for an unbounded number of digits, i.e. to perform general addition of any arbitrary pair of numbers.
CONCLUSION
We presented learner, building on several different lines of work in the literature, that traverses complex space of RNNs varying in both weights and architectures, in search of the network that has the minimal description length. We tested our learner on a range of sequential tasks and compared to various RNNs from the literature. We found that our learner arrived at networks that are reliably close to the true distribution across tasks and corpus sizes. In fact, in several cases the networks achieved perfect scores. Moreover, the networks lent themselves to direct inspection and showed an explicit statement of the pattern that generated the corpus. The RNNs from the literature, on the other hand, were not just opaque but also generally performed much less reliably on the test corpora.
In current work we attempt to extend the present paper several directions. For example, we are extending the range of generating patterns for our corpora, including dependencies from linguistic domains not considered here, such as phonotactic patterns. We are also considering training cor- pora that are more challenging than the ones used here in terms of size (using training corpora that are even smaller than the ones used here), noise (corrupting the training corpus using various noise patterns), and generating distribution (deviating from the simple generating distributions used here, which supported a direct comparison of simulation results with the true distribution but are overly simplistic). We also working on extending the learner in terms of allowable units and connec- tions. An obvious question is whether the GA search can be sufficiently efficient to support MDL, least on relatively small corpora; we take the current results encouraging in in this regard.
subtraction (100% accuracy), but fails to do five digits (less than 10% accuray)." Chuan Li, DDemystifying GPT-3', https:://aamiee
com/ommm/////oo og/ demyst wiinmnttttyynnn -ying-gptn3333 3/
8

---

Under review as a conference paper at ICLR 2021
More formally, we estimate that the computational power needed to train an MDL learner should not exceed that of a regular RNN through backpropagation
Beyond these technical extensions, are interested in connecting the present work more tightly with experimental results on parallel human biases and generalization preferences. MDL predicts very inclusive generalizations for small training corpora, with narrowing the corpus grows. Non- regularized RNNs do not make this prediction, and standard regularization schemes, which lower the values of weights but not the number of units, still predict time courses for generalization that differ from those of MDL. Another way to put it is: different learners come with different biases, biases which ought to be more visible with small training sets, and one question is how these biases relate to those of human learners. This question can be asked experimentally by looking at how human subjects generalize from very small corpora (see, e.g., Xu & Tenenbaum 2007 for such a comparison in a slightly different setting). Beyond the comparison of MDL with alternatives that do not rely on similar balance between simplicity and goodness of fit, we would like explore more detailed kind of comparison within the family of MDL models. Since the MDL score depends on the primitives that are provided and their given costs, is possible to reason about different choices of primitives and costs in view of human generalization (see Piantadosi et al. 2016).
REFERENCES
Panagiotis Adamidis. Review of parallel genetic algorithms bibliography. Aristotle Univ. Thessa- loniki, Thessaloniki, Greece, Tech. Rep, 1994.
Fardin Ahmadizar, Khabat Soltanian, Fardin Akhlaghian and Ioannis Tsoulos. Artificial neural network development by means of novel combination of grammatical evolution and genetic algorithm. Engineering Applications of Artificial Intelligence, 39:1-13, 2015.
P.J. Angeline, G.M. Saunders, and J.B. Pollack. An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 5(1):54-65, 1994.
Jon Barwise and Robin Cooper. Generalized quantifiers and natural language. Linguistics and Philosophy, 1111592299 1981.
Robert C. Berwick. Locality Principles and the Acquisition of Syntactic Knowledge. PhD thesis, MIT, Cambridge, MA, 1982.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models Few-Shot Learners. arXiv:2005.1 14165 arXiv: 2416.1
[cs], July 2020. URL http::///aaivvii arxiv. org. /bs
abs / attla/abs//C.../ 22000 14165
Erick Cantú-Paz. A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et sys- tems repartis, 10(2):141-171, 1998.
Gregory J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the ACM, 13:547-569, 1966.
Carl de Marcken. Unsupervised Language Acquisition. PhD thesis, MIT, Cambridge, MA, 1996.
Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):199-211, 1990.
Adam Gaier and David Ha. Weight agnostic neural networks. CoRR, abs/1906.04358, 2019.
F.A. Gers and E. Schmidhuber. LSTM recurrent networks leam simple context-free and context- sensitive languages. IEEE Transactions on Neural Networks, 12(6): 1333-1300, November 2001. ISSN 1941-0093. doi: 10.1109/72.663769. Conference Name: IEEE Transactions on Neural
Networks.
"Our MDL learner is trained over 1000 generations, each with 2000 individuals, with a single feedforward pass for each. Overall, this represents 2M feedforward passes, with no backpropagation step and presumably significantly smaller networks (so, faster feedforward passes).

---

Under review as a conference paper at ICLR 2021
C. Lee Giles, Guo-Zheng Sun, Hliing-Hen Chen, Yee-Chun Lee. and Dong Chen. Higher order recurrent networks and grammatical inference. In D. S. Touretzky (ed.), Advances in Neural 1990.
Information Processing Systems 2. pp. 380-387. Morgan-Kauffmnn
David E Goldberg and Kalyanmoy Deb, A comparative analysis of selection schemes used in genetic
algorithms. In Foundations of genetic algorithms, volume 1, pp. 69-93. Elsevier, 1991.
Scott Gordon and Darrell Whitley. Serial and parallel genetic algorithms as function optimizers. In ICGA, pp. 177-183, 1993.
Peter Grünwald. minimum description length approach grammar inference. Stefan Wermter, Ellen Riloff, and Gabriele Scheler (eds.), Connectionisl, Statistical and Symbolic Approaches to Learning for Natural Language Processing, Springer Lecture Notes in Artificial Intelligence, pp. 206.216. Springer, 1996.
John H Holland. Adaptation in natural and artificial systems. introductory analysis with applica- tion to biology, control, and artificial intelligence. Ann Arbor, MI: University of Michigan Press, pp. 439 444, 1975.
James Horning. A Study of Grammatical Inference. PhD thesis, Stanford, 1969.
Henrik Jacobsson. Rule extraction from recurrent neural networks: A taxonomy and review. Neural Computation, 17(6): 223-1263,, 201 4/07/01 2005.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference of Learning Representations (ICLR), 2015. URL https://erxiv.crgg abs/
1442. 6980
Andrei Nikolaevic Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission (Problemy Peredachi Informatsii), 1:1-7, 1965.
Ming Li and Paul Vitányi. Chapter 1.4, Binary Strings. In An Introduction to Kolmogorov Com-
plexity and Its Applications, Texts Computer Science. Springer New York, New York, NY, 2008. ISBN 978-0-387-339988 wwt.
doi: 10. 100100779978-03338---83----- URL http://...ppppggrr.oooooo/111/00 1ttp://0000000777------------880
978-0-387-49820-1.
Geoffrey F Miller, Peter M Todd, and Shailesh U Hegde. Designing Neural Networks using Genetic Algorithms., volume 89. 1989.
David J Montana and Lawrence Davis. Training feedforward neural networks using genetic algo- rithms. In IJCAI, volume 89, pp. 762-767, 1989.
Denis Paperno. Learnable classes of natural language quantifiers: Two perspectives. Ms., UCLA, December 2011.
Nicolas Papernot and Patrick McDaniel. Deep k-Nearest Neighbors: Towards Confident, Inter- pretable and Robust Deep Learning. arXiv:1803.044 04765 [cs, stat], March 2018. URL http: //arxiv. wtt.oo/ggaaaa/o/oooe /1803 04765
arXiv: 1803.04765.
Steven T. Piantadosi, Joshua B. Tenenbaum, and Noah D. Goodman. The logical primitives of thought: Empirical foundations for compositional cognitive models. Psychological review, 123 (4):392-424, 07 2016.
Jorma Rissanen. Modeling by shortest data description. Automatica, 14:465-471, 1978.
Jürgen Schmidhuber. Discovering neural nets with low Kolmogorov complexity and high general- ization capability. Neural Networks, 10(5):857-873, 1997.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 61(0): 85-117, 2015.
Ray J. Solomonoff. formal theory of inductive inference, parts and II. Information and Control, 7(1 & 22:1-22, 254, 1964.
10

---

Under review as a conference paper at ICLR 2021
Andreas Stolcke. Bayesian Learning of Probabilistic Language Models. PhD thesis, University of California at Berkeley, Berkeley, California, 1994.
Hans-Joerg Tiede. Identifiability in the limit of context-free free generalized quantifiers. Journal of Language and Computation, 1(1):93-102 10299------11 1999.
Qinglong Wang, Kaixuan Zhang, Alexander G. Ororbia II, Xinyu Xing, Xue Liu, and C. Lee Giles. An empirical evaluation of rule extraction from recurrent neural networks. Neural Computation, 30(9):2568-259) 2020/06/12 2018.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In Proceedings of the 35th International Conference on Machine Learning. 2018.
Whitley, T Starkweather, and C Bogart, Genetic algorithms and neural networks: optimizing connections and connectivity. Parallel Computing. 14(3):347-361, 1990.
Fei Xu and Joshua B. Tenenbaum. Word learning as Bayesian inference. Psychological review, 114 (2):245-272, 2007.
Byoung-
Syoung-Tak Tak Zhang and Heinz Mühlenbein. Evolving optimal neural networks using genetic algo- rithms with Occam's Razor. Complex Systems, 7(3):199-22 1200200 1993.
Byoung-Tai Tak Zhang and Heinz Mühlenbein. Balancing accuracy and parsimony in genetic program- ming. Evolutionary Computation, 3(1):17-38, 2020/07/11 1995.
A NETWORK ENCODING
A network consists of U units, U activation functions specified for each unit, and C' connections (including bias connections). In order to represent a network as a binary string, the following serial- ization scheme is used.
A.1 NODES
The number of nodes in the network affects its overall encoding length both explicitly and implicitly when is used encode other components: node numbers are used when specifying connection sources and targets, and so larger numbers require more space; and more nodes require more activa- tion functions to be specified.
Since the number of nodes varies from network to network, their string representation cannot be of fixed length. To ensure unique readability of network from its string representation we use prefix-free code.
Here and throughout this section we encode integers into bit-strings using the prefix-free encoding from Li & Vitányi 22008:
E(n) = 11111...1111
1010...010
Unary encoding of logen
Separator
logan
Thus for an integer n. its encoding length would be 2[log2n] + 1, and the total encoding length for all units in network would be [2[[logen] + 1).
A.2 ACTIVATIONS
For set of A possible activation functions and U units, the encoding cost for specifying all ac- tivations U A[oogA]]. Since is constant throughout the simulation no prefix-fre encoding is needed.
11

---

Under review as a conference paper at ICLR 2021
A.3 WEIGHTS
To simplify the representation of weights in neural networks and to make it easier to mutate weights incrementally in the genetic algorithm, we represent each weight as fraction made of a sign (plus/minus) and integer numerator and denominator:
D
This be serialized into bits using the following conversion and the integer encoding scheme presented above. For example, the weight wij = + would represented as:
E(2) 10... 10 1110...11
And its encoding length [ayl would be the sum of:
bit for the sign.
2 No + bits for the numerator
2 Toga D bits for the denominator.
A.4 CONNECTIONS
connection Gy consists of source unit a target unit j and a weight way. can thus be encoded
as:
(())))))LE(N,,))) (()))))
A.5 EXAMPLE
We'l ll encode the following network which consists of three units, two connections, and weights: 0.5 and
2.0.
Linear 0.5
Sigmoid
2.0
Linear
The final representation for this network is:
Note that F.(U) is prefixed to the string make it possible parse the activation part correctly.
12

---

Under review as a conference paper at ICLR 2021
11011 (3)
00 00
10 00..
01..01
101..011
0..11
Iin lin.
Encoded Network
B GENETIC ALGORITHM
The genetic algorithm implementation for our model comprises three main components: a popula- tion representation scheme, selection scheme and recombination scheme. We describe here the implementation choices made for each component.
The algorithm is initialized by creating population of N random neural networks. Each network is initialized by randomizing the following parameters: number of hidden units, activation function for each unit, the set of forward and recurrent connections between the units, and the weights of each connection. In order to avoid an initial population that contains mostly degenerate (specifically, disconnected) networks, output units are forced to have at least one incoming connection from an earlier unit.
The number of hidden units and the weight numerators and denominators are randomized from geometric prior (p = 0.5) to reflect their fitness based on the MDL metric.
The algorithm is run for generations, where each generation involves selection step followed by recombination step. During selection, networks compete for survival on to the next generation based on their fitness. network's fitness is the inverse of MDL score. We use Tournament Selection (Goldberg & Deb 1991). selection method which approximates exhaustive ranking of the population by selecting random subsets the population of size t and then selecting the best individual from each subset; this process is repeated N times to select
population with repeti- tions. The approximate nature of tournament selection prevents premature convergence by allowing less-than-optimal individuals to survive, and the same time alleviates the computational load of the selection step by lowering its run time from (NNoogN) to O(N).
Out of the selected population, N offspring networks are created through either mutation or crossover with other networks. A network is mutated using one of the following operations:
1. Add/remove a unit.
2. Add/remove forward or recurrent connection between two units.
3. Mutate connection by incrementin/ddccrmmnntng its weight's numerator or denominator, or by flipping its sign.
4. Replace a unit's 's activation function with another.
These mutations make possible to grow networks and prune them when necessary, and to poten- tially reach any architecture that can be expressed using building blocks.
Two networks can also be crossed-over to create an offspring network, potentially allowing networks who perform well on different aspects of the task share their 'genes' and create network that performs as well as its two parents combined. We cross-over two parent networks by constructing network which feeds the networks in parallel and averages their outputs. While this creates larger network which is penalized by the |G] term, this has the potential to create an offspring which performs better than its parents on the DD Gl term and can be pruned later. Networks are randomly selected for mutation and crossover by probabilities Pinutation and Perossouer.
top of the basic genetic algorithm we use the Island Model (Gordon & Whitley 1993 Adamidis 1994 Cantú-Paz, 1998) which divides larger population into 'islands' of equal size N. each run- ning its own genetic algorithm as described above. Once every minterval generations, a migration step occurs during which the mratio top networks of each island are sent to another island in round- robin fashion. At the receiving island, the lowest-ranking networks are replaced with the incoming migrants. The island model makes it possible to parallelize the algorithm by running each island on a different processor, while also mitigating against premature convergence, which often occurs when using large populations.
13

---

Under review as a conference paper at ICLR 2021
The simulation ends when all islands complete g generations and the best network from all islands taken as the solution.
All simulations reported in this paper the following
10
N 2, 000
islands 72
Pmutation = 0.9
Perossouer = 0.1
= 000
myatio 0.1
Mintersal
C
PROOF THAT THE NETWORK FOUND FOR c" IS ACCURATE
The table below shows the activation values of output units and the respective probabilities of each output class (columns) after the network is fed with one of the possible sequence inputs (rows).
Given a valid a" sequence, it can be seen that the accuracy is 100% (except for the last of the A's, where the prediction is probabilistic) and that confidence is over 91% in all cases (for n 1; for n >= confidence rises, at 95% for π 2).
Inputs / Outputs
B
C
#
#
1/2
0
0
0
(activations)
0
O
(probabilities)
1t A
1/2
1/16
-5k
O
(activations)
0
(probabilities)
th B
sig(-16)
1/64
5(k-n)+.177
0
(activations)
(k < n)
.000007
0. 0.999993
0
(probabilities)
th
sig(-16)
1/64
.17n
(activations)
< 10-6
0.085
.91
0
(probabilities)
hth
sig(-16)
.17(k-k)
0.009
(activations)
(k < n)
< 10-6
.0.994
0.0053
(probabilities)
nt
sig(-16)
0
0,009
(activations)
0.000125
0
0.999875
(probabilities)
D PROOF THAT THE NETWORK FOUND FOR ADDITION ACCURATE
Consider the network in Fig. Call i, and jn the inputs at time step n, hn the output of the hidden cell (in gray) and on the output the output cell.
At every time step n, (i) hn is the carry-over (0 1), with margin for error for this carry-over of Ezo .0013 (that is, fa, is in [0, 6.n] the carry-over is 0, and in [1 6cn- if the carry-over is 1; (ii) on is correct with margin of error -001, that is o, is below .001 if the nh digit of the sum is 0, and above .999 if is 1.
Proof. Note first that the network is such that:
hnp = sigmoid 16),
On xx,
4sigmoid(7:.. 16).
All simulations on AWS c5. 18xlarge machines with 72 vCPUs each (3.0 GHz Intel Xcon).
14

---

Under review as a conference paper at ICLR 2021
with Zn in + In + hn-1-
From there, the theorem is proven by induction. The initialization step can be easily checked (NB: h-1 is set to 0 by convention). Suppose the result holds for Then: In+1 [0, ccol U Eco: + 6col [2 - Eco, 2 + Eco] U [ - Eco, 3].
The fact that the result holds at the next time step can be proven graphically (it can also be proven analytically, e.g., using the continuity and local monotonicity of the relevant functions):
The left hand side of the following graph shows that fn+1 stays within error margin Ego .00013, and takes the appropriate value: in binary notation, the carry-over should be if In+1 (the sum of the current inputs and the carry-over) is 1, and should be 1 if Øx+1 is 2 or 3.
The right hand side shows that On+11 is correct and stays within the error margin .001: on+1 should be if Fn+1 is or (a null unit digit here because is in binary notation), and 1 if 2n+1 is 1 or 3 (in binary notation: and 11).
0,00013
0.001
hidden (n+1)
output(ne1)
0.000
-0.001
0.00000
0.00013
0.00000
0.00013
x(n+1)
x(n+1)
0,00013
1.000
hidden (n+
0.999
0.99987
1.00013
0.99987
1.00013
x(n+1)
x(n+1)
0.001
hidden (n=1)
output/n+1)
0.000
0.99987
-0.001
1.99987
2 2.00013
1.99987
2 2.00013
x(n+1)
x(n+1)
hidden (n+1)
0.99987
0.999
2.99987
3.00000
2.99987
3.00000
x(n+1)
x(n+1)
E CROSS-ENTROPY
15

---

Under review as a conference paper at ICLR 2021
identity(10]
identity[20]
identity[50]
identity[100]
previous character(10)
previous character[20]
previous character(50)
previous character[100]
exactly 1[100]
exactly 1[200)
exactly 1[500]
exactly 1[1000]
exactly 3[100]
exactly 3[200]
exactly 3[500]
exactly 3[1000]
Task [size of training set]
exactly 5[100]
exactly 5[200]
exactly 5[500]
exactly 5[1000]
least 1[200]
least 1[500]
at least 1[1000)
least 3[200]
at least 3(500)
at least 3[1000]
at least 5[200]
least 5[500]
at least 5[1000]
between and 6[100]
between and 6[200]
between 3 and 6[500]
between and 6[1000]
an [__0n[10]+
[n__n[100]
an [___n_cc[10]
addition[10]
MDL learner
addition[15]
RNN learners
addition(20)
uniform baseline
optimal baseline
0.0
0.5
1.5
2.0
2.5
Cross-entropy [normalized]
Figure 6: Cross-entropy of different learners across all the tasks presented here. For easier visualization, the cross-entropy is normalized (divided) by the cross-entropy of learner predicting uniform probability for all outputs. other extreme, the green line represents an optimal baseline as cross-entropy which would have captured the underlying task perfectly well. The gray lines represent the various RNN competitors, and the blue line is the MDL leamer. The x-axis distributes the various tasks (identity, previous character, addition, exactly least between and a b", a²b"""), for increasing sizes of the training Corresponding numbers given Appendix
learner
16

---

Under review as a conference paper at ICLR 2021
F FULL RESULTS
17

---

Under review as a conference paper at ICLR 2021
Unitoom
haseline
1000
1000.00
1000 00
1000.00
1000 00
1000.00
1590121
1500 21
1500.31
1577
1577
1577 04
1577.01
1587 007.51
1587.5 037553
1557. 03
1507 03755
158 79
1581 79
1581 70
1509
1580
1589 11
1581. 70
158
1581.79
1580.2
1580.21
1580.21
1580121
33005
33084.51
61622 (0)
61622 00
6250000
6250000
62500000
Opnimall boselline
0.00
0.00
0.00
0.00
0.00
0.00
0.00
00
957 00
967 00
987
965 00
965 00
965 00
963 00.00
089 00
989 00
909 00
989.00
1345 47
1345 47
1345 47
1168
116841
1168 41
1
1
1
1159.0
11:9.05
1159.0
1159.03
4680. 38
4680.36
4080 38
4880. 38
0.00
0.000
MUX
Jcumer
6.00
0.00
0,00
0,00
21
1292.76
997.24
00
141805
1231 39
1015-00
1367.3
133689
1170
1147.3
19
145837
134..6
1395,9
1230039
1337 42
11886477
1180447
1.866.1
1175.24
1176.43
4755.00
1455006
4987338
173.0P
Table 2: Cross-entropy of different learners across all the tasks presented here. The winner with the lowest cross-entropy (without considering the high and low baselines in the last two columns, of course) is in bold for each task (row).
1368
1394
9523
128
8.000
1,90
159 78
0.54
5148, 17
0.14
8918 52
6002 09
30
1305
6309
7855.11
6618 57
22H0
40
8305 14
2073 05
8 09
$420.10 10
357 02
7218.72
7912.91
2533
7515 30
3406. 04
9:92 35
6234 22
13300 39
112566 88
14383 72
4530.27
500496
2554335.21
32
3004
2.300 09
0.18
0.11
157. 72
0.10
7564 87
5236 51
4525.85
6002 06
4502 45
4354 36
2073
7862
8953 01
2123 65
8013 37
3939 20
5929 72
7399 21
1231
4719 92
5307
1391 52
7210-70
3306
1369 10
26508 87
9V02 64
4873 24
70055 53
567813.55 57
LSTM oells
231-71
4.00
1.28
5.26
360
1168 14
1.44
5003 09
2009 95
5000 92
1076 22
5-15
2023 80
17
6223.99
2543 35
1233.24
2773
2508 96
1491 10
1448
1330
2538 95
1218 54
4838
1508 S1
1233 91
11907..0 03
7866 55
5505. 36
24M55..0 06
14128
149.06
8 .8
8.76
473 53
100.00
1477.66
1385 69
1076 33
1038
4790.37
1234 36
1108 50
1082
4506.17
1021
1051 10
2173
1689 00
1967 12
1253.7
1251
2593 12
1395
1145.88
9238 .0
1972
125L-77
1223 72
5086673
5981.0
11188 59
10692 51
214553 36
401933.11
128
$35.00
25.00
0.17
0.04
5.98
0.02
0.00
7406
6990.5
5767.5
39
6501 10
B421 044
6009 02
8184
8683
6010 26
9523
8611.2 25
2393
8502.03
8227.0
2884
K373
7106.91
10198.2
-21 1/1.22
143492
8,0099.7
3244.52
5563.36
508344455
2112842:11
2286763.7 79
32
20440 090.09
77.00
0:40
0.
7522.49
0.81
0.03
0.03
6540
6321 99
4000
4397.
7176600
6391 01
4015.54
5162
6557.7
3022
863022
6357
0046
8995 08
8000 45
10265
5050.3
1346.05
7826.00
7369.45
1876
40007.00
3982.8 92
5796.00 89
1403211 1.55
435025.44
68919.80
CRRU calls
1636 S4
1.87
1.77
1.81
1900.5
0.37
0.00
1.85
50R0
1701 06
1155
1012.29
5247.
2124.05
1152.35
1675
1417.12
1077.5
82
1899 24
1472.74
2099
1330
1253.53
1978:74
1299.03
1237.54
5079.9 49
1552.33
1276.21
21075.00
9091
11392.14 14
8553.01
116119.88
168882.9
1189.76
3
1:13
17.04
2221 1:9
7.28
2393.00
15538-06
102
6806221
4070.21
999.50
3636.17
1753.08
1513373
101254
1705
1476.6
158545
2255.8
1274.88
118633
156838
1222
1169.10
5573226
119736
L177889
9527.16
1482113
14119233
15096244
75522007
128
9557.24
2151.76
0.20
0003
11777.00
5418.02
$4,38
703375
6557.55
1439.22
1689.50
7509.59
71 7156.00
2VS3
127661
88-22.9
1701.0
2641 66
3319.78
13922.2 78
8175,99
514.51
1350.10
7172.70
96
13:58844
225 0033
20329:44
9077161
1,00415,744
091198619
222113
0.50
0.72
0.17
0.8
7,20.30
8508 10
2745.11
5833.0
9623.23
25966001
300701
963.66
94477.00
592418
2368.24
11890.30
255 196
1626.05
7794.88
1360:03
$12452
188136
5996 19
152083
1358.50
9000
6872.13
1706665
8158.20
140215926
335996-33
542.
1303
Elman cals
1,50
1,40
1.40
L.71
1.83
1.89
3648-33
1529
$192.52
433955
2108
1039.35
9999.7
3388.2
1598 13
1009
1062.39
2571.8
1373-1
4408.00
135051
119452
1799900
1185.05
2746.98
2172.33
1221,87
1198.1
$721.00
S90157
12297.35
13558.35
1299ENS
9050.19
92.92
4.30
4.20
20.80
524 20
08
1938 60
10MA 25
1094
1636-3
1510 19
1125-4
1095.00
2927
1233.97
1133.30
1006
1509 11
1363
1965 09
1236.46
1205 68
1M22 21
1664
1835
1211 RL
1195.4
1633 92
21251
14903. 12
170722 13
164312.59
Soq. length
Networ
Units
100
20
50
100
200
500
100
200
500
100
200
500
200
500
1000
500
1000
200
500
1000
100
500
1000
10
100
Corpus
Meniiiy
domncer
epcelyy
cooelyy 3
between
3 and
an ho.cn
addition
18


Reviews:
[{"review_id": "xCGOFHrFxqK", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe authors proposed a new training framework for recurrent neural networks that involves updating the weights with genetic algorithm under a minimum description length principle. They evaluated it on a syntheic mini task of languange modeling and showed a better performance over classical RNNs trained by backpropagation.\n\n\nStrength\n\n+ it is a good thing to read about alternative approach to backpropagation in training deep networks.\n+ tackling the interpretablity issue of deep networks with symbolic knowledge is a great approach. \n+ the problem of generalization in recurrent networks is an important topic to study.\n+ As in the discussion section, this line of research has great potential in future extensions if implemented and understood well.\n\nWeakness\n\n- the previous work offers an intriguing task on the historical attempts in applying genetic algorithms and MDL principles in neural networks. However, it would be better if what works are done in these related work. For instance, the authors wrote \"These challenges were already taken up by early work on XXX\", but failed to say how they tackled these challenges. \n- the technical sections are very hard to follow. It is hard to decode in section 3 how the algorithm work. Although mentioned some details on the genetic algorithm in the Appendix, the main text should be self-contained. \n- Following the previous point, how is the MDL metric computed exactly? Is it a bitwise estimation? If so, is the RNN here merely a boolean network?\n- Why is the task descriptions in section 3.5 placed in the \"Learner\" section? And why are some results also included here in the method section? The writing needs some improvement to increase clarity and structure.\n- Still this section, \"Again, this network is transparent, the task is learned perfectly well, and no RNNs would do as well.\" Would the author mind explaining where this is coming from?\n- The result section is also lack of important details on the tasks and evaluations. Unlike section 4.3 where the experiments are adequately introduced, the setup in section 4.1 is far too brief for the authors to grasp the task (especially if it is not usually used in the field). \n- table 4.4. the cross entropy of MDL model is quite close with the best RNN in all tasks except addition (where MDL model kills) and a^nb^nc^n (where MDL model sucks). This could indicates an coincidence -- did the authors run multiple runs with different random seeds? (the plots in the appendix suggests that they only ran once).\n\n\nSummary\n\nOverall, the project introduced an interesting approach with great potential, but the results and writing appear to be preliminary. We suggest the authors to add more evaluations and improve the writing.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_vUn7TRwMpQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an approach to training recurrent neural networks with the mix objective of minimizing cross entropy (or something similar, which is not clearly defined) and minimizing minimum description length (MDL) by using a binary representation of the network which is optimized with a genetic algorithm. The model is evaluated in contrast to RNN, GRU and LSTM  baselines on modelling a number of formal languages.\n\n- (+) MDL is a powerful inductive bias which has been explored extensively in Machine Learning and Pattern Recognition, and it is interesting to see it revisited in the context of neural networks and in contrast to deep learning models.\n\n- (+) The paper exhibits numerous examples in which the presented system produces simple hypothesis to model (also relatively simple) data.\n\n- (-) Nonetheless, the studied tasks are good for a start, but insufficient to motivate the approach because actually neural networks can deal with them quite well [e.g., 1]. Moreover, the claims about the binary addition experiments are notably flawed. In particular, the task that is considered in this paper involves two bit sequences that are fed *bit by bit* in parallel to the system. This poses no serious challenge to no RNN, and in fact you can find example code directed at students that solves this task: https://github.com/mineshmathew/pyTorch_RNN_Examples. (I have personally tried this code on the same setup of using sequences of up to 20 bits and evaluating on a test set of up to 250 bits with 100% accuracy -- It only required updating a few lines to more modern versions of python/pytorch and changing the loss to BCE). The version of binary addition which is actually more challenging for RNNs is when the output is produced _after_ all operands are given [2]. Nonetheless, other neural network architectures deal with this task effectively [3].\n\n I can see two directions in which this work could be improved moving forward:\n\n   - If the goal is to improve interpretability of models, the authors could aim at tackling problems in gradient-based neural network remain obscure (e.g. see https://blackboxnlp.github.io/)\n   - If on the other hand the goal is improving generalization, the authors could consider tackling tasks in which neural networks have been shown to be deficient in their generalization skills [2].\n\n- (-) Furthermore, RNN baselines might not be properly trained across the paper. First, as mentioned in the previous point, RNNs can in fact learn the binary addition task, and thus it is unclear why the authors report that they fail. Second, the authors report that the RNNs perform worse than chance on some other tasks, which could be explained by divergent training. Since no code was provided it is not possible to assess how the models were trained.\n\n- (-) The authors enumerate some works related to theirs, but they do not comment in which ways they are similar or different from theirs.  Also, given that whole books have been written on the MDL principle, the related work section could be considerably more detailed. The relation to neural architecture search (NAS) is missing too.\n\n- (-) It is also unclear how the training objective is quantified. It is only mentioned that |G : D| relates to cross-entropy, but no precise definition is given, nor it is detailed in which ways it differs from the former.\n\n**Questions for the authors**\n\n1) Do the addition RNN models reach 100% accuracy on the training data?\n\n2) The cross-entropy numbers are quite high for binary classification problems. Could you report how you computed them?\n\n3) For the test data you mention that you test the model on \"an unseen sequence of length X\". By \"an unseen\" you mean 1 sequence?\n\n4) Regarding footnote 7, why not properly quantifying the number of operations needed to train each type of model?\n\n**References**\n\n[1] Weiss, Gail, Yoav Goldberg, and Eran Yahav. \"On the practical computational power of finite precision RNNs for language recognition.\" arXiv preprint arXiv:1805.04908 (2018).\n\n[2] Joulin, Armand, and Tomas Mikolov. \"Inferring algorithmic patterns with stack-augmented recurrent nets.\" Advances in neural information processing systems. 2015.\n\n[3] Kaiser, Łukasz, and Ilya Sutskever. \"Neural gpus learn algorithms.\" arXiv preprint arXiv:1511.08228 (2015).\n\n[4] Lake, Brenden, and Marco Baroni. \"Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.\" International Conference on Machine Learning. PMLR, 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_5g5ZpJVMxX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper describes a method for training neural network based on\ngenetic algorithms that minimizes the minimum description length\n(MDL). The aim of the study is to obtain smaller, explainable networks\nthat learn generalizations from sequences. The paper shows that the\nprocedure, indeed, learns compact and interpretable networks\nrecognizing a number of (artificial) formal languages, as well as\naddition. The networks are also compared to common RNN models\ntuned/trained on the same task, indicating that the networks\ndiscovered by MDL outperforms RNNs in majority of the experiments.\n\n\nAlthough study uses well-known methods (MDL, genetic algorithms), the\napplication and premise is interesting. Without doubt, both smaller\nand explainable models are good, and the paper demonstrates this\nnicely with the included experiments. It is not specific to the\nparticular study, but strengths of the method also include learning\nstructure of the network as well as its weights and possibility of\nlearning a larger class of network architectures.\n\nMy main criticism likes within two aspects of the paper/study:\n\n- Although the authors touch upon this in the concluding remarks, I'd\n  be interested to see a more through proof or demonstration of\n  scalability of the method. All the experiments provided can be\n  solved by relatively simple networks. With increasing problem\n  complexity, the networks size (as a result its encoding) and the\n  number of alternative networks to test before finding a solution is\n  expected to increase as well. In short: the usability of the method\n  would be more convincing if one of the problems had a larger\n  alphabet, and less well-defined solutions (e.g., a linguistic\n  problem as elaborated by the authors).\n\n- I was very surprised to find the description of the proposed\n  method/model in an appendix. Although the method is relatively\n  straightforward for most ICLR audience, I thin the paper needs a\n  reasonably detailed description of the method in the main text. If\n  the space is the issue here, one can shorten the descriptions of the\n  artificial language experiments, or even push part of them to an\n  appendix.\n\nI also have some minor remarks/suggestions:\n\n- From the description in the paper, I am not sure if the baseline\n  RNNs got the same care and love as the proposed system. If not tuned\n  properly, it would not be surprising that they do not necessarily\n  perform well. For example, for these simple problems there is a fair\n  chance that at 1000 epochs some of the networks badly overfit. Hence\n  while comparing the method with RNNs the study may be basing the\n  conclusions on weak baselines.\n\n- Similar to some of the points noted above, I'd be also interested to\n  see more discussion/comparison with (L1) regularized learning.\n\n- Some readers may benefit from a better description of the network\n  representation in the figures. For example, it is not clear to me\n  what an output unit with no input produces (assuming that there is\n  an intercept/bias term, but an explicit remark would be useful).\n\n- A few typographic/language suggestions/issues:\n\n    - Footnote marks should go after punctuation (e.g., footnote mark\n      2).\n    - The fonts on figures are sometimes unreadably small, and\n      resolution is not optimal (especially fig. 6 in the appendix,\n      but others may also benefit from high-resolution or vector\n      graphics).\n    - Aligning numbers in table 1 properly would increase their\n      readability.\n    - The color choice on figures (although it did not seem\n      significant) was not kind to this color blind reader.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-qXy79O-55", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The importance of finding minimum description RNNs is definitely unquestionable for several reasons. Thus the authors address an important problem. They decide to use GA in order to find such a representation. \n\nMy main reservation is that the paper is a vanilla application of GA without any enhancements or tailored aspects. In other words, I can't find methodological or algorithmic contributions. The experimental results also don't stand out. The tasks selected are all artificial (learning mathematical operations). To this end it would be great to include some practical cases. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Rather than using backprop to train RNNs, this paper explores instead using GA's to train them along with an extra Minimal Description Length objective to search in the space of the simplest possible networks that can perform the task at hand. They demonstrate that the method can indeed find minimal RNNs that, when trained even on small corpus dataset of formal languages can generalize beyond the training data.

Most reviewers and myself agree that this work is really interesting, and also refreshing to see a new approach compared to the typical way of doing things. However, as we can see in the reviews, the work is not at the level of an ICLR conference submission at this point. R1, R3, and R4's reviews breaks down the points of the papers into strengths and weaknesses, and I am inclined to believe that if the authors spend more time to try to address the weakness and improve the work, this can be a great paper in the future. Although R3 gave a score of clear reject (which is too low IMO), and the authors responded to their points, I'm inclined to believe that this work warrants another revision.

Specifically, reviewers (and myself) believe that the baseline methods can indeed perform better than reported. And while, for a novel method, we don't expect the approach to scale to SOTA approaches for sequence modeling, it would improve the work vastly if there is evidence to show that it can scale to larger tasks, and give an impression that there can be a roadmap of attacking larger problems that standard methods can currently handle.

Currently, I would say the work is a great workshop paper, but would encourage the authors to continue to consider the feedback given here to work on a future revision.
Decision: Reject