Maximum entropy classification for record linkage
Section 3. Maximum entropy classification: Supervised

• Previous
• Next

As noted in Section 1, the record linkage problem is a classification problem. Maximum entropy classification has been used in image restoration or text analysis (Gull and Daniell, 1984; Berger, Della Pietra and Della Pietra, 1996). Maximum entropy classification (MEC) has been proposed for supervised learning (SL) to standard classification problems, where the units are known but the true classes of the units are unknown apart from a sample of labelled units. Let $Y\in \left\{\mathrm{1,}0\right\}$ be the true class and $X$ the random vector of features. Let the density ratio be

$$r\left(x\mathrm{<mo>;</mo>}\eta \right)\mathrm{<mo>=</mo>}\frac{f\left(x|Y\mathrm{<mo>=</mo>}\mathrm{1<mo>;</mo>}\eta \right)}{f\left(x|Y\mathrm{<mo>=</mo>}\mathrm{0<mo>;</mo>}\eta \right)}\mathrm{<mo>:=</mo>}\frac{f_1\left(x\mathrm{<mo>;</mo>}\eta \right)}{f_0\left(x\mathrm{<mo>;</mo>}\eta \right)}\mathrm{,}$$

where $f_1$ and $f_0$ are the conditional density functions given $Y\mathrm{<mo>=</mo>}1$ or 0, respectively, and $\eta$ contains the unknown parameters. For MEC based on $r\left(x\right),$ one finds $\widehat{\eta }$ that maximises the Kullback-Leibler (KL) divergence from $f_0$ to $f_1$ subjected to a constraint, i.e.

$D\mathrm{<mo>=</mo>}{\displaystyle {\int }_{S_1}{f}_1\left(x\mathrm{<mo>;</mo>}\eta \right)}\text{log}r\left(x\mathrm{<mo>;</mo>}\eta \right)dx$   subjected to   ${\displaystyle {\int }_{S_1}{f}_0\left(x\mathrm{<mo>;</mo>}\widehat{\eta }\right)r\left(x\mathrm{<mo>;</mo>}\widehat{\eta }\right)dx}\mathrm{<mo>=</mo>}\mathrm{1,}$

where $S_1$ is the support of $X$ given $Y\mathrm{<mo>=</mo>}1,$ and the normalisation constraint arises since $r\left(x\mathrm{<mo>;</mo>}\widehat{\eta }\right)f_0\left(x\mathrm{<mo>;</mo>}\widehat{\eta }\right)$ is an estimate of $f_1\left(x\right).$ Provided common support $S_1=S_0,$ where $S_0$ is the support of $X$ given $Y\mathrm{<mo>=</mo>}0,$ one can use the empirical distribution function (EDF) of $X$ over $\left\{x_i\mathrm{<mo>:</mo>}{y}_i\mathrm{<mo>=</mo>}1\right\}$ in place of $f_1$ for $D,$ and that over $\left\{x_i\mathrm{<mo>:</mo>}{y}_i\mathrm{<mo>=</mo>}0\right\}$ in place of $f_0$ for the constraint. Having obtained ${\widehat{r}}_x\mathrm{<mo>=</mo>}r\left(x\mathrm{<mo>;</mo>}\widehat{\eta }\right),$ one can classify any unit given the associated feature vector $x$ based on $\text{Pr}\left(Y\mathrm{<mo>=</mo>}1|x\mathrm{<mo>;</mo>}\widehat{p}\mathrm{,}{\widehat{r}}_x\right),$ where $\widehat{p}$ is an estimate of the prevalence $p\mathrm{<mo>=</mo>}\text{Pr}\left(Y\mathrm{<mo>=</mo>}1\right).$

We describe how the idea of MEC for supervised learning can be adapted to record linkage problem in the following subsections.

3.1   Probability ratio for record linkage

For supervised learning based MEC to record linkage, suppose $M$ is observed for the given $\Omega ,$ and the trained classifier is to be applied to the record pairs outside of $\Omega .$ To fix the idea, suppose $B$ is a non-probability sample that overlaps with the population $P,$ and $A$ is a probability sample from $P$ with known inclusion probabilities. While ${\gamma }_M\mathrm{<mo>=</mo>}\left\{{\gamma }_{ab}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in M\right\}$ may be considered as an IID sample, since each $\left(a\mathrm{,}b\right)$ in $M$ refers to a distinct entity, this is not the case with $\left\{{\gamma }_{ab}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\cancel{\in }M\right\},$ whose joint distribution is troublesome to model.

Probability ratio (I)

Let $r_q\left(\gamma \right)$ be the probability ratio given by

$$r_q\left(\gamma \right)\mathrm{<mo>=</mo>}\frac{m\left(\gamma \right)}{q\left(\gamma \right)}\mathrm{,}$$

where $m\left(\gamma \right)$ is the probability mass function of ${\gamma }_{ab}\mathrm{<mo>=</mo>}\gamma$ given $g_{ab}\mathrm{<mo>=</mo>}1,$ and $q\left(\gamma \right)$ is that over ${\gamma }_{\Omega }\mathrm{<mo>=</mo>}\left\{{\gamma }_{ab}\mathrm{<mo>:</mo>}\left(a\mathrm{,}b\right)\in \Omega \right\}.$ The KL divergence measure from $q\left(\gamma \right)$ to $m\left(\gamma \right)$ and the normalisation constraint are

$D_f\mathrm{<mo>=</mo>}{\displaystyle \sum _{\gamma \in S\left(M\right)}m\left(\gamma \right)}\log r_q\left(\gamma \right)$   and   ${\displaystyle \sum _{\gamma \in S\left(M\right)}\widehat{q}\left(\gamma \right)}{\widehat{r}}_q\left(\gamma \right)\mathrm{<mo>=</mo>}\mathrm{1<mi>\; </mi>,}$

where $S\left(M\right)$ is the support of ${\gamma }_{ab}$ given $g_{ab}\mathrm{<mo>=</mo>}1.$ This set-up allows $S\left(M\right)$ to be a subset of $S,$ where $S$ is the support of all possible ${\gamma }_{ab}.$ It follows that, based on the IID sample ${\gamma }_M$ of size $n_M\mathrm{<mo>=</mo>}\left|M\right|,$ the objective function to be minimized for $r_q$ can be given by

$$Q_f\mathrm{<mo>=</mo>}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in M}\frac{f\left({\gamma }_{ab}\right)}{n_M\left({\gamma }_{ab}\right)}}{r}_q\left({\gamma }_{ab}\right)-\frac{1}{n_M}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in M}\text{log}{r}_q\left({\gamma }_{ab}\right)}\mathrm{,}(3.1)$$

where $n_M\left({\gamma }_{ab}\right)=$ ${\displaystyle {\sum }_{\left(i\mathrm{,}j\right)\in M}\text{}}$ $I\left({\gamma }_{ij}={\gamma }_{ab}\right)$  based on the observed support $S\left(M\right).$

Probability ratio (II)

Provided $S\left(M\right)\subseteq S\left(U\right),$ where $S\left(U\right)$ is the support of ${\gamma }_{ab}$ over $U,$ one can let the probability ratio be given by

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

where $u\left(\gamma \right)$ is the probability of ${\gamma }_{ab}\mathrm{<mo>=</mo>}\gamma$ given $g_{ab}\mathrm{<mo>=</mo>}0.$ We have

$$r_q\left(\gamma \right)\mathrm{<mo>=</mo>}\frac{m\left(\gamma \right)}{q\left(\gamma \right)}\mathrm{<mo>=</mo>}\frac{m\left(\gamma \right)}{\pi m\left(\gamma \right)+\left(1-\pi \right)u\left(\gamma \right)}\mathrm{<mo>=</mo>}\frac{r\left(\gamma \right)}{\pi \left(r\left(\gamma \right)-1\right)+1}$$

where $q\left(\gamma \right)\mathrm{<mo>=</mo>}\pi m\left(\gamma \right)+\left(1-\pi \right)u\left(\gamma \right),$ so that $r_q\left(\gamma \right)$ and $r\left(\gamma \right)$ are one-to-one. Meanwhile, the KL divergence measure from $u\left(\gamma \right)$ to $m\left(\gamma \right)$ is given by

$$D\mathrm{<mo>=</mo>}{\displaystyle \sum _{\gamma \in S\left(M\right)}m\left(\gamma \right)}\log r\left(\gamma \right)$$

and the objective function to be minimized for $r$ can now be given by

$$Q\mathrm{<mo>=</mo>}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in M}\frac{u\left({\gamma }_{ab}\right)}{n_M\left({\gamma }_{ab}\right)}}r\left({\gamma }_{ab}\right)-\frac{1}{n_M}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in M}\log r\left({\gamma }_{ab}\right)}\mathrm{.}(3.2)$$

Model of $\gamma$:  Under the multinomial model, one can simply use the EDF of $\gamma$ over ${\gamma }_{\Omega }$ as $f\left(\gamma \right),$ for each distinct level of $\gamma ,$ as long as $\left|\Omega \right|$ is large compared to $\left|S\right|.$ Similarly for $m\left(\gamma \right)$ over ${\gamma }_M$ and $u\left(\gamma \right)$ over $U.$ For linkage outside of $\Omega ,$ the estimated $m\left(\gamma \right)$ from $M\left(\Omega \right)$ applies, if the selection of $A$ from $P$ is non-informative.

For $\gamma$ made up of $K$ binary agreement indicators, ${\gamma }_k\mathrm{<mo>=</mo>}\text{0,}\text{1}$ for $k\mathrm{<mo>=</mo>}\mathrm{1,}\dots \mathrm{,}K,$ there are up to $2^K$ distinct levels of $\gamma ,$ which can sometimes be relatively large compared to $\left|M\right|.$ A more parsimonious model of $m\left(\gamma \mathrm{<mo>;</mo>}\theta \right)$ that is commonly used is given by

$$m\left(\gamma \mathrm{<mo>;</mo>}\theta \right)\mathrm{<mo>=</mo>}{\displaystyle \prod _{k\mathrm{<mo>=</mo>}1}^K{\theta }_k^{{\gamma }_k}{\left(1-{\theta }_k\right)}^{1-{\gamma }_k}}(3.3)$$

where ${\theta }_k\mathrm{<mo>=</mo>}\text{Pr}\left({\gamma }_{ab\mathrm{,}k}\mathrm{<mo>=</mo>}1|g_{ab}\mathrm{<mo>=</mo>}1\right),$ and ${\gamma }_{ab\mathrm{,}k}$ is the $k^{\text{th}}$ component of ${\gamma }_{ab}.$ It is possible to model ${\theta }_k$ based on the distributions of the key variables that give rise to $\gamma ,$ which makes use of the differential frequencies of their values, such as the fact that some names are more common than others. Similarly, $u\left(\gamma \mathrm{<mo>;</mo>}\xi \right)$ can be modeled as in (3.3) with parameters ${\xi }_k$ instead of ${\theta }_k,$ where ${\xi }_k\mathrm{<mo>=</mo>}\text{Pr}\left({\gamma }_{ab\mathrm{,}k}\mathrm{<mo>=</mo>}1|g_{ab}\mathrm{<mo>=</mo>}0\right).$

Note that (3.3) implies conditional independence among agreement indicators. Winkler (1993) and Winkler (1994) demonstrated that even when the conditional independence assumption does not hold, results based on conditional independence assumption are quite robust. More complicated models that allow for correlated ${\gamma }_k$ can also be considered. See Armstrong and Mayda (1993) and Larsen and Rubin (2001) for discussion of those models. See Xu, Li, Shen, Hui and Grannis (2019) for a recent study which compares models with or without correlated ${\gamma }_k.$

3.2   MEC sets for record linkage

Provided there are no duplicated records in either $A$ or $B,$ a classification set for record linkage, denoted by $\widehat{M},$ consists of record pairs from $\Omega ,$ where any record in $A$ or $B$ appears at most in one record pair in $\widehat{M}.$ Let the entropy of a classification set $\widehat{M}$ be given by

$$D_{\widehat{M}}\mathrm{<mo>=</mo>}\frac{1}{\left|\widehat{M}\right|}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}}\text{log}r\left({\gamma }_{ab}\right).}(3.4)$$

A MEC set of given size $n^{*}\mathrm{<mo>=</mo>}\left|\widehat{M}\right|$ is the first classification set that is of size $n^{*},$ obtained by deduplication in the descending order of $r\left({\gamma }_{ab}\right)$ over $\Omega .$ It is possible to have $\left(a\mathrm{,}b\prime \right)\cancel{\in }\widehat{M}$ and $r\left({\gamma }_{ab\prime }\right)>r\left({\gamma }_{a\prime \mathrm{,}b\prime }\right)$ for $\left(a\prime \mathrm{,}b\prime \right)\in \widehat{M},$ if there exists $\left(a\mathrm{,}b\right)\in \widehat{M}$ with $r\left({\gamma }_{ab}\right)>r\left({\gamma }_{ab\prime }\right).$

A MEC set of size $n^{*}$ is not necessarily the largest possible classification set with the maximum entropy, to be referred to as a maximal MEC set, which is the largest classification set such that $r\left({\gamma }_{ab}\right)\mathrm{<mo>=</mo>}{{\displaystyle \text{max}}}_{\gamma }r\left(\gamma \right)$ for every $\left(a\mathrm{,}b\right)$ in it. In practice, a maximal MEC set is given by the first pass of deterministic linkage, which only consists of the record pairs with perfect and unique agreement of all the key variables.

Probabilistic linkage methods for MEC set are useful if one would like to allow for additional links, even though their key variables do not agree perfectly with each other. For the uncertainty associated with a given MEC set $\widehat{M},$ we consider two types of errors. First, we define the false link rate (FLR) among the links in $\widehat{M}$ to be

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

which is different to $\mu$ by (2.1) where the denominator is $\left|U\right|.$ Second, the missing match rate (MMR) of $\widehat{M},$ which is related to the false non-link probability $\lambda$ in (2.1), is given by

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

While $\mu$ and $\lambda$ in (2.1) are theoretical probabilities, the FLR and MMR are actual errors.

It is instructive to consider the situation, where one is asked to form MEC sets in $\Omega$ given all the necessary estimates related to the probability ratio $r\left(\gamma \right),$ which can be obtained under the SL setting, without being given $n_M,$ $g_{\Omega }$ or $M$ directly.

First, the perfect MEC set should have the size $n_M.$ Let $n\left(\gamma \right)=$ ${\displaystyle {\sum }_{\left(a\mathrm{,}b\right)\in \Omega }\text{}}$ $I\left({\gamma }_{ab}=\gamma \right)$. One can obtain $n_M$ as the solution to the following fixed-point equation:

$$n_M\mathrm{<mo>=</mo>}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \Omega }\widehat{g}\left({\gamma }_{ab}\right)}\mathrm{<mo>=</mo>}{\displaystyle \sum _{\gamma \in S}n\left(\gamma \right)\widehat{g}\left(\gamma \right)}(3.7)$$

where

$$\widehat{g}\left(\gamma \right)\mathrm{<mo>:=</mo>}\text{Pr}\left(g_{ab}=1|{\gamma }_{ab}=\gamma \right)\mathrm{<mo>=</mo>}\frac{\pi r\left(\gamma \right)}{\pi \left(r\left(\gamma \right)-1\right)+1}=\frac{n_{M}r\left(\gamma \right)}{n_M\left(r\left(\gamma \right)-1\right)+n}(3.8)$$

and the probability is defined with respect to completely random sampling of a single record pair from $\Omega .$ To see that $\widehat{g}\left(\gamma \right)$ by (3.8) satisfies (3.7), notice $\widehat{g}\left(\gamma \right)\mathrm{<mo>=</mo>}{n}_{M}m\left(\gamma \right)/n\left(\gamma \right)$ satisfies (3.7) for any well defined $m\left(\gamma \right),$ and $n\left(\gamma \right)/n=\pi m\left(\gamma \right)+\left(1-\pi \right)u\left(\gamma \right)$ by definition.

Next, apart from a maximal MEC set, one would need to accept discordant pairs. In the SL setting, one observes the EDF of $\gamma$ over $M,$ giving rise to ${\widehat{\theta }}_k\mathrm{<mo>=</mo>}{n}_M\left(\mathrm{1<mo>;</mo>}k\right)/n_M,$ where $n_M\left(\mathrm{1<mo>;</mo>}k\right)$ is the number of agreements on the $k^{\text{th}}$ key variable over $M.$ The perfect MEC set $\widehat{M}$ should have these agreement rates. We have then, for $k\mathrm{<mo>=</mo>}\mathrm{1,}\dots ,K,$

${\widehat{\theta }}_k\mathrm{<mo>=</mo>}\frac{1}{\left|\widehat{M}\right|}{\displaystyle \sum _{\left(a\mathrm{,}b\right)\in \widehat{M}}\text{}}$ $I\left({\gamma }_{ab,k}=1\right)$    for   $\left|\widehat{M}\right|\mathrm{<mo>=</mo>}{n}_M\mathrm{.}(3.9)$

Thus, no matter how one models $m\left(\gamma \right),$ the perfect MEC set should satisfy jointly the $K+1$ equations defined by (3.7) and (3.9), given the knowledge of $r\left(\gamma \right).$

• Previous
• Article main page
• Next