Maximum entropy classification for record linkage
Section 2. Problems with the classical approach

• Previous
• Next

Suppose that we have two data files $A$ and $B$ that are believed to have many common entities but no duplicates within each file. Any record in $A$ and another one in $B$ may or may not refer to the same entity. Our goal is to find the true matches among all possible pairs of the two data files. Let the bipartite comparison space $\Omega \mathrm{<mo>=</mo>}A\times B\mathrm{<mo>=</mo>}M\cup U$ consist of matches $M$ and non-matches $U$ between the records in files $A$ and $B.$ For any pair of records $\left(a\mathrm{,}b\right)\in \Omega ,$ let ${\gamma }_{ab}$ be the comparison vector between a set of key variables associated with $a\in A$ and $b\in B,$ respectively, such as name, sex, date of birth. The key variables and the comparison vector ${\gamma }_{ab}$ are fully observed over $\Omega .$ In cases where the key variables may be affected by errors, a match $\left(a\mathrm{,}b\right)$ may not have complete agreement in terms of ${\gamma }_{ab},$ and a non-match $\left(a\mathrm{,}b\right)$ can nevertheless agree on some (even all) of the key variables.

In the classical approach of Fellegi and Sunter (1969), one recognizes the probabilistic nature of ${\gamma }_{ab}$ due to the perturbations that cause key-variable errors. The related methods are referred to as probabilistic record linkage. To explain the probabilistic record linkage method of Fellegi and Sunter (1969), let $m\left({\gamma }_{ab}\right)\mathrm{<mo>=</mo>}f\left({\gamma }_{ab}|\left(a\mathrm{,}b\right)\in M\right)$ be the probability mass function of the discrete values ${\gamma }_{ab}$ can take given $\left(a\mathrm{,}b\right)\in M.$ Similarly, we can define $u\left({\gamma }_{ab}\right)\mathrm{<mo>=</mo>}f\left({\gamma }_{ab}|\left(a\mathrm{,}b\right)\in U\right).$ The ratio

$$r_{ab}\mathrm{<mo>=</mo>}\frac{m\left({\gamma }_{ab}\right)}{u\left({\gamma }_{ab}\right)}$$

is then the basis of the likelihood ratio test (LRT) for $H_0\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in M$ vs. $H_1\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in U.$ Let $M^{*}\mathrm{<mo>=</mo>}\left\{\left(a\mathrm{,}b\right)\text{:}{r}_{ab}>c_M\right\}$  be the pairs classified as matches and $U^{*}\mathrm{<mo>=</mo>}\{\left(a\mathrm{,}b\right)\text{:}{r}_{ab}<c_U\}MathType@MTEF@5@5@+=\; feaagKart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn\; hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr\; 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbf9F4rqqrFfpeea0xe9Lq=Jc9\; vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=x\; fr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyvamaaCa\; aaleqabaGaaiOkaaaakiaaysW7caaI9aGaaGjbVpaacmqabaWaaeWa\; beaacaWGHbGaaGilaiaaysW7caWGIbaacaGLOaGaayzkaaGaaGPaVl\; aaiQdacaaMe8UaaGPaVlaadkhadaWgaaWcbaGaamyyaiaadkgaaeqa\; aOGaaGjbVlabgYda8iaaysW7caWGJbWaaSbaaSqaaiaadwfaaeqaaa\; GccaGL7bGaayzFaaaaaa@51CC@$ the non-matches, the remaining pairs are classified by clerical review, where $\left(c_M\mathrm{,}{c}_U\right)$ are the thresholds related to the probabilities of false links (of pairs in $U)$ and false non-links (of pairs in $M),$ respectively, defined as

$\mu \mathrm{<mo>=</mo>}{\displaystyle \sum _{\gamma }u\left(\gamma \right)\delta \left(M^{*};\gamma \right)}$   and   $\lambda \mathrm{<mo>=</mo>}{\displaystyle \sum _{\gamma }m\left(\gamma \right)\delta \left(U^{*}\mathrm{<mo>;</mo>}\gamma \right),}(2.1)$

where $\delta \left(M^{*}\mathrm{<mo>;</mo>}\gamma \right)\mathrm{<mo>=</mo>}1$ if ${\gamma }_{ab}\mathrm{<mo>=</mo>}\gamma$ means $\left(a\mathrm{,}b\right)\in M^{*}$ and 0 otherwise, similarly for $\delta \left(U^{*}\mathrm{<mo>;</mo>}\gamma \right).$

In practice the probabilities $m\left(\gamma \right)$ and $u\left(\gamma \right)$ are unknown. Neither is the prevalence of true matches, given by $\pi \mathrm{<mo>=</mo>}\left|M\right|/\left|\Omega \right|\mathrm{<mo>:=</mo>}{n}_M/n.$ Let $\eta$ be the set containing $\pi$ and the unknown parameters of $m\left(\gamma \right)$ and $u\left(\gamma \right).$ Let $g_{ab}\mathrm{<mo>=</mo>}1$ if $\left(a\mathrm{,}b\right)\in M$ and 0 if $\left(a\mathrm{,}b\right)\in U.$ Given the complete data $\left\{\left(g_{ab}\mathrm{,}{\gamma }_{ab}\right)\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in \Omega \right\},$ Winkler (1988) and Jaro (1989) assume the log-likelihood to be

$$h\left(\eta \right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \Omega }{g}_{ab}}\log \left(\pi m\left({\gamma }_{ab}\right)\right)+{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \Omega }\left(1-g_{ab}\right)}\log \left(\left(1-\pi \right)u\left({\gamma }_{ab}\right)\right).(2.2)$$

An EM-algorithm follows by treating $g_{\Omega }\mathrm{<mo>=</mo>}\left\{g_{ab}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in \Omega \right\}$ as the missing data.

• There are two fundamental problems with this classical approach. 
  • [Problem-I] Record linkage is not a direct application of the LRT, because one needs to evaluate all the pairs in $\Omega$ instead of any given pair. The classification of $\Omega$ into $M^{*}$ and $U^{*}$ is incoherent generally, since a given record can belong to multiple pairs in $M^{*}.$ Post-classification deduplication of $M^{\mathrm{<mo>*</mo>}}$ would be necessary then, which is not part of the theoretical formulation above. In particular, there lacks an associated method for estimating the uncertainty surrounding the final linked set, such as the amount of false links in it or the remaining matches outside of it.
  • [Problem-II] In reality the comparison vectors of any two pairs are not independent, as long as they share a record. For example, given $\left(a\mathrm{,}b\right)\in M$ and ${\gamma }_{ab}$ not subjected to errors, then $g_{ab\prime }$ must be 0, for $b\prime \ne b$ and $b\prime \in B,$ as long as there are no duplicated records in either $A$ or $B,$ and ${\gamma }_{ab\prime }$ depends only on the key-variable errors of $b\prime .$ Whereas, marginally, $g_{ab\prime }\mathrm{<mo>=</mo>}1$ with probability $\pi$ and ${\gamma }_{ab\prime }$ depends also on the key-variable errors of $a.$ It follows that $h\left(\eta \right)$ in (2.2) does not correspond to the true joint-data distribution of ${\gamma }_{\Omega }\mathrm{<mo>=</mo>}\left\{{\gamma }_{ab}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in \Omega \right\},$ even when the marginal $m$ and $u$ -probabilities are correctly specified. Similarly, although one may define marginally $\pi \mathrm{<mo>=</mo>}\text{Pr}\left[\left(a\mathrm{,}b\right)\in M|\left(a\mathrm{,}b\right)\in \Omega \right]$ for a randomly selected record pair from $\Omega ,$ it does not follow that $\text{log}f\left(g_{\Omega }\right)\mathrm{<mo>=</mo>}{n}_M\text{log}\pi +\left(n-n_M\right)\log \left(1-\pi \right)$ jointly as in (2.2). For both reasons, $h\left(\eta \right)$ given by (2.2) cannot be the complete-data log-likelihood.

  In the next two sections, we develop maximum entropy classification to record linkage to avoid the problems above, after which more discussions of the classical approach will be given.

  • Previous
  • Article main page
  • Next