Refining a dictionary for information extraction

A method for refining a dictionary for information extraction, the operations including: inputting a set of extracted results from execution of an extractor comprising the dictionary on a collection of text, wherein the extracted results are labeled as correct results or incorrect results; processing the extracted results using an algorithm configured to set a score of the extractor above a score threshold, wherein the score threshold balances a precision and a recall of the extractor; and outputting a set of candidate dictionary entries corresponding to a full set of dictionary entries, wherein the candidate dictionary entries are candidates to be removed from the dictionary based on the extracted results.

BACKGROUND

Extracting structured information from unstructured text is an essential component of many important applications including business intelligence, social media analytics, semantic search, and regulatory compliance. The success of these applications is tightly connected with the quality of the extracted results. Incorrect or missing results may often render the application useless.

Building high-quality information extraction rules to extract structured information from unstructured text is a difficult and time-consuming process. Exhaustive dictionaries of words and phrases are integral to any information extraction system. One of the most important parts of this process can include refining the dictionaries by selectively removing dictionary entries that lead to false positives. Sophisticated extractors that use greater numbers of fine-grained dictionaries to improve accuracy also increase the difficulty of refining the dictionaries for efficient and accurate extraction due to the size and number of dictionaries.

SUMMARY

Embodiments of a method are described. In one embodiment, the method is a method for refining a dictionary for information extraction. The method includes: inputting a set of extracted results from execution of an extractor comprising the dictionary on a collection of text, wherein the extracted results are labeled as correct results or incorrect results; processing the extracted results using an algorithm configured to set a score of the extractor above a score threshold, wherein the score threshold balances a precision and a recall of the extractor; and outputting a set of candidate dictionary entries corresponding to a full set of dictionary entries, wherein the candidate dictionary entries are candidates to be removed from the dictionary based on the extracted results. Other embodiments of the method are also described.

DETAILED DESCRIPTION

While many embodiments are described herein, at least some of the described embodiments present a system and method for refining at least one dictionary for information extraction. More specifically, the system uses statistical modeling and refinement optimization to balance the precision and recall of an extractor for efficient, accurate information extraction. The system may use extracted results that have been labeled as correct or incorrect to determine candidate entries138to be removed from the dictionary to provide the highest precision for avoiding false positives while minimizing any decrease in recall. These candidate entries138may also be analyzed by a user to determine which entries should be removed from the dictionary.

In general, developing and maintaining high-quality extractors is a laborious and time consuming process. When creating an extractor, developers may start by writing an initial extractor that includes an initial set of basic features and rules that combine the features to extract the desired entities. The extractor may be executed on a document collection, the results may be examined to determine the cause of incorrect results, and the features and rules may then be refined to remove the incorrect results. This process may be repeated as many times as necessary to obtain satisfactory performance of the extractor. Generally, removing the sources of false positives from the extractor helps produce a higher precision in the extracted results. Specifically, refining dictionaries used in an extractor by removing the sources (words or phrases) of false positives can improve the quality of the extractor. The system and method described herein allow the refinement of dictionaries to improve the precision (minimization of false positives) of the extractor while maintaining a sufficient level of recall (avoidance of discarding correct answers) for the extractor.

Refining the dictionary may be divided into two sub-problems: statistical modeling and refinement optimization. The primary goal of the statistical modeling problem is to estimate the precision of each individual dictionary entry in an extractor, given a set of extracted entities that have been labeled as “correct” or “incorrect”. Labeling the outputs of extractors may be an expensive task requiring large amounts of human effort. Dictionaries frequently contain thousands of entries, so very little information about individual entries may be available even with a large collection of labeled data. Consequently, the extractor may need to be capable of coping with very sparse labeled data in order to be usable in practice.

The refinement optimization problem involves using the outputs of parameter estimation to choose the best set of entries to remove from the dictionary in order to improve the quality of the extractor. Balancing the requirements of precision and recall allow the maximization of an F-score (the harmonic mean of precision and recall) for the extractor. In some embodiments, the F-score maximization may be subject to a limit on the number of entries removed from the dictionary, or the maximum allowable decrease in recall.

FIG. 1depicts a schematic diagram of one embodiment of a dictionary refinement system100. The depicted dictionary refinement system100includes various components, described in more detail below, that are capable of performing the functions and operations described herein. In one embodiment, at least some of the components of the dictionary refinement system100are implemented in a computer system. For example, the functionality of one or more components of the dictionary refinement system100may be implemented by computer program instructions stored on a computer memory device102and executed by a processing device104such as a CPU. The dictionary refinement system100may include other components, such as input/output devices106, a disk storage drive108, an extractor110, a dictionary112, and a processor114. Some or all of the components of the dictionary refinement system100may be stored on a single computing device or on a network of computing devices, including a wireless communication network. The dictionary refinement system100may include more or fewer components or subsystems than those depicted herein. In some embodiments, the dictionary refinement system100may be used to implement the methods described herein as depicted inFIG. 4.

In one embodiment, the processor114is wholly contained within the processing device104. In another embodiment, the processor114includes one or more separate devices that may be spread among a network of computers, such that the processing capabilities are shared by multiple computing devices and/or executed simultaneously. In various embodiments, the extractor is implemented in the processing device104or the processor114. In one embodiment, the dictionary112is contained on the storage disk108on the same computing device as the processing device104, though the dictionary112may be contained on any number of storage disks108. In one embodiment, the dictionary refinement system100includes more than one dictionary112. Each dictionary112may be a specialized dictionary for any given subject or grouping of information.

In one embodiment, the extractor110is applied to a collection of text, dictionary entries124in the dictionary112are matched to the collection of text and the extractor110outputs extracted results116. The extractor may include multiple dictionaries112and may be applied to the collection of text based on a set of predefined rules118. At least some of the extracted results116may be labeled by a user to identify correct results120(true positives) and incorrect results122(false positives). In one embodiment, the precision130of the extractor110is the fraction of true positives among the total number of extracted results116. The precision of each dictionary entry124is the probability that an extracted entity will be correct, given that the entity is based, in whole or in part, on a match of the dictionary entry124. An extractor110with high precision130outputs few incorrect results122. An expected mention that is not identified by the extractor110is referred to herein as a missing result or a false negative. The term “recall”128is broadly interpreted herein to include the fraction of true positives among the total number of expected occurrences. An extractor110with high recall128misses very few expected results. In one embodiment, the recall128and precision130are balanced to maximize a score of the extractor, for example, by setting the score above a score threshold that may be predetermined based on a desired balance of the precision130and recall128. The score may be an F-score, an F-measure, or some other measure of scoring the dictionary. The term “F-score”132, or “F-measure”, is broadly interpreted herein to include combining precision130and recall128into a single measure that is computed as the harmonic mean of precision130and recall128depicted as

2⁢PR(P+R)
where P is the precision130and R is the recall128.

In various embodiments, the refinement optimization problem includes executing a refinement algorithm126under two constraints. First, because the refinement of an extractor110is often done with human supervision, the problem may include a size constraint134to limit the size of dictionary entries124to be examined at a time. For an extractor E, the size constraint134may include a set S of size at most k to maximize the F-score132of the resulting extractor E′. Alternatively, the extractor110may be refined such that the recall128does not fall below a certain limit using a recall constraint136. The recall constraint136includes a set w such that the F-score132of E′ is maximized, while at the same time the recall128of E′ does not decrease more than a fixed budget. In other embodiments, the refinement optimization problem may be approached without constraints on size or recall128. The algorithm126produces a set of candidate dictionary entries138that may be removed from the dictionary112to improve performance of the extractor110.

Maximizing the quality of the extractor110on the entirety of the labeled dataset for the extracted results116may not be useful in practice. Instead, by using statistical modeling and refinement optimization, the system may maximize the quality of the extractor110in general and avoid overfitting to the labeled dataset. The system may use a model for refining the dictionary112by estimating the parameters of the model including the precision130of each individual dictionary entry, given the set of extracted results116that have been labeled as correct or incorrect.

FIG. 2depicts a flowchart diagram of one embodiment of a method200for determining candidate dictionary entries138. While the method200is described in conjunction with the dictionary refinement system100ofFIG. 1, embodiments of the method200may be implemented with other types of dictionary refinement systems100.

In one embodiment, the extractor110receives a collection of text202to be matched to a set of one or more dictionaries112according to a set of rules associated with the extractor110. Each dictionary112may include a set of dictionary entries124corresponding to a given subject or grouping of words and phrases. Some of the entries124in the dictionaries112may overlap with other dictionaries112, depending on the subjects or groupings for the dictionaries112.

The extractor110is applied to the collection of text202and outputs the extracted results116. For each result116, the system100examines the rules and dictionaries112of the extractor110and determines which dictionaries112are involved in producing the extracted result116, and also determines the provenance of the extracted result116. Some or all of the extracted results116are then given labels204as correct results120or incorrect results122based on a user input. The incorrect results122are false positives output by the extractor110. For example, given a dictionary112containing “first name” entries, a second dictionary112containing “last name” entries, and a third dictionary112containing “full name” entries, the collection of text202may include a phrase “Mark Calendar” that is marked as a name based on matches in one or more of the dictionaries112.

The extracted results116are input into the processor114, and the processor114uses an algorithm126that maximizes the F-score132for the extractor110. The algorithm126produces a set of candidate dictionary entries138for each dictionary112that are output by the processor114. The set of candidate dictionary entries138are candidates that may be removed from the dictionary112that would maximize the F-score132for the extractor110.

Because the labels204for a given false positive may be determined by multiple dictionary entries124, the label204may not be used to estimate the precision130of a dictionary entry directly. Using the false positive example given above, it is not clear whether the false positive is because “Mark” is an incorrect first name, “Calendar” is an incorrect last name, or both. Furthermore, the same dictionary entry can contribute to different results, some correct and some incorrect. For example, “Mark” may contribute to an incorrect result “Mark Calendar”, as well as a correct result for “Mark Smith”. In this case, the processor114determines the candidate dictionary entries138by using the provenance of each false positive to model the complex dependencies between the dictionary entries124and the extracted results116, along with an algorithm126for estimating precisions130based on an expectation-maximization (EM) algorithm.

In one embodiment, the algorithm126is configured to determine which dictionary entries124may be removed to result in the highest quality improvement of the extractor110. In another example, two dictionary entries “Chelsea” and “Mark” are both ambiguous as a person name. If “Chelsea” is labeled as an incorrect result 60 times and as a correct result 40 times, and “Mark” is labeled as an incorrect result 9 times and as a correct result 1 time, the precision130of “Mark” (10%) is lower than that of “Chelsea” (40%). However, removing “Chelsea” results in removing more incorrect results122, possibly leading to a higher overall quality improvement for the extractor110.

FIG. 3depicts a flowchart diagram of one embodiment of a method for refining a dictionary112. While the method is described in conjunction with the dictionary refinement system100ofFIG. 1, embodiments of the method may be implemented with other types of dictionary refinement systems100.

In one embodiment, after the processor114outputs the candidate dictionary entries138, the processor114then receives a user input302that selects one or more of the candidate dictionary entries138for removal from the dictionaries112. The processor114may then read the dictionary entries124currently stored in the dictionaries112, remove the selected dictionary entries, and modify the dictionaries112according to the new set of dictionary entries124. This may allow a user to manually refine the candidate dictionary entries138by determining which entries from the set of candidate dictionary entries138are actually removed from the dictionaries112.

FIG. 4depicts a flowchart diagram of one embodiment of a method400for refining a dictionary112for information extraction. While the method400is described in conjunction with the dictionary refinement system100ofFIG. 1, embodiments of the method400may be implemented with other types of dictionary refinement systems100.

In one embodiment, the dictionary refinement system100inputs a set of extracted results116from matching the dictionary112to the collection of text202. The extracted results116are labeled410as correct results122or incorrect results122. In some embodiments, the extracted results116that are labeled include only a portion of the entities from the collection of text202matched to entries124in the dictionary112. In one embodiment, the system uses405a set of predetermined rules118and a dictionary112to determine the extracted results116for the collection of text202. In one embodiment, the correct results122and incorrect results122are labeled based on a user input302.

The dictionary refinement system100processes415the extracted results116using an algorithm126configured to maximize an F-score132for the extractor110, for example, by setting the F-score above a score threshold. The score threshold for the maximized F-score132balances the precision130and recall128of the extractor110. The system may process the extracted results116by computing the set of candidate dictionary entries138that maximize the F-score132under a maximum size constraint134for the set of candidate dictionary entries138. The system may process the extracted results116by computing the set of candidate dictionary entries138that maximize the F-score132within an allocated recall constraint136. The recall constraint136determines a minimum coverage of the dictionary112, which may help the system avoid false negatives. The system may process the extracted results116by estimating the precision130of each dictionary entry in the full set of dictionary entries124using the extracted results116. The algorithm126used by the system may be the EM algorithm.

The dictionary refinement system100outputs420a set of candidate dictionary entries138corresponding to a full set of dictionary entries124of the dictionary112. The candidate dictionary entries138are candidates to be removed from the dictionary112based on the extracted results116. In one embodiment, the dictionary refinement system100receives425a user input302to select dictionary entries from the set of candidate dictionary entries138. The dictionary refinement system100then removes430the selected dictionary entries from the dictionary112.

In some embodiments, the system may obtain extracted results116using a plurality of specialized dictionaries. Each dictionary112may produce extracted results116labeled as correct results122or incorrect results122, which may then be processed for each corresponding dictionary112to determine which dictionary entries124should be removed for greatest improvement of the performance of the extractor110.

In one embodiment, for a single dictionary case, the dictionary A contains a set of n entries124. A given partially labeled corpus may be a random sample of entries from A sampled independently according to their relative frequency denoted by fw, i.e., any occurrence in the corpus is a match for entry w with probability fwand

In addition, each entry has a fixed precision pwε[0,1]. An occurrence of an entry w is Good if it is a correct match for the annotation used in a query, otherwise the occurrence is Bad. For example, a match for ‘Ford’, ‘Chelsea’ or ‘Mark’ is Good for the Person annotator if the match corresponds to a person name, and Bad otherwise. In practice, a human annotator labels a subset of the occurrences explicitly as Good or Bad. In one embodiment, it is assumed that each occurrence of w in the given corpus was chosen to be Good with probability pwand Bad with probability 1−pwrandomly and independently of the other occurrences and of whether the label204is given to the refinement algorithm126. For an entry w let twdenote the number of occurrences of w in the given corpus, gwdenote the number of times the entry was labeled Good and bwdenote the number of times the entry was labeled Bad.

For the collections of text202in which the total number of occurrences is much larger than the number of labeled occurrences, the empirical frequencies

(tw/∑w∈A⁢tw)
may be referred to as true frequencies. Consequently, the goal of the parameter estimation problem is estimating precisions130.

In one embodiment, estimating the precision130for w includes observing the precision130of other entries124. For example, if other entries124with a large number of labels204have precision130close to 80% then w is also more likely to have precision130close to 80%. This dependency may be expressed in the model as described below. The precision130of each word is assumed to be chosen randomly and independently from a fixed and unknown distribution Π over [0,1]. In a Bayesian analysis, when estimating pw, distribution Π represents a prior belief about pw. This allows the use of the given labels204for w to perform Bayesian updates so as to obtain the posterior distribution Πw. The posterior distribution Πwrepresents a knowledge of pwand can be used to derive an estimate of pw. Taking the mean of Πwprovides a simple and more optimal way to use Πw.

In some embodiments, it is assumed that the prior distribution Π is not given to the algorithm126, and a suitable Π may need to be found given the available labels204. To find the distribution Π from which each precision pwis assumed to be drawn randomly and independently. The distribution Π may be modeled using beta distributions. This may be a convenient distribution for Bayesian updates using the labels204. The beta distribution also allows easy estimation of parameters.

A beta distribution Beta(α,β) has two parameters α,β>0, and the probability density function (PDF) of the distribution is cΘα−1(1−Θ)β−1where c is the normalizing constant. The mean of the distribution is

αα+β.
If a Good (or Bad) label204is observed, the posterior Π updates to Beta(α+1,β) (or Beta(α,β+1), respectively). More generally, if gw=bw=0, the posterior Πwis the same as the prior Π.

Better estimates of the parameters of the prior Beta(α,β) improve the estimate of the obtained precision pw. The system may use a uniform prior case with Beta(1,1) as the prior. The available empirical precisions

gwgw+bw
may be used to compute the prior using the standard method of moments. Let

μ^=1n⁢∑w⁢⁢ε⁢⁢A⁢⁢gwgw+bw
be the sample mean of observed precisions, and

α^=μ^⁡(u^⁡(1-μ^)σ^2-1)andβ^=(1-μ^)⁢(μ^⁡(1-μ^)σ^2-1)
which are considered as the parameters.

The mean of the posterior distribution Πw, which equals

α+gwα+gw+β+bw,
is used to estimate pw. This simplification may not affect the quality of the refinement optimization significantly because the F-score132of a dictionary112is determined by large sums of precisions130multiplied by frequencies. A large sum of precisions130, each drawn independently from the corresponding distribution Πw, is strongly concentrated around the expectation of the sum, which depends only on the mean of each Πw.

In one embodiment, the optimization problem may be considered for single dictionary refinement, assuming that the true values of pw,fware given as input for all wεA. The standard notions of precision130, recall128and F-score132may be used to measure the quality of the solution for the refinement optimization problem. For a subset of entries S, precision (PS), recall (RS), and F-score (FS) are defined as

F-score132is the harmonic mean of PSand RSand is used to balance the precision130with recall128of the refined dictionary. When a subset of S is removed from the dictionary A, the residual precision130, recall128and F-score132are denoted by PS=PA\S, RS=RA\Sand FS=FA\S. The F-score132may be maximized under two constraints:1. Size constraint: Given an integer k≦n, find a subset S that maximizes FS, where |S|≦k.2. Recall constraint: Given a fraction ρ≦1, find a subset S that maximizes FS, where the residual recall RS≧ρ.
The F-score132may alternatively be maximized with no size or recall budget constraints.

FSis a non-linear function of the precisions {circumflex over (p)}w, wεS, since both the numerator and the denominator are dependent on the set S being removed, thereby making the analysis of the optimization problem non-trivial.

For the size constraint134, the goal is to maximize

FS_=2⁢∑w⁢⁢ε⁢⁢A⁢⁢pw⁢fw∑w⁢⁢ε⁢⁢A⁢⁢pw⁢fw+∑w∉S⁢⁢fw,
where |S|≦k. Finding out whether there exists a dictionary112with F-score132of at least θ may be allow the algorithm126to overcome the non-linearity of the objective function. Accordingly, the algorithm126guesses a value θ and then checks if θ is a feasible F-score132for some S. The maximum value of the F-score132is then found by doing a binary search.

To check whether θ is a feasible F-score132, the system first checks whether there is a set S of entries such that

The right hand side of the inequality is independent of S, so the system selects the highest (at most) k entries with non-negative value of fw(θ−2pw) and checks if the sum is at least

A subset S is desired such that FS≧FA. Consequently, the minimum value of the guess is FAand the maximum value is 1. The algorithm126is presented in Algorithm 1, shown below, in terms of parameter Δ where Δ is the desired accuracy of the algorithm.

Algorithm 1: Algorithm for size constraint (given k and parameter Δ)1: Let θlow= FAand θhigh= 12: while θhigh− θlow> Δ do3:  Let θ = (θhigh+ θlow)/2 be the current guess.4:  Sort the entries w in descending order of fw(θ − 2pw) .5:  Let S be the top l ≦ k entries in the sorted order such thatfw(θ − 2pw) ≧ 0 for all w ∈ S.6⁢:⁢⁢if⁢⁢∑w⁢∈S⁢⁢fw⁡(θ-2⁢pw)≥⁢∑w⁢∈A⁢fw⁡(θ-(2-θ)⁢pw)⁢⁢then7:   θ is feasible, set θlow= FSand continue.8:  else9:   θ is not feasible, set θhigh= θ and continue.10:  end if11: end while12: Output the set s to define the most recent θlow.

A linear time O(n) time algorithm for checking the feasibility includes: (i) use the standard linear time selection algorithm to find the k-th highest entry, for example u, according to fw(θ−2pw), (ii) do a linear scan to choose the entries w such that fw(θ−2pw)>fu(θ−2pu), and then choose entries such that fw(θ−2pw)=fu(θ−2pu) to get k entries total, (iii) discard the selected entries with negative values of fw(2pw−θ) and output the remaining ≦k as the set S. However, a simpler implementation of verification uses a mini-heap that gives O(n+k log n) time, whereas a simple sorting gives O(n log n) time.

Since values of the guesses are between 0 and 1 and the algorithm stops when the upper and lower bounds are less than Δ away, at most log(1/Δ) steps will be required. This means that there is an implementation of the algorithm with running time O(n log(1/Δ)). Setting Δ to a sufficiently low value may allow the algorithm to find the optimal solution. Specifically, there is an optimal algorithm for maximizing the residual F-score132for single dictionary refinement under a size constraint134. The algorithm runs in time O(n(log n+B)), where B is the number of bits used to represent each of the pwand fwvalues given to the algorithm.

A simple and efficient algorithm that gives a nearly optimal solution when used on a large corpus where frequencies of individual entries124are small is described below. The algorithm sorts the entries124in increasing order of precisions pw, and selects entries124according to this order until the recall budget is exhausted or there is no improvement of F-score132by selecting the next entry. The algorithm runs in time O(n log n).

To obtain a lower bound on the F-score132of the solution produced by the algorithm, let w1, . . . , wnbe the entries124sorted by precision130and p1≦ . . . ≦pnbe the corresponding precisions130. Let S* be the set of entries124whose removal gives the optimal F-score132such that RS*≧ρ. Let

r*=∑i∈s_*⁢pi⁢fi
and let l be the largest index for which

∑i>l⁢pi⁢fi≥r*.
Then the set S returned by the algorithm satisfies

The lower bound guaranteed by the algorithm differs from the optimal F-score PS*only by the addition of the error term

fmaxpℓ+1
to the denominator. Individual frequencies are likely to be small when the given corpus and the dictionary112are large. At the same time l, and hence pl+1are determined by the recall budget. Therefore, the error term

fmaxpℓ+1
is likely to be much smaller than the denominator for a large dictionary112.

While it is not necessarily optimal in general, without the recall budget (i.e., with p=0) this algorithm finds the solution with the globally optimal F-score132. The optimal solution can also be found using Algorithm 1 with k=n.

While the algorithms above are described primarily in conjunction with a single dictionary case, the system and method described herein are capable of refining and optimizing an extractor110using more than one dictionary112. For example, in one embodiment there are b dictionaries A1, . . . , Ab, and there are n entries in total in

A=A=⋃l=1b⁢Al.
Any occurrence τ is produced by matches of one or more dictionary entries124combined by the given extraction rule; all such dictionary entries w are said to be in provenance of τ. How the entries124produce τ is captured by the provenance expression Prov(τ) of τ; for all such entries w, wεProv(τ) is a Boolean expression where the entries124in Prov(τ) are treated as variable (every entry in A corresponds to a unique Boolean variable). Given two Boolean expressions φ1and φ2, φ1=φ2if the variable sets in φ1and φ2are the same and the truth tables of φ1and φ2on these variables are also the same. For the same provenance expression φ, there may be multiple occurrences τ such that Prov(τ)=φ. This is analogous to the single dictionary case, where the trivial provenance expression φ=w for any entry w has one or more occurrences. Note that with extraction rules based on SELECT-PROJECT-JOIN-UNION queries, the provenance expressions are monotone.

The statistical model of a single dictionary112is extended to the multiple dictionary case. Every provenance expression φ may be assumed to be a true frequency f(φ)ε[0,1] and a true precision p(φ)ε[0,1]. As before,

∑ϕ⁢f⁡(ϕ)=1,
where the sum is over all possible Boolean expressions on the set of entries124, and any occurrence τ has Prov(τ)=φ with probability f(φ). In addition, the label204of τ is Good with probability p(φ) and Bad with probability 1−p(φ) randomly and independently of other occurrences, and whether the label204of τ is given.

In practice, unlabeled data is sufficiently large, so the frequencies of results are estimated using their empirical frequencies

f^⁡(ϕ)=τ⁢:⁢Prov⁡(τ)=ϕ∑ψ⁢⁢τ⁢:⁢Prov⁡(τ)=ψ,
and the hat may be dropped. The precision p(φ) of results φ may be estimated from a limited amount of labeled data. A natural approach to find the precisions130of provenance expressions is to estimate them empirically. The problem with this approach is that the possible number of such provenance expression is very large and it is likely that very few (if any) labels204would be available for most of the provenance expressions. At the same time, it is quite likely that individual dictionary entries124have similar precision130across different provenance expressions. This intuition may be represented by strengthening the model described herein in the following way.

It may be assumed that, as in the single dictionary case, every entry w has a fixed (and unknown) precision130denoted by pw. For any given occurrence τ such that wεProv(τ), the match of w for τ is correct with probability pwand incorrect with probability 1−pwindependent of the other occurrences and other entries124in the provenance of τ. Further, it may be assumed that the AQL rule is correct, i.e., the label204of τ is Good if and only if its provenance Prov(τ) evaluates to true with the matches of the dictionary entries124in Prov(τ) ((Good≡true and Bad≡false). Computing the probability of any Boolean expression φ given the probabilities of the individual variables is in general #P-hard, and the classes of queries for which the probability of the Boolean provenance can be efficiently computed have been extensively studied in the literature. However, the Boolean provenance expression described herein involves a small number of variables (typically ≦10). Thus, p(φ) may be computed given pwby an exhaustive enumeration of satisfying assignments of φ and using the assumption of independence of variables.

Here, the goal is to estimate the values of precision pwgiven a set of occurrences τ along with their labels204and provenance expressions Prov(τ). The Expectation-Maximization (EM) algorithm may be used to solve this problem.

The EM algorithm is a widely-used technique for maximum likelihood estimation of parameters of a probabilistic model under hidden variables. This algorithm estimates the parameters iteratively either for a given number of steps or until some convergence criteria are met.

The following notations present the update rules of the EM algorithm for the problem described herein. The entries124are indexed arbitrarily as w1, . . . , wn. Each entry wihas a true precision pi=pwi. There are N labeled occurrences in τ1, . . . , τN. It is assumed that τ1, . . . , τNalso denote the labels204of the occurrences. So each τiis Boolean, where τi=1 (resp. 0) if the label204is Good (resp. Bad). If wiεProv(τj), then τjεSucc(wi).

For simplicity in presentation, it may be assumed that entries124from exactly b dictionaries112are involved in the provenance expression φj=Prov(τj) for each occurrence τj, although this implementation works for general cases. Hence, each φjtakes b inputs yj1, . . . , yjband produces τj. Each yjlis Boolean, where yjl=1 (resp. 0) if the match of the dictionary entry corresponding the yjlis correct (resp. incorrect) while producing the label204for τj. The entry corresponding the yjlis denoted by Provjlε{w1, . . . , wn}.

To illustrate the notations, consider the following example extraction rule expressed in the Annotation Query Language (AQL) language:

The result is a person name if it is a match from first-name (FN) dictionary, followed by a match from last-name (LN) dictionary. This rule is called the FN-LN rule. In this example, b=2 and for every occurrence τj, τj=φj(yj1, yj2)=yj1yj2. For a Good occurrence “John Smith”, τj=1, yj1=1 (for “John”), and yj2=1 (for “Smith”), Provj1=“John” and Provj2=“Smith”. For a Bad occurrence “Mark Calendar”, τj=0, yj1=1 (for “Mark”), and yj2=0 (for “Calendar”).

The vector {right arrow over (x)}=τ1, . . . , τNis the observed data, the vector of vectors {right arrow over (y)}=yjljε|1,N|,bε|1,l| is the hidden data, and the vector {right arrow over (θ)}={p1, . . . ,pn} is the vector of unknown parameters.

The parameter vector at iteration t is denoted to be {right arrow over (θ)}t. Suppose: cwt,τj,t=E[yjl|τj,{right arrow over (θ)}t|, where τjεSucc(wi) and Provjl=wi. It may be shown that the update rules for parameters pihas a nice closed form:

pi=C1C1+C2,⁢whereC1=∑⁢cwi,τj,tandC2=∑⁢(1-cwi,τj,t),
and the sum is over 1≦j≦N such that τjεSucc(wi). These parameter values are considered to be θ{right arrow over (t)}+1, estimation of the parameter in the t+1-th round.

In the single dictionary case, every occurrence τ of an entry w has Prov(τ)=w, and when w is deleted only those entries124get deleted. However, in the multiple-dictionary case, if an entry w is deleted, multiple provenance expressions τ such that wεProv(τ) can disappear from the result set. When a subset of entries S⊂A is removed, it may be seen that a provenance expression φ disappears if and only if, after assigning all variables for entries124in S value false and all variables for entries124in A\S value true, the Boolean provenance φ evaluates to false. Denote the set of provenance expressions φ that survive (do not disappear) after a given set S is deleted by surv(S). For example, if there are three occurrences with provenance expressions uv, u+v, uw+uv, when S={u} is deleted, the set surv(S) will only contain the occurrence with provenance expression u+v. Hence the residual recall (RS) and the residual precision (PS) are defined as (FSis their harmonic mean):

The above definitions for multiple dictionary generalize the definitions for single dictionary refinement optimization.

Since the multiple dictionary refinement problem is non-deterministic polynomial-time (NP)-hard under both size and recall constraints134,136several simple and efficient algorithms are proposed and evaluated. These algorithms take the precisions130of individual dictionary entries124(which may be obtained using the EM algorithm) and a set of occurrences with their provenance expressions as input, and produce a subset of entries124across all dictionaries112to be removed. The types of algorithms evaluated here are (1) greedy, and, (2) entry-precision-based, or EP-based in short.

To compute the residual F-score132, both greedy and EP-based algorithms compute the precision130of tuples from precision entries124under independence assumption. The greedy algorithms select the next entry that gives the maximum improvement in F-score132. The algorithm stops if no further improvement in F-score132is possible by deleting any entry or when the given size or recall budget is exhausted.

On the other hand, the EP-based algorithms exploit the precision130of individual dictionary entries124. The dictionary entries124may be treated as if they come from a single dictionary (however, note that the actual provenances were used by the EM algorithm to estimate the precision130of entries124). These algorithms use the selection criteria of incremental algorithms for the single-dictionary case, i.e., maximize ΔF for size constraint134and ΔF/ΔR for recall constrain, where ΔF, ΔR denote the changes in F-score132and recall128by deleting one additional entry. It may be shown that, in the single-dictionary case, selection according to these criteria can be approximated by selecting entries124according to increasing value of fw(pw−F/2) for size constraint134, and pwfor recall constrain, where F is the current value of F-score132(the proof appears in the full version). In the multiple-dictionary case, pwis considered as the given precision130of entry w, and fwas the total frequency of provenance expressions that include w. An entry is selected for removal from the top of such a sorted order if it gives an improvement in F-score132. The selection continues until the given size or recall budget is exhausted. For optimization under the size constraint134, the value of F-score132is also recomputed after each entry is selected.

FIG. 5depicts a schematic diagram of one embodiment of a computer system500for implementation of one or more aspects of the functionality described herein. The illustrated computer system500is only one example of a suitable computer architecture and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the invention described herein. Regardless, the computer system500is capable of being implemented to performing any or all of the functionality set forth hereinabove.

The computer processing device502may be described in the general context of computer system-executable instructions, such as program modules, being executed by a computer system. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types. Embodiments of the computer processing device502may be practiced locally, remotely, or in distributed cloud computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed cloud computing environment, program modules may be located in both local and remote computer system storage media including memory storage devices.

In one embodiment, the computer processing device502includes components and functionality typical of a general-purpose computing device. The components of the computer processing device502may include, but are not limited to, one or more processors or processing units504, a system memory506, and a bus508that couples various system components including the system memory506to the processor504.

The computer processing device502typically includes a variety of computer system readable media (also referred to as computer readable media and/or computer usable media). Such media may be any available media that is accessible by the computer processing device502. Embodiments of the computer readable media may include one or more of the following types of media: volatile and non-volatile media, removable and non-removable media.

The system memory506can include computer system readable media in the form of volatile memory, such as random access memory (RAM)510and/or cache memory512. The computer processing device502may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, a storage system514can be provided for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a “hard drive”). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a “floppy disk”), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media can be provided. In such instances, each can be connected to the bus508by one or more data media interfaces. As will be further depicted and described below, the memory506may include at least one program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the invention.

In some embodiments, a program/utility516, having a set (at least one) of program modules518, is stored in the memory506. The program modules518generally carry out one or more of the functions and/or methodologies of the embodiments described herein. The memory506also may store an operating system, one or more application programs, other program modules, and/or program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a personal computer and/or networking environment.

The computer processing device502may also communicate with one or more external devices520such as a keyboard, a pointing device, a display522, etc.; one or more devices that enable a user to interact with the computer processing device502; and/or any devices (e.g., network card, modem, etc.) that enable the computer processing device502to communicate with one or more other computing devices. Such communication can occur via input/output (I/O) interfaces524. Additionally, the computer processing device502can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via a network adapter526. As depicted, the network adapter526communicates with the other components of the computer processing device502via the bus508. It should be understood that, although not shown, other hardware and/or software components could be used in conjunction with embodiments of the computer processing device502. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

An embodiment of a dictionary refinement system100includes at least one processor coupled directly or indirectly to memory elements through a system bus such as a data, address, and/or control bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.

Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) can be coupled to the system either directly or through intervening I/O controllers. Additionally, network adapters also may be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modems, and Ethernet cards are just a few of the currently available types of network adapters.