Title: LEARNING WHAT TO LEARN IN A NEURAL PROGRAM

Abstract: Learning programs with neural networks is a challenging task, addressed by a long line of existing work. It is difficult to learn neural networks which will generalize to problem instances that are much larger than those used during training. Furthermore, even when the learned neural program empirically works on all test inputs, we cannot verify that it will work on every possible input. Recent work has shown that it is possible to address these issues by using recursion in the Neural Programmer-Interpreter, but this technique requires a verification set which is difficult to construct without knowledge of the internals of the oracle used to generate training data. In this work, we show how to automatically build such a verification set, which can also be directly used for training. By interactively querying an oracle, we can construct this set with minimal additional knowledge about the oracle. We empirically demonstrate that our method allows automated learning and verification of a recursive NPI program with provably perfect generalization.

1. INTRODUCTION:

In recent years, the use of larger datasets and bigger models with greater representational capacity has led to significant advances in many applications such as object recognition in images and machine translation. Inspired by this progress, many researchers have used neural networks for program induction, especially through the development of novel neural network architectures which feature components such as a variable-size memory (Sukhbaatar et al., 2015; Kurach et al., 2016; Graves et al., 2014; Joulin & Mikolov, 2015b) . Compared to baseline approaches like recurrent neural networks and LSTMs, these architectures are able to learn more effectively from input-output examples on tasks such as addition, sorting, and permutation of sequences, as measured by their empirical accuracy on a held-out test set of input-output examples.

For program induction, there typically exists a parsimonious underlying program to solve the problem which has been specified using input-output example pairs. However, as the space of all programs is extremely large, it is often difficult for neural networks to learn the correct underlying program just using input-output examples. Indeed, many of the prior works report that the learned neural network empirically fails to generalize to significantly larger inputs than those in the training data, which indicates that the neural network has learned spurious dependencies on irrelevant idiosyncrasies of the training data (such as length of each training example). These failures occur despite the use of approaches like curriculum learning (Bengio et al., 2009) , where the training data initially consists of easy examples and gradually becomes more complicated as training progresses. Furthermore, the neural network architectures may be very sensitive to hyperparameter settings, with the best generalization results only achieved in a fraction of a percent of the hyperparameter space (Kaiser & Sutskever, 2016) .

Even when a learned neural program exhibits empirical generalization to arbitrarily complicated inputs, a more fundamental issue remains: while the learned neural program may empirically produce the correct result on every input example attempted, we cannot show that the neural network will operate correctly on every other possible input. Without actually running the neural network on a given input, it is quite difficult to predict or otherwise characterize its behavior on that single input, let alone a large (often infinitely large) class of inputs. Nevertheless, we would like a proof of correctness that the learned neural network has learned the right underlying program, and will therefore operate correctly on any input.

Prior work by Cai et al. (2017) addresses the problem of proving correctness of a learned neural network program by introducing recursion to the Neural Programmer-Interpreter (NPI) architec-ture (Reed & de Freitas, 2016) . Unlike most other architectures designed for learning programs and solving algorithmic tasks, the Neural Programmer-Interpreter emphasizes the compositional nature of programs, solving a problem through functions which can call other functions. Both the original work by Reed & de Freitas (2016) and the later work by Cai et al. (2017) train the architecture not with just input-output pairs, but with execution traces which describe in detail the role of each function in solving a given input problem. Cai et al. (2017) ensured that these traces are recursive: each function only takes a finite, bounded number of actions. To solve problems where the number of actions needed grows with the size of the problem, the function calls itself to perform the necessary repetition. This property not only led to empirically better generalization compared to the earlier work, but enabled the authors to formally verify that the learned neural programs would generalize to any input.

Problem statement and proposed approach. For any of the prior neural program architectures, the goal is to train a neural network to duplicate the behavior of an oracle which can solve any instance of the problem at hand. In this work, we seek to answer the question of how to generate a suitable training set for learning such a neural program architecture so that it can successfully duplicate the behavior of the oracle. In other words, what is the set of input examples for which we should demand labels from the oracle? To our knowledge, prior work does not explicitly address this question: the usual practice has been to use a "large enough" training set in the hope that the resulting learned neural program will be good enough. Indeed, prior work usually assumes that a fixed set of data is available, and treats the task as learning something from this fixed set. Our goal is to learn the true underlying program-if we are only given a fixed set of data, it could easily be that this data does not demonstrate all of the behaviors of the latent program (see Section B for more discussion). To overcome this issue, the setting in this paper is closer to active learning, where we assume that we can query an oracle with previously unlabeled data points to obtain more labels. Many past works, through their combination of curriculum learning Bengio et al. (2009) , and dynamic generation of new problem instances then solving them with an oracle to obtain each mini-batch of training data, also use a setting similar to active learning (see Section C).

We work with recursive NPI oracles from Cai et al. (2017) , as they provide a detailed execution trace that describes how to solve a problem in terms of smaller functions. We iteratively explore all possible behaviors of the oracle in a breadth-first manner, and the bounded nature of the recursive oracle ensures that our procedure reaches a fixed point in finite time. This method automatically identifies a sufficient training set for fully learning the behavior of the oracle, and perfect accuracy on this training set provides a proof that the learned neural program will generalize to any input.

Furthermore, once we have a complete training set which fully describes the behavior of the oracle, we can identify and remove redundant information in each trace of the set, to significantly reduce the set's size and enable faster training. The minimized set also allows for provably perfect duplication of the oracle.

Contributions of this work. We make the following contributions:

• We provide an algorithm for automatically generating a sufficiently large and diverse NPI training set which, by construction, allows us to exactly mimic the oracle's behavior on any valid input.

• We provide a formal proof of correctness that this algorithm, for a bounded-length NPI oracle adhering to some mild conditions, will produce execution traces which cover all of the possible behaviors of the oracle.

• We also demonstrate a method for removing irrelevant observations in each trace, which allows us to significantly reduce the size of a NPI training set needed to mimic an oracle through deduplication of the simplified traces.

• As a consequence of the above, we automate the process of showing provably perfect generalization (Cai et al., 2017) for a learned recursive NPI program; we automatically generate a training set, such that achieving perfect accuracy on this set guarantees perfect generalization.

We empirically validate our methods on the addition, bubblesort, and topological sort tasks from Cai et al. (2017) . Our experimental results show that, with only black-box access to the oracle, we can automatically generate a small training set. A neural program learned from this training set empirically generalizes to all attempted inputs; furthermore, we show that a neural program which achieves perfect accuracy on the training set is guaranteed to give correct results on any input.

As shown in Section B of the appendix, manually creating a suitable training set can take trial and error. Manually creating a verification set for provable generalization (Cai et al., 2017) requires careful reasoning about the internal mechanisms of the oracle. In contrast, our approach provides a complete and automated solution to the problem of learning a neural program with provably perfect generalization, with only black-box access to the oracle, for our target domain of recursive NPI oracles.

2. BACKGROUND: NEURAL PROGRAMMER-INTERPRETER:

In this section, we review the Neural Programmer-Interpreter architecture by Reed & de Freitas (2016) , with an emphasis on the aspects that are most salient for our contributions.

The Neural Programmer-Interpreter architecture consists of three components: a core module shared across all tasks, learned function embeddings which direct the core module, and domain-specific encoders which summarize the environment into a fixed-size representation and provides it as an input to the core module.

The core module is recurrent and implemented as an LSTM (Hochreiter & Schmidhuber, 1997) . At each step, it receives the embeddings for the current function being executed (p) and its arguments (a), the domain-specific encoder's (f enc ) observation of the environment (e t ), and the previous hidden state (h t-1 ); it produces the next function to run (and arguments for the function) using content-based addressing (k t ), whether to return control to the caller function in the next step (r t ; 0 ≤ r t ≤ 1), and the next hidden state (h t ). More formally, we write h t = LST M (f enc (e t ), p, a, h t-1 )

r t = f end (h t ), p = f prog (h t ), a = f arg (h t )

The LSTM applies a small neural network, e.g. with two hidden layers, to merge the inputs for the current timestep.

If p is a primitive function, we follow its (hardcoded) definition to manipulate the environment. Otherwise, if p is not a primitive function, we suspend the execution of the current function p and transfer control to p : the current hidden state h t is set aside, and in the next step of execution, the NPI core receives 0 as the previous hidden state and p as the current function being executed. When p returns control to the caller (when r t > 0.5), we restore the set-aside hidden state and the program embedding for the caller p in the next step of execution.

Conceptually, we can view the Neural Programmer-Interpreter as producing a long sequence of primitive function calls, each of which manipulate the environment in some way, until the environment reaches a desired state. The observations (produced by f enc summarizing an environment) inform the core module which functions to invoke.

Example task: bubblesort. For the purpose of exposition, we will examine the bubblesort task from Reed & de Freitas (2016) and Cai et al. (2017) throughout the paper.

In this task, the environment is a one-hot encoded scratch pad Q ∈ R N ×K where N is the array length and K is the one-hot encoding dimension (number of possibilities for each array entry). We will sort decimal digits, so K = 10. The environment also contains three pointers called p1, p2, and p3. We initialize the environment with the array we wish to sort, and the pointers at location 0. We will sort arbitrarily large arrays, so the environment can also have unbounded size.

f enc encodes the values at p1 and p2, and whether p3 is within bounds or beyond the length of the array. Therefore, the observation is a fixed-size tuple of these three values, whereas the environment can have arbitrary size depending on the length of the array.

Figure 1 shows an example execution trace. 

Input:

Output Execution traces and the oracle. In order to train the NPI architecture, we use an oracle to obtain an execution trace that describes the behavior of each function. The oracle can be described by a function1 Oracle :

Function Conditions on n∈N O n Function r t BSTEP n = 1 ∧ o 1 [p2] = end NOP 1 n = 1 ∧ o 1 [p2] = end COMPSWAP 0 n = 2 RSHIFT 0 n = 3 BSTEP 1 COMPSWAP n = 1 ∧ o 1 [p1] ≤ o 1 [p2] NOP 1 n = 1 ∧ o 1 [p2] > o 1 [p2] SWAP 1 2 0

EQUATION

where F is the set of non-primitive functions, P is the set of primitive functions, A is the set of all arguments, O is the set of all observations (i.e., the range of f enc (•)), and n∈N O n is the set of all sequences of observations. The last part of the output {0, 1} corresponds to r t : whether to return control to the caller function.

Table 1 shows a subset of Oracle for the bubblesort task, for the BSTEP and COMPSWAP functions. Each row represents a possible output of Oracle, and columns 1 and 2 show the conditions for when it would have that output.

Oracle is not defined over all of F × A × ( n∈N O n ) because not all combinations of F and A are allowed, and also because most functions will not execute for an arbitrary number of steps. For example, in Table 1 , BSTEP executes for at most three steps (1 ≤ n ≤ 3) and COMPSWAP only for one step.

While past work using NPI did not explicitly define an oracle in this way, we would like to emphasize that the training data used by past work nevertheless needs to have originated from a generative process which can be described by such a function. Otherwise, it would not be feasible for the NPI model to learn the behavior of the oracle accurately, because there is not enough information provided to the NPI core at inference time to unambiguously reproduce the oracle's response.

3. CREATING A TRAINING SET FROM AN NPI ORACLE:

Now that we have formally defined the Neural Programmer-Interpreter and the oracle, we will now discuss how to automatically generate a training set of execution traces by querying the oracle. In summary, we build trees describing all possible behaviors of the oracle. We expand them breadth-first in an iterative manner, as we learn about the oracle's response to each observation sequence. Our procedure reaches a fixed point due to the boundedness of the oracle. After completion, traversals of the trees form a complete training and verification set for the oracle.

3.1. ENUMERATING THE ORACLE'S BEHAVIOR:

So that we can train the NPI core LSTM to duplicate the oracle's behavior on any input, we would like to record the oracle's response to all possible combinations of functions, arguments, and observation sequences that may arise during execution on a valid problem instance. However, it is untenable to query the oracle for all elements in F × A × ( n∈N O n ), with an immediate obstacle being that this set is infinitely large. Even if we know that all functions in the oracle only execute for a bounded number of steps, we may not know the precise bound.

Instead, we will assume that we know the set of possible initial observations and the entry function that begins every execution trace. In our bubblesort example, the entry function is BUBBLESORT (as seen in Figure 1 ) and the set of initial observations is

EQUATION

p1 and p2 initially point to the same position in the array.

The initial observations and the entry function form a subset of

F × A × ( n∈N O n ), which we shall call Q 0 . By querying the oracle on Q 0 , we can obtain Q 1 ⊂ F × A × ( n∈N O n )

; query the oracle on Q 1 to create Q 2 ; and so on, until we observe no growth in

Q (i.e. i≤n-1 Q i = i≤n Q i ).

Then by taking i Q i and the corresponding responses of the oracle, we obtain the training data needed to clone the oracle's behavior.

More specifically, let us denote an arbitrary element of (f, a,

[o 0 , • • • , o i ]) ∈ Q i .

We can then query the oracle on this element to obtain (f , a ,

r i ) = Oracle(p, a, [o 0 , • • • , o i ]). If f is a non-primitive function, then (f , a , [o i ]) ∈ Q i+1 . If f is a primitive function, we compute f (o i ) = O i+1 ⊂ O,

the set of observations we can obtain after invoking f , and add

(f, a, [o 0 , • • • , o i , o i+1 ]) to Q i+1 for each o i+1 ∈ O i+1 .

The next section discusses f in greater depth.

Please refer to Algorithm 1 in the appendix for a full description of the procedure and proof of its correctness and termination.

Bubblesort example. In bubblesort, an element of

Q 0 is (BUBBLESORT, (), [(p1 = 3, p2 = 3, p3 in bounds = 1)]). As shown in line 2 of Figure 1, Oracle(BUBBLESORT, (), [(p1 = 3, p2 = 3, p3 in bounds = 1)]) = (BUBBLE, (), 0). Therefore, we can add (BUBBLE, (), [(p1 = 3, p2 = 3, p3 in bounds = 1)]) to Q 1 .

3.2. EXECUTING OVER OBSERVATIONS INSTEAD OF STATES:

Normally, we execute the instructions from the oracle (or from an NPI core after it has been trained) on a concrete environment. Each primitive function call directly transforms a given environment to a different environment. A non-primitive function also indirectly transforms a given environment to a particular different environment (a single one, assuming determinism of the oracle) through making a series of primitive function calls.

However, the set of valid environments can be infinitely large, because the initial environment must encode the input problem exactly and there is an infinite number of input problems (e.g. sorting of arbitrarily long arrays). Furthermore, sequences of observations determine the oracle's behavior, not the environments themselves. Therefore, we base our analysis on observations, even though environments represent the actual state of execution. This is similar to abstract interpretation (Cousot & Cousot, 1977) . We replace the environments (in bubblesort: the entire array being sorted) which are concrete states with observations (bubblesort: value at p1, value at p2, and whether p3 is within bounds) as abstract states.

For this, we need a correspondence to primitive functions which operate over observations instead of environments. Consider a primitive function f : A × E → E, which operates on some environment e i and transforms it into a different environment e j . We will now define f :

A × O → 2 O as the following: f (a, o) = {o ∈ O | ∃e i , e j ∈ E. f (a, e i ) = e j ∧ f enc (e j ) = o }.

Informally, f (a, o) gives the set of all observations o we could obtain if we run the primitive function f with argument a from all possible environments e where f enc (e) = o. We assume that f is given for each primitive function f .

Bubblesort example. We have two primitive functions: PTR moves a pointer to the left or right, and SWAP swaps the value under two pointers. Then we have

fPTR ((p, LEFT or RIGHT), (p1 = v 1 , p2 = v 2 , p3 in bounds = v 3 )) =    {(p1 = i, p2 = v 2 , p3 in bounds = v 3 ) | i ∈ {0, • • • , 9}} if p = 1 {(p1 = v 1 , p2 = i, p3 in bounds = v 3 ) | i ∈ {0, • • • , 9}} if p = 2 {(p1 = v 1 , p2 = v 2 , p3 in bounds = i) | i ∈ {0, 1}} if p = 3 fSWAP ((1, 2), (p1 = v 1 , p2 = v 2 , p3 in bounds = v 3 )) = {(p1 = v 2 , p2 = v 1 , p3 in bounds = v 3 )}

Intuitively, fPTR ((dir, p), o) produces a set of observations where the dimension corresponding to p is allowed to vary arbitrarily from o, and fSWAP swaps the observed values for the given pointers.

3.3. CREATING THE TRAINING SET:

Our method (Algorithm 1 in the appendix) outputs trees corresponding to elements of F × A, which we label Oracle f,a . Each node (except the root) of Oracle f,a corresponds to an element in (F ∪ P ) × A × {0, 1}, and each edge corresponds to an element in O.

Oracle(f, a, [o 1 , • • • , o n ])

can be computed by starting at the root of Oracle f,a and traversing the edges for o 1 , • • • , o n in turn. Each element in i Q i (from Section 3.1) maps to a similar traversal of Oracle f,a . Figure 2a shows a partial example for bubblesort.

For training the NPI core LSTM, we extract sequences of the form

((o 1 , f 1 , a 1 , r 1 ), • • • , (o n , f n , a n , r n ))

by performing root-to-leaf traversals on each of Oracle f,a ; o i come from the edges, and f i , a i , r i from the nodes. If the NPI core gets 100% accuracy on these sequences, then it is guaranteed to match the oracle's behavior in any setting.

However, due to the approximations made in considering observations instead of environments, some of these sequences may never arise during execution of the oracle on a concrete problem. For example, consider PTR 1 RIGHT in RSHIFT of Figure 1 . Before, p1 points to one location left of p2; after, they point to the same location, so the value for p1 and p2 must match in the observation. fPTR cannot account for this as it is unaware of the pointer locations. Nevertheless, every sequence of observations that the oracle may produce from its operations will be present in the set.

4. DETECTING AND REMOVING IRRELEVANT OBSERVATIONS:

In the NPI architecture, the NPI core receives an observation o ∈ O at each step of execution, and the set O from which the observation is drawn is identical across all functions and all steps. In theory, it is possible to take a different action for each of the possible sequences of observations up to that point in the execution of the function. However, practical NPI functions typically have simple behavior, with many parts of the observation sequence irrelevant for execution and therefore unneeded. For example, the LSHIFT and RSHIFT functions in bubblesort should always execute the same sequence of actions no matter which observation sequence is given.

Therefore, we propose to instead provide the NPI core with observations õ ∈

Õ(c1,••• ,cn) f,a

, where

Õ(c1,••• ,cn) f,a

is a family of sets indexed by a function f , argument a, and the sequence of actions c i taken so far (c i ∈ (F ∪ P ) × A × {0, 1}). There exists a function µ

(c1,••• ,cn) f,a : O → Õ(c1,••• ,cn) f,a

for each set in the family; in other words, every element in O maps to an element in

Õ(c1,••• ,cn) f,a

, but the mapping is many-to-one.

At the beginning of executing function f with argument a, we obtain observation o 1 . We will then compute µ By performing this transformation, training and verifying the NPI core requires much less data and computation, since there are not as many behaviors that it needs to learn. This reduction is particularly beneficial for the automatically generated training sets of Section 3.3, because it mostly removes the extraneous execution traces they contain. We also obtain a more parsimonious explanation for the behavior of the oracle.

Multi-dimensional observations. In the tasks and oracles considered by Cai et al. (2017) (including the two algorithmic tasks from Reed & de Freitas ( 2016)), the observation exposed through the domain-specific encoder has a natural multi-dimensional structure. For example, in the bubblesort task, an observation consists of three dimensions: two digits (value at p1 and p2) and a boolean value (whether p3 is within bounds).

This provides a natural method for constructing

Õ(c1,••• ,cn) f,a : if O = X × Y × Z, then we can exclude some of the dimensions to form Õ(c1,••• ,cn) f,a = X × Y or Õ(c1,••• ,cn) f,a

= Z for instance. We can also exclude all dimensions, in which case

Õ(c1,••• ,cn) f,a

would be a singleton set (a nullary Cartesian product). µ

(c1,••• ,cn) f,a

(o) simply drops the excluded dimensions of o.

Detecting irrelevant observation dimensions. Section 3.3 describes trees where the nodes correspond to NPI actions ((F ∪ P ) × A × {0, 1}) and the edges correspond to observations, to describe the behavior of the oracle. To determine which observation dimensions are irrelevant and can be excluded in

Õ(c1,••• ,cn) f,a

, for each (f, a), we build a tree with actions as edges and nodes as branching points which describe the set of observations dimensions necessary to determine the branch to take.

Example trees for BSTEP and COMPSWAP are illustrated in Figure 2b .

We construct these trees from a complete training or verification set which describes all of the possible behaviors of the oracle on any input. We can use the automated method described in Section 3 to obtain this set. Each execution trace of a function f with argument a is a sequence of the form

(o 1 , f 1 , a 1 , r 1 ), • • • , (o n , f n , a n , r n ).

In the tree for (f, a), we ensure that a path exists from the root to a leaf where the i th edge along this path is labeled with (f i , a i , r i ) (without any duplicates, i.e., each node does not have more than one outgoing edge with the same label). Each edge also contains a set of observations, and we add each observation from the execution trace to the set in the corresponding edge. For example, when processing the above execution trace, we add o 1 to the edge for (f 1 , a 1 , r 1 ) at depth 1; we traverse the edge to reach n 1 , and add o 2 to the outgoing edge of n 1 corresponding to (f 2 , a 2 , r 2 ), and so on.

Afterwards, we examine each node with more than one outgoing edge, and then decide which subset of observation dimensions would have been sufficient to decide which of the branches to take. For example, in Figure 2b 's tree for (BSTEP, ()), the root node has two children: for (NOP, (), 1) and (COMPSWAP, (), 0). By looking at the values of o attached to each edge, we can determine that only p1 is relevant for deciding between the two.

Using information about irrelevant observation dimensions. To obtain µ

(c1,••• ,cn) f,a

, we start at the root of the tree for f, a and traverse the edges labeled with c 1 , • • • , c n . We apply µ to replace all o with õ in our training set of execution traces. This replacement typically results in many redundant traces, and removing them significantly shrinks the set's size. We can then exclusively use õ for training and evaluating the neural network.

5. EXPERIMENTAL RESULTS:

We re-implemented three tasks from Cai et al. (2017) : addition, bubblesort, and topological sort. We defined our oracles exactly as described in their paper, automatically generated suitable training sets by making queries to the oracle per Section 3, and minimized them following Section 4.

5.1. ARCHITECTURAL DETAILS:

For all experiments, we used a 2-layer LSTM with 256 units in each layer as the NPI core. a t has 64 dimensions, p t has 256 dimensions, and k t has 32 dimensions. The LSTM accepts each timestep's input through a 3-layer MLP, where the 1st layer receives f enc and a t as input, and the second layer additionally receives p t (concatenated with the output of the first layer).

5.2. EMPIRICAL RESULTS OF USING ABSTRACT INTERPRETER TRAINING SET:

On all three of the listed tasks, we trained the NPI model with the automatically generated then minimized training sets. We continue training each model until it achieves 100% accuracy on the training set. The automatically generated training sets are also verification sets (as defined in Cai et al. (2017) ),2 and so 100% accuracy on the training set indicates that the neural network has learned to copy the oracle perfectly.

The resulting models show empirically perfect generalization. Specifically:

• Addition: 100% accuracy on 80 random problems consisting of 2, 4, 8, 16 digits.

• Bubblesort: 100% accuracy on 100 random arrays of length 2, 4, 8, 20, 50.

• Topological sort: 100% accuracy on 100 random graphs of 5, 6, 7, 8, 70 nodes. Furthermore, we obtain 100% accuracy on conventional verification sets constructed through manual analysis of the oracle, following the methodology described in Cai et al. (2017) .

Without minimization, we reached 100% training accuracy on the automatically generated training set for topological sort, but not for bubblesort and addition. As explained in Section 3.3, the approximations made due to our method means that many of the generated traces for each function would never occur while running the oracle on an input problem. Different hyperparameters may enable leaning of the un-minimized set, but we did not investigate further.

5.3. EFFECT OF REMOVING IRRELEVANT OBSERVATIONS:

Removing irrelevant observations can significantly reduce the size of the automatically generated training set.

• Addition: originally 10129737 unique traces in the automatically generated training set, reduced to 704 traces. • Bubblesort: originally 325622 unique traces, reduced to 137 traces.

• Topological sort: originally 831 unique traces, reduced to 16 traces.

As a point of comparison, we also tried randomly sampling the same number of traces as would be chosen by the minimization, and training the neural network on those training datasets. As expected, these models do not succeed at solving any of the test problems. As such, they also fail to achieve full accuracy on the verification sets.

5.4. COMPARISON AGAINST PREVIOUS WORK:

We also generated training sets for the three problems, using methodology similar to that used by previous work. Specifically, we consider the systematic approach of generating all problems containing a certain number of digits/elements/nodes, and also randomly generating problems of a certain size. We also generated conventional verification sets using the methodology described by Cai et al. (2017) .

The appendix includes the detailed results. To summarize them here: we often fail to learn a verified NPI neural program from many of the training sets, and it is tricky to figure out what a training set should contain to ensure success.

The procedure of Section 4 for removing irrelevant observations allows us to learn correct programs with smaller training sets, by excluding many possible spurious behaviors of the oracle and therefore simplifying learning. However, detecting irrelevant observation dimensions requires a dataset which exhibits all of the possible behaviors of the oracle (such as one generated per Section 3).

In the previous work of Cai et al. (2017) , the creation of a verification set was a manual process based on a careful analysis of the oracle. Our work allows us to create a training and verification set automatically, with only black-box queries to the oracle and without any manual analysis needed.

6. RELATED WORK:

Active learning. In semi-supervised learning, we have a set of examples where some are labeled and others are not, and we would like to learn a function from the example to the label. Active learning extends this setting by allowing the system to query the data provider for labels of some of the unlabeled points (Settles, 2010) . The goal, then, is to learn the best possible classifier while minimizing the number of queries which need to be made.

Our work is similar in that we assume the existence of an oracle which can provide the correct answer for any example. However, unlike most past work in active learning, our querying does not depend on the status of a machine learning model under training. By assuming a structured oracle which can provide execution traces, we also do not explicitly work in the space of input examples, but rather in terms of the observations which (by assumption) the oracle uses to make its decisions.

Software testing. Given a piece of software, we would like to characterize its behavior as completely as possible to ensure that it will not misbehave under any input. In the field of software engineering and programming languages research, many approaches have been developed towards achieving this goal. Techniques such as symbolic execution (King, 1976), concolic testing (Godefroid et al., 2005) , and model checking (Clarke et al., 1999) try to uncover all of the states and behaviors exhibited by a program for the purpose of discovering bugs and security vulnerabilities.

In our work, we also seek to comprehensively describe all of the possible behaviors of an NPI oracle. However, we only assume black-box access to the oracle, unlike many software testing techniques which make direct use of the code of the target program. Network protocol inference and fuzz testing are some software testing applications with similar assumptions.

7. CONCLUSION:

Generalization to complex inputs and inability to provide a proof of correctness have been two challenges faced by most previous work in the space of learning algorithmic tasks with neural networks. While previous work by Cai et al. (2017) provides an approach to address these challenges in the Neural Programmer-Interpreter framework, it assumes the existence of training sets manually designed to contain sufficient diversity and complexity in order to fully describe the task. In this work, we showed how to entirely automate the process of learning NPI programs with provably perfect generalization, through automatic generation of the necessary training and verification sets for the Neural Programmer-Interpreter with only black-box access to an oracle. Furthermore, we discuss how to detect and remove irrelevant observations from execution traces which enables faster and easier learning of the oracle's behavior.

node.traverse(x 1 , • • • , x n ): Follow the edges labeled with x 1 , • • • , x n and return the resulting node, which will have depth n. node.addChild(o, v) adds an outgoing edge labeled with o, connecting to a (new) node labeled with v. It does nothing if there already exists an outgoing edge labeled with o. • callers and obsM ap are multimaps. callers(k) and obsM ap(k) returns the set of values with given key from the map. callers(k).add(...) and obsM ap(k).add(...) adds a value to this set. • queue.popLef t() removes and returns the leftmost element of queue. queue.enqueue(x)

adds a new element to the right end of queue. However, if x has already been added to queue, then enqueue does nothing, even if x was already returned by popLef t(). Theorem. Assuming that each function of the oracle always executes for at most k steps for some fixed k, and the possible number of observations is finite, Algorithm 1 terminates.

Proof. Consider traversing the path from the root of oracleT ree to an internal node, and reading the labels of edges present along the path. We obtain an element of F × A × O ≤k , where F × A comes from the first edge, and O ≤k comes from all subsequent edges (≤ k because the tree would have at most k depth).

ξ : oracleT ree → 2 F ×A×O ≤k performs this traversal over all such paths, and returns their combined result: a set where each element is from

F × A × O ≤k .

Let us denote the the effect of the outer loop of Algorithm 1 on oracleT ree as x i+1 = f (x i ), where x i is the old value of oracleT ree and x i+1 is the new value. ξ(x) ⊆ ξ(f (x)), because f can only add new nodes and edges to oracleT ree, and does not delete nodes or change their labels.

We can consider a partial ordering over 2 F ×A×O ≤k . Then ξ(x) ≤ ξ(f (x)), and 2 F ×A×O ≤k has a maximal element with respect to this partial ordering (the set of all elements of F × A × O ≤k , so x cannot grow indefinitely.

Similarly, we can treat possible states of obsM ap as elements of 2 F ×A×O×2 O . Like oracleT ree, the loop in Algorithm 1 only adds new elements to obsM ap. Following the same argument as in the previous paragraph, obsM ap cannot grow indefinitely either.

When oracleT ree and obsM ap eventually stops growing, the outer loop in Algorithm 1 will terminate, as specified in the pseudocode.

Theorem. When Algorithm 1 terminates, oracleTree contains all possible behaviors of the oracle, including all sequences of observations and actions which might occur when the oracle runs on any valid input problem.

Proof. We will first prove the theorem for a less efficient version of Algorithm 1, where each item removed from queue is also added to nextQueue. In this version, there exists a corresponding item in queue or nextQueue for each node in oracleT ree, because each item removed from queue creates at most one new node in oracleT ree. By the previous theorem, there exists an iteration where the algorithm terminates because no changes have been made to obsM ap and oracleT ree. In this iteration, there exists an item in queue for each node in oracleT ree, and we want to show that oracleT ree already contains all possible behaviors of the oracle (since we will not be modifying oracleT ree further before returning).

For the purposes of the proof, we will assign a generation to each entry in each set contained within obsM ap. Since obsM ap is finite, the number of generations is also finite. To reiterate, obsM ap(f, a, o) ∈ 2 O gives, when executing non-primitive function f with argument a and initial observation o, the set of resulting observations after f returns. If obsM ap(f, a, o) is empty, it means that execution of (f, a, o) never terminates, no matter which observation is selected at each node in the execution tree (we assume that our oracles are well-behaved, and has no such functions).

At the start of the algorithm, we initialize queue with tuples containing initialF unction, initialArgument, and observations in the set of initial observations. We assign generation 0 to the final observations in obsM ap produced by execution traces starting at some (f, a, o) that (1) are reachable from the initial queue without using obsM ap, and (2) contain only calls to primitive functions. To clarify, satisfying (1) means (i) (f, a, o) either needs to be in the initial queue; or (ii) invoked within an execution trace of a function in the initial queue before any non-primitive functions have been called in that trace; (iii) invoked within an execution trace of a function satisfying (ii) before any non-primitive functions have been called in that trace; and so on recursively.

Generation n is assigned to the final observations produced by execution traces starting at some (f, a, o) that (1) are reachable from the initial queue using only entries in obsM ap belonging to generations i < n, and (2) when encountering a node corresponding to a non-primitive function call while traversing the execution tree, chose an outgoing edge for an observation corresponding to generation i (for both, i < n; we choose the the smallest possible n).

In the final idempotent iteration of the modified version of Algorithm 1, we will consider every node inside oracleT ree, but make no changes to obsM ap or oracleT ree. Using induction on n, we will now show that at the start of this iteration, obsM ap(f, a, o) is an overcomplete approximation to the true behavior of the oracle.

• At termination, all items which should belong to generation 0 are present in obsM ap.

There are two parts to check. First, queue contains each (f, a, o) that has a final observation in generation 0; second, for those (f, a, o), obsM ap(f, a, o) actually contains those generation 0 final observations.

To check the first part: each (f, a, o) for generation 0 is either in the initial queue, in which case it should still be in queue; otherwise, we can see it would have been added to nextQueue through some path of function invocations starting at an initial entry of queue.

For the second part, we assumed that ĝ specifies the behavior of primitive functions in an overcomplete way. Since the final iteration is idempotent by assumption, we can be confident we have already explored all the possible execution traces consisting only of primitive function calls, and therefore the corresponding entries in obsM ap are also present.

• Assuming generations 0, • • • , n -1 are present in obsM ap, generation n is also present.

The argument is similar to the base case, except we are now allowed to use parts of obsM ap which we have shown are present. For the first part of the argument, those parts of obsM ap allow us to reach more (f, a, o) tuples that are only called from execution traces containing more than one non-primitive function call. For the second part, we use not only ĝ but also the parts of obsM ap we have already assumed presence. Now we have shown that obsM ap is complete, it is straightforward to see oracleT ree is also complete in this iteration; as if it were not, we would necessarily end up modifying oracleT ree to add something from obsM ap (or ĝ).

We can also see that we do not need to make the modification to Algorithm 1 assumed at the beginning of the proof in order for it to be correct. After an entry has appeared on and been processed from queue, it is only relevant for that entry to be placed upon queue again if its renewed presence on it will lead to some change in oracleT ree. This only happens when obsM ap changes, and indeed we keep track of callers to re-add items to queue at that time.

A.1 REQUIREMENTS AND ASSUMPTIONS:

We list the requirements on the oracle used throughout the paper. The oracles for the tasks evaluated in our paper (addition, bubblesort, and topological sort from Cai et al. (2017) ) meet all of the requirements.

Oracle is deterministic. We assume that Oracle will always give the same output on the same input. O, the set of observations, is finite. We need to be able to enumerate the set of possible observations. This not a hurdle for the computational problems as considered in Cai et al. (2017) , but poses a challenge for tasks like 3D model canonicalization from Reed & de Freitas (2016) , where the observation was a bitmap image.

Primitive functions are deterministic, and we can compute f . A primitive function f : A×E → E, operates on some environment e i and transforms it into a different environment e j .

In Section 3.2, we defined the corresponding f : A × O → 2 O , which maps from observations to sets of observations.

In order to use our method, we must know enough about the environment and defined primitive functions so that we can efficiently compute f for each primitive function f .

Set of initial observations is known. An oracle which can solve a problem like addition or sorting will require that the input be encoded in the environment in a particular way. If the domain of inputs is known, it is straightforward to then determine the set of possible observations that would arise once we have encoded each possible input into the environment as demanded.

Each function always executes for a bounded number of steps. Assuming only black-box access to the oracle, describing all of the possible behaviors of a function finitely is impossible unless each function only executes for a bounded number of steps. The oracles considered in Cai et al. (2017) satisfy this assumption, but the ones in Reed & de Freitas (2016) do not, as those contain functions which execute for a variable number of steps depending on the size of the input.

Oracle terminates on at least one input. We assume that the oracle will complete on at least one problem within a bounded number of steps. Most useful oracles will terminate in finite time for any input, not just at least one.

B RESULTS WITH CONVENTIONAL TRAINING SETS:

Tables 2, 3, 4 show results when we train the NPI model on conventionally created training sets. In these tables, 'mini." denotes application of the procedure in Section 4. To determine whether we could learn a correct NPI program with a given dataset, we ran the training procedure for at least as many iterations as we needed to obtain a verified model when training on any other dataset.

We generated problems systematically in the following way:

• Addition: all pairs of numbers where at least one number is 2 digits long (with no leading 0s), or all pairs of numbers where one number is 2 digits long and the other is 3 digits long. • Bubblesort: all arrays of given length, where each element in the array can be one of the digits between 0 and 9. • Topological sort: all DAGs with a given number of nodes. We number all nodes, and generate a complete DAG by adding an edge from node i to j if i < j. We consider all DAGs created by removing some set of edges from this complete DAG.

These In the above table, we summarize the number of training examples that past works in neural program learning reported using for their experiments. "Dynamic" indicates that, to the best of our knowledge from reading the papers and also any available code, the training data used for each step of training was generated randomly on-the-fly. In other words, the training data is equivalent to the set of all possible problems of a given complexity, and the training procedure samples from this set with replacement. Often, the complexity of the problems in each mini-batch will be adjusted dynamically through the use of curriculum learning.

:

Without loss of generality, we consider each function to only take one argument.

However, unlikeCai et al. (2017), our training set directly contain execution traces for each non-primitive function (such as BSTEP and COMPSWAP in bubblesort); we do not identify each execution trace as created for a particular input problem (in bubblesort, a concrete array to sort).

Figures and Tables:

Figure 1: A partial execution trace for the bubblesort task. Ellipses denote elided portions of the trace. The dashed arrows show the environment at various points of execution. Primitive functions are bold.

Oracle BST EP,() and Oracle COM P SW AP,() generated by Algorithm 1 for the bubblesort task.

The crossed-out text corresponds to the observation dimensions which are irrelevant for deciding the next action.

Figure 2: The main outputs of our proposed methods, in the form of trees. See Sections 3.3 and 4 for more details.

(o 1 ) = õ1 , and provide õ1 to the NPI core, producing c 1 as the first action. After c 1 completes, we obtain the next observation o 2 , compute µ (c1) f,a (o 2 ) = õ2 , provide it to the NPI core, and so on. Even though µ (c1,••• ,cn) f,a is a many-to-one mapping, õ1 , • • • , õn should contain the salient information from o 1 , • • • , o n necessary to exactly specify the next action c n+1 .

The primitive function PTR moves a pointer by one location left or right, as specified by the arguments; SWAP switches the array values pointed to by

Table content: <table><tr><td>BUBBLESORT</td><td>RESET</td></tr><tr><td>BUBBLE</td><td>LSHIFT</td></tr><tr><td>PTR 2 RIGHT</td><td>PTR 1 LEFT</td></tr><tr><td>BSTEP</td><td>PTR 2 LEFT</td></tr><tr><td>COMPSWAP</td><td>LSHIFT</td></tr><tr><td>SWAP 1 2</td><td>PTR 1 LEFT</td></tr><tr><td>RSHIFT</td><td>PTR 2 LEFT</td></tr><tr><td>PTR 1 RIGHT</td><td>LSHIFT</td></tr><tr><td>PTR 2 RIGHT</td><td>...</td></tr><tr><td>BSTEP</td><td>PTR 1 RIGHT</td></tr><tr><td>...</td><td>PTR 3 RIGHT</td></tr><tr><td>BUBBLE</td><td>BUBBLESORT</td></tr><tr><td>...</td><td>...</td></tr><tr><td>RESET</td><td/></tr></table>



Table content: <table/>

Conventional training sets for addition.

Table content: <table><tr><td/><td colspan="2">No. of function traces</td><td colspan="2">Success with</td></tr><tr><td/><td>Orig.</td><td colspan="3">Mini. Orig. Mini.</td></tr><tr><td>Systematic, 2 digits; 9900 problems</td><td>108900</td><td>647</td><td>N</td><td>N</td></tr><tr><td colspan="2">Systematic, 2 + 3 digits; 162000 problems 2145240</td><td>692</td><td>N</td><td>N</td></tr><tr><td>Random, 4 digits; 10000 problems</td><td>149656</td><td>704</td><td>N</td><td>Y</td></tr><tr><td>Random, 4 digits; 200000 problems</td><td>2994804</td><td>704</td><td>Y</td><td>Y</td></tr><tr><td/><td colspan="2">No. of function traces</td><td colspan="2">Success with</td></tr><tr><td/><td>Orig.</td><td colspan="3">Mini. Orig. Mini.</td></tr><tr><td>Systematic, length 2; 100 problems</td><td>2100</td><td>127</td><td>Y</td><td>Y</td></tr><tr><td>Systematic, length 2 + 3; 1100 problems</td><td>45100</td><td>127</td><td>Y</td><td>Y</td></tr><tr><td>Systematic, length 2 + 3 + 4; 11100 problems</td><td>775100</td><td>127</td><td>Y</td><td>Y</td></tr><tr><td>Random, length 5; 100 problems</td><td>11100</td><td>126</td><td>Y</td><td>Y</td></tr><tr><td>Random, length 5; 1100 problems</td><td>122100</td><td>127</td><td>Y</td><td>Y</td></tr><tr><td>Random, length 5; 11100 problems</td><td>1232100</td><td>127</td><td>N</td><td>Y</td></tr></table>

Conventional training sets for bubblesort.

Table content: <table/>

Conventional training sets for topological sort.

Table content: <table><tr><td colspan="2">No. of function traces</td><td>Success with</td></tr><tr><td>Orig.</td><td colspan="2">Mini. Orig. Mini.</td></tr></table>

tables show that it can be difficult to figure out what demonstrations need to be provided in the training set in order to learn the correct NPI program. To generate a suitable training set without trial and error, the creator needs to have a full understanding of how the oracle functions internally, which is counter to the original goal of automatically learning the behavior of a given program. The methods in our paper can fully automate this process.

Table content: <table><tr><td colspan="3">C SAMPLE COMPLEXITY OF PAST WORK IN NEURAL PROGRAM LEARNING</td></tr><tr><td>Paper</td><td>Tasks</td><td>Training data</td></tr><tr><td>Grefenstette et al. (2015)</td><td>Sequence copying, sequence reversal</td><td>Dynamic</td></tr><tr><td>Joulin &amp; Mikolov (2015a)</td><td>Counting, memorization, binary addition</td><td>Dynamic</td></tr><tr><td colspan="2">Zaremba &amp; Sutskever (2015) Repeated copy, sequence reversal</td><td>Dynamic</td></tr><tr><td>Kaiser &amp; Sutskever (2016)</td><td>Binary addition, binary multiplication, copying,</td><td>200,000</td></tr><tr><td/><td>reversing, duplicating, counting</td><td/></tr><tr><td>Reed &amp; de Freitas (2016)</td><td>Decimal addition, bubblesort</td><td>640/1216</td></tr><tr><td>Kurach et al. (2016)</td><td>BST traversal, array merge, linked list search,</td><td>Dynamic</td></tr><tr><td/><td>etc.</td><td/></tr><tr><td>Zaremba et al. (2016)</td><td>Copy, reverse, walk, addition, multiplication</td><td>Dynamic</td></tr><tr><td>Graves et al. (2016)</td><td>Graph traversal, shortest path, logical inference,</td><td>Dynamic</td></tr><tr><td/><td>mini-SHRDLU</td><td/></tr><tr><td>Price et al. (2016)</td><td>Multiplication</td><td>Dynamic</td></tr><tr><td>Freivalds &amp; Liepins (2017)</td><td>Multiplication</td><td>200,000</td></tr></table>

Peer review (iclr2018):
 Quality The paper is well-written and clear, and includes relevant comparisons to previous work (NPI and recursive NPI). Clarity The paper is clearly written. Originality To my knowledge the method proposed in this work is novel. It is the first to study constructing minimal training sets for NPI given a black-box oracle. However, as pointed out by the authors, there is a lot of similar prior work in software testing. Significance The work could be potentially significant, but there are some very strong assumptions made in the paper that could limit the impact. If the NPI has access to a black-box oracle, it is not clear what is the use of training an NPI in the first place. It would be very helpful to describe a potential scenario where the proposed approach could be useful. Also, it is assumed that the number of possible inputs is finite (also true for the recursive NPI paper), and it is not clear what techniques or lessons of this paper might transfer to tasks with perceptual inputs. The main technical contribution is the search procedure to find minimal training sets and pare down the observation size, and the empirical validation of the idea on several algorithmic tasks. Pros - Greatly improves the data efficiency of recursive NPI. - Training and verification sets are automatically generated by the proposed method. Cons - Requires access to a black-box oracle to construct the dataset. - Not clear that the idea will be useful in more complex domains with unbounded inputs.