Semantic entity manipulation using input-output examples

A system for producing a desired output item from one or more input items employing a probabilistic program generated using input-output examples, comprising:

• a computing device;
• and
• a computer program comprising program modules executed by the computing device, said program modules comprising,
• a parsing module which parses input items and output items making up said input-output examples to produce a weighted set of parses, each weighted parse representing a different potential parsing of each input and output item weighted in accordance with a measure of the likelihood the parsing is a valid parsing based on a comparison to a library of parses,
• a transform module which, for each input-output example, identifies one or more transforms from a library of transforms of a type that can produce the desired output item from the input items, and
• a formatting module which identifies formatting instructions that are capable of formatting an output item so as to match the formatting of the desired output item of an input-output example;
• a program generation module which generates a probabilistic program that given one or more input items of a same type as the input items of the input-output examples, employs the identified transforms and the formatting instructions, to produce a set of ranked output items, wherein the output items are ranked in order of a weighting factor computed therefor comprising a measure indicative of how accurately the transform produces the output item from the input items associated with the input-output examples, and
• a program execution module which produces an output item corresponding to a received input item of the same type as the input items of the input-output examples using the generated probabilistic program.

A computer-readable storage medium for storing computer readable instructions, the computer-readable instructions providing a probabilistic program generation system which produces a desired output item from one or more input items using input-output examples when executed by one or more processing devices, the computer-readable instructions comprising:

• parsing logic configured to receive input-output examples, each input-output example providing one or more input items and a corresponding desired output item, and to parse the input items and the output items to produce a weighted set of parses, each weighted parse representing a different potential parsing of each input and output item weighted in accordance with a measure of the likelihood the parsing is a valid parsing based on a comparison to a library of parses;
• transformation logic configured to, for each input-output example, identify one or more transforms of a type that can produce the desired output item from the input items;
• formatting logic configured to identify formatting instructions which are capable of formatting an output item so as to match the formatting of the desired output item of a input-output example;
• generating logic configured to generate a probabilistic program which given one or more input items of a same type as the input items of the input-output examples, employs the identified transforms and the formatting instructions, to produce an output item corresponding to the one or more input items;
• and
• execution logic configured to receive one or more input items of the same type as the input items of the input-output examples, and produce an output item corresponding to the received input item using the generated probabilistic program.