# Maximum entropy classification
for record linkage

Danhyang Lee  Department of Information Systems, Statistics and Management
Science, University of Alabama, Tuscaloosa, AL, U.S.A.  Li-Chun Zhang
Department of Social Statistics and Demography, University of Southampton,
Southampton, U.K.  Statistics Norway, Oslo, Norway  Department of Mathematics,
University of Oslo, Oslo, Norway  Jae Kwang Kim  Department of Statistics,
Iowa State University, Ames, IA, U.S.A.

###### Abstract

By record linkage one joins records residing in separate files which are
believed to be related to the same entity. In this paper we approach record
linkage as a classification problem, and adapt the maximum entropy
classification method in machine learning to record linkage, both in the
supervised and unsupervised settings of machine learning. The set of links
will be chosen according to the associated uncertainty. On the one hand, our
framework overcomes some persistent theoretical flaws of the classical
approach pioneered by Fellegi and Sunter (1969); on the other hand, the
proposed algorithm is fully automatic, unlike the classical approach that
generally requires clerical review to resolve the undecided cases.

Keywords: Probabilistic linkage; Density ratio; False link; Missing match;
Survey sampling

##  1 Introduction

Combining information from multiple sources of data is a frequently
encountered problem in many disciplines. To combine information from different
sources, one assumes that it is possible to identify the records associated
with the same entity, which is not always the case in practice. The entity may
be individual, company, crime, etc. If the data do not contain unique
identification number, identifying records from the same entity becomes a
challenging problem. _Record linkage_ is the term describing the process of
joining records that are believed to be related to the same entity. While
record linkage may entail the linking of records within a single computer file
to identify duplicate records, referred to as _deduplication_ , we focus on
linking of records across separate files.

Record linkage (RL) has been employed for several decades in survey sampling
producing official statistics. In particular, linking administrative files
with survey sample data can greatly improve the quality and resolution of the
official statistics. As applications, Jaro (1989) and Winkler and Thibaudeau
(1991) merged post-enumeration survey and census data for census coverage
evaluation. Zhang and Campbell (2012) linked population census data files over
time, and Owen et al. (2015) linked administrative registers to create a
single statistical population dataset. The classical approach pioneered by
Fellegi and Sunter (1969), which is the most popular method of RL in practice,
has been successfully employed for these applications.

The probabilistic decision rule of Fellegi and Sunter (1969) is based on the
likelihood ratio test idea, by which we can determine how likely a particular
record pair is a true match. In applying the likelihood ratio test idea, one
needs to estimate the model parameters of the underlying model and determine
the thresholds of the decision rule. Winkler (1988) and Jaro (1989) treat the
matching status as an unobserved variable and propose an EM algorithm for
parameter estimation, which we shall refer to as the WJ-procedure. See Herzog
et al. (2007), Christen (2012) and Binette and Steorts (2020) for overviews.
However, as explained in Section 2, to motivate the WJ-procedure as an EM
algorithm requires the crucial assumption that measures of agreement between
the record pairs, called comparison vectors, are independent from one record
pair to another, which is impossible to hold in reality. Newcombe et al.
(1959) address dependence between comparison vectors through data application.
Also, see e.g. Tancredi and Liseo (2011), Sadinle (2017), and Binette and
Steorts (2020) for discussions of this issue. Bayesian approaches to RL are
also available in the literature (Steorts, 2015; Sadinle, 2017; Stringham,
2021). Bayesian approaches to RL problems allow us to quantify uncertainty on
the matching decisions. However, the stochastic search using MCMC algorithm in
the Bayesian approach involves extra computational burden.

To develop an alternative approach, we first note that the RL problem is
essentially a classification problem, where each record pair is classified
into either “match” or “non-match” class. Various classification techniques
based on machine learning approaches have been employed for record linkage
(Hand and Christen, 2018; Christen, 2012, 2008; Sarawagi and Bhamidipaty,
2002). In this paper, we adapt the maximum entropy method for classification
to record linkage. Specifically, we can view the likelihood ratio of the
method proposed by Fellegi and Sunter (1969) as a special case of the density
ratio and apply the maximum entropy method for density ratio estimation. For
example, Nigam et al. (1999) use the maximum entropy for text classification
and Nguyen et al. (2010) develop a more unified theory of maximum entropy
method for density ratio estimation. There is, however, a key difference of
record linkage to the standard setting of classification problems, in that the
different record pairs are not distinct ‘units’ because the same record is
part of many record pairs.

We present our maximum entropy record linkage algorithm for both supervised
and unsupervised settings, while our main contributions concern the
unsupervised case. Supervised approaches need training data, i.e., record
pairs with known true match and true non-match status. Such training data are
often not available in real world situations, or have to be prepared manually,
which is very expensive and time-consuming (Christen, 2007). Thus, the
unsupervised case is by far the most common in practice. In the unsupervised
case, however, one cannot estimate the density ratio directly based on the
observed true matches and non-matches, and it is troublesome to jointly model
for the unobserved match status and the observed comparison scores over all
the record pairs. We develop a new iterative algorithm to jointly estimate the
density ratio as well as the maximum entropy classification set in the
unsupervised setting and prove its convergence. The associated measures of the
linkage uncertainty are also developed.

Furthermore, we show that the WJ-procedure can be incorporated as a special
case of our approach to estimation, but without the need of the independence
assumption between the record pairs. This reveals that the WJ-procedure can be
motivated without the independence assumption, and explains why it gives
reasonable results in many situations. The choice of the set of links is
guided by the uncertainty measures developed in this paper. This is an
important practical improvement over the classical approach, which does not
directly provide any uncertainty measure for the final set of links. Our
procedure is fully automatic, without the need for resource-demanding clerical
review that is required under the classical approach.

The paper is organised as follows. In Section 2, the basic setup and the
classical approach are introduced. In Section 3, the proposed method is
developed under the setting of supervised record linkage. In Section 4, we
extend the proposed method to the more challenging case of the unsupervised
record linkage. Discussions of some related estimation approaches and
technical details are presented in Section 5 and Appendix. Results from an
extensive simulation study are presented in Section 6. Some concluding remarks
and comments on further works are given in Section 7.

##  2 Problems with the classical approach

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=A\times B=M\cup U$ consist of _matches_
$M$ and _non-matches_ $U$ between the records in files $A$ and $B$. For any
pair of records $(a,b)\in\Omega$, let $\bm{\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 $\bm{\gamma}_{ab}$ are fully observed over $\Omega$. In
cases where the key variables may be affected by errors, a match $(a,b)$ may
not have complete agreement in terms of $\bm{\gamma}_{ab}$, and a non-match
$(a,b)$ 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 $\bm{\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(\bm{\gamma}_{ab})$ $=f(\bm{\gamma}_{ab}\mid(a,b)\in
M)$ be the probability mass function of the discrete values $\bm{\gamma}_{ab}$
can take given $(a,b)\in M$. Similarly, we can define $u(\bm{\gamma}_{ab})$
$=f(\bm{\gamma}_{ab}\mid(a,b)\in U)$. The ratio

$r_{ab}={\frac{m(\bm{\gamma}_{ab})}{u(\bm{\gamma}_{ab})}}$

is then the basis of the likelihood ratio test (LRT) for $H_{0}:(a,b)\in M$
vs. $H_{1}:(a,b)\in U$. Let $M^{*}=\\{(a,b):r_{ab}>c_{M}\\}$ be the pairs
classified as matches and $U^{*}=\\{(a,b):r_{ab}<c_{U}\\}$ the non-matches,
the remaining pairs are classified by clerical review, where $(c_{M},c_{U})$
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=\sum_{\bm{\gamma}}u(\bm{\gamma})\delta(M^{*};\bm{\gamma})\qquad\text{and}\qquad\lambda=\sum_{\bm{\gamma}}m(\bm{\gamma})\delta(U^{*};\bm{\gamma}),$
(1)

where $\delta(M^{*};\bm{\gamma})=1$ if $\bm{\gamma}_{ab}=\bm{\gamma}$ means
$(a,b)\in M^{*}$ and 0 otherwise, similarly for $\delta(U^{*};\bm{\gamma})$.

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

$h(\bm{\eta})=\sum_{(a,b)\in\Omega}g_{ab}\log(\pi{m(\bm{\gamma}_{ab})})+\sum_{(a,b)\in\Omega}(1-g_{ab})\log\big{(}(1-\pi){u(\bm{\gamma}_{ab})}\big{)}.$
(2)

An EM-algorithm follows by treating $g_{\Omega}=\\{g_{ab}:(a,b)\in\Omega\\}$
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^{*}$ 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 $(a,b)\in M$
and $\bm{\gamma}_{ab}$ not subjected to errors, then $g_{ab^{\prime}}$ must be
0, for $b^{\prime}\neq b$ and $b^{\prime}\in B$, as long as there are no
duplicated records in either $A$ or $B$, and $\bm{\gamma}_{ab^{\prime}}$
depends only on the key-variable errors of $b^{\prime}$. Whereas, marginally,
$g_{ab^{\prime}}=1$ with probability $\pi$ and $\bm{\gamma}_{ab^{\prime}}$
depends also on the key-variable errors of $a$. It follows that $h(\bm{\eta})$
in (2) does not correspond to the true joint-data distribution of
$\bm{\gamma}_{\Omega}=\\{\bm{\gamma}_{ab}:(a,b)\in\Omega\\}$, even when the
marginal $m$ and $u$-probabilities are correctly specified. Similarly,
although one may define _marginally_ $\pi=\mbox{Pr}[(a,b)\in
M|(a,b)\in\Omega]$ for a _randomly_ selected record pair from $\Omega$, it
does not follow that $\log f(g_{\Omega})=n_{M}\log\pi+(n-n_{M})\log(1-\pi)$
_jointly_ as in (2). For both reasons, $h(\bm{\eta})$ given by (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.

##  3 Maximum entropy classification: Supervised

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 et al., 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\\{1,0\\}$ be the true class and $\bm{X}$ the random vector of features.
Let the density ratio be

$r(\bm{x};\bm{\eta})=\frac{f(\bm{x}|Y=1;\bm{\eta})}{f(\bm{x}|Y=0;\bm{\eta})}{:=\frac{f_{1}(\bm{x};\bm{\eta})}{f_{0}(\bm{x};\bm{\eta})},}$

where $f_{1}$ and $f_{0}$ are the conditional density functions given $Y=1$ or
$0$, respectively, and $\bm{\eta}$ contains the unknown parameters. For MEC
based on $r(\bm{x})$, one finds $\hat{\bm{\eta}}$ that maximises the Kullback-
Leibler (KL) divergence from $f_{0}$ to $f_{1}$ subjected a constraint, i.e.

$D=\int_{\mathcal{S}_{1}}f_{1}(\bm{x};\bm{\eta})\log
r(\bm{x};\bm{\eta})d\bm{x}\quad\text{subjected
to}\quad\int_{\mathcal{S}_{1}}f_{0}(\bm{x};\hat{\bm{\eta}})r(\bm{x};\hat{\bm{\eta}})d\bm{x}=1,$

where $\mathcal{S}_{1}$ is the support of $\bm{X}$ given $Y=1$, and the
normalisation constraint arises since
$r(\bm{x};\hat{\bm{\eta}})f_{0}(\bm{x};\hat{\bm{\eta}})$ is an estimate of
$f_{1}(\bm{x})$. Provided common support $\mathcal{S}_{1}=\mathcal{S}_{0}$,
where $\mathcal{S}_{0}$ is the support of $\bm{X}$ given $Y=0$, one can use
the empirical distribution function (EDF) of $X$ over
$\\{\bm{x}_{i}:y_{i}=1\\}$ in place of $f_{1}$ for $D$, and that over
$\\{\bm{x}_{i}:y_{i}=0\\}$ in place of $f_{0}$ for the constraint. Having
obtained $\hat{r}_{\bm{x}}=r(\bm{x};\hat{\bm{\eta}})$, one can classify any
unit given the associated feature vector $\bm{x}$ based on
$\mbox{Pr}(Y=1|\bm{x};\hat{p},\hat{r}_{\bm{x}})$, where $\hat{p}$ is an
estimate of the prevalence $p=\mbox{Pr}(Y=1)$.

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 $\mathcal{P}$, and $A$ is
a probability sample from $\mathcal{P}$ with known inclusion probabilities.
While $\bm{\gamma}_{M}=\\{\bm{\gamma}_{ab}:(a,b)\in M\\}$ may be considered as
an IID sample, since each $(a,b)$ in $M$ refers to a distinct entity, this is
not the case with $\\{\bm{\gamma}_{ab}:(a,b)\not\in M\\}$, whose _joint_
distribution is troublesome to model.

#### Probability ratio (I)

Let $r_{q}(\bm{\gamma})$ be the _probability ratio_ given by

$r_{q}(\bm{\gamma})=\frac{m(\bm{\gamma})}{q(\bm{\gamma})},$

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

$D_{f}=\sum_{\bm{\gamma}\in\mathcal{S}(M)}m(\bm{\gamma})\log{r_{q}(\bm{\gamma})}\quad\text{and}\quad\sum_{\bm{\gamma}\in\mathcal{S}(M)}{\hat{q}(\bm{\gamma})\hat{r}_{q}(\bm{\gamma})}=1~{},$

where $\mathcal{S}(M)$ is the support of $\bm{\gamma}_{ab}$ given $g_{ab}=1$.
This set-up allows $\mathcal{S}(M)$ to be a subset of $\mathcal{S}$, where
$\mathcal{S}$ is the support of all possible $\bm{\gamma}_{ab}$. It follows
that, based on the IID sample $\bm{\gamma}_{M}$ of size $n_{M}=|M|$, the
objective function to be _minimized_ for $r_{q}$ can be given by

$Q_{f}=\sum_{(a,b)\in
M}\frac{f(\bm{\gamma}_{ab})}{n_{M}(\bm{\gamma}_{ab})}{r_{q}(\bm{\gamma}_{ab})}-\frac{1}{n_{M}}\sum_{(a,b)\in
M}\log{r_{q}(\bm{\gamma}_{ab})},$ (3)

where $n_{M}(\bm{\gamma}_{ab})=\sum_{(i,j)\in
M}\mathbb{I}(\bm{\gamma}_{ij}=\bm{\gamma}_{ab})$ based on the observed support
$\mathcal{S}(M)$.

#### Probability ratio (II)

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

$r(\bm{\gamma})=\frac{m(\bm{\gamma})}{u(\bm{\gamma})}$

where $u(\bm{\gamma})$ is the probability of $\bm{\gamma}_{ab}=\bm{\gamma}$
given $g_{ab}=0$. We have

${r_{q}(\bm{\gamma})}=\frac{m(\bm{\gamma})}{{q(\bm{\gamma})}}=\frac{m(\bm{\gamma})}{\pi
m(\bm{\gamma})+(1-\pi)u(\bm{\gamma})}=\frac{r(\bm{\gamma})}{\pi\big{(}r(\bm{\gamma})-1\big{)}+1}$

where ${q(\bm{\gamma})}=\pi m(\bm{\gamma})+(1-\pi)u(\bm{\gamma})$, so that
${r_{q}(\bm{\gamma})}$ and $r(\bm{\gamma})$ are one-to-one. Meanwhile, the KL
divergence measure from $u(\bm{\gamma})$ to $m(\bm{\gamma})$ is given by

$D=\sum_{\bm{\gamma}\in\mathcal{S}(M)}m(\bm{\gamma})\log r(\bm{\gamma})$

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

$\displaystyle Q=\sum_{(a,b)\in
M}\frac{u(\bm{\gamma}_{ab})}{n_{M}(\bm{\gamma}_{ab})}r(\bm{\gamma}_{ab})-\frac{1}{n_{M}}\sum_{(a,b)\in
M}\log r(\bm{\gamma}_{ab}).$ (4)

####  Models of $\bm{\gamma}$:

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

For $\bm{\gamma}$ made up of $K$ binary agreement indicators, $\gamma_{k}=0,1$
for $k=1,\ldots,K$, there are up to $2^{K}$ distinct levels of $\bm{\gamma}$,
which can sometimes be relatively large compared to $|M|$. A more parsimonious
model of $m(\bm{\gamma};\bm{\theta})$ that is commonly used is given by

$m(\bm{\gamma};\bm{\theta})=\prod_{k=1}^{K}\theta_{k}^{\gamma_{k}}(1-\theta_{k})^{1-\gamma_{k}}$
(5)

where $\theta_{k}=\mbox{Pr}(\gamma_{ab,k}=1|g_{ab}=1)$, and $\gamma_{ab,k}$ is
the $k$-th component of $\bm{\gamma}_{ab}$. It is possible to model
$\theta_{k}$ based on the distributions of the key variables that give rise to
$\bm{\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(\bm{\gamma};\bm{\xi})$ can be modeled as in (5) with parameters
$\xi_{k}$ instead of $\theta_{k}$, where $\xi_{k}=Pr(\gamma_{ab,k}=1\mid
g_{ab}=0)$.

Note that (5) 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 et
al. (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 $\hat{M}$, consists of
record pairs from $\Omega$, where any record in $A$ or $B$ appears at most in
one record pair in $\hat{M}$. Let the _entropy_ of a classification set
$\hat{M}$ be given by

$\displaystyle D_{\hat{M}}=\frac{1}{|\hat{M}|}\sum_{(a,b)\in\hat{M}}\log
r(\bm{\gamma}_{ab})$ (6)

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

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(\bm{\gamma}_{ab})=\max_{\bm{\gamma}}r(\bm{\gamma})$ for every $(a,b)$ 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
$\hat{M}$, we consider two types of errors. First, we define the _false link
rate (FLR)_ among the links in $\hat{M}$ to be

$\psi=\frac{1}{|\hat{M}|}\sum_{(a,b)\in\hat{M}}(1-g_{ab})$ (7)

which is different to $\mu$ by (1) where the denominator is $|U|$. Second, the
_missing match rate (MMR)_ of $\hat{M}$, which is related to the false non-
link probability $\lambda$ in (1), is given by

$\tau=1-\frac{1}{n_{M}}\sum_{(a,b)\in\hat{M}}g_{ab}.$ (8)

While $\mu$ and $\lambda$ in (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(\bm{\gamma})$, 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(\bm{\gamma})=\sum_{(a,b)\in\Omega}\mathbb{I}(\bm{\gamma}_{ab}=\bm{\gamma})$.
One can obtain $n_{M}$ as the solution to the following fixed-point equation:

$n_{M}=\sum_{(a,b)\in\Omega}\hat{g}(\bm{\gamma}_{ab})=\sum_{\gamma\in\mathcal{S}}n(\bm{\gamma})\hat{g}(\bm{\gamma})$
(9)

where

$\hat{g}(\bm{\gamma}):=\mbox{Pr}(g_{ab}=1|\bm{\gamma}_{ab}=\bm{\gamma})=\frac{\pi
r(\bm{\gamma})}{\pi\big{(}r(\bm{\gamma})-1\big{)}+1}=\frac{n_{M}r(\bm{\gamma})}{n_{M}\big{(}r(\bm{\gamma})-1\big{)}+n}$
(10)

and the probability is defined with respect to completely random sampling of a
single record pair from $\Omega$. To see that $\hat{g}(\bm{\gamma})$ by (10)
satisfies (9), notice
$\hat{g}(\bm{\gamma})=n_{M}m(\bm{\gamma})/n(\bm{\gamma})$ satisfies (9) for
any well defined $m(\bm{\gamma})$, and $n(\bm{\gamma})/n=\pi
m(\bm{\gamma})+(1-\pi)u(\bm{\gamma})$ 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 $\bm{\gamma}$ over $M$, giving rise
to $\hat{\theta}_{k}=n_{M}(1;k)/n_{M}$, where $n_{M}(1;k)$ is the number of
agreements on the $k$-th key variable over $M$. The perfect MEC set $\hat{M}$
should have these agreement rates. We have then, for $k=1,...,K$,

$\hat{\theta}_{k}=\frac{1}{|\hat{M}|}\sum_{(a,b)\in\hat{M}}\mathbb{I}(\gamma_{ab,k}=1)\qquad\text{for}\quad|\hat{M}|=n_{M}.$
(11)

Thus, no matter how one models $m(\bm{\gamma})$, the perfect MEC set should
satisfy jointly the $K+1$ equations defined by (9) and (11), given the
knowledge of $r(\bm{\gamma})$.

##  4 MEC for unsupervised record linkage

Let $\bm{z}$ be the $K$-vector of key variables, which may be imperfect for
two reasons: it is not rich enough if the true $\bm{z}$-values are not unique
for each distinct entity underlying the two files to be linked, or it may be
subjected to errors if the observed $\bm{z}$ is not equal to its true value.
Let $A$ contain only the distinct $\bm{z}$-vectors from the first file, after
removing any other record that has a duplicated $\bm{z}$-vector to some record
that is retained in $A$. In other words, if the first file initially contains
two or more records with exactly the same value of the combined key, then only
one of them will be retained in $A$ for record linkage to the second file.
Similarly let $B$ contain the unique records from the second file. The reason
for _separate deduplication of keys_ is that no comparisons between the two
files can distinguish among the duplicated $\bm{z}$ in either file, which is
an issue to be resolved otherwise.

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 (7) and MMR (8), an
estimate of $n_{M}$ is also needed.

###  4.1 Algorithm of unsupervised MEC

The idea now is to apply (9) and (11) jointly. Since setting
$\hat{n}_{M}=|M_{1}|$ and $\hat{\theta}_{k}\equiv 1$ associated with the
maximal MEC set satisfies (9) and (11) automatically, probabilistic linkage
requires one to assume $n_{M}>|M_{1}|$ and $\theta_{k}<1$ for at least some of
$k=1,...,K$. Moreover, unless there is external information that dictates it
otherwise, one can only assume common support $\mathcal{S}(M)=\mathcal{S}(U)$
in the unsupervised setting. Let

$r(\bm{\gamma})=m(\bm{\gamma};\bm{\theta})/u(\bm{\gamma};\bm{\xi})$ (12)

where the probability of observing $\bm{\gamma}$ is
$m(\bm{\gamma};\bm{\theta})$ by (5) given that a randomly selected record pair
from $\Omega$ belongs to $M$, and $u(\bm{\gamma};\bm{\xi})$ otherwise,
similarly given by (5) with parameters $\xi_{k}$ instead of $\theta_{k}$. An
iterative algorithm of unsupervised MEC is given below.

  * I.

Set $\bm{\theta}^{(0)}=(\theta_{1}^{(0)},\ldots,\theta_{K}^{(0)})$ and
$n_{M}^{(0)}=|M_{1}|$, where $M_{1}$ is the maximal MEC set.

  * II.

For the $t$-th iteration, let ${g}_{ab}^{(t)}=1$ if $(a,b)\in M^{(t)}$, and 0
otherwise.

    * i.

Update $u(\bm{\gamma};\bm{\xi}^{(t)})$ by using (15), which is discussed
below, given $\mathbf{g}^{(t)}=\\{g_{ab}^{(t)}:(a,b)\in\Omega\\}$, and
calculate

$\displaystyle\theta_{k}^{(t)}$ $\displaystyle=$
$\displaystyle\frac{1}{|M^{(t)}|}\sum_{(a,b)\in\Omega}{g}_{ab}^{(t)}\mathbb{I}(\gamma_{ab,k}=1),$
(13)

which maximize $D_{M}$ in (6) for given
$u(\bm{\gamma};\bm{\xi}^{(t)}),M^{(t)}=\\{(a,b)\in\Omega:{g}_{ab}^{(t)}=1\\}$
and $|M^{(t)}|=\sum_{(a,b)\in\Omega}{g}_{ab}^{(t)}$. Once $\bm{\theta}^{(t)}$
and $\bm{\xi}^{(t)}$ are obtained, we can update
$n_{M}^{(t)}=\sum_{\bm{\gamma}}n(\bm{\gamma})\hat{g}^{(t)}(\bm{\gamma})$,
where

$\displaystyle\hat{g}^{(t)}(\bm{\gamma})\equiv\hat{g}(\bm{\gamma};\bm{\theta}^{(t)},\bm{\xi}^{(t)})=\min\Big{\\{}\frac{|M^{(t)}|r^{(t)}(\bm{\gamma})}{|M^{(t)}|\big{(}r^{(t)}(\bm{\gamma})-1\big{)}+n},~{}1\Big{\\}}$
$\displaystyle r^{(t)}(\bm{\gamma})\equiv
r(\bm{\gamma};\bm{\theta}^{(t)},\bm{\xi}^{(t)})=\frac{m(\bm{\gamma};\bm{\theta}^{(t)})}{u(\bm{\gamma};\bm{\xi}^{(t)})}.$

    * ii.

For given $\bm{\theta}^{(t)},\bm{\xi}^{(t)}$ and $n_{M}^{(t)}$, we find the
MEC set $M^{(t+1)}=\\{(a,b)\in\Omega:g_{ab}^{(t+1)}=1\\}$ such that
$|M^{(t+1)}|=n_{M}^{(t)}$ by deduplication in the descending order of
$r^{(t)}(\bm{\gamma}_{ab})$ over $\Omega$. It maximizes the entropy denoted by
$Q^{(t)}(\mathbf{g})$:

$\displaystyle Q^{(t)}(\mathbf{g})\equiv Q(\mathbf{g}\mid\bm{\psi}^{(t)})$
$\displaystyle=$
$\displaystyle\frac{1}{n_{M}^{(t)}}\sum_{(a,b)\in\Omega}{g}_{ab}\log
r^{(t)}(\bm{\gamma}_{ab}),$ (14)

with respect to $\mathbf{g}$.

    * III.

Iterate until $n_{M}^{(t)}=n_{M}^{(t+1)}$ or
$\|\bm{\theta}^{(t)}-\bm{\theta}^{(t+1)}\|<\epsilon$, where $\epsilon$ is a
small positive value.

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

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

$\hat{{\xi}}_{k}=\frac{1}{n}\sum_{(a,b)\in\Omega}\mathbb{I}(\gamma_{ab,k}=1)$
(15)

under the model (5) of $u(\bm{\gamma};\bm{\xi})$, in which case there is no
updating of $u(\bm{\gamma};\bm{\xi}^{(t)})$. Other possibilities of estimating
$u(\bm{\gamma};\bm{\xi})$ will be discussed in Section 5.2.

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

Table 1: MEC for record linkage in supervised or unsupervised setting | Supervised | Unsupervised
---|---|---
$\Omega=M\cup U$ | Observed | Unobserved
Probability ratio |  $r_{f}(\bm{\gamma})$ generally applicable |  $r(\bm{\gamma})$ generally
$r(\bm{\gamma})$ given $\mathcal{S}(M)\subseteq\mathcal{S}(U)$ | assuming $\mathcal{S}(M)=\mathcal{S}(U)$
Model of $\bm{\gamma}$ | Multinomial if only discrete comparison scores
Directly or via key variables and measurement errors
MEC set | Guided by FLR and MMR
Require estimate of $n_{M}$ in addition
Estimation |  $m(\bm{\gamma};\bm{\theta})$ from $\bm{\gamma}_{M}$ in $\Omega$ |  $m(\bm{\gamma};\bm{\theta})$ and $n_{M}$
$n_{M}$ by (9) outside $\Omega$ | jointly by (9) and (11)

###  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 $\\{\hat{g}_{ab}:(a,b)\in\hat{M}\\}$ of any MEC set $\hat{M}$ are
among the largest ones over $\Omega$, because MEC follows the descending order
of $\hat{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
$\hat{M}(c_{\psi})$, where $\hat{r}_{ab}\geq c_{\psi}$ for any
$(a,b)\in\hat{M}(c_{\psi})$.

  * ii.

Calculate the estimated FLR of the resulting MEC set $\hat{M}$ as

$\hat{\psi}=\frac{1}{|\hat{M}|}\sum_{(a,b)\in\hat{M}}(1-\hat{g}_{ab}).$ (16)

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

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

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

$\hat{\tau}=1-\sum_{(a,b)\in\hat{M}}\hat{g}_{ab}/\hat{n}_{M}$ (17)

where $\hat{n}_{M}$ is given by unsupervised MEC algorithm. Note that if
$|\hat{M}|=\hat{n}_{M}$, then we shall have $\hat{\psi}=\hat{\tau}$; but not
if $\hat{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.

##  5 Discussion

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 Appendix C.

###  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
$\hat{r}(\bm{\gamma}_{ab})$ is above a threshold value for all $(a,b)\in
M^{*}$. As “an advance over previous ad hoc assignment methods”, Jaro (1989)
chooses the linked set $\hat{M}^{*}\subseteq M^{*}$, which maximises the sum
of $\log\hat{r}(\bm{\gamma}_{ab})$ subject to the constraint of one-one link.
Since $\hat{g}_{ab}$ is a monotonic function of $\hat{r}(\bm{\gamma}_{ab})$,
this amounts to choose $\hat{M}^{*}$ which maximises the expected number of
matches in it, denoted by

$n_{M}^{*}=\sum_{(a,b)\in\hat{M}^{*}}\hat{g}_{ab}$

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

Consider linking two files with 100 records each. Suppose Jaro’s assignment
method yields $|\hat{M}^{*}|=100$ on one occasion, where 80 links have
$\hat{g}_{ab}\approx 1$ and 20 links have $\hat{g}_{ab}\approx 0.75$, such
that $n_{M}^{*}\approx 95$. Suppose it yields 90 links with
$\hat{g}_{ab}\approx 1$ and 10 links with $\hat{g}_{ab}\approx 0.5$ on another
occasion, where $n_{M}^{*}\approx 95$. Clearly, $n_{M}^{*}$ does not directly
control the linkage errors in $\hat{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 (16) and MMR in (17) 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) 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 (5) and the same estimator of
$u(\bm{\gamma};\bm{\xi})$ via $\hat{\xi}_{k}$ given by (15). It is then clear
that the same formula is used for updating $n_{M}^{(t)}$ at each iteration,
but a different formula is used for

$\theta_{k}^{(t)}=\frac{1}{{n}_{M}^{(t)}}\sum_{(a,b)\in\Omega}\hat{g}_{ab}^{(t)}\gamma_{ab,k}$
(18)

where the numerator is derived from _all_ the pairs in $\Omega$, whereas
$\theta_{k}^{(t)}$ given by (13) uses only the pairs in the MEC set $M^{(t)}$.
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 $\hat{g}_{ab}$.

Thus, one may incorporate the WJ-procedure as a variation of the unsupervised
MEC algorithm, where the formulae (18) and (15) 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 (13) and (18) for
$\theta_{k}^{(t)}$.

###  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 (15). This
requires a model of the key variables, which explicates the assumptions of
key-variable errors. Let $z_{k}$ be the $k$-th key variable which takes value
$1,...,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 $(a,b)\in M$, let $\alpha_{k}=\mbox{Pr}(e_{ab,k}=1)$, where $e_{ab,k}=1$
if the associated pair of key variables are subjected to _any form of
perturbation_ that could potentially cause disagreement of the $k$-th key
variable, and $e_{ab,k}=0$ otherwise. Let

$\displaystyle\theta_{k}=(1-\alpha_{k})+\alpha_{k}\sum_{d=1}^{D_{k}}m_{kd}^{2}=1-\alpha_{k}(1-\sum_{d=1}^{D_{k}}m_{kd}^{2})$

where we assume that $\alpha_{k}$ must be positive for some $k=1,...,K$, and

$m_{kd}=\mbox{Pr}(z_{ik}=d|g_{ab}=1,e_{ab,k}=1)=\mbox{Pr}(z_{ik}=d|g_{ab}=1,e_{ab,k}=0)$

for $i=a$ or $b$. Next, for any record $i$ in either $A$ or $B$, let
$\delta_{i}=1$ if it has a match in the other file and $\delta_{i}=0$
otherwise. Given $\delta_{i}=0$, with or without perturbation, let
$\mbox{Pr}(z_{ik}=d|\delta_{i}=0)=u_{kd}$. We have $\beta_{kd}:=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}=0$ in the _larger_ file. Suppose
$n_{A}<n_{B}$. Let

$p=\mbox{Pr}(\delta_{b}=1)=E(n_{M})/n_{B}=n_{A}\pi$

be the probability that a record in $B$ has a match in $A$. One may assume
$\bm{z}_{A}=\\{\bm{z}_{a}:a\in A\\}$ to be independent over $A$, giving

$\ell_{A}=\sum_{a\in A}\sum_{k=1}^{K}\log m_{ak}$

where $m_{ak}=\sum_{d=1}^{D_{k}}m_{kd}\mathbb{I}(z_{ak}=d)$. The complete-data
log-likelihood based on $(\delta_{B},\bm{z}_{B})$ is

$\ell_{B}=\sum_{b\in
B}\delta_{b}\log\Big{(}p\prod_{k=1}^{K}m_{bk}\Big{)}+\sum_{b\in
B}(1-\delta_{b})\log\Big{(}(1-p)\prod_{k=1}^{K}u_{bk}\Big{)}$ (19)

where $m_{bk}=\sum_{d=1}^{D_{k}}m_{kd}\mathbb{I}(z_{bk}=d)$ and
$u_{bk}=\sum_{d=1}^{D_{k}}u_{kd}\mathbb{I}(z_{bk}=d)$, based on an assumption
of independent $(\delta_{b},\bm{z}_{b})$ across the entities in $B$.

Under separate modelling of $\bm{z}_{A}$ and $(\bm{z}_{B},\delta_{B})$, let
$\hat{m}_{kd}$ be the MLE based on $\ell_{A}$, given which an EM-algorithm for
estimating $p$ and $u_{kd}$ follows from (19) by treating $\delta_{B}$ as the
missing data. However, the estimation is feasible only if $\\{u_{kd}\\}$ and
$\\{m_{kd}\\}$ are not exactly the same; whereas the MLE of $n_{M}$ has a
large variance, when $\\{m_{kd}\\}$ and $\\{u_{kd}\\}$ are close to each
other, even if they are not exactly equal.

Meanwhile, the closeness between $\\{m_{kd}\\}$ and $\\{u_{kd}\\}$ does not
affect the MEC approach, where $\hat{n}_{M}$ is obtained from solving (9)
given $\hat{r}(\bm{\gamma})=\hat{m}(\bm{\gamma})/\hat{u}(\bm{\gamma})$, where
$\hat{u}(\bm{\gamma})$ is indeed most reliably estimated when
$\\{m_{kd}\\}=\\{u_{kd}\\}$. Moreover, one can incorporate a _profile EM-
algorithm_ , based on (19) given $n_{M}^{(t)}$, to update
$u(\bm{\gamma};\bm{\xi}^{(t)})$ in the unsupervised MEC algorithm of Section
4.1. At the $t$-th iteration, where $t\geq 1$, given
$p^{(t)}=n_{M}^{(t)}/\max(n_{A},n_{B})$ and $\hat{m}_{kd}$ estimated from the
smaller file $A$, obtain $u_{kd}^{(t)}$ by

${\xi}_{k}^{(t)}=\Big{(}(1-p^{(t)})\sum_{d=1}^{D_{k}}u_{kd}^{(t)}\hat{m}_{kd}+p^{(t)}(1-\frac{1}{n_{A}})\sum_{d=1}^{D_{k}}\hat{m}_{kd}^{2}\Big{)}/\big{(}1-p^{(t)}/n_{A}\big{)}.$
(20)

##  6 Simulation Study

###  6.1 Set-up

To explore the practical feasibility of the unsupervised MEC algorithm for
record linkage, we conduct a simulation study based on the data sets listed in
Table 2, which are disseminated by ESSnet-DI (McLeod et al., 2011) and freely
available online. Each record in a data set has associated synthetic key
variables, which may be distorted by missing values and typos when they are
created, in ways that imitate real-life errors (McLeod et al., 2011).

Table 2: Data set description (size in parentheses) Data set | Description
---|---
Census | A fictional data set to represent some observations
$(25,343)$ | from a decennial Census
CIS | Fictional observations from Customer Information System,
$(24,613)$ | combined administrative data from the tax and benefit systems
PRD | Fictional observations from Patient Register Data
$(24,750)$ | of the National Health Service

We consider the linkage keys forename, surname, sex, and date of birth (DOB).
To model the key variables, we divide DOB into 3 key variables (Day, Month,
Year). For text variables such as forename and surname, we divide them into 4
key variables by using the Soundex coding algorithm (Copas and Hilton, 1990,
p. 290), which reduces a name to a code consisting of the leading letter
followed by three digits, e.g. Copas $\equiv$ C120, Hilton $\equiv$ H435. The
twelve key variables for record linkage are presented in Table 3.

Table 3: Twelve key variables available in the three data sets. Variable | Description | No. of Categories
---|---|---
PERNAME1 | 1 | First letter of forename | 26
2 | First digit of Soundex code of forename | 7
3 | Second digit of Soundex code of forename | 7
4 | Third digit of Soundex code of forename | 7
PERNAME2 | 1 | First letter of surname | 26
2 | First digit of Soundex code of surname | 7
3 | Second digit of Soundex code of surname | 7
4 | Third digit of Soundex code of surname | 7
SEX | Male / Female | 2
DOB | DAY | Day of birth | 31
MON | Month of birth | 12
YEAR | Year of birth (1910 $\sim$ 2012) | 103

We set up two scenarios to generate linkage files. We use the unique
identification variable (PERSON-ID) for sampling, which are available in all
the three data sets. We sample $n_{A}=500$ and $n_{B}=1000$ individuals from
PRD and CIS, respectively. Let $p_{A}$ be the proportion of records in the
smaller file (PRD) that are also selected in the larger file (CIS), by which
we can vary the degree of overlap, i.e. the set of matched individuals $AB$,
between $A$ and $B$. We use $p_{A}=0.8,0.5$ or $0.3$ under either scenario.

#### Scenario-I (Non-informative)

  * •

Sample $n_{0}=n_{B}/p_{A}$ individuals randomly from Census.

  * •

Sample $n_{A}$ randomly from these $n_{0}$ as the individuals of PRD, denoted
by $A$.

  * •

Sample $n_{B}$ randomly from these $n_{0}$ as the individuals of CIS, denoted
by $B$.

Under this scenario both $\delta_{a}$ and $\delta_{b}$ are non-informative for
the key-variable distribution. For any given $p_{A}$, we have
$E(n_{M})=n_{A}p_{A}$ and $\pi=E(n_{M})/n_{0}$, where $n_{M}$ is the random
number of matched individuals between the simulated files $A$ and $B$.

#### Scenario-II (Informative)

  * •

Sample $n_{A}$ randomly from Census $\cap$ PRD $\cap$ CIS, denoted by $A$ from
PRD.

  * •

Sample $n_{M}=n_{A}p_{A}$ randomly from $A$ as the matched individuals,
denoted by $AB$.

  * •

Sample $n_{B}-n_{M}$ randomly from CIS $\setminus$ A having $\mathrm{SEX}=F$,
$\mathrm{YEAR}\leq 1970$, and odd $\mathrm{MON}$, denoted by $B_{0}$. Let
$B=AB\cup B_{0}$ be the sampled individuals of CIS.

Under this scenario the key-variable distribution is the same in $A$, whether
or not $\delta_{a}=1$, but it is different for the records $b\in B_{0}$, or
$\delta_{b}=0$. Hence, scenario-II is informative. For any given $p_{A}$, we
have fixed $n_{M}=n_{A}p_{A}$ and $\pi=p_{A}/n_{B}$.

###  6.2 Results: Estimation

For the unsupervised MEC algorithm given in Section 4.1, one can adopt (13) or
(18) for updating $\theta_{k}^{(t)}$. Moreover, one can use (15) for
$\hat{\xi}_{k}$ directly, or (20) for updating $\xi_{k}^{(t)}$ iteratively. In
particular, choosing (18) and (15) effectively incorporates the procedure of
Winkler (1988) and Jaro (1989) for parameter estimation. Note that the MEC
approach still differs to that of Jaro (1989), with respect to the formation
of the linked set $\hat{M}$.

Table 4 compares the performance of the unsupervised MEC algorithm, using
different formulae for $\theta_{k}^{(t)}$ and $\xi_{k}^{(t)}$, where the size
of $\hat{M}$ is equal to the corresponding estimate $\hat{n}_{M}$. In
addition, we include $\hat{\theta}_{k}=n_{M}(1;k)/n_{M}$ estimated directly
from the matched pairs in $M$, as if $M$ were available for supervised
learning, together with (15) for $\hat{\xi}_{k}$. The true parameters and
error rates are given in addition to their estimates.

Table 4: Parameters and averages of their estimates, averages of error rates
and their estimates, over 200 simulations. Median of estimate of $n_{M}$ given
as $\tilde{n}_{M}$. Scenario I
---
Parameter | Formulae | Estimation
$\pi$ | $E(n_{M})$ | $\theta_{k}^{(t)}$ | $\xi_{k}^{(t)}$ | $\hat{\pi}$ | $\hat{n}_{M}$ | $\tilde{n}_{M}$ | FLR | MMR | $\widehat{\mbox{FLR}}$ | $\widehat{\mbox{MMR}}$
.0008 | 400 | $\hat{\theta}_{k}$ | (15) | .00080 | 400.0 | 397 | .0264 | .0266 | .0357 | .0357
(13) | (20) | .00082 | 407.9 | 405 | .0425 | .0257 | .0509 | .0509
(13) | (15) | .00083 | 414.7 | 407 | .0549 | .0244 | .0620 | .0620
(18) | (15) | .00081 | 406.0 | 405 | .0399 | .0269 | .0503 | .0503
.0005 | 250 | $\hat{\theta}_{k}$ | (15) | .00050 | 251.6 | 249 | .0340 | .0301 | .0370 | .0370
(13) | (20) | .00052 | 258.3 | 255 | .0559 | .0296 | .0533 | .0533
(13) | (15) | .00053 | 266.9 | 256.5 | .0742 | .0277 | .0680 | .0680
(18) | (15) | .00052 | 261.7 | 259 | .0676 | .0305 | .0636 | .0636
.0003 | 150 | $\hat{\theta}_{k}$ | (15) | .00030 | 152.3 | 151 | .0439 | .0356 | .0381 | .0381
(13) | (20) | .00033 | 165.9 | 156.5 | .0873 | .0244 | .0620 | .0620
(13) | (15) | .00041 | 205.4 | 161 | .1632 | .0308 | .1251 | .1251
(18) | (15) | .00054 | 271.4 | 169 | .3015 | .0785 | .1639 | .1639
Scenario II |
Parameter | Formulae | Estimation
$\pi$ | $n_{M}$ | $\theta_{k}^{(t)}$ | $\xi_{k}^{(t)}$ | $\hat{\pi}$ | $\hat{n}_{M}$ | $\tilde{n}_{M}$ | FLR | MMR | $\widehat{\mbox{FLR}}$ | $\widehat{\mbox{MMR}}$
.0008 | 400 | $\hat{\theta}_{k}$ | (15) | .00080 | 398.3 | 400 | .0230 | .0273 | .0326 | .0326
(13) | (20) | .00080 | 401.4 | 401 | .0305 | .0277 | .0403 | .0403
(13) | (15) | .00081 | 405.2 | 404 | .0379 | .0262 | .0467 | .0467
(18) | (15) | .00080 | 401.4 | 401 | .0316 | .0286 | .0438 | .0438
.0005 | 250 | $\hat{\theta}_{k}$ | (15) | .00050 | 249.6 | 250 | .0284 | .0302 | .0334 | .0334
(13) | (20) | .00050 | 251.8 | 251 | .0383 | .0320 | .0410 | .0410
(13) | (15) | .00052 | 257.7 | 253 | .0513 | .0295 | .0516 | .0516
(18) | (15) | .00051 | 255.4 | 253.5 | .0510 | .0336 | .0520 | .0520
.0003 | 150 | $\hat{\theta}_{k}$ | (15) | .00030 | 150.5 | 150 | .0382 | .0355 | .0350 | .0350
(13) | (20) | .00031 | 153.0 | 153 | .0559 | .0377 | .0452 | .0452
(13) | (15) | .00032 | 158.5 | 155 | .0708 | .0342 | .0558 | .0558
(18) | (15) | .00038 | 189.3 | 156 | .1414 | .0524 | .0903 | .0903

As expected, the best results are obtained when the parameter $\theta_{k}$ is
estimated directly from the matched pairs in $M$, i.e.,
$\hat{\theta}_{k}=n_{M}(1;k)/n_{M}$, together with (15) for $\hat{\xi}_{k}$,
despite $\hat{\xi}_{k}$ by (15) is not exactly unbiased. Nevertheless, the
approximate estimator $\hat{\xi}_{k}$ can be improved, since the profile-EM
estimator given by (20) is seen to perform better across all the set-ups,
where both are combined with (13) for $\theta_{k}^{(t)}$. When it comes to the
two formulae of $\theta_{k}^{(t)}$ by (13) and (18), and the resulting
$n_{M}$-estimators and the error rates FLR and MMR, we notice the followings.

  * •

Scenario-I: When the size of the matched set $M$ is relatively large at
$p_{A}=0.8$ , there are only small differences in terms of the average and
median of the two estimators of $n_{M}$, and the difference is just a couple
of false links in terms of the linkage errors. Figures 1 shows that (13)
results in a few larger errors of $\hat{n}_{M}$ than (18) over the 200
simulations, when $p_{A}=0.8$ or $\pi=0.0008$. As the size of the matched set
$M$ decreases, the averages and medians of the estimators of $n_{M}$ resulting
from (13) and (20) are closer to the true values than those of the other
estimators. Especially when the matched set $M$ is relatively small, where
$\pi=0.0003$, the formula (18) results in considerably worse estimation of
$n_{M}$ in every respect. While this is partly due to the use of (15) instead
of (20), most of the difference is down to the choice of $\theta_{k}^{(t)}$,
which can be seen from intermediary comparisons to the results based on (13)
and (15).

  * •

Scenario-II: The use of (13) and (20) for the unsupervised MEC algorithm
performs better than using the other formulae in terms of both estimation of
$n_{M}$ and error rates across the three sizes of the matched set (Figure 2).
Relatively greater improvement is achieved by using (13) and (20) for the
smaller matched sets.

Figure 1: Box plots of $\hat{n}_{M}-n_{M}$ based on 200 Monte Carlo samples
under Scenario I.  Figure 2: Box plots of $\hat{n}_{M}-n_{M}$ based on 200
Monte Carlo samples under Scenario II.

The results suggest that the unsupervised MEC algorithm tends to be more
affected by the size of the matched set under Scenario-I than Scenario-II.
Choosing (13) and (20), however, seems to yield the most robust estimation of
$n_{M}$ and error rates against the small size of the matched set $M$,
regardless the informativeness of key-variable errors. The reason must be the
fact that the numerator of $\theta_{k}^{(t)}$ is calculated in (18) over all
the pairs in $\Omega$ instead of the MEC set $M^{(t)}$, which seems more
sensitive when the imbalance between $M$ and $U$ is aggravated, while the
sizes of $A$ and $B$ remain fixed.

We also include the additional results obtained for $p_{A}=0.2,0.15,$ and
$0.1$ in Appendix D. The estimate $\hat{n}_{M}$ (or $\hat{\pi}$) gets worse as
$p_{A}$ (or $\pi$) reduces, which is consistent with the previous findings of
others, for example, Enamorado et al. (2019) showed that a greater degree of
overlap between data sets leads to better merging results in terms of the
error rates as well as the accuracy of their estimates. The problem is also
highlighted by Sadinle (2017). Record linkage in cases of extremely low
prevalence of true matches is a problem that needs to be studied more
carefully on its own.

###  6.3 Results: MEC set

Aiming the MEC set $\hat{M}$ at the estimated size $\hat{n}_{M}$ is generally
not a reasonable approach to record linkage. Record linkage should be guided
directly by the associated uncertainty, i.e. the error rates FLR and MMR,
based on their estimates (16) and (17), as described in Section 4.2. Note that
this does require the estimation of $n_{M}$ in addition to $r(\bm{\gamma})$.

We have $\widehat{\mbox{FLR}}=\widehat{\mbox{MMR}}$ in Table 4, because
$|\hat{M}|=\hat{n}_{M}$ here. It can be seen that these follow the true FLR
more closely than the MMR, especially when $\hat{n}_{M}$ is estimated using
the formulae (13) and (20). This is hardly surprising. Take e.g. the maximal
MEC set $M_{1}$ that consists of the pairs whose key variables agree
completely and uniquely. Provided reasonably rich key variables, as the
setting here, one can expect the FLR of $M_{1}$ to be low, such that even a
naïve estimate $\widehat{\mbox{FLR}}=0$ probably does not err much. Meanwhile,
the true MMR has a much wider range from one application to another, because
the difference between $n_{M}$ and $|M_{1}|$ is determined by the extent of
key-variable errors, such that the estimate of MMR depends more critically on
that of $n_{M}$. The situation is similar for any MEC set beyond $M_{1}$, as
long as $\hat{g}_{ab}$ remains very high for any $(a,b)\in\hat{M}$.

Table 5: Parameters and averages of their estimates, averages of error rates and their estimates, over 200 simulations, $n=|\Omega|=n_{A}n_{B}$. Scenario I |
---|---
Parameter | Target | Estimation
$\pi$ | $E(n_{M})$ | FLR | $\hat{n}_{M}$ | $|\hat{M}|/n$ | $|\hat{M}|$ | FLR | MMR | $\widehat{\mbox{FLR}}$ | $\widehat{\mbox{MMR}}$
.0008 | 400 | 0.05 | 407.9 | .00080 | 401.9 | .0313 | .0280 | .0393 | .0527
0.03 | .00079 | 395.0 | .0196 | .0328 | .0271 | .0568
.0005 | 250 | 0.05 | 258.3 | .00050 | 251.9 | .0396 | .0326 | .0385 | .0576
0.03 | .00049 | 246.7 | .0246 | .0374 | .0264 | .0650
.0003 | 150 | 0.05 | 165.9 | .00031 | 153.4 | .0533 | .0403 | .0389 | .0783
0.03 | .00030 | 149.3 | .0355 | .0483 | .0256 | .0905
Scenario II |
Parameter | Target | Estimation
$\pi$ | $n_{M}$ | FLR | $\hat{n}_{M}$ | $|\hat{M}|/n$ | $|\hat{M}|$ | FLR | MMR | $\widehat{\mbox{FLR}}$ | $\widehat{\mbox{MMR}}$
.0008 | 400 | 0.05 | 401.4 | .00080 | 397.8 | .0239 | .0294 | .0337 | .0418
0.03 | .00079 | 393.1 | .0164 | .0334 | .0256 | .0451
.0005 | 250 | 0.05 | 251.8 | .00050 | 248.6 | .0305 | .0361 | .0328 | .0447
0.03 | .00049 | 245.2 | .0226 | .0416 | .0245 | .0497
.0003 | 150 | 0.05 | 153.0 | .00030 | 150.1 | .0445 | .0443 | .0333 | .0514
0.03 | .00029 | 147.4 | .0322 | .0489 | .0238 | .0588

Table 5 shows the performance of the MEC set using the bisection procedure
described in Section 4.2, across the same set-ups as in Table 4. We use only
(13) for $\theta_{k}^{(t)}$ and (20) for $\xi_{k}^{(t)}$ to obtain the
corresponding $\hat{n}_{M}$. We let the target FLR be $\psi=0.05$ or 0.03,
where the latter is clearly lower than the true FLR of $\hat{M}$ that is of
the size $\hat{n}_{M}$ (Table 4), especially when the prevalence is relatively
low (at $\pi=0.0003$) under either scenario. The resulting true (FLR, MMR) and
their estimates are given in Table 5.

It can be seen that the MEC algorithm guided by the FLR yields the MEC set
$\hat{M}$, whose size $|\hat{M}|$ is close to the true $n_{M}$ across all the
set-ups. Indeed, under Scenario-I, the mean of $|\hat{M}|$ is closer to
$n_{M}$ than the mean (or median) of $\hat{n}_{M}$ over all the simulations,
which results directly from parameter estimation, especially when the match
set is relatively small (at $\pi=0.0003$) and the performance of $\hat{n}_{M}$
is most sensitive. In other words, the fact that $|\hat{M}|$ differs to the
estimate $\hat{n}_{M}$ is not necessarily a cause of concern for the MEC
algorithm guided by targeting the FLR.

To estimate the MMR by (17), one can either use $|\hat{M}|$ as the estimate of
$n_{M}$, or one can use $\hat{n}_{M}$ from parameter estimation based on (13)
and (20). In the former case, one would obtain
$\widehat{\mbox{MMR}}=\widehat{\mbox{FLR}}$. While this $\widehat{\mbox{MMR}}$
is not unreasonable in absolute terms since $|\hat{M}|$ is close to $n_{M}$
here, as can be seen from comparing the mean of $\widehat{\mbox{FLR}}$ with
that of the true MMR in Table 5, it has a drawback _a priori_ , in that it
decreases as the target FLR decreases, although one is likely to miss out on
more true matches when more links are excluded from the MEC set $\hat{M}$.
Using $\hat{n}_{M}$ from parameter estimation directly makes sense in this
respect, since the true $n_{M}$ must remain the same, regardless the target
FLR. However, the estimator $\widehat{\mbox{MMR}}$ could then become less
reliable given relatively low prevalence $\pi$, where $\hat{n}_{M}$ could be
sensitive in such situations.

In short, the estimation of FLR tends to be more reliable than that of MMR,
especially if the prevalence $\pi$ is relatively low in its theoretical range
$0<\pi\leq\min(n_{A},n_{B})/n$. The following recommendations for unsupervised
record linkage seem warranted.

  * •

When forming the MEC set $\hat{M}$ according to the uncertainty of linkage, it
is more robust to rely on the FLR, estimated by (16).

  * •

The estimate of MMR given by (17), derived from the parameter estimate
$\hat{n}_{M}$ based on (13) and (20) provides an additional uncertainty
measure. However, one should be aware that this measure can be sensitive when
the prevalence $\pi$ is relatively low.

  * •

Between two target values of the FLR, $\psi<\psi^{\prime}$, more attention can
be given to the estimate of additional missing matches in $\hat{M}(\psi)$
compared to $\hat{M}(\psi^{\prime})$, given by

$\sum_{(a,b)\in\hat{M}(\psi^{\prime})}\hat{g}_{ab}-\sum_{(a,b)\in\hat{M}(\psi)}\hat{g}_{ab}=\sum_{(a,b)\in\hat{M}(\psi^{\prime})\setminus\hat{M}(\psi)}\hat{g}_{ab}~{}.$

##  7 Final remarks

We have developed an approach of maximum entropy classification to record
linkage. This provides a unified probabilistic record linkage framework both
in the supervised and unsupervised settings, where a coherent classification
set of links are chosen explicitly with respect to the associated uncertainty.
The theoretical formulation overcomes some persistent flaws of the classical
approaches. Furthermore, the proposed MEC algorithm is fully automatic, unlike
the classical approach that generally requires clerical review to resolve the
undecided cases.

An important issue that is worth further research concerns the estimation of
relevant parameters in the model of key-variable errors that cause problems
for record linkage. First, as pointed out earlier, treating record linkage as
a classification problem allows one to explore many modern machine learning
techniques. A key challenge in this respect is the fact that the different
record pairs are not distinct ‘units’, such that any powerful supervised
learning technique needs to be adapted to the unsupervised setting, where it
is impossible to estimate the relevant parameters based on the true matches
and non-matches, including the number of matched entities. Next, the model of
the key-variable errors or the comparison scores can be refined. Once these
issues are resolved together, further improvements on the parameter estimation
can be hopefully made, which will benefit both the classification of the set
of links and the assessment of the associated uncertainty.

Another issue that is interesting to explore in practice is the various
possible forms of informative key-variable errors, insofar as the model
pertaining to the matched entities in one way or another differs to that of
the unmatched entities. Suitable variations of the MEC approach may need to be
configured in different situations.

ACKNOWLEDGMENTS

The authors thank the associate editor and the reviewers for their
constructive comments. Dr. Kim is partially supported by NSF grant MMS
1733572.

APPENDIX

## A. Convergence property of the proposed algorithm

Theorem 1. Let $\bm{\psi}=\\{\mathbf{g},\bm{\theta},\bm{\xi}\\}$ denote the
model parameters. The entropy of a classification set of $M$ can be re-written
as

$\displaystyle D_{M}\equiv
D(\bm{\psi})=\frac{1}{n_{M}(\bm{\psi})}\sum_{(a,b)\in\Omega}g_{ab}\log
r(\bm{\gamma}_{ab};\bm{\theta}(\bm{\psi}),\bm{\xi}(\bm{\psi})),$

and $n_{M}(\bm{\psi})=\sum_{\bm{\gamma}\in
S}n(\bm{\gamma})\hat{g}(\bm{\gamma};\bm{\psi})$ satisfying the fixed-point
equation (9). Let
$\bm{\psi}^{(t)}=\\{\mathbf{g}^{(t)},\bm{\theta}^{(t)},\bm{\xi}^{(t)}\\}$
denote the current values obtained from the $t$-iteration of the proposed
algorithm. If $Q(\mathbf{g}^{(t+1)}\mid\bm{\psi}^{(t)})\geq
Q(\mathbf{g}^{(t)}\mid\bm{\psi}^{(t)})$ holds, where
$Q(\mathbf{g}\mid\bm{\psi}^{(t)})$ is defined as in (14), then
$D(\bm{\psi}^{(t+1)})\geq D(\bm{\psi}^{(t)})$.

Note that Theorem 1 implies $\\{D^{(t)}\\}$ is monotone increasing, and it is
bounded if $S(M^{(t)})\subset S(U^{(t)})$. Thus, $\\{D(\bm{\psi}^{(t)})\\}$
converges to some value, $D^{\ast}$.

Proof. Let

$Q(\mathbf{g}\mid\bm{\psi}^{\prime})=\frac{1}{n_{M}(\bm{\psi}^{\prime})}\sum_{(a,b)\in\Omega}g_{ab}\log
r(\gamma_{ab};\bm{\psi}^{\prime}).$ $\displaystyle
D(\bm{\psi}^{(t+1)})-D(\bm{\psi}^{(t)})$ $\displaystyle=$ $\displaystyle
D(\bm{\psi}^{(t+1)})-Q(\mathbf{g}^{(t+1)}\mid\bm{\psi}^{(t)})+Q(\mathbf{g}^{(t+1)}\mid\bm{\psi}^{(t)})-D(\bm{\psi}^{(t)})$
$\displaystyle\geq$ $\displaystyle
D(\bm{\psi}^{(t+1)}-Q(\mathbf{g}^{(t+1)}\mid\bm{\psi}^{(t)})$ $\displaystyle=$
$\displaystyle\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}{g}_{ab}^{(t+1)}\left(\log\frac{m^{(t+1)}(\bm{\gamma}_{ab})}{m^{(t)}(\bm{\gamma}_{ab})}+\log\frac{u^{(t)}(\bm{\gamma}_{ab})}{u^{(t+1)}(\bm{\gamma}_{ab})}\right)+$
$\displaystyle\left(1-\frac{n_{M}^{(t+1)}}{n_{M}^{(t)}}\right)\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}\log
r^{(t)}(\bm{\gamma}_{ab})$ $\displaystyle\geq$
$\displaystyle-\log\left\\{\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}\frac{m^{(t)}(\bm{\gamma}_{ab})}{m^{(t+1)}(\bm{\gamma}_{ab})}\right\\}-\log\left\\{\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}\frac{u^{(t+1)}(\bm{\gamma}_{ab})}{u^{(t)}(\bm{\gamma}_{ab})}\right\\}-$
$\displaystyle\left|1-\frac{n_{M}^{(t+1)}}{n_{M}^{(t)}}\right|\frac{1}{n_{M}^{(t+1)}}\log\left\\{\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}\frac{m^{(t)}(\bm{\gamma}_{ab})}{u^{(t)}(\bm{\gamma}_{ab})}\right\\}$
$\displaystyle\geq$
$\displaystyle-\log\left\\{\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}m^{(t)}(\bm{\gamma}_{ab})\right\\}-\log\left\\{\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}u^{(t+1)}(\bm{\gamma}_{ab})\right\\}-$
$\displaystyle\left|1-\frac{n_{M}^{(t+1)}}{n_{M}^{(t)}}\right|\log\left\\{\frac{1}{n_{M}^{(t+1)}}\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}{m^{(t)}(\bm{\gamma}_{ab})}\right\\},$
$\displaystyle\geq$ $\displaystyle 0.$

The first inequality holds because we have
$Q(\mathbf{g}^{(t+1)}\mid\bm{\psi}^{(t)})\geq D(\bm{\psi}^{(t)})$ by the
construction of the $\mathbf{g}^{(t+1)}$. The second inequality holds by
applying the Jensen’s inequality and the condition that
$\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}\log r^{(t)}(\gamma_{ab})>0$, Third
inequality follows from by multiplying the first term by
$m^{(t+1)}(\bm{\gamma})$ and the second and third terms by
$u^{(t)}(\bm{\gamma})$, respectively. Since
$\sum_{(a,b)\in\Omega}g_{ab}^{(t+1)}m^{(t)}(\bm{\gamma})=\sum_{\bm{\gamma}\in
S}n_{M^{(t+1)}}(\bm{\gamma})m^{(t)}(\bm{\gamma})\leq
n_{M}^{(t+1)}\sum_{\bm{\gamma}\in S}m^{(t)}(\bm{\gamma})=n_{M}^{(t+1)}$, the
last inequality holds.

## B. Special cases of MEC sets for record linkage

Consider some special cases, given binary $\mathcal{S}$ where
$|\mathcal{S}|=2$. The Bernoulli model of $m(\gamma)$ has probability
$m(1)=\theta=1-m(0)$ for $\gamma\in\mathcal{S}(M)$, including $\theta=1$ or 0
if $|\mathcal{S}(M)|=1$. Under the Bernoulli model of $f(\gamma)$ in addition,
the normalisation constraint is always satisfied by $\hat{\theta}$ obtained
from maximising $D_{f}$ defined over $M$. Every pair $(a,b)$ in a maximal MEC
set $M_{1}$ must have $\gamma_{ab}=1$. The point we would like to demonstrate
is that generally probabilistic record linkage may be guided by the error
rates, FLR and MMR, without being restricted to the knowledge (or estimate) of
$n_{M}=|M|$.

#### _Case-0_

Suppose one has perfect key variables, such that $\gamma_{ab}=1$ iff $(a,b)\in
M$. Notice that $Q$ by (4) of the main manuscript is not applicable here since
$\mathcal{S}(U)\cap\mathcal{S}(M)=\emptyset$. Using $Q_{f}$ by (3), we have
$D_{f}=n_{M}\log\theta$, which is maximised at $\hat{\theta}=1$, as well as
$S(M)=\\{1\\}$ such that $\hat{\theta}=1$ follows directly from the
normalisation constraint in this case. By (9), we obtain $\hat{g}(1)=1$ since
$r(1)=\infty$, and $\hat{g}(0)=0$ since $r(0)=0$, so that the estimate of
$n_{M}$ by (8) is $n(1)=n_{M}$. The MEC set $\hat{M}$ of size $n_{M}$ is equal
to $M$, which is also the maximal MEC set. Since $\hat{\theta}=1$ and
$\hat{n}_{M}=n_{M}$, both the estimated FLR and MMR are 0.

#### _Case-M_

Suppose $\gamma_{ab}=0$ over $U$, and $\gamma_{ab}=1$ for $n_{M}-d$ pairs in
$M$, while $\gamma_{ab}=0$ for $d$ pairs in $M$ due to key-variable errors.
Again, $Q$ by (4) is not applicable. Using $Q_{f}$ by (3), we have
$D_{f}=(n_{M}-d)\log\theta+d\log(1-\theta)$ and
$\hat{\theta}=(n_{M}-d)/n_{M}$. By (9), we obtain $\hat{g}(1)=1$ again, and
$\hat{g}(0)=d/(n-n_{M}+d)$, so that the estimate of $n_{M}$ by (8) is
$(n_{M}-d)+d=n_{M}$. The maximal MEC set $M_{1}$ is of size $n_{M}-d$, whose
estimated FLR and MMR are $0$ and $d/n_{M}$, respectively. Let $\hat{M}$ be a
MEC set of size $n_{M}$. While $n_{M}-d$ pairs can be determined unequivocally
as $M_{1}$, there are many possibilities for the remaining $d$ pairs among
from $\Omega\setminus M_{1}$, all with $\gamma_{ab}=0$. If $d_{U}$ of them
belong to $U$, then both the FLR and MMR of $\hat{M}$ are $d_{U}/n_{M}$.
Clearly, one may choose a MEC set with respect to the FLR and MMR, without
being restricted to $|\hat{M}|=n_{M}$.

#### _Case-U_

Suppose $\gamma_{ab}=1$ over $M$, and $\gamma_{ab}=1$ for $d$ pairs in $U$ due
to key-variable errors, in such a manner that $n(1)=n_{M}+d$. Using $Q_{f}$ by
(3), we obtain $\hat{\theta}=1$. We can estimate $n_{M}$ by solving (8) given
$u(1)=d/(n-n_{M})$, since $\hat{g}(0)=0$ and

$\hat{g}(1)=\frac{n_{M}/u(1)}{n_{M}\big{(}1/u(1)-1\big{)}+n}=\frac{n_{M}}{n_{M}-u(1)n_{M}+u(1)n}=\frac{n_{M}}{n_{M}+d}$

satisfy (8), i.e. $(n_{M}+d)n_{M}/(n_{M}+d)+0=n_{M}$. The maximal MEC set
$M_{1}$ is of size $n_{M}+d$, whose estimated FLR and MMR are $d/(n_{M}+d)$
and $0$, respectively. For a MEC set of size $n_{M}$, one needs to exclude $d$
pairs from $M_{1}$. If $d_{M}$ of them belong to $M$, then both the FLR and
MMR of the resulting $\hat{M}$ are $d_{M}/n_{M}$. Again, MEC may be guided by
the error rates, without being restricted to $|\hat{M}|=n_{M}$.

## C. Discussions

### C.1. Modelling comparison scores jointly

Consider the possibility of MLE of $n_{M}$ and $m(\bm{\gamma})$, where
independent $\bm{\gamma}_{ab}$ are only assumed over the pairs in $M$, but not
over $\Omega$ as in the classical approach. Let all the distinct _entities_
underlying the comparison space $\Omega$ be divided into three parts: the
_matched_ entities $AB$, where each entity in $AB$ corresponds to a record
pair in $M$; the _unmatched_ entities, each of which corresponds to, and is
denoted by, either a record in $A_{0}=\\{a\in A:\delta_{a}=0\\}$ or
$B_{0}=\\{b\in B:\delta_{b}=0\\}$, where $\delta_{a}=\sum_{b\in B}g_{ab}$ and
$\delta_{b}=\sum_{a\in A}g_{ab}$.

Assume $\bm{\gamma}_{L}=\\{\bm{\gamma}_{M},\bm{z}_{A_{0}},\bm{z}_{B_{0}}\\}$
to be independent across the entities in $L=\\{AB,A_{0},B_{0}\\}$. Note that
$(g_{\Omega},\delta_{A},\delta_{B})$ are determined given $L$ and
$\bm{\gamma}_{L}$ determined given $(L,\bm{z}_{A},\bm{z}_{B})$, where
$\bm{z}_{A}=\\{\bm{z}_{a}:a\in A\\}$ and $\bm{z}_{B}=\\{\bm{z}_{b}:b\in B\\}$
contain the observed key vectors. Let $N_{AB}=|AB|$, $N_{A_{0}}=|A_{0}|$ and
$N_{B_{0}}=|B_{0}|$, and $N_{L}=N_{AB}+N_{A_{0}}+N_{B_{0}}$. A model of the
complete data $(\bm{z}_{A},\bm{z}_{B},L,N_{L})$ can be given as

$f(\bm{z}_{A},\bm{z}_{B},L,N_{L})=f(\bm{z}_{A},\bm{z}_{B}|L)f(L|N_{L})f(N_{L})$

where $f(\bm{z}_{A},\bm{z}_{B}|L)$ factorises over $AB$, $A_{0}$ and $B_{0}$,
and $f(L|N_{L})$ can be a multinomial model of $(N_{AB},N_{A_{0}},N_{B_{0}})$,
and $f(N_{L})$ a well-defined model of $N_{L}$ with its own parameters. The
observed data are $(\bm{z}_{A},\bm{z}_{B})$ and $(n_{A},n_{B})$, where
$n_{A}=N_{AB}+N_{A_{0}}$ and $n_{B}=N_{AB}+N_{B_{0}}$.

For instance, a model of $(\bm{z}_{A},\bm{z}_{B})$ conditional on $L$ can be
given as

$f(\bm{z}_{A},\bm{z}_{B}|L)=\prod_{(a,b)\in\Omega}g_{ab}f_{1}(\bm{z}_{a},\bm{z}_{b};\bm{\theta})~{}\prod_{a\in
A}(1-\delta_{a})f_{0}(\bm{z}_{a};\bm{\xi})~{}\prod_{b\in
B}(1-\delta_{b})f_{0}(\bm{z}_{b};\bm{\xi})$

where $f_{1}(\bm{z}_{a},\bm{z}_{b};\bm{\theta})$ is the model of
$(\bm{z}_{a},\bm{z}_{b})$ for a matched entity, and $f_{0}(\bm{z};\bm{\xi})$
is that of $\bm{z}$ for an unmatched entity. Next, given $N_{L}=|L|$, a
multinomial model of $L$ can be given as

$f(L|N_{L})=\binom{N_{L}}{N_{AB},N_{A_{0}},N_{B_{0}}}\phi_{AB}^{N_{AB}}\phi_{A_{0}}^{N_{A_{0}}}\phi_{B_{0}}^{N_{B_{0}}}$

where $\phi_{AB}+\phi_{A_{0}}+\phi_{B_{0}}=1$. Lastly, let $f(N_{L})$ be a
well-defined prior of $N_{L}$.

Recall that the conditional expectation of $g_{ab}$ is calculated as
$E(g_{ab}|\bm{\gamma}_{ab})$ in (8), marginally for a randomly selected record
pair. However, for the E-step under the joint-data model here, one needs to
evaluate $E(g_{ab}|\bm{z}_{A},\bm{z}_{B},n_{A},n_{B})$ conditional on all the
observed data, which is intractable, since the conditional distribution of
$(\bm{z}_{A},\bm{z}_{B},L,N_{L})$ given $(\bm{z}_{A},\bm{z}_{B},n_{A},n_{B})$
does not factorise in any helpful way. It is also exceedingly impractical to
calculate the observed likelihood based on
$(\bm{z}_{A},\bm{z}_{B},n_{A},n_{B})$, which requires integrating
$f(\bm{z}_{A},\bm{z}_{B},L,N_{L})$ over all $(L,N_{AB},N_{A_{0}},N_{B_{0}})$
that are compatible with the observed $(n_{A},n_{B})$.

Therefore, MLE by modelling the comparison scores jointly does not seem
viable.

### C.2 Moment-based estimation

It is possible to derive a moment-based estimator of the perturbation
probability $\alpha_{k}$, for $k=1,...,K$. Let
$\xi_{k}=\mbox{Pr}(\gamma_{ab,k}=1|g_{ab}=0)$ for a randomly selected record
pair from $\Omega$. Under the non-informative hit-miss model, where
$\beta_{kd}=m_{kd}=u_{kd}$, we have

$\xi_{k}=\sum_{d=1}^{D_{k}}\beta_{kd}^{2}\qquad\text{and}\qquad\theta_{k}=1-\alpha_{k}(1-\xi_{k})$

Let $n(1;k)$ be the observed number of pairs that agree on $z_{k}$, and let
$n(0;k)=n-n(1;k)$. It follows from
$E\big{(}n(1;k)|n_{M}\big{)}=n_{M}\theta_{k}+(n-n_{M})\xi_{k}$ that

$n_{M}(1-\alpha_{k})(1-\xi_{k})=n(1-\xi_{k})-E\big{(}n(0;k)|n_{M}\big{)}$
(C.1)

Plugging in the estimates of $\xi_{k}$ and $n_{M}$, and $n(0;k)$ for its
expectation, we obtain an estimate of $\alpha_{k}$, subjected to the
assumption that $\alpha_{k}$ is positive for some $k=1,...,K$.

Moreover, setting $\alpha_{k}=0$ in (C.1) yields an approximate estimating
equation for $n_{M}$,

$\Delta_{k}=n(0;k)-(n-n_{M})\big{(}1-\hat{\xi}_{k}\big{)}=0\quad\text{subjected
to}\quad n_{M}\leq\min(n_{A},n_{B})$

Note that in principle this makes it possible to estimate $n_{M}$ based on a
single binary key variable, which represents the minimal setting at all
conceivable for record linkage. For $K>1$, a possibility is to use the
_minimum distance estimator_ (Wolfowitz, 1957) of $n_{M}$, which is given by
the value that minimises a chosen metric that weighs together all the
$\Delta_{k}$, where $k=1,...,K$. Note that the bias of the resulting
$\hat{n}_{M}$ does not vanish as $n\rightarrow\infty$, as long as some
$\theta_{k}$ converges to a value unequal to 1.

However, the main problem with these moment-based estimates is that they are
very unstable. This is largely caused by the fact that the bipartition of the
comparison space $\Omega=M\cup U$ is highly imbalanced, where $\pi=n_{M}/n$ is
very close to 0, such that the right-hand side of (C.1) is the difference
between two numbers, both of which are much larger than the term on the left-
hand side of the equation.

The moment equation (C.1) can also be related to the objective function (2).
Let $n_{M}(1;k)$ and $n_{U}(1;k)$ be, respectively, the number of
$\gamma_{k}=1$ in $M$ and $U$, and $n_{M}(0;k)$ and $n_{U}(0;k)$ those of
$\gamma_{k}=0$. Assume the model (5) of $m(\bm{\gamma};\bm{\theta})$, and
similarly of $u(\bm{\gamma};\bm{\xi})$. The score functions derived from the
objective function (2) are given by $\pi=n_{M}/n$, and

$\displaystyle\begin{cases}\frac{\partial
h}{\partial\theta_{k}}=\frac{n_{M}(1;k)}{\theta_{k}}-\frac{n_{M}(0;k)}{1-\theta_{k}}=0\\\
\frac{\partial
h}{\partial\xi_{k}}=\frac{n_{U}(1;k)}{\xi_{k}}-\frac{n_{U}(0;k)}{1-\xi_{k}}=0\end{cases}\Leftrightarrow\quad\begin{cases}n_{M}\theta_{k}=n_{M}(1;k)=n(1;k)-n_{U}(1;k)\\\
(n-n_{M})\xi_{k}=n_{U}(1;k)=n(1;k)-n_{M}(1;k)\end{cases}$
$\displaystyle\Leftrightarrow\quad\begin{cases}n(0;k)=n_{M}(1-\theta_{k})+n_{U}(0;k)\\\
n(0;k)=n_{M}(0;k)+(n-n_{M})(1-\xi_{k})\end{cases}$

for $k=1,...,K$. Taking expectation of both score functions, we recover (C.1)
above. In other words, had one observed the missing data $g_{\Omega}$ and
maximised $h(\bm{\eta})$ by (2) directly, as if it were the complete-data log-
likelihood based on $(g_{\Omega},\gamma_{\Omega})$, one would have been
conducting rather inefficient moment-based estimation instead.

Finally, note that the imbalanced bipartition of $\Omega$, which affects
(C.1), has no bearing on the unsupervised MEC algorithm, where one uses a
value of $\theta_{k}$ that satisfies (10), which depends on two numbers that
are of the same magnitude of $n_{M}$.

## D. Additional simulations with low levels of overlap

Another simulation study was performed to assess the performance of the
proposed method when the degree of files’ overlap is small. Table 6 and Table
7 present the results obtained for $p_{A}=0.2,0.15,$ and $0.1$ (i.e.,
$\pi=0.0002,0.00015,$ and $0.0001$) under Scenario I and Scenario II,
respectively. As expected, the the estimate $\hat{n}_{M}$ (or $\hat{\pi}$)
gets worse as $p_{A}$ (or $\pi$) reduces, which is consistent with the
previous findings of Sadinle (2017) and Enamorado et al. (2019).

Table 6: Parameters and averages of their estimates, averages of error rates and their estimates, over 200 simulations under Scenario I. Median of estimate of $n_{M}$ given as $\tilde{n}_{M}$. Parameter | Formulae | Estimation
---|---|---
$\pi$ | $E(n_{M})$ | $\theta_{k}^{(t)}$ | $\xi_{k}^{(t)}$ | $\hat{\pi}$ | $\hat{n}_{M}$ | $\tilde{n}_{M}$ | FLR | MMR | $\widehat{\mbox{FLR}}$ | $\widehat{\mbox{MMR}}$
.0002 | 100 | $\hat{\theta}_{k}$ | (15) | .00020 | 100.7 | 100 | .0460 | .0395 | .0382 | .0382
(13) | (20) | .00026 | 132.0 | 107 | .1434 | .0400 | .0983 | .0983
(13) | (15) | .00033 | 162.9 | 110 | .2040 | .0358 | .1417 | .1417
(18) | (15) | .00077 | 387.4 | 500 | .6204 | .1406 | .3023 | .3023
.00015 | 75 | $\hat{\theta}_{k}$ | (15) | .00015 | 75.3 | 75 | .0495 | .430 | .0384 | .0384
(13) | (20) | .00024 | 117.9 | 81 | .1699 | .0457 | .1125 | .1125
(13) | (15) | .00031 | 152.9 | 84 | .2420 | .0412 | .1631 | .1631
(18) | (15) | .00084 | 420.3 | 500 | .7250 | .1579 | .3496 | .3496
.0001 | 50 | $\hat{\theta}_{k}$ | (15) | .00010 | 50.2 | 50 | .0582 | .0520 | .0397 | .0397
(13) | (20) | .00022 | 109.6 | 55 | .2163 | .0529 | .1365 | .1365
(13) | (15) | .00031 | 155.1 | 57 | .3030 | .0485 | .1979 | .1979
(18) | (15) | .00092 | 459.8 | 500 | .8424 | .1736 | .4015 | .4015
Table 7: Parameters and averages of their estimates, averages of error rates and their estimates, over 200 simulations under Scenario II. Median of estimate of $n_{M}$ given as $\tilde{n}_{M}$. Parameter | Formulae | Estimation
---|---|---
$\pi$ | $n_{M}$ | $\theta_{k}^{(t)}$ | $\xi_{k}^{(t)}$ | $\hat{\pi}$ | $\hat{n}_{M}$ | $\tilde{n}_{M}$ | FLR | MMR | $\widehat{\mbox{FLR}}$ | $\widehat{\mbox{MMR}}$
.0002 | 100 | $\hat{\theta}_{k}$ | (15) | .00020 | 100.7 | 100 | .0457 | .0394 | .0369 | .0369
(13) | (20) | .00022 | 111.0 | 103 | .0856 | .0436 | .0592 | .0592
(13) | (15) | .00024 | 118.7 | 104 | .1102 | .0418 | .0740 | .0740
(18) | (15) | .00050 | 249.0 | 110 | .3583 | .0923 | .1875 | .1875
.00015 | 75 | $\hat{\theta}_{k}$ | (15) | .00015 | 75.7 | 75 | .0496 | .0418 | .0367 | .0367
(13) | (20) | .00017 | 86.3 | 78 | .0952 | .0461 | .0600 | .0600
(13) | (15) | .00021 | 106.4 | 79 | .1424 | .0442 | .0920 | .0920
(18) | (15) | .00060 | 301.6 | 500 | .5031 | .1193 | .2528 | .2528
.0001 | 50 | $\hat{\theta}_{k}$ | (15) | .00010 | 50.5 | 50 | .0528 | .0445 | .0377 | .0377
(13) | (20) | .00013 | 63.6 | 52 | .1111 | .0501 | .0649 | .0649
(13) | (15) | .00016 | 82.3 | 53 | .1567 | .0478 | .0945 | .0945
(18) | (15) | .00077 | 385.5 | 500 | .7034 | .1537 | .3564 | .3564

## References

  * Armstrong and Mayda (1993) Armstrong, J. and J. Mayda (1993).  Model-based estimation of record linkage error rates.  Survey Methodology 19(2), 137–147.
  * Berger et al. (1996) Berger, A. L., S. A. Della Pietra, and V. J. Della Pietra (1996).  A maximum entropy approach to natural language processing.  Computational Linguistics 22, 39–71.
  * Binette and Steorts (2020) Binette, O. and R. C. Steorts (2020).  (almost) all of entity resolution.  arXiv preprint arXiv:2008.04443.
  * Christen (2007) Christen, P. (2007).  A two-step classification approach to unsupervised record linkage.  In Proceedings of the sixth Australasian conference on Data mining and analytics-Volume 70, pp. 111–119. Citeseer.
  * Christen (2008) Christen, P. (2008).  Automatic record linkage using seeded nearest neighbour and support vector machine classification.  In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 151–159.
  * Christen (2012) Christen, P. (2012).  A survey of indexing techniques for scalable record linkage and deduplication.  IEEE transactions on knowledge and data engineering 24(9), 1537–1555.
  * Copas and Hilton (1990) Copas, J. and F. Hilton (1990).  Record linkage: statistical models for matching computer records.  Journal of the Royal Statistical Society: Series A (Statistics in Society) 153(3), 287–312.
  * Enamorado et al. (2019) Enamorado, T., B. Fifield, and K. Imai (2019).  Using a probabilistic model to assist merging of large-scale administrative records.  American Political Science Review 113(2), 353–371.
  * Fellegi and Sunter (1969) Fellegi, I. P. and A. B. Sunter (1969).  A theory for record linkage.  Journal of the American Statistical Association 64(328), 1183–1210.
  * Gull and Daniell (1984) Gull, S. F. and G. J. Daniell (1984).  Maximum entropy method in image processing.  IEE Proceedings 131F, 646–659.
  * Hand and Christen (2018) Hand, D. and P. Christen (2018).  A note on using the f-measure for evaluating record linkage algorithms.  Statistics and Computing 28(3), 539–547.
  * Herzog et al. (2007) Herzog, T. N., F. J. Scheuren, and W. E. Winkler (2007).  Data quality and record linkage techniques.  Springer Science & Business Media.
  * Jaro (1989) Jaro, M. A. (1989).  Advances in record-linkage methodology as applied to matching the 1985 census of tampa, florida.  Journal of the American Statistical Association 84(406), 414–420.
  * Larsen and Rubin (2001) Larsen, M. D. and D. B. Rubin (2001).  Iterative automated record linkage using mixture models.  Journal of the American Statistical Association 96(453), 32–41.
  * McLeod et al. (2011) McLeod, P., D. Heasman, and I. Forbes (2011).  Simulated data for the on the job training.  Essnet DI available at http://www. crosportal. eu/content/job-training 70.
  * Newcombe et al. (1959) Newcombe, H. B., J. M. Kennedy, S. Axford, and A. P. James (1959).  Automatic linkage of vital records.  Science 130(3381), 954–959.
  * Nguyen et al. (2010) Nguyen, X., M. J. Wainwright, and M. I. Jordan (2010).  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  IEEE Transactions on Information Theory 56(11), 5847–5861.
  * Nigam et al. (1999) Nigam, K., J. Lafferty, and A. McCallum (1999).  Using maximum entropy for text classification.  In IJCAI-99 workshop on machine learning for information filtering, Volume 1, pp. 61–67. Stockholom, Sweden.
  * Owen et al. (2015) Owen, A., P. Jones, and M. Ralphs (2015).  Large-scale linkage for total populations in official statistics.  Methodological Developments in Data Linkage, 170–200.
  * Sadinle (2017) Sadinle, M. (2017).  Bayesian estimation of bipartite matchings for record linkage.  Journal of the American Statistical Association 112(518), 600–612.
  * Sarawagi and Bhamidipaty (2002) Sarawagi, S. and A. Bhamidipaty (2002).  Interactive deduplication using active learning.  In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 269–278.
  * Steorts (2015) Steorts, R. C. (2015).  Entity resolution with empirically motivated priors.  Bayesian Analysis 10, 849–875.
  * Stringham (2021) Stringham, T. (2021).  Fast bayesian record linkage with record-specific disagreement parameters.  Journal of Business & Economic Statistics 0(0), 1–14.
  * Tancredi and Liseo (2011) Tancredi, A. and B. Liseo (2011).  A hierarchical bayesian approach to record linkage and population size problems.  The Annals of Applied Statistics 5(2B), 1553–1585.
  * Winkler (1988) Winkler, W. E. (1988).  Using the em algorithm for weight computation in the fellegi–sunter model of record linkage.  In Proceedings of the Section on Survey Research Methods, pp. 667–671. American Statistical Association.
  * Winkler (1993) Winkler, W. E. (1993).  Improved decision rules in the fellegi-sunter model of record linkage.  In Proceedings of the Section on Survey Research Methods, pp. 274–270. American Statistical Association.
  * Winkler (1994) Winkler, W. E. (1994).  Advanced methods for record linkage.  In Proceedings of the Section on Survey Research Methods, pp. 467–472. American Statistical Association.
  * Winkler and Thibaudeau (1991) Winkler, W. E. and Y. Thibaudeau (1991).  An application of the Fellegi-Sunter model of record linkage to the 1990 US decennial census.  Citeseer.
  * Wolfowitz (1957) Wolfowitz, J. (1957).  The minimum distance method.  The Annals of Mathematical Statistics, 75–88.
  * Xu et al. (2019) Xu, H., X. Li, C. Shen, S. L. Hui, S. Grannis, et al. (2019).  Incorporating conditional dependence in latent class models for probabilistic record linkage: Does it matter?  Annals of Applied Statistics 13(3), 1753–1790.
  * Zhang and Campbell (2012) Zhang, G. and P. Campbell (2012).  Data survey: developing the statistical longitudinal census dataset and identifying its potential uses.  Australian Economic Review 45(1), 125–133.