US6523019B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probabilistic record linkage model derived from training data
Assignee: Open Invention Network LLC
•
Filing: 1999-10-28
•
Granted: 2003-02-18
•
Expires: 2019-10-28
Abstract
Abstract A method of training a system from examples achieves high accuracy by finding the optimal weighting of different clues indicating whether two data items such as database records should be matched or linked. The trained system provides three possible outputs when presented with two data items: yes, no or I don't know (human intervention required). A maximum entropy model can be used to determine whether the two records should be linked or matched. Using the trained maximum entropy model, a high probability indicates that the pair should be linked, a low probability indicates that the pair should not be linked, and intermediate probabilities are generally held for human review.
Inventors
- 👤 Andrew E. Borthwick
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:41
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/21; G06F16/215; G06N; G06N7/00; G06N7/01; G06N20/00; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
97 words
A computer-assisted process for determining linkages between data records comprising: constructing a predictive model based at least in part on a product divided by a sum of products; training said predictive model with record pair linkage data, including the step of applying at least one machine learning method on a corpus of record pairs presented so as to indicate decisions made by at least one human decision maker as to whether said record pairs should be linked; and using said trained predictive model to automatically identify records that have a predetermined type of similarity to other data.
Claim 2
Dependent Claim
97 words
A computer-assisted process for determining linkages between data records comprising: constructing a predictive model based at least in part on a product divided by a sum of products; training said predictive model with record pair linkage data, including the step of applying at least one machine learning method on a corpus of record pairs presented so as to indicate decisions made by at least one human decision maker as to whether said record pairs should be linked; and using said trained predictive model to automatically identify records that have a predetermined type of similarity to other data.
Claim 3
Dependent Claim
15 words
A process as in claim 1 wherein said predictive model comprises a maximum entropy model.
Claim 4
Dependent Claim
85 words
A computer-assisted process for linking records in at least one database including: assigning weights to plural different factors predicting a link or non-link decision, using said assigned weights to calculate a probability=L/(L+N) where L=product of the weights of all features indicating link, and N=product of the weights of all features indicating no-link; and using said calculated probability to generate a predictive model; and applying said predictive model to automatically identify records within said at least one database that bear a predetermined relationship to one another.
Claim 5
Dependent Claim
85 words
A computer-assisted process for linking records in at least one database including: assigning weights to plural different factors predicting a link or non-link decision, using said assigned weights to calculate a probability=L/(L+N) where L=product of the weights of all features indicating link, and N=product of the weights of all features indicating no-link; and using said calculated probability to generate a predictive model; and applying said predictive model to automatically identify records within said at least one database that bear a predetermined relationship to one another.
Claim 6
Dependent Claim
17 words
The process of claim 3 further including constructing said predictive model using the maximum entropy modeling technique.
Claim 7
Dependent Claim
45 words
The process of claim 4 further including executing said maximum entropy modeling technique on a corpus of record pairs which have been marked by at least one person with a decision as to that person's degree of certainty that the record pair should be linked.
Claim 8
Dependent Claim
26 words
The process of claim 3 further including creating a predictive model based on said calculated probability, including constructing said predictive model using a machine learning technique.
Claim 9
Dependent Claim
44 words
The process of claim 6 further including executing said machine learning technique on a corpus of record pairs which have been marked by at least one person with a decision as to that person's degree of certainty that each record pair should be linked.
Claim 10
Dependent Claim
14 words
The process of claim 1 wherein: said predictive model comprises a minimum divergence model.
Claim 11
Dependent Claim
16 words
A method as in claim 8 wherein said minimum divergence model comprises a maximum entropy model.
Claim 12
Dependent Claim
62 words
A method as in claim 8 wherein said training step includes calculating a probability L/(L+N) where L is the product of the weights of all features indicating that first and second data items bear a predetermined relationship, and N is the product of the weights of all features indicating that said first and second data items do not bear said predetermined relationship.
Claim 13
Dependent Claim
125 words
Apparatus for training a computer-based predictive model based at least in part on a product divided by a sum of products for determining whether at least two data items have a predetermined relationship, said apparatus comprising: an input device that accepts a training corpus comprising plural pairs of data items and an indication as to whether each of said plural pairs bears a predetermined relationship; a feature filter that accepts a pool of possible features, and outputs, in response to said training corpus, a filtered feature pool comprising a subset of said pool; and a maximum entropy parameter estimator responsive to said training corpus, said estimator developing weights for each of said features within said filtered feature pool for use with said computer-based predictive model.
Claim 14
Dependent Claim
125 words
Apparatus for training a computer-based predictive model based at least in part on a product divided by a sum of products for determining whether at least two data items have a predetermined relationship, said apparatus comprising: an input device that accepts a training corpus comprising plural pairs of data items and an indication as to whether each of said plural pairs bears a predetermined relationship; a feature filter that accepts a pool of possible features, and outputs, in response to said training corpus, a filtered feature pool comprising a subset of said pool; and a maximum entropy parameter estimator responsive to said training corpus, said estimator developing weights for each of said features within said filtered feature pool for use with said computer-based predictive model.
Claim 15
Dependent Claim
39 words
Apparatus as in claim 11 wherein said feature filter discards features not useful in discriminating between plural pairs of data items that bear a predetermined relationship and plural pairs of data items that may not bear a predetermined relationship.
Claim 16
Dependent Claim
40 words
Apparatus as in claim 11 wherein said feature filter discards features not useful in discriminating between plural pairs of data items that do not bear a predetermined relationship and plural pairs of data items that may bear a predetermined relationship.
Claim 17
Dependent Claim
40 words
Apparatus as in claim 11 wherein said estimator constructs a model which calculates a linkage probability based on features within the filtered feature pool that indicate an absence of linkage and features within the filtered feature pool that indicate linkage.
Claim 18
Dependent Claim
26 words
Apparatus as in claim 11 wherein said estimator outputs a real-number parameter for each feature in the filtered feature pool, said real-number parameter indicating a weight.
Claim 19
Dependent Claim
78 words
Apparatus for determining whether pairs of data items bear a predetermined relationship, said apparatus comprising: an input system that accepts pairs of data items; and a discriminator that determines whether each pair of data items bears a predetermined relationship, said discriminator including a trained computer-based minimum divergence model based at least in part on a product divided by a sum of products, wherein said discriminator computes the probability that said pair of data items bears said predetermined relationship.
Claim 20
Dependent Claim
78 words
Apparatus for determining whether pairs of data items bear a predetermined relationship, said apparatus comprising: an input system that accepts pairs of data items; and a discriminator that determines whether each pair of data items bears a predetermined relationship, said discriminator including a trained computer-based minimum divergence model based at least in part on a product divided by a sum of products, wherein said discriminator computes the probability that said pair of data items bears said predetermined relationship.
Claim 21
Dependent Claim
17 words
Apparatus as in claim 16 wherein said computer-based minimum divergence model comprises a trained maximum entropy model.
Claim 22
Dependent Claim
51 words
Apparatus as in claim 16 wherein said discriminator calculates the probability of linkage as L/(N+L) where L is the sum of weighted features indicating that said data items bear said predetermined relationship, and N is the product of weighted features indicating said plural data items do not bear said predetermined relationship.
Claim 23
Dependent Claim
52 words
The process of claim 1 further including determining a set of weights each corresponding to features empirically selected to indicate either that a pair of data items bear said predetermined relationship or that said plural data items do not bear said predetermined relationship, said features and said set of weights providing a
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-02-17 | 2006-08-19 | 2007-02-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-02-17 | 2010-08-19 | 2011-02-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-02-17 | 2014-08-19 | 2015-02-18 | $7700.00 | Window Closed / Lapsed |