Aller au contenu
English

Apprendre les poids sans étiquettes

  • Leçon 16
  • 45 min
  • Module 5 : L'appariement probabiliste

Où nous en sommes

Nous avons calculé les probabilités m et u quand nous connaissions les vraies correspondances. Habituellement, nous ne les connaissons pas. Dans cette leçon, nous laissons l'espérance-maximisation apprendre les poids sans étiquettes, entraînons Splink sur DuckDB et lisons ses poids de correspondance.

Lue depuis YouTube. Rien ne se charge depuis YouTube avant que vous appuyiez sur lecture. Confidentialité

Ce que vous saurez faire

Apprenez les probabilités m et u à partir des enregistrements seuls, sans paires étiquetées. Voyez comment l’espérance-maximisation trouve deux groupes de paires. Entraînez un modèle Splink sur DuckDB et lisez ses poids de correspondance. Puis comparez ses résultats à ceux des poids qui nécessitaient des étiquettes.

Carnet JupyterExécuter l'espérance-maximisation et Splink dans un carnet JupyterColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter exécute l’espérance-maximisation à la main sur 200 paires inventées. Vous complétez un cycle et vérifiez que la méthode trouve la réponse cachée dans les décomptes. Ensuite, il entraîne Splink sur les enregistrements de TermeLarkfieldUne boutique en ligne canadienne inventée, qui vend des articles pour la maison et le jardin. Ce n’est pas une vraie entreprise. Tous les cours Nextia utilisent son service d’assistance et ses données comme exemple.En savoir plus Découvrez Larkfield, et vous lisez un de ses poids. Ses cellules de préparation installent Splink et téléchargent les données. Aucune configuration locale n’est donc nécessaire.

Le carnet est en anglais. Colab et Kaggle ouvrent votre propre copie. Il faut un compte Google ou Kaggle gratuit. Vous êtes bloqué ? Consultez le carnet de solution.

Avant de commencerCe qu’il faut savoir et avoir sous la mainEnviron 45 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

Deux familles partagent une salle de lavage. Un jour, leurs vêtements propres se retrouvent dans un grand panier, sans noms pour les identifier. Vous devez les trier en deux piles.

Vous commencez par une hypothèse approximative : « La famille A a les petits vêtements. » Vous faites deux piles selon cette hypothèse. Puis vous regardez chaque pile. La pile A contient beaucoup de chemises bleues et d’uniformes scolaires. La pile B contient beaucoup de vêtements de travail. Vous avez maintenant une meilleure description de chaque famille. Vous triez encore le panier selon cette nouvelle description. Quelques vêtements changent de pile. Vous décrivez encore les piles, puis vous triez à nouveau. Après quelques cycles, plus rien ne bouge.

Personne ne vous a dit à qui appartient chaque vêtement. Les vêtements présentaient une régularité. Vous l’avez trouvée en faisant des hypothèses, en triant et en décrivant, encore et encore.

Le problème : les vrais enregistrements n’ont pas de réponses

Section intitulée « Le problème : les vrais enregistrements n’ont pas de réponses »

Dans la dernière leçon, fs.py a compté m et u sur 16 383 vraies paires. Il pouvait le faire seulement parce que nos enregistrements sont synthétiques. Le code qui les a créés connaît le vrai client de chaque enregistrement.

Les vraies listes de Larkfield n’ont pas cette colonne. Quelqu’un doit étiqueter les paires à la main. Selon les hypothèses du cours, Ivana a besoin de 1,2 minute par paire. Les 16 383 vraies paires, plus les autres paires bien plus nombreuses autour d’elles, lui prendraient plusieurs mois. Et chaque nouvelle source nécessiterait de nouvelles étiquettes.

Nous voulons les poids sans les étiquettes.

Les paires candidates ressemblent au linge. Elles mélangent deux groupes : les correspondances (le même client) et les non-correspondances. Chaque groupe présente sa propre régularité. Les correspondances concordent sur la plupart des champs. Les non-correspondances concordent sur peu de champs. Nous ne savons pas à quel groupe appartient chaque paire, mais nous voyons quels champs concordent.

L’espérance-maximisation (EM) trouve les deux groupes par cycles :

  1. Commencer par une hypothèse : une proportion de correspondances, ainsi que m et u pour chaque champ.
  2. Étape E (l’« espérance ») : pour chaque paire, calculer la probabilité de correspondance selon l’hypothèse actuelle. C’est le poids total de la dernière leçon, converti en probabilité.
  3. Étape M (la « maximisation ») : recompter m, u et la proportion. Chaque paire compte comme correspondance selon sa probabilité. Une paire dont la probabilité est de 0,9 compte pour 0,9 correspondance et 0,1 non-correspondance.
  4. Répéter les étapes 2 et 3 jusqu’à ce que les nombres ne changent plus.

EM est une méthode statistique générale pour les données qui contiennent un groupe caché. En appariement, elle apprend les probabilités m sans étiquettes.

Nous avons créé 200 paires avec trois champs : courriel, nom de famille et date de naissance. Nous les avons créées avec une réponse connue, 20 % de correspondances, pour pouvoir vérifier EM. EM ne voit jamais cette réponse. Elle voit seulement combien de paires présentent chaque combinaison de concordance (1 = concorde, 0 = diffère) :

Courriel Nom de famille Date de naissance Paires
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

Notre première hypothèse est volontairement mauvaise : la moitié des paires sont des correspondances, m vaut 0,6 et u vaut 0,4 pour chaque champ. Selon cette hypothèse, l’étape E attribue une probabilité de 0,771 à une paire qui concorde sur les trois champs. Une paire qui ne concorde sur aucun champ reçoit 0,229. L’étape M recompte ensuite. Les 134 paires sans aucune concordance comptent maintenant surtout comme non-correspondances, donc u diminue rapidement.

Les cycles d'espérance-maximisation sur 200 paires inventées. 1. Partir d'une hypothèse : proportion 0,5, m 0,6, u 0,4. 2. Étape E : la probabilité que chaque paire soit une correspondance; les trois champs concordent : 0,771; aucun ne concorde : 0,229. 3. Étape M : recompter, chaque paire selon sa probabilité : proportion 0,339, m du courriel 0,348, u du courriel 0,086. Une flèche retourne à l'étape 2. 4. Après 30 cycles : proportion 0,197, m du courriel 0,794, u du courriel 0,023.
Un cycle d'espérance-maximisation comprend une étape E et une étape M. Les cycles se répètent jusqu'à ce que plus rien ne change. Aucune étiquette n'est utilisée.
Description textuelle du diagramme

Quatre encadrés. Encadré 1, le départ : une proportion de 0,5, ainsi que m 0,6 et u 0,4 pour chaque champ. Une flèche mène à l’encadré 2, l’étape E : chaque paire reçoit une probabilité de correspondance. Une paire qui concorde sur les trois champs reçoit 0,771. Une paire qui ne concorde sur aucun champ reçoit 0,229. Une flèche descend vers l’encadré 3, l’étape M : m, u et la proportion sont recomptés, chaque paire selon sa probabilité. Après le premier cycle, la proportion vaut 0,339, le m du courriel 0,348 et son u 0,086. Une flèche marquée « encore » retourne à l’encadré 2. Encadré 4, la fin : après 30 cycles, la proportion vaut 0,197, le m du courriel 0,794 et son u 0,023.

Le tableau suit les cycles. La dernière ligne approche la réponse cachée : proportion 0,2; m 0,8, 0,9 et 0,7; u 0,02, 0,1 et 0,05.

CycleProportionm courrielm nom de famillem date de naissanceu courrielu nom de familleu date de naissance
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
Trois des nombres qu'EM apprend sur les 200 paires inventées, cycle par cycle. La réponse utilisée pour créer les paires : proportion 0,2, m du courriel 0,8, u du nom de famille 0,1.
Description textuelle du graphique

Un graphique en courbes sur 30 cycles. La proportion de correspondances commence à 0,5, descend à 0,339 après un cycle et se stabilise près de 0,197. Le m du courriel commence à 0,6, descend à 0,348 après un cycle, puis remonte et se stabilise près de 0,794. Le u du nom de famille commence à 0,4, descend à 0,157 après un cycle et se stabilise près de 0,099.

Le m du courriel descend d’abord, puis remonte. EM peut faire un détour. Après environ 20 cycles, les nombres bougent à peine.

Splink est une bibliothèque Python à code source ouvert pour l’appariement probabiliste, qui utilise le modèle Fellegi–Sunter. Elle ne conserve pas les paires dans Python. Elle écrit du SQL et laisse une base de données l’exécuter. Ici, la base de données est DuckDB : une petite base qui fonctionne dans le processus Python, sans serveur.

Splink s’entraîne en trois étapes, et le projet fait de même dans splinkmodel.py :

  1. La probabilité a priori : combien de paires correspondent. Splink compte les paires qui partagent un courriel. Nous lui indiquons qu’environ 45 % des vraies paires partagent un courriel (le rappel de cette règle, une hypothèse). À partir des deux nombres, il estime la proportion de correspondances parmi toutes les paires.
  2. u à partir de paires aléatoires. Deux enregistrements aléatoires représentent presque toujours deux personnes différentes. Splink compare donc 2 millions de paires aléatoires et compte la fréquence de concordance de chaque champ. C’est u, sans étiquettes. Cela règle le problème du nom de famille de la dernière leçon : les paires sont aléatoires, pas candidates d’une clé de nom de famille.
  3. m par espérance-maximisation, sur les paires sélectionnées par une règle de blocage. Parmi les paires aléatoires, les correspondances sont trop rares pour qu’EM les voie. Parmi les paires ayant la même date de naissance, les correspondances sont fréquentes. Un champ de la règle de blocage concorde toujours dans ces paires. EM ne peut donc pas y apprendre son m. Une deuxième règle, sur le prénom et le nom de famille ensemble, couvre la date de naissance.

DuckDB écrit des fichiers temporaires sur disque quand une étape ne tient pas en mémoire. Une grosse exécution peut remplir un disque. Le projet limite DuckDB à 4 Go de mémoire et à 4 Go de fichiers temporaires, dans outputs/duckdb_tmp/. Définissez LARKFIELD_DUCKDB_TEMP pour utiliser un autre dossier. Une exécution qui nécessite davantage s’arrête avec une erreur de DuckDB.

  1. Entraînez Splink et enregistrez le modèle dans outputs/models/splink.json :

    Fenêtre de terminal
    match splink

    Splink affiche son journal d’entraînement. Les premières lignes donnent la probabilité a priori. La fin donne les deux sessions EM (abrégées ici) :

    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

    Notre portable effectuait d’autres tâches. Sur un portable sans autre tâche en cours, le même entraînement a pris 2,9 secondes.

    La probabilité a priori de 1,72e-05 signifie une paire sur 58 264. Cela donne environ 31 004 vraies paires parmi les 1,8 milliard de paires. La vérité synthétique en compte 27 677 : une bonne estimation à partir d’une seule hypothèse.

  2. Affichez les poids à nouveau sans entraînement :

    Fenêtre de terminal
    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
Le poids d'une correspondance exacte sur chaque champ, appris par Splink à partir des 60 108 enregistrements synthétiques sans étiquettes. Résultats mesurés.
Description textuelle du graphique

Un graphique à points avec une ligne par champ, du plus fort au plus faible. Courriel 14,96; téléphone 14,16; code postal 13,28; date de naissance 10,17; rue 7,19; prénom 6,67; nom de famille 6,14; ville 3,84.

Comparez ces résultats aux poids obtenus avec des étiquettes dans la dernière leçon :

  • Le nom de famille constitue maintenant un indice : +6,14, et non +0,04. u provient de paires aléatoires, où un nom de famille partagé est rare.
  • Le courriel, le téléphone et le code postal sont bien plus forts ici : +13 à +15, contre +4 à +9. Encore une fois, u parmi les paires aléatoires est beaucoup plus faible que u parmi les candidates. Les deux réponses sont justes, mais répondent à des questions différentes.
  • La date de naissance est incorrecte. Une correspondance exacte vaut +10,17, ce qui semble correct. Mais « All other comparisons » (toutes les autres comparaisons), soit deux dates différentes, vaut seulement −0,11. Avec des étiquettes, une date de naissance différente valait −5,05 : un indice fort de deux personnes distinctes. EM a appris le m de la date de naissance dans la deuxième session, parmi des paires ayant les mêmes prénom et nom de famille. Dans ces paires, le groupe « correspondance » d’EM semble inclure beaucoup de personnes qui partagent seulement un nom. C’est notre interprétation des nombres; la prochaine leçon en montre le coût.

EM trouve une régularité entre deux groupes. Ce n’est pas toujours celle que vous voulez. Vérifiez ses poids avec quelques paires étiquetées.

Fenêtre de terminal
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)

L’exécution attribue un score aux paires candidates des cinq clés de blocage. Son score est le poids de correspondance, pas la probabilité; la leçon 3 explique pourquoi. Le seuil est choisi sur les données de validation, comme pour chaque exécution.

Exécution Étiquettes utilisées Précision Rappel F1
rules aucune 0,723 0,870 0,790
weighted aucune (poids estimés à la main) 0,751 0,766 0,759
fs-labels 16 383 vraies paires 0,839 0,747 0,790
splink aucune 0,817 0,779 0,797

Splink sans étiquettes égale Fellegi–Sunter avec étiquettes : F1 de 0,797 contre 0,790. C’est un résultat solide.

Splink sans étiquettes peut-il aussi battre un classificateur entraîné sur des étiquettes? Sur ces enregistrements, non. Dans le module 6, Un classificateur de paires supervisé entraîne une régression logistique sur les paires étiquetées. Elle atteint un F1 de 0,911. Les deux exécutions Fellegi–Sunter perdent contre elle par plus de 0,1. Un classificateur peut apprendre qu’un code postal et un téléphone partagés constituent un seul indice dans une famille. Fellegi–Sunter les additionne comme deux indices.

  • Utilisez Splink quand vous n’avez pas d’étiquettes, ou peu. Il fournit un premier apparieur avec des poids lisibles en quelques secondes. Sur un portable sans autre tâche en cours : 2,9 secondes d’entraînement et 2,2 secondes pour attribuer les scores.
  • Vérifiez les poids. Étiquetez quelques centaines de paires et comparez. EM peut apprendre un m incorrect, comme pour la date de naissance ici.
  • Choisissez les règles de blocage EM avec soin. Chaque règle doit rendre les correspondances fréquentes et laisser les autres champs varier librement.
  • Limitez DuckDB. Définissez sa limite de mémoire et son dossier temporaire. Dans La mise à l’échelle, l’entraînement sur 1,1 million d’enregistrements s’arrête à la limite de 4 Go, comme prévu.
  • Les étiquettes restent gagnantes quand vous en avez. Le prochain module les utilise.

Erreur courante

Une règle de blocage EM sur le code postal

Symptôme : TermeAmiraLa développeuse de Larkfield. Elle écrit le code des outils du service d’assistance dans les cours. veut qu’EM apprenne à partir de personnes qui vivent à une même adresse. Elle écrit un script em_postcode.py dans le dossier du projet, avec une règle EM sur le code postal :

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 exécute 19 cycles d’EM, puis s’arrête. La dernière ligne de l’erreur :

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 : parmi les paires ayant le même code postal, presque toutes partagent aussi la rue et la ville. Beaucoup partagent un nom de famille et un téléphone. Les correspondances et les ménages se ressemblent. EM pousse une probabilité m vers zéro, cycle après cycle. Le nombre devient trop petit pour qu’un ordinateur le stocke (sous 1e-300).

Solution : utilisez des règles EM qui rendent les correspondances fréquentes et laissent les autres champs libres. Le projet utilise la date de naissance, puis le prénom avec le nom de famille. Lisez le journal d’entraînement : il nomme les champs que chaque règle ne peut pas estimer.

Conséquence pour le travail en IA : une méthode sans étiquettes trouve la régularité la plus forte dans les données. Quand un deuxième groupe ressemble à celui que vous voulez, ici les ménages, la méthode peut le suivre. Le regroupement (clustering) dans L’exploration non supervisée, du cours d’apprentissage automatique, présente le même risque.

Vérifiez votre compréhension

À l'étape E, une paire reçoit une probabilité de correspondance de 0,9. Comment compte-t-elle à l'étape M?

Afficher la réponse

Comme 0,9 correspondance et 0,1 non-correspondance. Supposons que les courriels de la paire concordent. Elle ajoute alors 0,9 au décompte des « courriels concordants parmi les correspondances », pour m. Elle ajoute 0,1 au même décompte parmi les non-correspondances, pour u. Aucune paire n’est forcée dans un groupe. C’est pourquoi les hypothèses changent progressivement d’un cycle à l’autre.

Vérifiez votre compréhension

Pourquoi Splink n'exécute-t-il pas EM sur toutes les paires, ou sur des paires aléatoires?

Afficher la réponse

Parmi les paires aléatoires, les correspondances sont très rares : environ une sur 58 000 chez Larkfield. EM verrait presque seulement des non-correspondances et ne pourrait pas apprendre à quoi ressemble une correspondance. Une règle de blocage, comme la même date de naissance, sélectionne des paires où les correspondances sont fréquentes. Le coût : EM ne peut pas apprendre le m d’un champ de la règle, car ce champ concorde toujours. Splink utilise donc deux règles, chacune couvrant le champ que l’autre ne peut pas estimer.

Vérifiez votre compréhension

Splink sans étiquettes atteint un F1 de 0,797; Fellegi–Sunter avec 16 383 vraies paires étiquetées, 0,790. Omar demande : « Donc, on n'a jamais besoin d'étiquettes? » Répondez-lui honnêtement.

Afficher la réponse

Non. Splink a égalé Fellegi–Sunter avec étiquettes, ce qui économise beaucoup de travail. Mais les deux utilisent le même modèle, qui additionne chaque champ comme un indice distinct. Un classificateur entraîné sur des paires étiquetées au module 6 atteint 0,911. Les étiquettes servent aussi à vérifier ce qu’EM a appris. Ici, il a appris un poids incorrect pour une date de naissance différente. Quelques centaines de paires étiquetées pour vérifier, puis davantage pour un classificateur, valent leur coût.

Récapitulatif

  • L’espérance-maximisation trouve deux groupes cachés. L’étape E attribue à chaque paire une probabilité de correspondance. L’étape M recompte m et u, chaque paire selon sa probabilité. Répétez jusqu’à ce que plus rien ne change.
  • Splink s’entraîne en trois étapes. La probabilité a priori provient d’une règle de courriel avec un rappel supposé. Ensuite, u provient de paires aléatoires, et m d’EM sur des règles de blocage.
  • DuckDB exécute le SQL de Splink dans Python. Limitez sa mémoire et ses fichiers temporaires.
  • Splink sans étiquettes : précision de 0,817, rappel de 0,779, F1 de 0,797, aussi bon que Fellegi–Sunter avec étiquettes (0,790). Les deux perdent contre un classificateur avec étiquettes (0,911, module 6).
  • EM peut apprendre un poids incorrect : une date de naissance différente vaut −0,11 pour Splink, −5,05 avec étiquettes. Vérifiez avec quelques étiquettes.

Splink attribue à chaque paire un poids de correspondance. Ensuite, nous transformons les poids en décisions : fusionner, faire réviser ou garder séparés.

Leçon suivante : Des poids à une décision