Probabilistic record linkage across federated benefit rolls

1 The problem

A national program administered by many jurisdictions rarely has a shared, reliable identifier. Each jurisdiction maintains its own enrollment file, formats names and addresses its own way, and corrects errors on its own schedule. Detecting a person enrolled in more than one place is therefore a record linkage problem: deciding, for pairs of records drawn from different files, whether they refer to the same individual.

Exact matching on a few fields fails in both directions. It misses true duplicates whenever a single character differs, and it over-matches common names that share a date of birth. Probabilistic linkage replaces the yes-or-no rule with a calibrated score and makes the error trade-off explicit.

2 The Fellegi–Sunter model

Let $𝐴$ and $𝐵$ be two files. Every candidate pair $(𝑎, 𝑏) \in 𝐴 \times 𝐵$ belongs to one of two unknown classes: matches $𝑀$ or non-matches $𝑈$ . For each pair we compute a comparison vector $𝛾 = (𝛾_{1}, \dots, 𝛾_{𝐾})$ , where $𝛾_{𝑘} = 1$ if field $𝑘$ agrees and $0$ otherwise.¹

The model is parameterized by two probabilities per field:

𝑚_{𝑘} = Pr (𝛾_{𝑘} = 1 | 𝑀), 𝑢_{𝑘} = Pr (𝛾_{𝑘} = 1 | 𝑈) .

(1)

Here $𝑚_{𝑘}$ captures data quality (how often a true match agrees on field $𝑘$ ), and $𝑢_{𝑘}$ captures coincidence (how often two different people agree by chance). Assuming conditional independence of fields given the class, the log-likelihood ratio of a pair is a sum of per-field weights:

𝑤 (𝛾) = \sum_{𝑘 = 1}^{𝐾} [𝛾_{𝑘} {log}_{2} \frac{𝑚_{𝑘}}{𝑢_{𝑘}} + (1 - 𝛾_{𝑘}) {log}_{2} \frac{1 - 𝑚_{𝑘}}{1 - 𝑢_{𝑘}}] .

(2)

I. P. Fellegi and A. B. Sunter [1] showed that the decision rule with two thresholds $𝑇_{𝜇} > 𝑇_{𝜆}$ ,

decide {\begin{cases} 𝑀 & if 𝑤 (𝛾) \geq 𝑇_{𝜇} \\ review & if 𝑇_{𝜆} < 𝑤 (𝛾) < 𝑇_{𝜇} \\ 𝑈 & if 𝑤 (𝛾) \leq 𝑇_{𝜆} \end{cases}

(3)

minimizes the size of the clerical review region for fixed error rates on the two automatic decisions. That property is what makes the method operational: it tells you exactly how much human review a given tolerance for error will cost.

Field	$𝑚_{𝑘}$	$𝑢_{𝑘}$	Agree	Disagree
Last name	0.95	0.010	+6.57	−4.31
First name	0.90	0.020	+5.49	−3.29
Date of birth	0.97	0.003	+8.34	−5.05
Sex	0.98	0.500	+0.97	−4.64
ZIP code	0.80	0.020	+5.32	−2.29

Table 1: Illustrative parameters and the resulting weights from Equation 2, in bits.

With the values in Table 1, a pair that agrees on every field scores $+ 26.69$ . A pair that agrees on everything except ZIP code, the common case of a household that has moved, still scores $26.69 - 5.32 - 2.29 = 19.08$ . A pair that agrees only on sex scores well below zero. The weights encode intuition that is otherwise hard to apply consistently: agreement on a rare value is strong evidence, while agreement on a common one is almost none.

Figure 1: The decision rule in Equation 3 partitions the weight axis into three regions.

3 Estimating weights without labels

Labeled pairs are expensive and, across jurisdictions, usually unavailable. The parameters can instead be estimated directly from the unlabeled comparison vectors by treating class membership as missing data and applying the EM algorithm [2], [3]. Let $𝑝 = Pr (𝑀)$ be the match prevalence among candidate pairs. In the E-step, each pair $𝑗$ receives a posterior match probability

𝑔_{𝑗} = \frac{𝑝 \prod_{𝑘} 𝑚_{𝑘}^{𝛾_{𝑗 𝑘}} {(1 - 𝑚_{𝑘})}^{1 - 𝛾_{𝑗 𝑘}}}{𝑝 \prod_{𝑘} 𝑚_{𝑘}^{𝛾_{𝑗 𝑘}} {(1 - 𝑚_{𝑘})}^{1 - 𝛾_{𝑗 𝑘}} + (1 - 𝑝) \prod_{𝑘} 𝑢_{𝑘}^{𝛾_{𝑗 𝑘}} {(1 - 𝑢_{𝑘})}^{1 - 𝛾_{𝑗 𝑘}}} .

(4)

In the M-step, the parameters are re-estimated as weighted proportions:

{\hat{𝑚}}_{𝑘} = \frac{\sum_{𝑗} 𝑔_{𝑗} 𝛾_{𝑗 𝑘}}{\sum_{𝑗} 𝑔_{𝑗}}, {\hat{𝑢}}_{𝑘} = \frac{\sum_{𝑗} (1 - 𝑔_{𝑗}) 𝛾_{𝑗 𝑘}}{\sum_{𝑗} (1 - 𝑔_{𝑗})}, \hat{𝑝} = \frac{1}{𝑁} \sum_{𝑗} 𝑔_{𝑗} .

(5)

Two practical cautions apply. First, EM converges to a local optimum, so initialize with $𝑚_{𝑘}$ high and $𝑢_{𝑘}$ low; otherwise the classes can swap. Second, the $𝑢_{𝑘}$ estimates are dominated by the overwhelming number of non-matching pairs and are usually reliable, while the $𝑚_{𝑘}$ estimates depend on there being enough true matches among the candidates. That makes blocking a statistical decision, not only a performance one.

4 Blocking

Comparing every pair is quadratic in file size and infeasible at national scale. Blocking restricts comparison to pairs that share a key. Every key trades pair volume against recall: a true match that disagrees on the blocking key is never compared and can never be found.

Blocking key	Recall risk	Notes
Date of birth	Low	Very selective; misses transposed digits.
Phonetic last name + birth year	Low–moderate	Tolerant of spelling; misses name changes.
ZIP code	High	Misses movers, the population of most interest.

Table 2: Qualitative trade-offs of common blocking keys.

The standard remedy is to run several independent blocking passes and take the union of candidate pairs. As Table 2 suggests, keys should be chosen so that their failure modes do not overlap.

5 Choosing thresholds

Under the model, the expected number of false matches accepted above $𝑇_{𝜇}$ is

𝔼 [false matches] = \sum_{𝑗 : 𝑤_{𝑗} \geq 𝑇_{𝜇}} (1 - 𝑔_{𝑗}),

(6)

which can be read directly from the EM output. In practice we set $𝑇_{𝜇}$ so that this quantity is a small fraction of accepted pairs, set $𝑇_{𝜆}$ from the review capacity actually available, and audit a random sample from each region. Because conditional independence rarely holds exactly (first name and sex are correlated, for example), posterior probabilities tend to be overconfident. Audits are what keep the thresholds honest.

6 Practical notes

Normalize before comparing. Case, punctuation, suffixes, nicknames, and address standardization remove more spurious disagreement than any model refinement.
Use graded string comparison. Approximate agreement levels based on string comparators such as Jaro–Winkler substantially improve linkage of names [4].
Resolve transitively. Pairwise decisions must be reconciled into clusters; a single wrong link can merge two large groups.
Treat outputs as leads. A high score indicates a likely duplicate record, not a determination about a person. Adverse action should always follow verification.

Bibliography

[1] I. P. Fellegi and A. B. Sunter, “A Theory for Record Linkage,” Journal of the American Statistical Association, vol. 64, no. 328, pp. 1183–1210, 1969.
[2] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum Likelihood from Incomplete Data via the EM Algorithm,” Journal of the Royal Statistical Society: Series B, vol. 39, no. 1, pp. 1–38, 1977.
[3] W. E. Winkler, “Using the EM Algorithm for Weight Computation in the Fellegi–Sunter Model of Record Linkage,” in Proceedings of the Section on Survey Research Methods, American Statistical Association, 1988, pp. 667–671.
[4] W. E. Winkler, “String Comparator Metrics and Enhanced Decision Rules in the Fellegi–Sunter Model of Record Linkage,” in Proceedings of the Section on Survey Research Methods, American Statistical Association, 1990, pp. 354–359.

¹Real deployments use more than two levels per field, for example exact, approximate, and disagree. The algebra is unchanged; each level gets its own probability.