Neural network for program synthesis

Patent metadata

Field	Value
Publication number	US-10795645-B2
Application number	US-201715470784-A
Country	US
Kind code	B2
Filing date	Mar 27, 2017
Priority date	Mar 27, 2017
Publication date	Oct 6, 2020
Grant date	Oct 6, 2020

Abstract

Described are systems, methods, and computer-readable media for program generation in a domain-specific language based on input-output examples. In accordance with various embodiments, a neural-network-based program generation model conditioned on an encoded set of input-output examples is used to generate a program tree by iteratively expanding a partial program tree, beginning with a root node and ending when all leaf nodes are terminal.

First claim

What is claimed is:

1. A method comprising:
for a given domain-specific language that defines a plurality of symbols and a plurality of production rules, providing an input-output encoder and a program-generation model comprising a neural network, the input-output encoder and the neural network having been trained on a plurality of programs within the domain-specific language and a plurality of respective training sets of input-output examples associated with the programs, wherein, for each of the plurality of programs and its associated training set, each input-output example of the training set comprises a pair of an input to the program and a corresponding output produced by the program from the input;
providing a test set of input-output examples for a target program;
using one or more hardware processors to perform operations for generating the target program based on the test set of input-output examples, the operations comprising:
encoding the test set of input-output examples using the input-output encoder;
conditioning the program-generation model on the encoded set of input-output examples; and
using the neural network to generate a program tree representing the target program by iteratively expanding a partial program tree, beginning with a root node and ending when all leaf nodes are terminal, based on a computed probability distribution for a set of valid expansions, wherein leaves in the program tree and the partial program tree represent symbols in the domain-specific language and wherein non-leaf interior nodes in the program tree and the partial program tree represent production rules in the domain-specific language.

2. The method of claim 1 , wherein the neural network is a recursive-reverse-recursive neural network.

3. The method of claim 2 ,
wherein the recursive-reverse-recursive neural network specifies distributed representations of the plurality of symbols and the plurality of production rules and, for each of the plurality of production rules, first and second deep neural networks, and
wherein iteratively expanding the partial program tree comprises, in each iteration:
computing global leaf representations for at least non-terminal ones of the leaf nodes of the partial program tree by retrieving the distributed representations of the symbols represented by the leaf nodes, performing a recursive bottom-to-top pass through the partial program tree from the leaf nodes to the root node using the first deep neural networks, and thereafter performing a reverse-recursive top-to-bottom pass through the partial program tree from the root node to the leaf nodes using the second deep neural networks;
computing the probability distribution for the set of valid expansions from the global leaf representations and the distributed representations of the production rules;
selecting a non-terminal leaf node and a production rule based on the computed probability distribution; and
expanding the partial program tree by applying the selected production rule to the selected non-terminal leaf node.

4. The method of claim 3 , wherein the program-generation model is conditioned prior to performing the recursive bottom-to-top pass by appending the encoded set of input-output examples to the distributed representations of the symbols associated with the leaf nodes to obtain updated distributed representations of the leaf nodes, and passing the updated distributed representations to a conditioning network.

5. The method of claim 3 , wherein the program-generation model is conditioned after performing the recursive bottom-to-top pass and prior to performing the reverse-recursive top-to-bottom pass by appending the encoded set of input-output examples to a distributed representation of the root node resulting from the bottom-to-top pass to thereby obtain an updated distributed representation of the root node, and passing the updated distributed representation of the root node to a conditioning network.

6. The method of claim 3 , wherein the program-generation model is conditioned after performing the reverse-recursive top-to-bottom pass by appending the encoded set of input-output examples to the global leaf representations to obtain updated global leaf representations, and passing the updated global leaf representations to a conditioning network prior to computing the probability distribution.

7. The method of claim 3 , wherein encoding the set of input-output examples comprises processing input and output of each input-output example separately using two respective deep bidirectional long short term memory neural networks to obtain respective input and output representations, and computing a cross correlation between each input example representation and the respective output example representation.

8. The method of claim 3 , wherein the probability distribution is a normalized exponential distribution over products of the global leaf representations and the distributed representations of the production rules.

9. The method of claim 3 , further comprising processing the global leaf representations with a bidirectional long short term memory neural network prior to computing the probability distribution.

10. The method of claim 3 , wherein the production rules defined by the domain-specific language are string transformations.

11. A system comprising:
one or more hardware processors; and
one or more machine-readable media storing instructions that, when executed by the one or more hardware processors, cause the one or more hardware processors to perform operations for generating a target program in a domain-specific language based on a test set of input-output examples each comprising a pair of an input and an output to be produced by the target program from the input, the domain-specific language defining a plurality of symbols and a plurality of production rules, the operations comprising:
using an input-output encoder to encode the test set of input-output examples provided for the target program, the input-output encoder trained on a plurality of programs within the domain-specific language and a plurality of respective training sets of input-output examples associated with the programs, wherein, for each of the plurality of programs and its associated training set, each input-output example of the training set comprises a pair of an input to the program and a corresponding output produced by the program from the input;
conditioning a program-generation model on the encoded set of input-output examples, the program-generation model comprising a neural network trained, together with the input-output encoder, on the plurality of programs and the plurality of respective training sets of input-output examples; and
using the neural network to generate a program tree representing the target program by iteratively expanding a partial program tree, beginning with a root node and ending when all leaf nodes are terminal, based on a computed probability distribution for a set of valid expansions, wherein leaves in the program tree and the partial program tree represent symbols in the domain-specific language and wherein non-leaf interior nodes in the program tree and the partial program tree represent production rules in the domain-specific language.

12. The system of claim 11 ,
wherein the neural network is a recursive-reverse-recursive neural network that specifies distributed representations of the plurality of symbols and the plurality of production rules and, for each of the plurality of production rules, first and second deep neural networks; and
wherein iteratively expanding the partial program tree comprises, in each iteration, operations comprising:
computing global l

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Mohamed Abdelrahman S A
• Singh Rishabh
• Li Lihong
• Zhou Dengyong
• Kohli Pushmeet
• Parisotto Emilio

Classifications

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title

• G06N3/045

  Combinations of networks · CPC title

• G06N3/0455

  Auto-encoder networks; Encoder-decoder networks · CPC title

• G06N3/0442

  characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU] · CPC title

• G06N3/09

  Supervised learning · CPC title