Automatic refinement of information extraction rules

1. A computer-implemented method of automatically refining rules for information extraction, comprising:

a computer system receiving a plurality of documents, a plurality of rules for information extraction, and a plurality of correct results and a plurality of incorrect results from applying said plurality of rules on said plurality of documents;

said computer system determining a provenance graph of said plurality of rules applied on said plurality of documents, wherein for an operator of said plurality of operators, said provenance graph indicates a sequence of evaluations of a set of rules included in said plurality of rules that generates an output of said operator;

said computer system determining a first set of rule changes (high-level changes) to specify a set of operators of said plurality of operators to be changed to eliminate said incorrect results, wherein said determining said high-level changes is based on said provenance graph;

said computer system determining a second set of rule changes (low-level changes) to specify how to implement said high-level changes, wherein each low-level change specifies a change in a structure of an operator of said set of operators, or specifies an insertion of a new operator subtree in between two operators of said set of operators, wherein said determining said low-level changes includes:

determining a mapping from intermediate tuples to output tuples included in said incorrect results, wherein said intermediate tuples result from said high-level changes;

determining a top-k set of low-level changes for each operator of said set of operators and for a category of a plurality of categories of said low-level changes;

determining local effects of each low-level change of said top-k set of low-level changes; and

propagating said local effects to said output tuples based on said mapping;

said computer system determining effects of said low-level changes on said correct results and on said plurality of rules;

said computer system generating a ranked list of said low-level changes based on said determined effects of said low-level changes; and

a processor of said computer system implementing said low-level changes based on said ranked list, wherein said implementing said low-level changes includes refining said plurality of rules to eliminate said incorrect results and to minimize said determined effects of said low-level changes.

2. The method of claim 1 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies a modification to numerical join parameters n 1 , n 2 that specify a range [n 1 , n 2 ], and wherein said determining said corresponding top-k set of low-level changes includes:

determining a plurality of utility values corresponding to values in said range [n 1 , n 2 ], wherein a utility value of said plurality of utility values corresponds to a value in said range [n 1 , n 2 ] and is based on a change in quality of a result of applying said plurality of rules with said value removed from said range [n 1 , n 2 ]; and

determining top-k sub-sequences of said range [n 1 , n 2 ] based on maximum summations of utility values included in said plurality of utility values.

3. The method of claim 1 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies a removal of entries in a dictionary file by removing corresponding entries in said dictionary file from input to said plurality of rules, and wherein said determining said corresponding top-k set of low-level changes includes:

grouping outputs of a Dictionary operator by entry in said dictionary file;

for each entry in said dictionary file that matches at least one high-level change, determining tuples that are eliminated from a result of applying said plurality of rules based on a removal of an entry in said dictionary file;

ranking said entries in said dictionary file according to an effect that removing each entry has on quality of said result; and

generating a low-level change for the top 1 entry, the top 2 entries, . . . , up to the top k entries based on said ranking said entries.

4. The method of claim 1 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies an addition of a new filtering dictionary that filters spans based on a presence of matches of entries of said dictionary file in close proximity, and wherein said determining said corresponding top-k set of low-level changes includes:

identifying tokens to the left and to the right of each span in a tuple affected by a high-level change of said high-level changes;

determining potential entries of said dictionary file by performing a union of said tokens;

ranking said potential entries according to an effect on quality of a result of applying said plurality of rules by filtering with said potential entries; and

generating said top-k set of low-level changes based on said ranking said potential entries.

5. The method of claim 1 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies an addition of a filtering view, and wherein said determining said corresponding top-k set of low-level changes includes:

identifying each pair of views V 1 and V 2 such that V 1 and V 2 are not descendants of one another in a relational algebra representation of said plurality of rules;

for each filter policy selected from the group consisting of Overlap, Contains and Contained, identifying tuples of V 1 that are in relationships with at least one span in V 2 ;

ranking filters resulting from said identifying said tuples of V 1 , wherein said ranking filters is based on an effect on quality of a result of applying said plurality rules; and

generating said top-k set of low-level changes based on said ranking said filters.

6. The method of claim 1 , wherein said determining said provenance graph of said plurality of rules includes rewriting an SQL query Q representing said plurality of rules into a provenance query Q P by recursively rewriting each operator Op in a relational algebra representation of Q, wherein said recursively rewriting Op in Q preserves a result of Op along with additional provenance attributes through which information about input tuples to Op that contributed to a creation of an output tuple is propagated, and wherein given Op and a tuple t in said result of Op, said additional provenance attributes are sufficient to reconstruct tuples included in said input tuples that are responsible for generating said tuple t.

7. A computer system comprising:

a processor; and

a computer-readable memory unit coupled to said processor, said memory unit containing instructions that when carried out by said processor implement a method of automatically refining rules for information extraction, said method comprising:

receiving a plurality of documents, a plurality of rules for information extraction, and a plurality of correct results and a plurality of incorrect results from applying said plurality of rules on said plurality of documents;

determining a provenance graph of said plurality of rules applied on said plurality of documents, wherein for an operator of said plurality of operators, said provenance graph indicates a sequence of evaluations of a set of rules included in said plurality of rules that generates an output of said operator;

determining a first set of rule changes (high-level changes) to specify a set of operators of said plurality of operators to be changed to eliminate said incorrect results, wherein said determining said high-level changes is based on said provenance graph;

determining a second set of rule changes (low-level changes) to specify how to implement said high-level changes, wherein each low-level change specifies a change in a structure of an operator of said set of operators, or specifies an insertion of a new operator subtree in between two operators of said set of operators, wherein said determining said low-level changes includes:

determining a mapping from intermediate tuples to output tuples included in said incorrect results, wherein said intermediate tuples result from said high-level changes;

determining a top-k set of low-level changes for each operator of said set of operators and for a category of a plurality of categories of said low-level changes;

determining local effects of each low-level change of said top-k set of low-level changes; and

propagating said local effects to said output tuples based on said mapping;

determining effects of said low-level changes on said correct results and on said plurality of rules;

generating a ranked list of said low-level changes based on said determined effects of said low-level changes; and

implementing said low-level changes based on said ranked list, wherein said implementing said low-level changes includes refining said plurality of rules to eliminate said incorrect results and to minimize said determined effects of said low-level changes.

8. The system of claim 7 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies a modification to numerical join parameters n 1 , n 2 that specify a range [n 1 , n 2 ], and wherein said determining said corresponding top-k set of low-level changes includes:

determining a plurality of utility values corresponding to values in said range [n 1 , n 2 ], wherein a utility value of said plurality of utility values corresponds to a value in said range [n 1 , n 2 ] and is based on a change in quality of a result of applying said plurality of rules with said value removed from said range [n 1 , n 2 ]; and

determining top-k sub-sequences of said range [n 1 , n 2 ] based on maximum summations of utility values included in said plurality of utility values.

9. The system of claim 7 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies a removal of entries in a dictionary file by removing corresponding entries in said dictionary file from input to said plurality of rules, and wherein said determining said corresponding top-k set of low-level changes includes:

grouping outputs of a Dictionary operator by entry in said dictionary file;

for each entry in said dictionary file that matches at least one high-level change, determining tuples that are eliminated from a result of applying said plurality of rules based on a removal of an entry in said dictionary file;

ranking said entries in said dictionary file according to an effect that removing each entry has on quality of said result; and

generating a low-level change for the top 1 entry, the top 2 entries, . . . , up to the top k entries based on said ranking said entries.

10. The system of claim 7 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies an addition of a new filtering dictionary that filters spans based on a presence of matches of entries of said dictionary file in close proximity, and wherein said determining said corresponding top-k set of low-level changes includes:

identifying tokens to the left and to the right of each span in a tuple affected by a high-level change of said high-level changes;

determining potential entries of said dictionary file by performing a union of said tokens;

ranking said potential entries according to an effect on quality of a result of applying said plurality of rules by filtering with said potential entries; and

generating said top-k set of low-level changes based on said ranking said potential entries.

11. The system of claim 7 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies an addition of a filtering view, and wherein said determining said corresponding top-k set of low-level changes includes:

identifying each pair of views V 1 and V 2 such that V 1 and V 2 are not descendants of one another in a relational algebra representation of said plurality of rules;

for each filter policy selected from the group consisting of Overlap, Contains and Contained, identifying tuples of V 1 that are in relationships with at least one span in V 2 ;

ranking filters resulting from said identifying said tuples of V 1 , wherein said ranking filters is based on an effect on quality of a result of applying said plurality rules; and

generating said top-k set of low-level changes based on said ranking said filters.

12. The system of claim 7 , wherein said determining said provenance graph of said plurality of rules includes rewriting an SQL query Q representing said plurality of rules into a provenance query Q P by recursively rewriting each operator Op in a relational algebra representation of Q, wherein said recursively rewriting Op in Q preserves a result of Op along with additional provenance attributes through which information about input tuples to Op that contributed to a creation of an output tuple is propagated, and wherein given Op and a tuple t in said result of Op, said additional provenance attributes are sufficient to reconstruct tuples included in said input tuples that are responsible for generating said tuple t.

13. A computer program product, comprising:

a computer-readable, tangible storage device that is not a transitory form of signal transmission; and

a computer-readable program code stored on the computer-readable storage device, said computer-readable program code containing instructions that are carried out by a processor of a computer system to implement a method of automatically refining rules for information extraction, said method comprising the steps of:

said computer system receiving a plurality of documents, a plurality of rules for information extraction, and a plurality of correct results and a plurality of incorrect results from applying said plurality of rules on said plurality of documents;

said computer system determining a provenance graph of said plurality of rules applied on said plurality of documents, wherein for an operator of said plurality of operators, said provenance graph indicates a sequence of evaluations of a set of rules included in said plurality of rules that generates an output of said operator;

said computer system determining a first set of rule changes (high-level changes) to specify a set of operators of said plurality of operators to be changed to eliminate said incorrect results, wherein said determining said high-level changes is based on said provenance graph;

said computer system determining a second set of rule changes (low-level changes) to specify how to implement said high-level changes, wherein each low-level change specifies a change in a structure of an operator of said set of operators, or specifies an insertion of a new operator subtree in between two operators of said set of operators, wherein said determining said low-level changes includes:

determining a mapping from intermediate tuples to output tuples included in said incorrect results, wherein said intermediate tuples result from said high-level changes;

determining a top-k set of low-level changes for each operator of said set of operators and for a category of a plurality of categories of said low-level changes;

determining local effects of each low-level change of said top-k set of low-level changes; and

propagating said local effects to said output tuples based on said mapping;

said computer system determining effects of said low-level changes on said correct results and on said plurality of rules;

said computer system generating a ranked list of said low-level changes based on said determined effects of said low-level changes; and

said computer system implementing said low-level changes based on said ranked list, wherein said implementing said low-level changes includes refining said plurality of rules to eliminate said incorrect results and to minimize said determined effects of said low-level changes.

14. The program product of claim 13 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies a modification to numerical join parameters n 1 , n 2 that specify a range [n 1 , n 2 ], and wherein said determining said corresponding top-k set of low-level changes includes:

determining a plurality of utility values corresponding to values in said range [n 1 , n 2 ], wherein a utility value of said plurality of utility values corresponds to a value in said range [n 1 , n 2 ] and is based on a change in quality of a result of applying said plurality of rules with said value removed from said range [n 1 , n 2 ]; and

determining top-k sub-sequences of said range [n 1 , n 2 ] based on maximum summations of utility values included in said plurality of utility values.

15. The program product of claim 13 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies a removal of entries in a dictionary file by removing corresponding entries in said dictionary file from input to said plurality of rules, and wherein said determining said corresponding top-k set of low-level changes includes:

grouping outputs of a Dictionary operator by entry in said dictionary file;

for each entry in said dictionary file that matches at least one high-level change, determining tuples that are eliminated from a result of applying said plurality of rules based on a removal of an entry in said dictionary file;

ranking said entries in said dictionary file according to an effect that removing each entry has on quality of said result; and

generating a low-level change for the top 1 entry, the top 2 entries, . . . , up to the top k entries based on said ranking said entries.

16. The program product of claim 13 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies an addition of a new filtering dictionary that filters spans based on a presence of matches of entries of said dictionary file in close proximity, and wherein said determining said corresponding top-k set of low-level changes includes:

identifying tokens to the left and to the right of each span in a tuple affected by a high-level change of said high-level changes;

determining potential entries of said dictionary file by performing a union of said tokens;

ranking said potential entries according to an effect on quality of a result of applying said plurality of rules by filtering with said potential entries; and

generating said top-k set of low-level changes based on said ranking said potential entries.

17. The program product of claim 13 , wherein said determining said top-k set of low-level changes includes determining a corresponding top-k set of low-level changes in a category of said plurality of categories, wherein said category specifies an addition of a filtering view, and wherein said determining said corresponding top-k set of low-level changes includes:

identifying each pair of views V 1 and V 2 such that V 1 and V 2 are not descendants of one another in a relational algebra representation of said plurality of rules;

for each filter policy selected from the group consisting of Overlap, Contains and Contained, identifying tuples of V 1 that are in relationships with at least one span in V 2 ;

ranking filters resulting from said identifying said tuples of V 1 , wherein said ranking filters is based on an effect on quality of a result of applying said plurality rules; and

generating said top-k set of low-level changes based on said ranking said filters.