Maximum entropy classification for record linkage
Section 4. MEC for unsupervised record linkage

• Previous
• Next

Given $A$ and $B$ preprocessed as above, the maximal MEC set $M_1$ only consists of the record pairs with the perfect agreement of all the key variables. For probabilistic linkage beyond $M_1,$ one can follow the same scheme of MEC in the supervised setting, as long as one is able to obtain an estimate of the probability ratio, given which one can form the MEC set of any chosen size. Nevertheless, to estimate the associated FLR (3.5) and MMR (3.6), an estimate of $n_M$ is also needed.

4.1   Algorithm of unsupervised MEC

The idea now is to apply (3.7) and (3.9) jointly. Since setting ${\widehat{n}}_M\mathrm{<mo>=</mo>}\left|M_1\right|$ and ${\widehat{\theta }}_k\equiv 1$ associated with the maximal MEC set satisfies (3.7) and (3.9) automatically, probabilistic linkage requires one to assume $n_M>\left|M_1\right|$ and ${\theta }_k<1$ for at least some of $k\mathrm{<mo>=</mo>}\mathrm{1,}\dots ,K.$ Moreover, unless there is external information that dictates it otherwise, one can only assume common support $S\left(M\right)\mathrm{<mo>=</mo>}S\left(U\right)$ in the unsupervised setting. Let

$$r\left(\gamma \right)\mathrm{<mo>=</mo>}m\left(\gamma \mathrm{<mo>;</mo>}\theta \right)/u\left(\gamma \mathrm{<mo>;</mo>}\xi \right)(4.1)$$

where the probability of observing $\gamma$ is $m\left(\gamma \mathrm{<mo>;</mo>}\theta \right)$ by (3.3) given that a randomly selected record pair from $\Omega$ belongs to $M,$ and $u\left(\gamma \mathrm{<mo>;</mo>}\xi \right)$ otherwise, similarly given by (3.3) with parameters ${\xi }_k$ instead of ${\theta }_k.$ An iterative algorithm of unsupervised MEC is given below. 

• I. Set ${\theta }^{\left(0\right)}\mathrm{<mo>=</mo>}\left({\theta }_1^{\left(0\right)}\mathrm{,}\dots ,{\theta }_K^{\left(0\right)}\right)$ and $n_M^{\left(0\right)}\mathrm{<mo>=</mo>}\left|M_1\right|,$ where $M_1$ is the maximal MEC set.
• II. For the $t^{\text{th}}$ iteration, let $g_{ab}^{\left(t\right)}\mathrm{<mo>=</mo>}1$ if $\left(a\mathrm{,}b\right)\in M^{\left(t\right)},$ and 0 otherwise. 

  • i. Update $u\left(\gamma \mathrm{<mo>;</mo>}{\xi }^{\left(t\right)}\right)$ by using (4.4), which is discussed below, given $g^{\left(t\right)}\mathrm{<mo>=</mo>}\left\{g_{ab}^{\left(t\right)}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in \Omega \right\},$ and calculate

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

  • which maximize $D_M$ in (3.4) for given $u\left(\gamma \mathrm{<mo>;</mo>}{\xi }^{\left(t\right)}\right)\mathrm{,}{M}^{\left(t\right)}\mathrm{<mo>=</mo>}\left\{\left(a\mathrm{,}b\right)\in \Omega \mathrm{<mo>:</mo>}{g}_{ab}^{\left(t\right)}\mathrm{<mo>=</mo>}1\right\}$ and $\left|M^{\left(t\right)}\right|\mathrm{<mo>=</mo>}{\displaystyle {\sum }_{\left(a\mathrm{,}b\right)\in \Omega }{g}_{ab}^{\left(t\right)}}.$ Once ${\theta }^{\left(t\right)}$ and ${\xi }^{\left(t\right)}$ are obtained, we can update $n_M^{\left(t\right)}\mathrm{<mo>=</mo>}{\displaystyle {\sum }_{\gamma }n\left(\gamma \right){\widehat{g}}^{\left(t\right)}\left(\gamma \right)},$ where

  $${\widehat{g}}^{\left(t\right)}\left(\gamma \right)\equiv \widehat{g}\left(\gamma \mathrm{<mo>;</mo>}{\theta }^{\left(t\right)}\mathrm{,}{\xi }^{\left(t\right)}\right)\mathrm{<mo>=</mo>}\text{min}\left\{\frac{\left|M^{\left(t\right)}\right|r^{\left(t\right)}\left(\gamma \right)}{\left|M^{\left(t\right)}\right|\left(r^{\left(t\right)}\left(\gamma \right)-1\right)+n}\mathrm{,<mi>\; </mi><mtext>\hspace{0.17em}</mtext>1}\right\}$$

  $$r^{\left(t\right)}\left(\gamma \right)\equiv r\left(\gamma \mathrm{<mo>;</mo>}{\theta }^{\left(t\right)}\mathrm{,}{\xi }^{\left(t\right)}\right)\mathrm{<mo>=</mo>}\frac{m\left(\gamma \mathrm{<mo>;</mo>}{\theta }^{\left(t\right)}\right)}{u\left(\gamma \mathrm{<mo>;</mo>}{\xi }^{\left(t\right)}\right)}\mathrm{.}$$

  • ii. For given ${\theta }^{\left(t\right)}\mathrm{,}{\xi }^{\left(t\right)}$ and $n_M^{\left(t\right)},$ we find the MEC set $M^{\left(t+1\right)}\mathrm{<mo>=</mo>}\left\{\left(a\mathrm{,}b\right)\in \Omega \mathrm{<mo>:</mo>}{g}_{ab}^{\left(t+1\right)}\mathrm{<mo>=</mo>}1\right\}$ such that $\left|M^{\left(t+1\right)}\right|\mathrm{<mo>=</mo>}{n}_M^{\left(t\right)}$ by deduplication in the descending order of $r^{\left(t\right)}\left({\gamma }_{ab}\right)$ over $\Omega .$ It maximizes the entropy denoted by $Q^{\left(t\right)}(g):$

  $$Q^{\left(t\right)}\left(g\right)\equiv Q\left(g|{\psi }^{\left(t\right)}\right)\mathrm{<mo>=</mo>}\frac{1}{n_M^{\left(t\right)}}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \Omega }{g}_{ab}}\log r^{\left(t\right)}\left({\gamma }_{ab}\right)\mathrm{,}(4.3)$$

  • with respect to $g.$
• III. Iterate until $n_M^{\left(t\right)}=n_M^{\left(t+1\right)}$ or $\Vert {\theta }^{\left(t\right)}-{\theta }^{\left(t+1\right)}\Vert <$ $Є$ , where $Є$  is a small positive value.

A theoretical convergence property of the proposed algorithm and its proof are presented in the supplementary materials.

Notice that, insofar as $\Omega \mathrm{<mo>=</mo>}M\cup U$ is highly imbalanced, where the prevalence of $g_{ab}\mathrm{<mo>=</mo>}1$ is very close to 0, one could simply ignore the contributions from $M$ and use

${\widehat{\xi }}_k=\frac{1}{n}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \Omega }\text{}}$ $I\left({\gamma }_{\left(ab,k\right)}=1\right)$ $(4.4)$

under the model (3.3) of $u\left(\gamma \mathrm{<mo>;</mo>}\xi \right),$ in which case there is no updating of $u\left(\gamma \mathrm{<mo>;</mo>}{\xi }^{\left(t\right)}\right).$ Other possibilities of estimating $u\left(\gamma \mathrm{<mo>;</mo>}\xi \right)$ will be discussed in Section 5.2.

Table 4.1 provides an overview of MEC for record linkage in the supervised or unsupervised setting. In the supervised setting, one observes $\gamma$ for the matched record pairs in $M,$ so that the probability $m\left(\gamma \right)$ can be estimated from them directly. Whereas, for MEC in the unsupervised setting, one cannot separate the estimation of $m\left(\gamma \right)$ and $n_M.$

4.2   Error rates

MEC for record linkage should generally be guided by the error rates, FLR and MMR, without being restricted to the estimate of $n_M.$

Note that $\left\{{\widehat{g}}_{ab}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in \widehat{M}\right\}$ of any MEC set $\widehat{M}$ are among the largest ones over $\Omega ,$ because MEC follows the descending order of ${\widehat{r}}_{ab},$ except for necessary deduplication when there are multiple pairs involving a given record. To exercise greater control of the FLR, let $\psi$ be the target FLR, and consider the following bisection procedure. 

• i. Choose a threshold value $c_{\psi }$ and form the corresponding MEC set $\widehat{M}\left(c_{\psi }\right),$ where ${\widehat{r}}_{ab}\ge c_{\psi }$ for any $\left(a\mathrm{,}b\right)\in \widehat{M}\left(c_{\psi }\right).$
• ii. Calculate the estimated FLR of the resulting MEC set $\widehat{M}$ as

$$\widehat{\psi }\mathrm{<mo>=</mo>}\frac{1}{\left|\widehat{M}\right|}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}}\left(1-{\widehat{g}}_{ab}\right)\mathrm{.}}(4.5)$$

• If $\widehat{\psi }>\psi ,$ then increase $c_{\psi };$ if $\widehat{\psi }<\psi ,$ then reduce $c_{\psi }.$

Iteration between the two steps would eventually lead to a value of $c_{\psi }$ that makes $\widehat{\psi }$ as close as possible to $\psi ,$ for the given probability ratio $\widehat{r}\left(\gamma \right).$

The final MEC set $\widehat{M}$ can be chosen in light of the corresponding FLR estimate $\widehat{\psi }.$ It is also possible to take into consideration the estimated MMR given by

$$\widehat{\tau }\mathrm{<mo>=</mo>}1-{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}}{\widehat{g}}_{ab}/{\widehat{n}}_M}(4.6)$$

where ${\widehat{n}}_M$ is given by unsupervised MEC algorithm. Note that if $\left|\widehat{M}\right|\mathrm{<mo>=</mo>}{\widehat{n}}_M,$ then we shall have $\widehat{\psi }\mathrm{<mo>=</mo>}\widehat{\tau };$ but not if $\widehat{M}$ is guided by a given target value of FLR or MMR.

In Section 6.2, we investigate the performance of the MEC sets guided by the error rates through simulations.

• Previous
• Article main page
• Next