Ranking for inductive synthesis of string transformations
AssigneeMicrosoft Technology Licensing, LLC
InventorsSumit Gulwani, Rishabh Singh
Life of this patent
Estimating the term…
Abstract
Ranking technique embodiments are presented that use statistical and machine learning techniques to learn the desired ranking function for use in inductive program synthesis for the domain of string transformations. This generally involves automatically creating a training dataset of positive and negative examples from a given set of training tasks, each including multiple input-output examples. From the training dataset, a ranking function is learned that assigns an expression in a program in the domain specific language to a likelihood measure. This ranking function is then used to compute likelihoods of learnt programs from a very small number of input-output examples for a new task.
Claims20
A computer-implemented process for ranking candidate transformation programs, each comprising program expressions comprising sub-expressions, to establish a ranked group of one or more transformation programs each of which produces an output string in a user-desired form from input strings entered by a user, consistent with each of one or more user-supplied input-output examples, comprising:
- using a computer to perform the following process actions:
- inputting the set of candidate transformation programs, which were inductively synthesized from the one or more user-supplied input-output examples, each of which produces an output string in a form exhibited by each user-supplied output example from each user-supplied input example;
- for each candidate transformation program,
- for each sub-expression of the candidate transformation program, in an order from smaller to larger, for which a ranking scheme has been established, establishing a likelihood score using the ranking scheme established for that sub-expression, and
- computing an overall ranking score for the candidate transformation program from the sub-expression likelihood scores established for that candidate transformation program.
A computer-implemented process for performing string transformations, comprising:
- using a computer to perform the following process actions:
- inputting a set of candidate transformation programs, each comprising program expressions comprising sub-expressions, which were inductively synthesized from one or more user-supplied input-output examples, and each of which produces an output string in a form exhibited by each user-supplied output example from each user-supplied input example;
- ranking the set of candidate transformation programs to identify a highest-ranked transformation program;
- and
- applying the highest-ranked transformation program to a user-supplied input string to produce an output string.
A system for ranking candidate transformation programs, each program comprising program expressions comprising sub-expressions, to establish a ranked group of one or more transformation programs each of which produces an output string in a user-desired form from input strings entered by a user, consistent with each of one or more user-supplied input-output examples, comprising:
- one or more computing devices, wherein said computing devices are in communication with each other via a computer network whenever there are multiple computing devices;
- and
- a computer program having program modules executed by the one or more computing devices, the one or more computing devices being directed by the program modules of the computer program to,
- input the set of candidate transformation programs, which were inductively synthesized from the one or more user-supplied input-output examples, each of which produces an output string in a form exhibited by each user-supplied output example from each user-supplied input example;
- and
- for each candidate transformation program,
- for each sub-expression of the candidate transformation program, in an order from smaller to larger, for which a ranking scheme has been established, establish a likelihood score using the ranking scheme established for that sub-expression, and
- compute an overall ranking score for the candidate transformation program from the sub-expression likelihood scores established for that candidate transformation program.
Dependencies are inferred from the claim text.