Semantic entity manipulation using input-output examples

• US 8,799,234 B2
• Filed: 02/03/2011
• Issued: 08/05/2014
• Est. Priority Date: 07/12/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gulwani, Sumit, Singh, Rishabh
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/020,153
• Publication Number:
  US 20120011084A1
• Time in Patent Office: 1,279 Days
• Field of Search: 707/687, 707/692, 707/697, 707/736, 707/781
• US Class Current: 707/687
• CPC Class Codes: G06F 40/16 Automatic learning of transformation rules, e.g. from examples
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Semantic entity manipulation technique embodiments are presented that generate a probabilistic program capable of manipulating character strings representing semantic entities based on input-output examples. The program can then be used to produce a desired output consistent with the input-output examples from inputs of a type included in the examples. The probabilistic program is generated based on the output of parsing, transform and formatting modules. The parsing module employs a probabilistic approach to parsing the input-output examples. The transform module identifies a weighted set of transforms that are capable of producing the output item from the input items of an input-output example to a likelihood specified by their assigned weight. The formatting module generates formatting instructions that transform selected output parts into a form specified by the output items in the input-output examples.

Claims

1. A computer-implemented process for producing a desired output item from one or more input items employing a probabilistic program generated using input-output examples, comprising:

using a computer to perform the following process actions;

receiving input-output examples, each input-output example providing one or more input items and a corresponding desired output item;

parsing 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;

for each input-output example,

identifying one or more transforms from a library of transforms of a type that can produce the desired output item from the input items, and

identifying formatting instructions which are capable of formatting an output item so as to match the formatting of the desired output item of the input-output example;

generating a probabilistic program which given one or more input items of the 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

receiving one or more input items of the same type as the input items of the input-output examples, and producing an output item corresponding to the received input item using the generated probabilistic program.

2. The process of claim 1, wherein each input item and output item comprises a character string, and wherein the library of parses comprises a plurality of semantic entities each comprising an entity class and a collection of fields, and wherein the process action of parsing the input items and the output items to produce a weighted set of parses, comprises the actions of:

for each character string representing the input and output items and each semantic entity found in the library of parses,

identifying a set of field matches wherein each field match comprising the longest sub-string in the input or output item character string that matches a field of a semantic entity from the library of parses,

constructing a parse graph from the set of field matches such that a node exists for each character in the character string, and for each field match a field edge is directed from the node representing the starting character of the field match to the node representing the ending character of the field match, and a delimiter edge is established from each node representing a character in the character string and a node representing any next character in the character string,

identifying parse paths through the parse graph, wherein each parse path comprises a sequence of nodes that starts with the node representing the first character in the character string and ends with the node representing the last character in the character string, and whose nodes are alternately connected by an edge that alternates between a field edge and a delimiter edge, such that each identified parse path comprises a sequence of semantic entity field and delimiter pairs, and

for each parse path identified,

computing a constraint weight factor for each identified parse path which is proportional to the number of constraints associated with the semantic entity under consideration that the parse path satisfies and the constraint weight assigned to each of the satisfied constraints, wherein each semantic entity is associated with a set of weighted constraints specifying field assignments and ordering between fields or delimiters for the semantic entity with the constraint weight of such a constraint being greater for constraints that are more likely to be exhibited by the semantic entity,

computing a measure of the similarity between the parse path and each of a set of valid parse descriptors which are associated with the semantic entity, wherein each of the valid parse descriptors comprises a sequence of semantic entity field and delimiter pairs that represents a valid parsing of the semantic entity,

computing a weight value for the parse path based on the constraint weight factor and valid parse descriptor similarity measure computed for the parse path, and

designating the parse path to be a designated parse descriptor of the semantic entity and associating the designated parse descriptor and the computed weight value with the semantic entity to form a weighted semantic entity and parse descriptor tuple.

3. The process of claim 2, further comprising a process action of, for each weighted semantic entity and parse descriptor tuple, converting the semantic entity to a prescribed canonical form of the semantic entity.

4. The process of claim 2, wherein the process action of computing the measure of the similarity between an identified parse path and a parse descriptors, comprises the actions of:

computing a closeness measure that is inversely proportional to the hamming distance between the parse path and the parse descriptor, such that the closer the pattern of semantic entity fields and delimiters in the parse path is to the pattern of semantic entity fields and delimiters in the parse descriptor, the larger the closeness measure; and

designating the closeness measure to be the valid parse descriptor similarity measure for the parse path.

5. The process of claim 2, wherein the process action of computing a constraint weight factor for each identified parse path which is proportional to the number of constraints associated with the semantic entity under consideration that the parse path satisfies and the constraint weight assigned to each of the satisfied constraints, comprises an action of taking the ratio of the sum of the weights of the constraints that are satisfied by the weight of all constraints.

6. The process of claim 2, wherein the process action of computing the weight value for the parse path based on the constraint weight factor and valid parse descriptor similarity measure computed for the parse path, comprises an action of taking the product of the constraint weight factor and the similarity measure.

7. The process of claim 2, wherein the entity class of each semantic entity identifies one or more transforms that apply to that class of entities, and wherein the process action of, for each input-output example, identifying one or more transforms from a library of transforms of a type that can produce the desired output item from the input items, comprises the actions of:

identifying the parse descriptor tuples associated with the input items of the input-output example;

identifying the parse descriptor tuple associated with the output item of the input-output example; and

for each of the one or more transforms associated with the classes of the entities in the parse descriptor tuples of the input and output items of the input-output example,

identifying those transforms that when applied to the semantic entities of the identified parse descriptor tuples associated with the input items produce the entity of the identified parse descriptor tuple associated with the output item, and

computing a weighting factor for each such transform, where the weighting factor is a measure of the likelihood of the transform being the desired one.

8. The process of claim 7, wherein the process action of identifying formatting instructions which are capable of formatting an output item so as to match the formatting of the desired output item of the input-output example, comprises an action of associating formatting instructions from a library of formatting instructions, for each semantic entity field identified in the parse descriptor of the parse descriptor tuple associated with the output item of the input-output example, which produces the corresponding field of the semantic entity of that descriptor tuple in the format exhibited by the portion of the output item associated with the semantic entity field.

9. The process of claim 8, wherein the process action of generating a probabilistic program which given one or more input items of the 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, comprises the actions of:

for each semantic entity in the parse descriptor tuples of the output items of the input-output examples,

associating the transform, its computed weight factor, and the identified formatting instructions for the semantic entity of the identified parse descriptor tuple associated with the output item to form a parse-compute-print tuple, for each of the one or more transforms associated with the classes of the entities in the parse descriptor tuples of the input items of the input-output examples;

identifying parse-compute-print tuples that have the same transform and the formatting instructions;

for each group of parse-compute-print tuples that have the same transform and the formatting instructions, replacing the group with a single parse-compute-print tuple having the same transform and the formatting instructions as the group and in which the weight factor is the sum of all the weight factors in the group;

identifying parse descriptor tuples of the input items and output items of the input-output examples that have the same parse descriptor;

for each group of parse descriptor tuples that have the same parse descriptor, replacing the group with a single parse descriptor tuple having the same parse descriptor as the group and in which the weight value is the sum of all the weight values in the group; and

grouping the remaining parse descriptor tuples and the parse-compute-print tuples to form the probabilistic program.

10. The process of claim 8, wherein the entity class of each semantic entity identifies a prescribed canonical form of the semantic entity, said process further comprising a process actions of, for each weighted semantic entity and parse descriptor tuple, converting the semantic entity to the prescribed canonical form of the semantic entity, and wherein the process action of applying the transform to the semantic entities of the identified parse descriptor tuples associated with the input items to produce the entity of the identified parse descriptor tuple associated with the output item, comprises an action of producing the entity of the identified parse descriptor tuple associated with the output item in the prescribed canonical form, and wherein the process action of identifying formatting instructions which are capable of formatting an output item so as to match the formatting of the desired output item of the input-output example, further comprises an action of converting the output item from the prescribed canonical form to a form consistent with the desired output item of the input-output example.

11. The process of claim 7, wherein the process action of computing the weighting factor for the identified transform, comprises an action of computing the weighting factor based on the weight values computed for the parse descriptor tuples of the input items and output item in the input-output example and a measure of the complexity of the transform.

12. The process of claim 7, wherein the process action of computing the weighting factor for the applied transform, comprises the actions of:

identifying the minimum weight value among the weight values of the parse descriptor tuples associated with the input items of the input-output example for which the transform was identified and the weight value of the parse descriptor tuple associated the output item of the input-output example for which the transform was identified;

computing an inverse of a size of the applied transform;

computing the product of the identified minimum weight and the computed inverse of the size of the applied transform;

designating the computed product to be the weighting factor.

13. The process of claim 7, wherein the process action of identifying formatting instructions which are capable of formatting an output item so as to match the formatting of the desired output item of the input-output example, comprises the process actions of:

for each semantic entity field identified in the parse descriptor of the parse descriptor tuple associated with the output item of the input-output example, determining whether the semantic entity field is one of a group of prescribed base-type fields;

whenever a semantic field in the parse descriptor of the parse descriptor tuple associated with the output item of the input-output example is determined to be a base-type field, associating formatting instructions with that semantic field which have been pre-defined for that type of base-type field;

whenever a semantic field in the parse descriptor of the parse descriptor tuple associated with the output item of the input-output example is determined not to be a base-type field, associating formatting instructions which produce the corresponding field of the semantic entity of that descriptor tuple in the format exhibited by the portion of the output item associated with the semantic entity field.

14. The process of claim 2, wherein the entity class of each semantic entity identifies one or more transforms that apply to that class of entities, and wherein the process action of, for each input-output example, identifying one or more transforms from a library of transforms of a type that can produce the desired output item from the input items, comprises the actions of:

identifying the parse descriptor tuples associated with the input items of the input-output example;

identifying the parse descriptor tuple associated with the output item of the input-output example; and

for combinations of the one or more transforms associated with the classes of the entities in the parse descriptor tuples of the input and output items of the input-output example, up to a prescribed number of transformations in the combination,

identifying those combinations of transforms that when applied to the semantic entities of the identified parse descriptor tuples associated with the input items produce the entity of the identified parse descriptor tuple associated with the output item, and

computing a weighting factor for each identified transform combination comprising a measure of the likelihood of the transform combination being the desired one.

15. The process of claim 1, wherein the one or more input items of the same type as the input items of the input-output examples are received in conjunction with receiving the input-output examples, and wherein the process action of parsing the input items and the output items to produce a weighted set of parses, comprises an action of parsing the input and output items associated with the input-output examples, as well as the received input items of the same type as the input items of the input-output examples.

16. The process of claim 15, wherein input-output examples and the one or more input items of the same type as the input items of the input-output examples comprise spreadsheet data.

17. 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.

18. The system of claim 17, wherein the program execution module produces the output item corresponding to the highest ranking output item in the set of ranked output items, and whenever there are more than one output item in the set of ranked output items, the program execution module further produces an indicator indicating that other lower ranking output items were produced and are available for review.

19. 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.

20. The computer-readable storage medium of claim 19, wherein the transformation logic identifies transforms that apply at least one of arithmetic computations, or round-off computations, or lookup table computations, or computer network-based computations, to the input items to produce the desired output item.