Towards Modular Algorithm Induction
Authors: Daniel A. Abolafia
Rishabh Singh
Manzil Zaheer
Charles Sutton
Venue:  (2020)
Keywords: algorithm induction
reinforcement learning
program synthesis
modular

Abstract: We present a modular neural network architecture MAIN that learns algorithms given a set of input-output examples. MAIN consists of a neural controller that interacts with a variable-length input tape and learns to compose modules together with their corresponding argument choices. Unlike previous approaches, MAIN uses a general domain-agnostic mechanism for selection of modules and their arguments. It uses a general input tape layout together with a parallel history tape to indicate most recently used locations. Finally, it uses a memoryless controller with a length-invariant self-attention based input tape encoding to allow for random access to tape locations. The MAIN architecture is trained end-to-end using reinforcement learning from a set of input-output examples. We evaluate MAIN on five algorithmic tasks and show that it can learn policies that generalizes perfectly to inputs of much longer lengths than the ones used for training.

Under review as a conference paper at ICLR 2020
TOWARDS MODULAR ALGORITHM INDUCTION
Anonymous authors Paper under double-blind review
ABSTRACT
We present modular neural network architecture MAIN that learns algorithms given set of input-output examples. MAIN consists of neural controller that in- teracts with a variable-length input tape and learns to compose modules together with their corresponding argument choices. Unlike previous approaches, MAIN uses a general domain-agnostic mechanism for selection of modules and their ar- guments. It uses general input tape layout together with a parallel history tape to indicate most recently used locations. Finally, it uses a memoryless controller with length-invariant self-attention based input tape encoding to allow for ran- dom access to tape locations. The MAIN architecture is trained end-to-end using reinforcement learning from set input-output examples. We evaluate MAIN on five algorithmic tasks and show that it can learn policies that generalizes perfectly to inputs much longer lengths than the ones used for training.
INTRODUCTION
Many applications in artificial intelligence require the ability learn and perform tasks that have algorithmic structure, such as learning a sequence of precise actions together with conditional de- cisions and branching. Therefore, an important research problem is learning to induce algorithms from input-output examples. A particular focus of research attention has been on neural algorithm induction, which are neural architectures for representing algorithms by including unbounded inter- mediate state and mechanisms for learning control flow. The neural Turing machine (Graves et al.) 2014) and its successor the Differentiable Neural Computer (Graves al. 2016) augment a re- current network with an external memory using differentiable read/write mechanisms, and are able to learn simple algorithmic tasks such as array copying and sorting. Neural Random-Acces Ma- chines (NRAM) (Kurach et al.) (2166) learn algorithms by generating fuzzy circuit comprising of pre-defined modules together with modules for dereferencing and storing values a fixed memory.
Existing architectures do not fully leverage key fact that algorithmic tasks can be solved by flexibly combining the results smaller, reusable procedures, which we call modules. modular architec- ture aims to represent in learning system these aspects of programming languages intended for human developers: (i) procedural abstractions that perform computations to produce outputs given some inputs and that can be reused in the algorithm multiple times; (ii) control flow constructs such as branching and loops to compose and combine intermediate results. Although there has been recent movement toward modular neural architectures for supervised tasks (Andreas et 2016 Kirsch et al. 2018; Rosenbaum et al. 2018 Valkov et al,, 2018 Chang et al.) 2018), the design space of modular networks has not been fully explored for algorithm induction.
Towards this end, we present new architecture MAIN (short for Modular Algorithm Induction Network) for neural algorithm induction. Our architecture consists of a neural controller that inter- acts with variable-length read/write tape where inputs, outputs, and intermediate values are stored. Each module is a small computational procedure that reads from and writes to a small fixed number of tape cells (a given fixed set of modules are specified in advance). At each time step, the controller selects module to use together with the tape location of the module's 's input arguments and the write location of the module output. This architecture is trained end-to-end using reinforcement learning.
A comparison of architectural design choices in MAIN with those in recent neural program induction approaches NTM (Graves et al. 2014). LSA (Zaremba et al.) 2016).. NRAM (Kurach et al. 2016), NGPU (Kaiser & Sutskever] 2016), CRL (Chang et al. 20188), and DNC (Graves et al. (016) is presented in Table [] Unlike previous architectures, MAIN allows for learning to compose modules

---

Under review as a conference paper at ICLR 2020
NTM
LSA
NRAM
NGPU
CRL
DNC
MAIN
Modules
X
X
X
X
General module selection
X
J
General argument selection
V
X
Read/write history
V
X
X
X
J
Random access
J
X
X
V
Memoryless controller
X
X
J
V
X
X
Encoder type
Attn
FF
FF
CNN
RNN
Attn
CNN + Attn
Table 1: Comparison of design choices used in MAIN to recent algorithm induction approaches.
together with the corresponding argument values for the chosen modules using general domain- agnostic mechanism for module and argument choices. It uses generic linear tape layout together with a parallel history tape of landmark symbols that indicate the most recently read and written cells. Finally, the architecture allows for random access of the memory cells and uses memoryless controller with a length- -ngerraann self-attention based encoding of input tape contents.
There are two key design choices in MAIN that we found crucial for good performance. The first is in the representation of the previous history of the computation. Like previous work (Graves et al.) 2016), find that providing history to the model is important source of information. We intro- duce a simple but effective discrete representation, introducing a parallel history lape of landmark symbols that indicate the most recently read and written cells. This helps the model to learn com- mon patterns of control flow, such as maps and reduce operations over the tape. The second choice in the encoder architecture of the abstracted tape view with the controller. We find that using an attention-based encoder performs much better than recurrent network based encoding within the controller, which has been employed by previous architectures for neural algorithm induction.
We evaluate our architecture MAIN on five algorithmic tasks including array copying, reversing, increment, filter-even, and multi-digit add. MAIN can learn these tasks in an end-to-end manner using input-output examples and is also able to generalize to longer input lengths. We observe that both parallel tape history and length-invariant input tape encoding based on self-attention are necessary for the architecture to learn these tasks. Moreover, for tasks such as filter-even and multi- digit add that require the controller to perform some computations, we observe that abstracting the tape contents only certain landmark positions can help learn the corresponding algorithms.
2 RELATED WORK
Learning to Compose and Modular Networks: Compositional Recursive Learner (CRL) (Chang ct al. 2018) a framework for learning algorithmic procedures for composing representation trans- formations, where both the transformations and their compositions simultancously learnt from a sparse supervision. The controller that learns to compose transformation is trained using rein- forcement learning, whereas the transformations themselves trained using supervised learning. The CRL architecture supports two forms of transformations: reducers and translators. Because of specialized transformations, CRL imposes a restriction on always selecting either full tape or three consecutive input tokens as arguments (that result in resulting token) for the transformation In contrast, our architecture allows the controller select arbitrary locations on the input tape to select as module arguments and also the write locations for their outputs.
There has also been some recent related work on learning Modular Networks (Kirsch et 2018) and Routing Networks (Rosenbaum et al., 2018). In routing networks, router learns to select sequence of function blocks to compose given an input, and is trained using reinforcement learning- Kirsch et al. (2018) use probabilistic model to represent the module choice latent variable and use Expectation Maximization (EM) to learn the module parameters and the decomposition choice in end-to-end manner by maximizing variational lower bound of the likelihood. Both of these approaches learn modular composition of functions with the aim of reusability and better gener- alization across multiple tasks. Our architecture, in contrast, is designed for learning algorithms where the modules are pre-specified but the task of the controller agent to learn to compose those modules achieve desired input-output behavior.
2

---

Under review as a conference paper at ICLR 2020
Neural Program Induction and Synthesis: Several neural architectures have been proposed cently to learn algorithmic tasks. Neural Turing Machine (NTM) (Graves et al. 2014) extends an LSTM controller with an external memory together with differentiable read wwrte mechanism. Dif- ferentiable Neural Computer (DNC) (Graves et al. 2016), a successor to NTM, added capabilities of freeing up unused memory for processing long sequences and temporal link matrix for better tracking the write order. Zaremba et al. (2016) propose an architecture with an RNN controller that learns to navigate structured input grid by selecting move actions and outputs tokens on an output grid. Unlike our architecture, which separates control from compute, these architectures require the controller to learn both the control structure as well as the desired computations.
Neural RAM (NRAM) (Kurach et al. 2016) uses a neural controller that learns to produce fuzzy circuit consisting of fixed number of modules. The controller learns to wire the modules with inputs coming from a fixed set of registers or intermediate outputs, and also learns to write output back to registers and memory tape. There are three key differences between Neural RAM and our architecture. First, NRAM uses fixed sequence of 14 modules (with an option to repeat the whole sequence multiple times). In contrast, our controller learns to select appropriate module at each time step. Second, since registers and memory tape in NRAM architecture store distributions over integers, the modules also need to be differentiable to compute output over such inputs. Our architecture, on the other hand, does not require the modules discrete values on the input tape. Finally, our architecture uses a parallel history tape of recent read and write positions for accessing the input tape unlike pointer dereferencing in NRAM.
be differentiable and also writes
We summarize the characteristics of these architectures, comparing them to our work in Table [ To understand the rows of this table, "Modules" means whether computation is performed by compos- able modules. "General module selection" means the modules can be selected in any order at any point in the computation (NRAM enforces fixed ordering). "General argument selection" means module arguments can come from anywhere in memory without restriction (CRL enforces inputs be locally adjacent). "Read/write history" means that history of previous read and write locations is provided as context to the controller. "Random access" means the architecture can look up arbi- trary memory contents and agregate information across memory regions, rather than be restricted by relative head movements (LSA). "Memoryless controller" means the architecture does not require the controller to have hidden memory over time, i.e. the controller is not recurrent, and only uses external memory for context. Finally, the "Encoder type" indicates how memory is consumed by the controller, ferd-forward (FF), convolutional (CNN), recurrent (RNN), or antention-based (Attn).
There is also growing interest in using neural models generate symbolic programs as output. RobustFill (Devlin et al. 2017) trains an attention based encoder-decoder model that generates a program given a of input-output examples. Deepcoder (Balog et al., 2017) learns probability
distribution over a set of functions in DSL to guide an enumerative search. Chen et al. (2019) also use an encoder-decoder based approach to synthesize Karel programs (Bunel al.) 2018).
but in addition also execute the partially decoded program to guide the decoder. In contrast, our architecture uses more general mechanism read and write on the variable length input tape, and uses reinforcement learning to learn to compose the desired modules for each individual task.
3 ARCHITECTURE
We describe MAIN, an architecture which can express arbitrary modular Turing machines. Our architecture has three parts: the memory which stores the state of the computation, the modules which update the tape, and the controller which chooses a module M, to execute at each stage of the computation as illustrated in Figures(3] Once M; is selected out of the module set (4 modules depicted), and the read/write locations on the tape are chosen, the module sees only the read inputs, and modifies the tape only at the write position. Each module is a user provided function (which could in principle also be learned). In our experiments we picked modules of two arguments and one output, but our architecture is agnostic to the number of read/write heads shown in Figure [
Mo
M₁
M2
M3
Figure I: Module interaction with memory
3

---

Under review as a conference paper at ICLR 2020
Initial Tape
Initial tape
4
7
2
$
&
1
2
3
+
9
8
7
$
Middle of computation
Middle of computation
4 7
2
$
4
2
&
1
3
+
9
8
7
$
0
(a) Copy Task
(b) Multi-digit Add Task
Figure 2: Example initial and intermediate tapes for (a) Copy and (b) Multi-digit add task.
The memory is a finite tape of discrete tokens/symbols. Formally, let 80: 81, -1,---,,77 8T be memory states at each computation step t o..... T. Each 8, is itself an array of tokens, indexed as sx so] 8 s.(L 1]. At the start of the computation, 80 is initialized with the program input, and necessary empty space to perform intermediate computation and write the output. The memory length L is dynamically set based on the size of the given input, so every neural architecture com- ponent that depends on L needs be length invariant.
The memory contains landmark tokens, which are are task-specific tokens, e.g. 'S', '+' 'a', that provide positional information. For example, these tokens indicate where the input starts, where the output should be written, etc. In our experiments we found that the controller would often overwrite the landmark tokens during training. As a workaround, we provide the positions of landmark tokens as immutable metadata. These are the lambdas A(1), A(2) .... inside or shown above. Additionally, we place Start- Start-Of- Tape and End-Of Tape landmarks at the first and last tape positions.
The initial tape so contains the input and additional space for scratch work. At the end, the output of computation will be read from designated regions of the tape, called target locations, which are initialized with the empty token '.' Note that the architecture is free to overwrite any position during the course of computation, including important input tokens. When scoring the final tape sT, we only look at designated target positions, designated by the token. The initial tape configura- tions for Copy and Multi-digit Add Tasks is shown in Figure 2 The tape configuration in addition to the input tape also consists landmark positions as well as the read/write heads history.
The modules M {m1..... m are functions that read narrow portion of the memory, and compute new values that are stored in memory. Each module m, is a function of R arguments, and outputs vector of size W, i.e. number of read/write heads corresponds the number of inputs and outputs of the modules. During the computation, each input and output of the modules will be a single cell on the memory tape. Some example modules are the maximum module which returns the maximum of two inputs, and the sum module which returns the sum of two inputs mod base B.
The controller is a policy over actions that specifies module-tape interaction. The troller cannot directly modify memory. Instead it selects module and the locations on the tape the module will read from and write to. Specifically. the controller defines distribution (H(r.1) (r, (w..)) ...., H(w,W), W,,,, M G)), where ((-) are random variables over tape positions (support is {0,.... L 1)); one for each head. The variables H(.1) ...., :.... Hr..R) select read-head locations, and (1,,1) ..... H(w,W) select write-head locations. The random variable M is one of the modules. Finally 6 is the context, which contains the current state of memory and information about the computation history. We will define this in more detail shortly.
The controller defines an end-to-end computation as follows. At each step L of the computation, let the current state of the memory by 8t. To choose the next module and the locations of the read and write heads, we sample from the controller. This produces a module choice my and locations n.(+1)), ..... A(..R) for the read heads, and ((w.1) troller is free to choose any tape location for each read and write head independently, the memory is random access. The tape is updated by calling the module m,, with the tape contents under the read
h, ((w.W) for the write heads. Because the con-
heads as input, and then writing to the position specified by the write heads. More formally,
81+1 [1e (wnd) = (1("(16 (r:1)
se 10 T D(
Vj E (1,..... W} (10,1)
S441/0] [z)
Ai E (h)
..... m, (w,WW)

---

Under review as a conference paper at ICLR 2020
The selected write indices are updated with module's output, and other tape elements unchanged.
The context c is the input to the controller, which represents both the current tape contents s and an action history that represents information about the previous computation. The action history consists of two parts:
Fixed-size part: Contains the module choice and head locations chosen at the previous time step.
Module choice: m4-1
Tape values undernaath heads: sı [_hh""),..... [h/-1']] [1 [6|_1"]
Variable-size part: One-hot encoding of [h[-1), the read and write head locations at the previous step of the computation.
The tape values underneath the heads are technically redundant information, because the controller can use 8, combined with the head locations from the variable-sized part to lookup the corresponding tape values. However, we found that the controller had a hard time doing this our experiments, and providing the head values as auxiliary input to the controller proved helpful.
Formally, the context is a tuple e = (Er, where &. is a fixed sized encoding (does not depend on the tape length L), and is a variable sized encoding (depends the tape length L). First, & describes the current tape values underneath the tape heads chosen at the previous time step:
& = (st [s... .......s.... [1("111) se se[h
( J.... se [1 (,,"") m)-1).
where m,-1 is the previous module choice. Second, the variable sized encoding a is a matrix concatenation that provides complete information about sy:
[v(s)
[v
Iv(s 1]}
12
We can think of oe as stack of binary channels, each rec-or of length L. The one-hot function D {d} produces a vector of length D which is filled with Os, and I at position d. Each 1v [s]{}} a one-hot vector of token se(.). Their horizontal concatenation produces channel for each token (indicates its presence or absense). The 1 (x) and 1 [1(h"") channels indicate the positions of landmarks and heads respectively (A are fixed throughout the episode and not indexed by t). Note that at / = no actions have been taken, so the previous-action encodings are all Os.
Now describe the controller architecture. Given the context ct, the controller begins with sequence encoder for the variable length encoding a.- We pass ae through two 1D convolutional layers (along the dimension) with filter width and stride This is the only aspect of our encoder that provides awareness of the local ordering of cells on the tape.
After that, we explore two different seq2fixed encoders:
RNN encoder: BiL.TTM produces fixed length embedding (concat of embedding for each direc- tion) which is fed into the controller.
Attention encoder: A context-indepee context-independent query set is learned (fixed during evaluation). Queries are fed into attention over the tape, and the resulting weighted sum over tape values is a fixed length embedding that is fed into the controller.
5

---

Under review as a conference paper at ICLR 2020
modsles
reproseria the compled value distribution
S
M
Prev Module Index m
HDD
-H
Full lape attendion based encoddr plus head Valuuss
Fncader
H(w
Figure 3: Controller interaction with memory and module. Controller consumes memory state from the previous timestep using encoder, and outputs module M, from {M,,... M& and attention weights over memory positions that determine the read and write positions for that module.
Next, we pass the resulting fixed-sized embedding for a along with & into a feed forward network which outputs attention queries for the read/write head actions, and logits for the module selec- tion action. Logits for the read/write head actions are produced with dot-product attention over at (independent attention head for each read/write head).
Learning the Controller. We frame our setup in the reinforcement learning paradigm, where the controller is the agent, and other components (memory and modules) are part of the environment. From the perspective algorithm induction, only the program input and target outputs are external, while everything in MAIN is part of the black box that performs the computation. The controller trained end-to-end on all its actions with Impala (Espeholt et al.) 2018). a distributed variant of REINFORCE. Simultaneously learning to halt with RL, while learning what computation to perform, proved to be unstable in our experiments. We removed the additional complication of learning when halt by providing halting oracle. The oracle is given the correct output, and immediately ends the episode if the answer is in memory. The oracle is used in evaluation as well.
4 EXPERIMENTS
We present empirical evaluation of our architecture MAIN in order to establish that (i) it can learn to perform algorithmic tasks, (ii) attention is important for length generalization, and (iii) separating control flow and data flow through limited view helps in learning.
Tasks: We consider five algorithmic tasks with six pre-defined modules. All but the Multi-Digit Addition task given the same module pool. We found that Multi-Digit Addition was more difficult to learn, and to reduce the action space we cut down the module pool to only ones needed to perform the computation. For simplicity, we make all the modules have the same number of inputs and outputs. Specifically in our experiments there are two read-heads and one write head. Modules which naturally read less than inputs ignore their additional inputs. We consider the following modules: Identity, Increment, Max, Sum, Suminc, and Reset. The semantics of the modules is presented in Appendix A.1 We consider the following tasks.
Copy: Given array of base 10 digits in the memory tape and pointer the destination, the task is to copy all elements from the array to the destination (e.g. see Figure 2(a).. We provide landmarks to start of the input and start of the output location. For an input array of length n, the
output would be also of length n,, and so the total memory tape size would be 2n + 1, including separation token. Modules: Reset, Identity, Increment, Max. Sum
Reverse: Same tape size as Copy task, with the goal of writing the input digits in reverse order.
Increment: Same tape size as Copy task, with the goal of writing the result adding to each digit of the input array (modulo base) to the destination.

---

Under review as a conference paper at ICLR 2020
Copy
Reverse
1.0
1.0
Accuracy
0.9
Accuracy
0.9
0.8
0.7
0.7
Tool
0.5
0.5
10
20
100
10
20
100
Generalization Length
Generalization Length
Increment
Filter Even
1.0
1.0
0.8
Accuracy
Accuracy
0.8
0.6
0.4
0.6
0.5
0.0
10
20
100
10
20
100
Generalization Length
Generalization Length
Figure 4: The average success rate and the variance of MAIN for different algorithmic tasks for different input generalization lengths of 10, 20, and 100.
Filter Even: Given an array of base digits the tape, the goal output a sequence containing only the even-valued digits in the same order. Modules: Reset, Identity, Increment, Max, Sum Multi-Dight Addition: Given arrays of base 10 digits separated by '+', the goal is to output the sum of the integers (denoted by input arrays) as a sequence of digits. Modules: Sum, SumInc
4.1 EXPERIMENTAL SETUP
We train the controller with Impala, distributed asynchronous algorithm. We used 50 data collec- tion workers to sample episodes from the most recent policy. There is one training worker which queues up episodes sent by the data collectors into training batches. We train until 30M timesteps across all episodes. We use curriculum over task difficulty, which essentially corresponds to the input length. For each episode, an input-output pair is sampled from the task generator given a dif- ficulty level, and the difficulty level is sampled uniformly range [1, C1, where C' is the maximum curriculum setting. We vary C from 2 to with linear schedule starting at 1M and ending at 18M. During training, each data collector generates
task inputs the fly.
For evaluation, we precompute datasets of 100 test inputs for generalization with larger input lengths 10, 20, and 100 sampled from the same data generator. We evaluation repeatedly and concur- rently with training, and take the highest observed success rate as the final metric. For given input, compute success whether the controller controller produced exactly the desired output. We take the average success across the 100 evaluation inputs as the success rate. Because we run each experiment 10 times, can estimate the variance of success rate due random weight initializa- tion, randomly sampling from the policy, and stochastic effects of asynchronous training. We report average success rate (across the 10 trials) and the empirical standard deviation.
4.2 RESULTS AND ABLATIONS
Table presents the experiment results of evaluating MAIN the five algorithmic tasks with differ- ent ablation choices for the generalization imput length of 100. For each task, we report the number of runs out of 10 that achieved 100% success the test set of 100 evaluation inputs (each of length 100). Additionally, the average of success rates together with their variance for four the tasks for different input generalization lengths of 10, 20, and 100 is shown in Figure

---

Under review as a conference paper at ICLR 2020
Copy
Reverse
Increment
Filter Even
Multi-Digit
Add
Attention Encoder
7
7
0
No Tape Values
3
6
1
No Action History
0
0
0
No Action History Tape Values
7
8
0
Recurrent Encoder
3
0
Table 2: Ablations and variability of success. For each task, we report number of runs out of 10 that achieve 100% success on length 100 inputs. Each row is different setting of our architecture.
As shown in Table 2 MAIN can learn to generalize perfectly for inputs of length 100 when trained on imputs with length up to 10 only. For the copy. reverse, increment, and filter-even tasks, MAIN can generalize in majority of runs out of 10. The multi-digit addition task is particularly challenging in architectural setting. For learning this task, the controller first needs learn select appropriate individual digits to be added for each timestep. In addition, also needs to learn to use the digits and module choices selected in the previous timestep decide whether add carry or not while computing the addition. Remarkably, MAIN was able to learn one such controller.
Now we evaluate whether the special architectural features of MAIN are necessary for good per- formance. First, we evaluate whether the controller needs to observe the values on the tape, by considering an ablation (labeled "No Tape Values" in the table) which removes the top third of de (i.e. removes the tape values 8,). It may then seem like the controller cannot do anything. but it still has access to the action history metadata and values under the previously placed read/write heads. Notably, we found that without tape values, the controller performance goes down, except in Multi- Digit Addition, which is the only setting in which could generalize to length 100. Since this task requires the controller to compute whether carry bit should be used for adding the intermediate result for two digits, hiding the tape contents and only providing the head values constrains the space of possible argument choices for modules and helps the controller learn desired computation.
Next, we evaluate the usefulness of action history, by considering an ablation (labeled "No Action History" in the table) which removes the fixed context & and the bottom third of at, so that the controller does not have information about previous actions. As expected, these architectures do not generalize, achieving generalization accuracy of O. The reason that without the action history, the controller does not have a mechanism to remember which part of the computation it is at currently, and therefore cannot learn iterative computations, which is required by all of our tasks.
Recall that & contains the tape values underneath the previous read-wrin locations, even though the controller could infer this from other context. Next, we evaluate whether this helpful by removing this in the ablation labeled "No Action History Tape Values". On most tasks, the performance is comparable the full model, except on filter-even which this ablation is slightly better.
Finally, we evaluate whether our attention-based encoder could be replaced with a simpler recurrent controller, as has been used in previous work (Chang et al. 2018). For shorter inputs of length 10, the recurrent encoder achieves perfect average evaluation accuracy for the simpler tasks such as copy, reverse, and increment (Figure 4). However, when evaluated on longer input lengths, its performance degrades significantly. For filter-even and multi-digit addition tasks, the generalization accuracy of the recurrent encoder goes to almost for length 100. On the other hand, attention based tape encoder always result in significantly higher generalization accuracies across all the tasks.
CONCLUSION
We presented a new neural architecture MAIN that learns algorithmic tasks from input-output ex- amples. MAIN uses a neural controller that interacts with variable-length input tape to learn to compose modules. At each time step, the controller chooses which module to use together with the corresponding tape locations for module arguments and for writing the module output back to the tape. This architecture is trained end-to-end using reinforcement learning and we show that it can learn several algorithms successfully that generalize perfectly to inputs much longer length (100) than the used for training (up 10).
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 39-48, 2016. doi: 10. ww.1199/VVR..201..110 URL https:
//doi. 10. 1109/CVPR. 2016.12
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In 5th International Conference on Learning Represen- tations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018
Michael Chang, Abhishek Gupta, Sergey Levine, and Thomas I.. Griffiths. Automatically compos- ing representation transformations as a means for generalization. CoRR, abs/1807.00 600700440, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guiie guided neural program synthesis. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-1 August 2017, pp. 900-9999999999 908.998,228 2017.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1407-1416, Stock- holmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:://rrocedd.ggs. mlr. wttpppsss////essehoo.o...
html
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, abs/1410.5401, 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puigdomênech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukeuoglu, and Demis Hassabis. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626): 471-476 2016.
Lukasz Kaiser and llya Sutskever. Neural gpus learn algorithms. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Louis Kirsch, Julius Kunze, and David Barber. Modular networks: Learning to decompose neural computation. In NewrIPS, pp. 2414-2423, 2018.
Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-access machines. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Clemens Rosenbaum, Tim Klinger, and Matthew Riemer. Routing networks: Adaptive selection of non-linear functions for multi-task learning. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018

---

Under review as a conference paper at ICLR 2020
Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Synthesis of differentiable functional programs for lifelong learning. In Neural Information Processing Systems, 2018.
Wojeiech Zaremba, Tomas Mikolov, Armand Joulin, and Rob Fergus. Learning simple algorithms from examples. In ICML, pp. 421-429, 2016.
A APPENDIX
A.1 SEMANTICS OF MODULES
The semantics of the modules we consider are as follows.
Modules:
Reset(-,-)--> -
Identity(I,_) æ.
Increment(r; (1, char(int(z) + 1) if isnumeric(x) else >.
Max( y) max y)-
Sum(x, [z y) char((int(z)) + (nt(y)))B if innumeri((()) and isnumeric(y) else '0'. SumIne( y) - char((int(z)) + int + 1)%B) issumerri((z) and isnumeric(y) else '
10


Reviews:
[{"review_id": "SJlbBsl5FB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 proposes a novel modular neural architecture for algorithm induction. The modules are fixed and a controller policy is learned which outputs a distribution over modules and input/output locations on a memory tape. An oracle (which knows the correct answer) is necessary to decide when to stop computing. The controller is trained by a variant of REINFORCE.\n\nMy main concern with this paper is that there is zero experimental comparison against previous neural program induction approaches. It makes it difficult to evaluate whether the specifics of the proposed architecture actually are advantageous (albeit the authors argue so in table 1, it is not clear that these differences translate in better learning).\n\nI find it rather disappointing that the controller needs to be stopped using an oracle which knows the right answer, making the practical use of such an architecture essentially infeasible in practice. It is also disappointing that a different subset of predefined modules is chosen for each task. I understand it helps to not have unnecessary modules in the module set, but it seems to be another weakness of the approach, and there was no evaluation against using the same full set for all tasks. Also, it is not clear that the chosen set of modules is sufficiently  general and universal, which  would be necessary to scale this approach to learn arbitrary programs.\n\nSince the controller is trained by REINFORCE, one could be concerned that the gradient estimator has high variance (compared to methods based on soft-attention where one can backprop all the way through a sequence of actions). It would thus have been good to verify how sample complexity worsens as the complexity of the task  scales up, but there is no such analysis.\n\nConsidering the above issues, I suggest to reject that submission.\n\nMinor:\n\nPage 4, 2nd par, the text refers to sigma_t \"shown above\", which has not yet been introduced (comes in the middle of page 5).\n\nPage 7, 2nd par, \"linear schedule starting at 1M and ending at 18M\" needs to be clarified. 1M what?\n\nPage 8, \"generalize perfectly\": it does not seem to be the case since none of the experiments have led to 10/10 successes.  Are the \"runs\" mentioned training runs?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HygP6m6FjB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 proposes a new variation of modular neural networks. Specifically, they proposed a new architecture for the neural controller that selects which module to use given the current state and history computations, and evaluated the architectures for five symbolic tasks. I'm leaning towards rejection because:\n1. The story is confusing. Instead of framing algorithm induction as a program synthesis task, the paper told the story from the modular networks's view. This is quite confusing as most of work in this line of research usually assumes the modules are neural networks and are learned, while this paper uses user provided modules. This should then be framed as doing program synthesis with pre-specified primitive functions. This work hence is quite close to NPI [1]. A RL version of NPI is also recently proposed [2].\n2. Lack of novelty. Continuing from the previous point, it seems it is not easy to distinguish the main idea of this work and the work of NPI. There are two differences. There's an architectural difference about how one deals with history. NPI uses a LSTM and this work uses the last time step's computation configuration as input to a FNN. It is unclear why one is better than the other? Such modification is also lack of motivation, unexplained in the paper. Another difference is about how one designs the tasks/environments. This work uses a working tape while NPI uses programming traces.\n3. Lack of baseline comparisons. In the experiment section, no previous work are evaluated and compared to the proposed method, leaving one unknown how well the proposed method compares with previously known work.\n\nThat being said, there are still some merits in the paper. The currently known work for training NPI with RL [2] does not support argument predictions, while this work does. I do not know if this is due to the interface/environment that's designed for the tasks in the paper, but I recommend the authors to rewrite the story and clarify these differences more clearly. Also how general is this environment? For harder programming tasks, can one still uses tape? How scalable is this?\n\nMinor point\n- How do you use FNN to produce all actions of the controller? Do you use a different heads for different action output? Or do you use an autoregressive architecture? Have you tried both and compared?\n\n[1] Neural Programmer-Interpreters.\n[2] Learning Compositional Neural Programs with Recursive Tree Search and Planning.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1gspdehFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 proposes Modular Algorithm Induction Network (MAIN) that learns algorithms given input-output examples. MAIN is equipped with several components that make it perform better than baselines, but probably the most important part is its use of modules to break-down algorithmic tasks into simpler problems. MAIN is learned end-to-end using reinforcement learning and demonstrated to perform well in several tasks.\n\nThe paper provides a good comparison between the proposed architectures and other related works. The idea to compose modules is reasonable. Nevertheless, I find this paper somewhat incomplete and not ready for publication. The most critical part is its lack of experimental validation. Table 2 presents a bunch of success rates without comparison to other methods. Unless being an expert or practitioner having the experience to implement baselines, it is hard to assess how good the proposed algorithm is. The authors provide some ablations and some of them may roughly correspond to the baselines, but the most import part - introducing modules and a mechanism to compose them actually helps - is not demonstrated in the paper at all. Hence I think the experiment section demonstrated nothing but a proof-of-concept (the proposed algorithm seems to work).\n\nThe main section describing the algorithm is not very comprehensive. I could imagine how difficult it would be to reproduce the results in the paper. It would be better to specify more detailed architectural choices.\n\nOverall, I agree with the main point of the paper but vote for the rejection for now, and the paper needs a major revision on its experimental validation and presentation.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agreed that although there is a sensible idea here, the method and presentation need a lot of work, especially their treatment of related methods.
Decision: Reject