Expectation-Maximization Algorithm

The Expectation-Maximization Algorithm (EM) estimates the m/u probabilities for each field used in record linkage. It alternates between estimating the probability each pair is a match (E-step) and recomputing parameters (M-step) until convergence.

Step 1 - Initialize

Provide initial guesses for each field:

• Name: m = 0.90, u = 0.01
• ZIP: m = 0.55, u = 0.005
• Gender: m = 0.99, u = 0.5

These values do not need to be perfect. EM will refine them.

Step 2 - Expectation (E-step)

For each pair, compute the likelihood of observing its agreement pattern under both match (M) and non-match (U) assumptions.

field	agreement	m_prob	u_prob
NAME	1	0.90	0.01
ZIP	0	0.55	0.005
GENDER	0	0.99	0.5

We assume fields are conditionally independent. The likelihoods are:

• P(y | M) = product over fields: use m_prob if agreement = 1, otherwise use (1 - m_prob)
• P(y | U) = product over fields: use u_prob if agreement = 1, otherwise use (1 - u_prob)

Example calculation:

• P(y|M) = 0.9 * (1 - 0.55) * (1 - 0.99) = 0.9 * 0.45 * 0.01 = 0.00405
• P(y|U) = 0.01 * (1 - 0.005) * (1 - 0.5) = 0.01 * 0.995 * 0.5 = 0.004975

Now compute the posterior probability that the pair is a match:

• w = (prior * P(y|M)) / (prior * P(y|M) + (1 - prior) * P(y|U))
• w = (0.1 * 0.00405) / (0.1 * 0.00405 + 0.9 * 0.004975)
• w ≈ 0.0829

This means there is about an 8.29% chance that this pair is a true match.

Step 3 - Maximization (M-step)

Now we recompute the m and u probabilities using all pairs. Each pair contributes:

• w toward matches
• 1 - w toward non-matches

Updated formulas for each field:

• m_j = (sum over pairs of w_i * indicator(agreement_ij = 1)) / (sum over pairs of w_i)
• u_j = (sum over pairs of (1 - w_i) * indicator(agreement_ij = 1)) / (sum over pairs of (1 - w_i))

Important notes:

• The probabilities get re-computed every run, they are not being incrementally updated
• All pairs contribute to the sums
• Agreement = 0 still affects the denominator indirectly

Intuition:

• If a field agrees mostly in high-probability matches → m increases
• If a field agrees often in low-probability matches → u increases

Step 4 - Repeat

Repeat the E-step and M-step until convergence, when the parameters stop changing significantly.

At that point, the model has learned the m/u probabilities that best explain the data.