{"id":447768,"date":"2017-12-07T10:28:50","date_gmt":"2017-12-07T18:28:50","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=447768"},"modified":"2017-12-07T10:28:50","modified_gmt":"2017-12-07T18:28:50","slug":"neural-program-induction","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/neural-program-induction\/","title":{"rendered":"New Meta-learning Techniques for Neural Program Induction"},"content":{"rendered":"

\"\"<\/p>\n

Much research in AI lately focuses on extending the capabilities of deep learning architectures: moving beyond simple classification and pattern recognition into the realm of learning algorithmic<\/em> tasks, such as inductive programming. Building on our past work in neural program synthesis<\/a> for learning string transformations in a functional language, our most recent work explores the challenges of training neural architectures for inducing programs in a more challenging imperative language (Karel) with complex control-flow.<\/p>\n

Specifically, we are working to address the difficulty of program induction when a limited number of examples are available. Traditionally, neural program induction approaches rely on extremely large number of input-output examples\u2014often on the order of hundreds of thousands to millions of examples\u2014to achieve acceptable results. A portion of our research was directed at developing new techniques that can be used with significantly fewer examples. These new techniques, generally termed \u201cportfolio adaptation\u201d and \u201cmeta program induction,\u201d rely on knowledge transfer from similar learning tasks to compensate for the lack of many input\/output examples.<\/p>\n

We compared the performance of four such techniques in a benchmark test over a range of datasets. For the test case, we used the Karel programming language, which introduces complex control flow including conditionals and loops in addition to a set of imperative actions. The neural architectures were provided with a fixed number of example input\/output pairs (ranging from 1 to 100,000), and subsequently asked to derive the correct outputs from a set of new inputs (by implicitly learning to induce the corresponding Karel program). The figure below shows a couple of program induction tasks for the Karel dataset that our meta model could learn accurately from only 2 to 4 examples.<\/p>\n

\"\"<\/p>\n

As detailed in our recently published paper<\/a>, the results are quite promising: one of our meta induction techniques achieved an accuracy of nearly 40% with fewer than 10 examples (compared to 0% using the PLAIN example-driven technique alone).<\/p>\n

The accompanying graph illustrates how the performance of each of the four models varies with the sample size. As can be seen, the newer techniques performed significantly better when fewer examples were provided. While the results converge as the number of examples increase, we believe that our newer techniques still present some advantage in that they require less computing resources\u2014and less processing time\u2014than the traditional model.<\/p>\n

\"\"<\/p>\n

The four techniques are summarized below.<\/p>\n