Skip to content
Français

Learn the weights without labels

  • Lesson 16
  • 45 min
  • Module 5: Probabilistic linkage

Where we are

We computed m and u probabilities when we knew the true matches. Usually we do not know them. In this lesson, we let expectation maximisation learn the weights without labels, train Splink on DuckDB, and read its match weights.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

What you will be able to do

Learn the m and u probabilities from the records alone, with no labelled pairs. See how expectation maximisation finds two groups of pairs. Train a Splink model on DuckDB and read its match weights. Then measure it against the weights that needed labels.

NotebookRun expectation maximisation and Splink in a notebookColab · Kaggle · GitHub

The notebook runs expectation maximisation by hand on 200 made-up pairs. You complete one round, and check that it finds the answer we hid in the counts. Then it trains Splink on TermLarkfieldA made-up Canadian online shop for home and garden products. It is not a real company. All Nextia courses use its help desk and data as the example.Learn more Meet Larkfield’s records and you read one of its weights. Its setup cells install Splink and download the data, so it needs no local setup.

Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.

Before you startWhat to know and to have readyAbout 45 minutes

What you need to know

What you need on your computer

Two families share a laundry room. One day, their clean clothes end up in one big basket, and nobody wrote names on them. You must sort them into two piles.

You start with a rough guess: “Family A has the small clothes.” You make two piles by that guess. Then you look at each pile. Pile A has many blue shirts and many school uniforms. Pile B has many work clothes. Now you have a better description of each family. You sort the basket again with the new description. A few clothes move. You describe the piles again, and sort again. After a few rounds, nothing moves.

Nobody told you which piece belongs to whom. The clothes themselves had a pattern, and you found it by guessing, sorting and describing, again and again.

In the last lesson, fs.py counted m and u on 16,383 true pairs. It could do that only because our records are synthetic: the code that made them knows the true customer of every record.

Larkfield’s real lists have no such column. Somebody must label pairs by hand. With the course’s assumptions, Ivana needs 1.2 minutes for one pair. 16,383 true pairs, plus the much larger number of other pairs around them, would take her many months. And every new source would need new labels.

We want the weights without the labels.

The candidate pairs are like the laundry. They are a mix of two groups: matches (the same customer) and non-matches. Each group has its own pattern. Matches agree on most fields. Non-matches agree on few. We do not know which pair is in which group, but we see which fields agree.

Expectation maximisation (EM) finds the two groups in rounds:

  1. Start with a guess: a share of matches, and m and u for each field.
  2. E step (the “expectation”): for every pair, compute the chance that it is a match, with the current guess. This is the total weight of the last lesson, turned into a probability.
  3. M step (the “maximisation”): count m, u and the share again. Each pair counts as a match by its chance. A pair with a chance of 0.9 counts as 0.9 of a match and 0.1 of a non-match.
  4. Repeat steps 2 and 3 until the numbers stop changing.

EM is a general method of statistics for data with a hidden group. In record matching, it learns the m probabilities without labels.

A tiny example: 200 pairs and three fields

Section titled “A tiny example: 200 pairs and three fields”

We made 200 pairs with three fields: email, surname and date of birth. We made them with a known answer, 20% matches, so that we can check EM. EM itself never sees that answer. It sees only how many pairs have each pattern of agreement (1 = agrees, 0 = differs):

Email Surname Date of birth Pairs
1 1 1 20
1 1 0 9
1 0 1 2
1 0 0 4
0 1 1 6
0 1 0 17
0 0 1 8
0 0 0 134

Our first guess is poor on purpose: half of the pairs are matches, m is 0.6 and u is 0.4 for every field. With this guess, the E step gives a pair that agrees on all three fields a chance of 0.771. A pair that agrees on none gets 0.229. The M step then counts again. The 134 pairs that agree on nothing now count mostly as non-matches, so u falls fast.

The rounds of expectation maximisation on 200 made-up pairs. 1. Start with a guess: share 0.5, m 0.6, u 0.4. 2. E step: the chance that each pair is a match; all three fields agree: 0.771; none agrees: 0.229. 3. M step: count again, each pair counted by its chance: share 0.339, m of the email 0.348, u of the email 0.086. An arrow goes back to step 2. 4. After 30 rounds: share 0.197, m of the email 0.794, u of the email 0.023.
One round of expectation maximisation is an E step and an M step. The rounds repeat until nothing changes. No labels are used.
Text description of the diagram

Four boxes. Box 1, the start: a share of 0.5, and m 0.6 and u 0.4 for every field. An arrow leads to box 2, the E step: each pair gets a chance of being a match. A pair that agrees on all three fields gets 0.771. A pair that agrees on none gets 0.229. An arrow leads down to box 3, the M step: m, u and the share are counted again, and each pair counts by its chance. After the first round, the share is 0.339, the m of the email 0.348 and its u 0.086. An arrow marked “again” goes back to box 2. Box 4, the end: after 30 rounds the share is 0.197, the m of the email 0.794 and its u 0.023.

The table follows the rounds. The last row is close to the answer that we hid: share 0.2, m 0.8, 0.9 and 0.7, u 0.02, 0.1 and 0.05.

RoundSharem emailm surnamem date of birthu emailu surnameu date of birth
00.50.60.60.60.40.40.4
10.3390.3480.460.3450.0860.1570.095
20.3270.460.5910.4470.0370.0990.05
30.30.5490.7070.5280.0150.0680.031
50.2670.6350.8010.5870.0080.0630.032
100.2240.7370.8650.6420.0130.0860.047
200.1980.790.9130.6940.0230.0980.053
300.1970.7940.9160.6980.0230.0990.053
Three of the numbers that EM learns on the 200 made-up pairs, round by round. The answer we used to make the pairs: share 0.2, m of the email 0.8, u of the surname 0.1.
Text description of the chart

A line chart over 30 rounds. The share of matches starts at 0.5, falls to 0.339 after one round, and settles near 0.197. The m of the email starts at 0.6, falls to 0.348 after one round, then rises and settles near 0.794. The u of the surname starts at 0.4, falls to 0.157 after one round, and settles near 0.099.

The m of the email first falls, then climbs back. EM can take a detour. After about 20 rounds, the numbers barely move.

Splink is an open-source Python library for probabilistic record matching, with the Fellegi–Sunter model inside. It does not keep the pairs in Python. It writes SQL and lets a database run it. Here, the database is DuckDB: a small database that runs inside the Python process, with no server.

Splink trains in three steps, and the project does the same in splinkmodel.py:

  1. The prior: how many pairs match. Splink counts the pairs that share an email. We tell it that about 45% of the true pairs share an email (the recall of that rule, an assumption). From the two numbers, it estimates the share of matches among all pairs.
  2. u from random pairs. Two random records are almost always two different people. So Splink compares 2 million random pairs and counts how often each field agrees. That is u, with no labels. This fixes the surname problem of the last lesson: the pairs are random, not the candidates of a surname key.
  3. m by expectation maximisation, on pairs that a blocking rule selects. Among random pairs, matches are too rare for EM to see. Among pairs with the same date of birth, matches are common. A field in the blocking rule always agrees in those pairs, so EM cannot learn its m there. A second rule, on the first name and surname together, covers the date of birth.

DuckDB writes temporary files to disk when a step does not fit in memory. A large run can fill a disk. The project limits DuckDB to 4 GB of memory and 4 GB of temporary files, in the folder outputs/duckdb_tmp/. Set LARKFIELD_DUCKDB_TEMP to use another folder. A run that needs more stops with DuckDB’s error.

  1. Train Splink and save the model to outputs/models/splink.json:

    Terminal window
    match splink

    Splink prints its training log. The first lines give the prior. The end gives the two EM sessions (shortened here):

    Probability two random records match is estimated to be 1.72e-05.
    This means that amongst all possible pairwise record comparisons, one in 58,264.41 are expected to match. With 1,806,455,778 total possible comparisons, we expect a total of around 31,004.44 matching pairs
    ----- Estimating u probabilities using random sampling -----
    …
    Estimating the m probabilities of the model by blocking on:
    l."dob" = r."dob"
    …
    Parameter estimates cannot be made for the following comparison(s) since they are used in the blocking rules:
    - dob
    …
    EM converged after 5 iterations
    …
    Estimating the m probabilities of the model by blocking on:
    (l."first" = r."first") AND (l."last" = r."last")
    …
    EM converged after 25 iterations
    Your model is fully trained. All comparisons have at least one estimate for their m and u values
    Trained Splink in 43.6 s; saved to outputs/models/splink.json

    Our laptop was busy with other work. On a quiet laptop, the same training took 2.9 seconds.

    The prior 1.72e-05 means one pair in 58,264. That gives about 31,004 true pairs among all 1.8 billion pairs. The synthetic truth has 27,677: a good estimate from one assumption.

  2. Show the weights again without training:

    Terminal window
    match splink --show
    Probability that two random records match: 1.72e-05
    field level m u weight
    first Exact match on first 0.8105 0.0080 6.6655
    first Jaro-Winkler distance of first >= 0.92 0.0486 0.0012 5.2875
    first Jaro-Winkler distance of first >= 0.8 0.0507 0.0087 2.5513
    first All other comparisons 0.0902 0.9821 -3.4449
    last Exact match on last 0.8743 0.0124 6.1439
    last Jaro-Winkler distance of last >= 0.92 0.0756 0.0010 6.1846
    last All other comparisons 0.0501 0.9866 -4.3007
    email Exact match on email 0.3852 0.0000 14.9594
    email Exact match on username 0.0525 0.0000 10.9693
    email Jaro-Winkler distance of email >= 0.88 0.3694 0.0008 8.9434
    email Jaro-Winkler >0.88 on username 0.0650 0.0006 6.8736
    email All other comparisons 0.1279 0.9987 -2.9652
    phone Exact match on phone 0.4055 0.0000 14.1642
    phone All other comparisons 0.5945 1.0000 -0.7502
    postcode Exact match on postcode 0.4628 0.0000 13.2750
    postcode All other comparisons 0.5372 1.0000 -0.8963
    street Exact match on street 0.4662 0.0032 7.1865
    street Jaro-Winkler distance of street >= 0.9 0.0099 0.0097 0.0412
    street All other comparisons 0.5239 0.9871 -0.9141
    town Exact match on town 0.5006 0.0350 3.8364
    town All other comparisons 0.4994 0.9650 -0.9503
    dob Exact match on date of birth 0.0701 0.0001 10.1701
    dob Levenshtein distance <= 1 0.0015 0.0015 0.0069
    dob Abs date difference <= 1 month 0.0025 0.0026 -0.0401
    dob Abs date difference <= 1 year 0.0302 0.0316 -0.0638
    dob Abs date difference <= 10 year 0.2460 0.2610 -0.0857
    dob All other comparisons 0.6497 0.7033 -0.1143
The weight of an exact match on each field, learned by Splink from the 60,108 synthetic records without labels. Measured.
Text description of the chart

A dot chart with one row per field, from the strongest to the weakest. Email 14.96; phone 14.16; postcode 13.28; date of birth 10.17; street 7.19; first name 6.67; surname 6.14; town 3.84.

Compare this with the weights that labels gave in the last lesson:

  • The surname is now evidence: +6.14, not +0.04. u comes from random pairs, where a shared surname is rare.
  • Email, phone and postcode are much stronger here: +13 to +15, against +4 to +9. Again, u from random pairs is much lower than u among candidates. Both are right answers to different questions.
  • The date of birth is wrong. An exact match is +10.17, which looks fine. But “All other comparisons”, two different dates, is only −0.11. With labels, a different date of birth was −5.05: strong evidence of two people. EM learned the m of the date of birth in the second session, among pairs with the same first name and surname. In those pairs, EM’s “match” group seems to include many people who only share a name. This is our reading of the numbers; the next lesson shows its cost.

EM finds a pattern of two groups. It is not always the pattern you want. Check its weights with a few labelled pairs.

Terminal window
match eval --run splink
Blocking time: 0.67 seconds
Predict time (post-blocking): 3.56 seconds
Ran splink: 24,356 pairs called the same, in 39.5 s
splink on the test split: pair precision 0.817, recall 0.779, F1 0.797
5,300 pairs called the same: 4,332 right, 968 wrong; 1,232 of 5,564 true pairs missed
entities after clustering (all records): 39,405 (true: 37,500)

The run scores the candidate pairs of the five blocking keys. Its score is the match weight, not the probability; lesson 3 explains why. The threshold is chosen on the validation split, as for every run.

Run Labels used Precision Recall F1
rules none 0.723 0.870 0.790
weighted none (guessed weights) 0.751 0.766 0.759
fs-labels 16,383 true pairs 0.839 0.747 0.790
splink none 0.817 0.779 0.797

Splink with no labels matches Fellegi–Sunter with labels: F1 0.797 against 0.790. That is a strong result.

Can Splink without labels also beat a classifier trained on labels? On these records, it cannot. In Module 6, A supervised pair classifier trains a logistic regression on the labelled pairs, and it reaches F1 0.911. Both Fellegi–Sunter runs lose to it by more than 0.1. A classifier can learn that a shared postcode and a shared phone are one piece of evidence in a family. Fellegi–Sunter adds them as two.

  • Use Splink when you have no labels, or few. It gives a first matcher with readable weights in seconds: 2.9 seconds to train and 2.2 seconds to score on a quiet laptop.
  • Check the weights. Label a few hundred pairs and compare. EM can learn a wrong m, as for the date of birth here.
  • Choose the EM blocking rules with care. Each rule must make matches common, and it must leave the other fields free to vary.
  • Cap DuckDB. Set its memory limit and its temporary folder. In Scale, training on 1.1 million records stops at the 4 GB cap, as it should.
  • Labels still win when you have them. The next module uses them.

Common mistake

An EM blocking rule on the postcode

Symptom: TermAmiraLarkfield’s developer. She writes the code of the help-desk tools in the courses. wants EM to learn from people who live at one address. She writes a script em_postcode.py in the project folder, with an EM rule on the postcode:

from splink import Linker, block_on
from larkfield_match import splinkmodel
api = splinkmodel._api() # DuckDB with the project's limits
linker = Linker(api.register(splinkmodel.table()), splinkmodel.settings())
linker.training.estimate_probability_two_random_records_match([block_on("email")], recall=0.45)
linker.training.estimate_u_using_random_sampling(max_pairs=2e6, seed=1)
linker.training.estimate_parameters_using_expectation_maximisation(block_on("postcode"))

python em_postcode.py runs 19 rounds of EM, then stops. The last line of the error:

ValueError: m_probability value 1.9332266573275025e-305 is below the minimum allowed value of 1e-300. Values this small cannot be represented accurately as float64 and will underflow to 0.0. Please use a value >= 1e-300.

Cause: in pairs with one postcode, almost every pair also shares the street and the town, and many share a surname and a phone. Matches and households look alike. EM pushes one m probability towards zero, round after round, until the number is too small for a computer to store (below 1e-300).

Fix: use EM rules that make matches common and leave the other fields free. The project uses the date of birth, then the first name with the surname. Read the training log: it names the fields that each rule cannot estimate.

Consequence in AI work: a method without labels finds the strongest pattern in the data. When a second group looks like the one you want, here households, the method can follow it. Clustering in Unsupervised exploration, in the machine learning course, has the same risk.

Check your understanding

In the E step, a pair gets a chance of 0.9 of being a match. How does it count in the M step?

Show the answer

As 0.9 of a match and 0.1 of a non-match. Say the pair’s email agrees. Then it adds 0.9 to the count of “email agrees among matches”, for m. It adds 0.1 to the same count among non-matches, for u. No pair is forced into one group. That is why the guesses change smoothly from round to round.

Check your understanding

Why does Splink not run EM on all pairs, or on random pairs?

Show the answer

Among random pairs, matches are very rare: about one in 58,000 at Larkfield. EM would see almost only non-matches, and it could not learn what a match looks like. A blocking rule, such as the same date of birth, selects pairs where matches are common. The cost: EM cannot learn the m of a field in the rule, because that field always agrees there. So Splink uses two rules, each one covering the field that the other cannot.

Check your understanding

Splink without labels reached F1 0.797, and Fellegi–Sunter with 16,383 labelled true pairs 0.790. Omar asks: “So we never need labels?” Answer him honestly.

Show the answer

No. Splink matched Fellegi–Sunter with labels, and that saves a lot of work. But both use the same model, which adds each field as separate evidence. A classifier trained on labelled pairs in Module 6 reaches 0.911. Labels are also needed to check what EM learned: here, it learned a wrong weight for a different date of birth. A few hundred labelled pairs to check, and later more for a classifier, are worth their cost.

Recap

  • Expectation maximisation finds two hidden groups. The E step gives each pair a chance of being a match. The M step counts m and u again, each pair counted by its chance. Repeat until nothing changes.
  • Splink trains in three steps. The prior comes from an email rule with an assumed recall. Then u from random pairs, and m by EM on blocking rules.
  • DuckDB runs Splink’s SQL inside Python. Cap its memory and its temporary files.
  • Splink without labels: precision 0.817, recall 0.779, F1 0.797, as good as Fellegi–Sunter with labels (0.790). Both lose to a classifier with labels (0.911, Module 6).
  • EM can learn a wrong weight: a different date of birth is −0.11 for Splink, −5.05 with labels. Check with a few labels.

Splink gives every pair a match weight. Next, we turn weights into decisions: merge, review, or leave apart.

Next: From weights to a decision