Maximum entropy classification for record linkage
Section 5. Discussion

• Previous
• Next

Below we discuss and compare two other approaches in the unsupervised setting, including the ways by which some of their elements can be incorporated into the MEC approach. Other less practical approaches are discussed in the supplementary material.

5.1   The classical approach

Recall Problems I and II of the classical approach mentioned in Section 2.

From a practical point of view, Problem I can be dealt with by any deduplication method of the set $M^{*}$ of classified records pairs, where $\widehat{r}\left({\gamma }_{ab}\right)$ is above a threshold value for all $\left(a\mathrm{,}b\right)\in M^{*}.$ As “an advance over previous ad hoc assignment methods”, Jaro (1989) chooses the linked set ${\widehat{M}}^{*}\subseteq M^{*},$ which maximises the sum of $\text{log}\widehat{r}\left({\gamma }_{ab}\right)$ subject to the constraint of one-one link. Since ${\widehat{g}}_{ab}$ is a monotonic function of $\widehat{r}\left({\gamma }_{ab}\right),$ this amounts to choose ${\widehat{M}}^{*}$ which maximises the expected number of matches in it, denoted by

$$n_M^{*}\mathrm{<mo>=</mo>}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in {\widehat{M}}^{*}}{\widehat{g}}_{ab}}$$

But $n_M^{*}$ is still not connected to the probabilities of false links and non-links defined by (2.1). As illustrated below, neither does it directly control the errors of the linked ${\widehat{M}}^{*}.$

Consider linking two files with 100 records each. Suppose Jaro’s assignment method yields $\left|{\widehat{M}}^{*}\right|\mathrm{<mo>=</mo>}100$ on one occasion, where 80 links have ${\widehat{g}}_{ab}\approx 1$ and 20 links have ${\widehat{g}}_{ab}\approx \text{0}\text{.75},$ such that $n_M^{*}\approx 95.$ Suppose it yields 90 links with ${\widehat{g}}_{ab}\approx 1$ and 10 links with ${\widehat{g}}_{ab}\approx \text{0}\text{.5}$ on another occasion, where $n_M^{*}\approx 95.$ Clearly, $n_M^{*}$ does not directly control the linkage errors in ${\widehat{M}}^{*}.$ Moreover, there is no compelling reason to accept 100 links on both these occasions, simply because 100 one-one links are possible.

In forming the MEC set one deals with Problem I directly, based on the concept of maximum entropy that has relevance in many areas of scientific investigation. The implementation is simple and fast for large datasets. The estimated error rates FLR (4.5) and MMR in (4.6) are directly defined for a given MEC set.

Problem II concerns the parameter estimation. As explained earlier, applying the EM algorithm based on the objective function (2.2) proposed by Winkler (1988) and Jaro (1989) is not a valid approach of maximum likelihood estimation (MLE). One may easily compare this WJ-procedure to that given in Section 4.1, where both adopt the same model (3.3) and the same estimator of $u\left(\gamma \mathrm{<mo>;</mo>}\xi \right)$ via ${\widehat{\xi }}_k$ given by (4.4). It is then clear that the same formula is used for updating $n_M^{\left(t\right)}$ at each iteration, but a different formula is used for

$${\theta }_k^{\left(t\right)}\mathrm{<mo>=</mo>}\frac{1}{n_M^{\left(t\right)}}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \Omega }{\widehat{g}}_{ab}^{\left(t\right)}{\gamma }_{ab\mathrm{,}k}}(5.1)$$

where the numerator is derived from all the pairs in $\Omega ,$ whereas ${\theta }_k^{\left(t\right)}$ given by (4.2) uses only the pairs in the MEC set $M^{\left(t\right)}.$ Notice that the two differ only in the unsupervised setting, but they would become the same in the supervised setting, where one can use the observed binary $g_{ab}$ instead of the estimated fractional ${\widehat{g}}_{ab}.$

Thus, one may incorporate the WJ-procedure as a variation of the unsupervised MEC algorithm, where the formulae (5.1) and (4.4) are chosen specifically. This is the reason why it can give reasonable parameter estimates in many situations, despite its misconception as the MLE. Simulations will be used later to compare empirically the two formulae (4.2) and (5.1) for ${\theta }_k^{\left(t\right)}.$

5.2   An approach of MLE

Below we derive another estimator of ${\xi }_k$ by the ML approach, which can be incorporated into the proposed MEC algorithm, instead of (4.4). This requires a model of the key variables, which explicates the assumptions of key-variable errors. Let $z_k$ be the $k^{\text{th}}$ key variable which takes value $\mathrm{1,}\dots ,D_k.$ Copas and Hilton (1990) envisage a non-informative hit-miss generation process, where the observed $z_k$ can take the true value despite the perturbation. Copas and Hilton (1990) demonstrate that the hit-miss model is plausible in the SL (Supervised Learning) setting based on labelled datasets.

We adapt the hit-miss model to the unsupervised setting as follows. First, for any $\left(a\mathrm{,}b\right)\in M,$ let ${\alpha }_k=\text{Pr}\left(e_{ab\mathrm{,}k}=1\right),$ where $e_{ab\mathrm{,}k}=1$ if the associated pair of key variables are subjected to any form of perturbation that could potentially cause disagreement of the $k^{\text{th}}$ key variable, and $e_{ab\mathrm{,}k}\mathrm{<mo>=</mo>}0$ otherwise. Let

$${\theta }_k\mathrm{<mo>=</mo>}\left(1-{\alpha }_k\right)+{\alpha }_k{\displaystyle \sum _{d\mathrm{<mo>=</mo>}1}^{D_k}{m}_{kd}^2}\mathrm{<mo>=</mo>}1-{\alpha }_k\left(1-{\displaystyle \sum _{d\mathrm{<mo>=</mo>}1}^{D_k}{m}_{kd}^2}\right)$$

where we assume that ${\alpha }_k$ must be positive for some $k\mathrm{<mo>=</mo>}\mathrm{1,}\dots ,K,$ and

$$m_{kd}=\text{Pr}\left(z_{ik}=d|g_{ab}\mathrm{<mo>=</mo>}\mathrm{1,}{e}_{ab\mathrm{,}k}=1\right)=\text{Pr}\left(z_{ik}\mathrm{<mo>=</mo>}d|g_{ab}\mathrm{<mo>=</mo>}\mathrm{1,}{e}_{ab\mathrm{,}k}\mathrm{<mo>=</mo>}0\right)$$

for $i=a$ or $b.$ Next, for any record $i$ in either $A$ or $B,$ let ${\delta }_i\mathrm{<mo>=</mo>}1$ if it has a match in the other file and ${\delta }_i=0$ otherwise. Given ${\delta }_i=0,$ with or without perturbation, let $\text{Pr}\left(z_{ik}=d|{\delta }_i=0\right)=u_{kd}.$ We have ${\beta }_{kd}\mathrm{<mo>:=</mo>}{m}_{kd}\equiv u_{kd}$ if ${\delta }_i$ is non-informative. A slightly more relaxed assumption is that ${\delta }_i$ is only non-informative in one of the two files. To be more resilient against its potential failure, one can assume $m_{kd}$ to hold for all the records in the smaller file, and allow $u_{kd}$ to differ for the records with ${\delta }_i\mathrm{<mo>=</mo>}0$ in the larger file. Suppose $n_A<n_B.$ Let

$$p=\text{Pr}\left({\delta }_b=1\right)=E\left(n_M\right)/n_B=n_A\pi$$

be the probability that a record in $B$ has a match in $A.$ One may assume $z_A=\left\{z_a\mathrm{<mo>:</mo>}a\in A\right\}$ to be independent over $A,$ giving

$${\text{ℓ}}_A={\displaystyle \sum _{a\in A}{\displaystyle \sum _{k\mathrm{<mo>=</mo>}1}^K\log m_{ak}}}$$

where $m_{ak}={\displaystyle {\sum }_{d\mathrm{<mo>=</mo>1}}^{D_k}{m}_{kd}}\text{}$ $I\left(z_{ak}=d\right)$ .  The complete-data log-likelihood based on $\left({\delta }_B\mathrm{,}{z}_B\right)$ is

$${\text{ℓ}}_B={\displaystyle \sum _{b\in B}{\delta }_b}\log \left(p{\displaystyle \prod _{k\mathrm{<mo>=</mo>1}}^K{m}_{bk}}\right)+{\displaystyle \sum _{b\in B}\left(1-{\delta }_b\right)}\log \left(\left(1-p\right){\displaystyle \prod _{k\mathrm{<mo>=</mo>1}}^K{u}_{bk}}\right)(5.2)$$

where $m_{bk}\mathrm{<mo>=</mo>}{\displaystyle {\sum }_{d\mathrm{<mo>=</mo>1}}^{D_k}{m}_{kd}}$ $I\left(z_{ak}=d\right)$  and $u_{bk}\mathrm{<mo>=</mo>}{\displaystyle {\sum }_{d\mathrm{<mo>=</mo>1}}^{D_k}{u}_{kd}}$ $I\left(z_{ak}=d\right)$ , based on an assumption of independent $\left({\delta }_b\mathrm{,}{z}_b\right)$ across the entities in $B.$

Under separate modelling of $z_A$ and $\left(z_B\mathrm{,}{\delta }_B\right),$ let ${\widehat{m}}_{kd}$ be the MLE based on ${\text{ℓ}}_A,$ given which an EM-algorithm for estimating $p$ and $u_{kd}$ follows from (5.2) by treating ${\delta }_B$ as the missing data. However, the estimation is feasible only if $\left\{u_{kd}\right\}$ and $\left\{m_{kd}\right\}$ are not exactly the same; whereas the MLE of $n_M$ has a large variance, when $\left\{m_{kd}\right\}$ and $\left\{u_{kd}\right\}$ are close to each other, even if they are not exactly equal.

Meanwhile, the closeness between $\left\{m_{kd}\right\}$ and $\left\{u_{kd}\right\}$ does not affect the MEC approach, where ${\widehat{n}}_M$ is obtained from solving (3.7) given $\widehat{r}\left(\gamma \right)\mathrm{<mo>=</mo>}\widehat{m}\left(\gamma \right)/\widehat{u}\left(\gamma \right),$ where $\widehat{u}\left(\gamma \right)$ is indeed most reliably estimated when $\left\{m_{kd}\right\}=\left\{u_{kd}\right\}.$ Moreover, one can incorporate a profile EM-algorithm, based on (5.2) given $n_M^{\left(t\right)},$ to update $u\left(\gamma \mathrm{<mo>;</mo>}{\xi }^{\left(t\right)}\right)$ in the unsupervised MEC algorithm of Section 4.1. At the $t^{\text{th}}$ iteration, where $t\ge 1,$ given $p^{\left(t\right)}=n_M^{\left(t\right)}/\max \left(n_A\mathrm{,}{n}_B\right)$ and ${\widehat{m}}_{kd}$ estimated from the smaller file $A,$ obtain $u_{kd}^{\left(t\right)}$ by

$${\xi }_k^{\left(t\right)}=\left(\left(1-p^{\left(t\right)}\right){\displaystyle \sum _{d\mathrm{<mo>=</mo>}1}^{D_k}{u}_{kd}^{\left(t\right)}{\widehat{m}}_{kd}+p^{\left(t\right)}\left(1-\frac{1}{n_A}\right){\displaystyle \sum _{d\mathrm{<mo>=</mo>}1}^{D_k}{\widehat{m}}_{kd}^2}}\right)/\left(1-p^{\left(t\right)}/n_A\right)\mathrm{.}(5.3)$$

• Previous
• Article main page
• Next