Neural Program Meta-Induction
Most recently proposed methods for Neural Program Induction work under the assumption of having a large set of input/output (I/O) examples for learning any underlying input-output mapping. This paper aims to address the problem of data and computation efficiency of program induction by leveraging information from related tasks. Specifically, we propose two approaches for cross-task knowledge transfer to improve program induction in limited-data scenarios. In our first proposal, portfolio adaptation, a set of induction models is pretrained on a set of related tasks, and the best model is adapted towards the new task using transfer learning. In our second approach, meta program induction, a k-shot learning approach is used to make a model generalize to new tasks without additional training. To test the efficacy of our methods, we constructed a new benchmark of programs written in the Karel programming language [17]. Using an extensive experimental evaluation on the Karel benchmark, we demonstrate that our proposals dramatically outperform the baseline induction method that does not use knowledge transfer. We also analyze the relative performance of the two approaches and study conditions in which they perform best. In particular, meta induction outperforms all existing approaches under extreme data sparsity (when a very small number of examples are available), i.e., fewer than ten. As the number of available I/O examples increase (i.e. a thousand or more), portfolio adapted program induction becomes the best approach. For intermediate data sizes, we demonstrate that the combined method of adapted meta program induction has the strongest performance.
The paper investigates neural nets learning to imitate programs from varying numbers of input-output examples, both in the plain supervised learning setting and by leveraging transfer across problems. This is done in the domain of Karel, a simple programming language that describes how input grid worlds are transformed into output grid worlds through actions of a so-called hero who moves around in those worlds according to instructions given in a Karel program. The paper randomly generates many such Karel programs and, for each program, a number of corresponding input-output worlds. The learning problem for the neural architectures is to learn from input-output examples how to apply the same transformation to worlds as the (latent) Karel program. The paper compares plain supervised learning, supervised learning that's initialized using the closest previous task, k-shot meta-learning, and k-shot meta-learning that is refined based on the current task. The paper finds that in the Karel domain, each of these techniques has its use depending on the number of tasks and input-output examples per task available.
The paper seems technically sound.
There is another natural comparison that the authors didn't make, which is to follow the k-shot approach, but to learn a function from the example tasks to the *weights* of a neural net that turns input into output. That is, the task encoder generates the weights of both input encoder and output decoder. In this setting, adaptation is more natural than in the current META+ADAPT case, since you can literally just start with the weights generated by the meta network and optimize from there in exactly the same way that plain supervised learning does.
The paper is generally clear, but I don't sufficiently understand the Karel task and the difficulty of the associated learning problem. The paper shows a Karel sample task, but I would have liked to see more examples of the randomly sampled tasks (perhaps in an appendix) so that I can better understand how representative the sample task is. This would have answered the following questions: (1) How complex are the programs sampled from the Karel DSL CFG? A thing that can happen if you sample expressions from recursive PCFGs is that most are really simple, and a few are very complex; the expressions are not of similar size. Is that the case here? (2) How large are the I/O grids? How much variation is there? (3) I'm surprised that the LSTM can output the required diff to transform inputs into outputs as well as it does. If the diffs are long, I would have expected issues with the LSTM "forgetting" the initial context after a while or having trouble to exactly produce the right values or not generalizing correctly. The fact that this works so well makes me wonder whether the learning problem is easier than I think. I was also surprised to see that the NLL is as good as it is (in Figure 5). Because the computational structure of the conv net is quite different from the way the input-output examples are produced by the Karel program (the hero moves around locally to manipulate the grid, the conv net produces the output in one go), I think I would have expected the neural net to only approximately solve the problems. (This impression may well be due to the fact that I don't have a good intuition for what the problems are like.)
The table comparing to related work is helpful. That said, I'm still a bit unclear on the extent to which the paper's main contribution is the systematic evaluation of different program induction methods, and to what extent the paper claims to actually have invented some of the methods.
I think this paper will be useful to practitioners, conditioned on the results generalizing across domains. As the paper says, the results do seem fairly intuitive, so it seems plausible that they do generalize, but it would certainly have been nice to replicate this in another domain.