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.