Back to results
US 6,714,941 B1Granted
Learning data prototypes for information extraction
AssigneeUniversity of Southern California
InventorsKristina Lerman, Steven Minton
Life of this patent
Estimating the term…
Abstract
A method for determining statistically significant token sequences lends itself for use in the recognition of broken wrappers as well as the construction of new wrapper rules. When new wrapper rules are needed as the underlying wrapped data has changed, training examples are used to recognized data rule candidates that are culled with a bias for rule candidates that would be probably more successful. The resulting rule candidate set is clustered according to feature characteristics, then compared to the training examples. Those rule candidates most similar to the training examples are used to create new wrapper rules.
Claims22
A method for recognizing significant token sequences, the steps comprising:
- providing tokenized data, said data having a token sequence, said token sequence having tokens, each of said tokens assigned a number of different hierarchical token types, said token types categorizing each of said tokens;
- constructing a prefix tree according to said token types of said token sequence;
- pruning a first generalization node among first sibling nodes of said prefix tree when first specific nodes of said first generalization node substantially repeat said first generalization node;
- removing token sequence patterns from a second generalization node that are repeated in second sibling nodes to said second generalization node, said second sibling nodes being specific nodes of said second generalization node;
- and
- returning a token sequence pattern from a node of said prefix tree when a difference between a number of occurrences of said pattern and a number of occurrences of patterns of children of said node is significant with respect to a number of occurrences of said pattern in a parent node to said node;
- whereby
- said token sequence pattern indicates a type of information when information manifests said token sequence pattern so that said information may be recognized for its type.
5 more elements
A method for recognizing data fields in a data collection, the steps comprising:
- pre-processing the data collection to provide a syntactic hierarchy tree of tokens;
- determining statistically significant token patterns in the data collection;
- providing examples of desired data fields;
- and
- establishing a prefix tree for said desired data fields according to said statistically significant token patterns;
- whereby
- determination is made of token sequences identifying said desired data fields.
4 more elements
A method for validating wrapper operation, the steps comprising:
- executing a wrapper on a first data collection and extracting a first number N of training examples as a result thereof, said N training examples being indexed separately by a first index ti;
- learning a second number m of patterns describing common beginnings and endings of each data field of said training examples, said m patterns being indexed separately by a second index m1;
- executing said wrapper on a second data collection and extracting a third number n of test examples as a result thereof, said n test examples being indexed separately by a third index ki;
- ti providing a first distribution t;
- ki providing a second distribution k;
- comparing said first distribution t with said second distribution k;
- verifying proper operation of said wrapper if said first distribution t is the same as said second distribution k within a significance level;
- and
- verifying improper operation of said wrapper if said first distribution t is not the same as said second distribution k within said significance level;
- whereby
- operation of said wrapper may be verified over time and due to changes in said first and second data collections.
8 more elements
A method for determining a new wrapper for a changed source of data, the steps comprising:
- providing a set of training examples relevant to a data source prior to a change in said data source;
- providing a set of pages from said data source after said change in said data source;
- establishing data fields in said sets of data from said changed data source to provide a set of data candidates;
- clustering said data candidates according to characteristic features to provide data candidate clusters;
- scoring said data candidate clusters based on how similar each data candidate cluster is to each of said training examples;
- selecting a data cluster having a highest score for a particular one of said training examples as corresponding to said particular training example;
- whereby
- a new wrapper may be constructed by substituting said selected data cluster for said particular training example and generating rules appropriate for said substitution for said new wrapper.
5 more elements
A method for recognizing data fields in a data collection, the steps comprising:
- pre-processing the data collection to provide a syntactic hierarchy tree of tokens;
- determining statistically significant token patterns in the data collection including determining if a sequence of tokens occurs more than would be expected if said token sequence were to occur randomly including determining a probability of a token T being the next token in k number of sequences in n randomly-generated identical sequences and including determining a significance level that the null hypothesis has been rejected, said significance level being:
- α = P ( k ≥ n 1 ) = ∫ n 1 ∞ P ( x , μ , σ ) ⅆ x ;
- where :
- μ=np;
- p is an overall probability of the token T occurring;
- and
- σ2=np(1−p);
- providing examples of desired data fields;
- and
- establishing a prefix tree for said desired data fields according to said statistically significant token patterns;
- whereby
- determination is made of token sequences identifying said desired data fields.
10 more elements
A method for determining a new wrapper for a changed source of data, the steps comprising:
- providing a set of training examples relevant to a data source prior to a change in said data source;
- providing a set of pages from said data source after a change in said data source;
- establishing data fields in said sets of data from said changed data source to provide a set of data candidates including learning a beginning token sequence pattern for each of said data fields, and learning a terminating token sequence pattern for each of said data fields so that each data field is determined by its beginning and terminating token sequence
- determining a mean and variance for a number-of-tokens distribution for in each data field;
- scanning each page in said set of pages;
- identifying all token segments beginning with one of said beginning token sequences and ending with one of said terminating token sequences to provide an initial set of data candidates;
- evaluating said initial set of data candidates;
- eliminating ones of said initial set of data candidates having a number of tokens significantly different from an expectation derived from said number-of-tokens distribution to provide said set of candidates so that said set of data candidates may be provided that is biased towards more relevant data candidates;
- clustering said data candidates according to characteristic features to provide data candidate clusters including associating ones of said data candidates according to characteristic features selected from the group consisting of:
- page position, adjacent tokens, and visibility to a user;
- scoring said data candidate clusters based on how similar each data candidate cluster is to each of said training examples;
- selecting a data cluster having a highest score for a particular one of said training examples as corresponding to said particular training example;
- whereby
- a new wrapper may be constructed by substituting said selected data cluster for said particular training example and generating rules appropriate for said substitution for said new wrapper.
11 more elements
A method for wrapping a first database, the steps comprising:
- providing a second database, said second database similar to said first database;
- providing a wrapper for said second database, said wrapper extracting information of interest from said second database, said wrapper having a first set of rules for wrapping said second database;
- wrapping the first database with said wrapper for said second database;
- evaluating effectiveness of said wrapper in wrapping the first database;
- and
- reinducing ineffective rules of said wrapper when wrapping said first database to generate a second set of rules comprising a second wrapper, said second wrapper better extracting information from said first database;
- whereby
- the first database is more easily wrapped by reinducing wrapper rules applicable to a similar database.
5 more elements
Dependencies are inferred from the claim text.