Ranking for inductive synthesis of string transformations

摘要

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.

主权项

1. 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, andcomputing an overall ranking score for the candidate transformation program from the sub-expression likelihood scores established for that candidate transformation program.