Aller au contenu
English

MinHash et LSH

  • Leçon 10
  • 40 min
  • Module 3 : Le blocage : ne pas tout comparer

Où nous en sommes

Les clés de blocage exigent un champ identique. Les titres de produits sont rarement identiques. Dans cette leçon, nous utilisons MinHash et LSH pour trouver des titres similaires sans tous les comparer. Cinq titres de produits servent d'exemple.

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

Ce que vous saurez faire

Trouvez des paires de textes similaires, comme deux titres pour un même boyau, sans comparer toutes les paires. Apprenez les trois étapes de MinHash LSH : fragments, signatures et bandes. Puis mesurez ses résultats sur les deux flux fournisseurs 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.

Carnet JupyterFragments, signatures et bandes dans un carnet JupyterColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter calcule les fragments et la similarité de Jaccard des cinq titres. Vous écrivez vous-même une petite version de MinHash. Vous constatez que son accord est proche de la similarité de Jaccard. Puis vous bloquez les deux flux fournisseurs avec la bibliothèque datasketch et mesurez le résultat. Ses cellules de préparation téléchargent les données. Aucune préparation 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 40 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

  • Le projet larkfield-match avec les fichiers de blocage de la dernière leçon. Ou utilisez seulement le carnet.

Imaginez une bibliothécaire qui reçoit deux listes de nouveaux livres provenant de deux magasins. Une liste indique « The Garden Year, by A. Morel, paperback ». L’autre indique « Morel – garden year (the), pbk ». C’est le même livre. Aucun champ ne correspond exactement : ni le titre, ni l’auteur, ni le format. Mais les deux lignes partagent la plupart de leurs morceaux : « garden », « year », « morel ».

Hana, responsable du marchandisage chez Larkfield, a le même problème avec les deux flux fournisseurs. Northfield Supply envoie 4 460 produits, et Copperleaf Wholesale en envoie 3 501. Voici cinq de leurs titres :

Titre Flux Identifiant du produit
A Mossway Vinyl Garden Hose 30 ft Brown Northfield NF-03673
B gdn hose 9.1 m vinyl brown MOSSWAY Copperleaf CL-03459
C Mossway Vinyl Garden Hose 30 ft Brown Pack of 2 Northfield NF-02877
D Copperwren Ceramic Planter 12 in Black Northfield NF-01651
E planter 30.5 cm ceramic black Copperwren Copperleaf CL-00741

Nous avons seulement retiré la ponctuation. Les mots restent tels qu’ils apparaissent dans les flux. A et B désignent un même boyau : 30 pieds équivalent à 9,1 mètres. D et E désignent un même pot de fleurs : 12 pouces équivalent à 30,5 centimètres. C est un paquet de deux boyaux : un autre produit, créé exprès comme problème d’exercice. Tous les flux sont synthétiques.

Le problème : aucune clé ne fonctionne pour les titres

Section intitulée « Le problème : aucune clé ne fonctionne pour les titres »

Essayez les clés de la dernière leçon. La clé fondée sur le titre échoue : aucun de ces titres n’est identique à un autre. Le premier mot échoue : « Mossway » contre « gdn », et « Copperwren » contre « planter ». La marque fonctionne ici, après conversion en minuscules, mais elle crée d’énormes blocs. Chaque produit Mossway d’un flux rencontre chaque produit Mossway de l’autre.

Sur les flux complets, la clé de marque crée 783 869 paires candidates. Elle conserve les 2 750 vraies paires, mais élimine seulement 95 % des 15 614 460 paires possibles.

Voici ce que nous voulons : une paire devient candidate quand les deux titres sont similaires, pas identiques. Nous devons trouver ces paires sans toutes les comparer, sinon nous revenons au point de départ.

Décidez d’abord ce que « similaire » veut dire. Découpez chaque titre en fragments (shingles) : toutes les suites de 3 caractères, après conversion en minuscules. « garden hose » donne « gar », « ard », « rde », « den », « en », « n h », « ho », « hos », « ose ». Un titre devient un ensemble de fragments. L’ordre des mots compte peu : « hose rubber » et « rubber hose » partagent la plupart de leurs fragments.

Deux ensembles sont similaires quand ils partagent beaucoup d’éléments. La similarité de Jaccard mesure cela :

Jaccard = les fragments présents dans les deux titres ÷ les fragments présents dans au moins un titre

Pour A et B : A a 35 fragments et B en a 32. Ils en partagent 19 et, ensemble, ils ont 48 fragments différents. Jaccard = 19 ÷ 48 = 0,396.

Voici les dix paires des cinq titres :

Paire Ce qu’elle représente Jaccard Accord MinHash (100 valeurs)
A–B un boyau, deux flux 0,396 0,4
A–C un boyau et son paquet de 2 0,778 0,79
B–C un boyau et un paquet de 2 0,351 0,37
D–E un pot de fleurs, deux flux 0,51 0,52
A–D, A–E, B–D, B–E, C–D, C–E un boyau et un pot de fleurs 0,000 à 0,037 0,00 à 0,03

Les vraies paires, A–B et D–E, ont un Jaccard de seulement 0,396 et 0,510. Le flux B écrit « gdn » pour « garden », utilise des mètres plutôt que des pieds et place la marque à la fin. Les paires boyau–pot de fleurs n’ont presque rien en commun. Le paquet de deux, C, est très proche de A (0,778) : le titre ajoute seulement « Pack of 2 ». La mauvaise paire A–C est donc beaucoup plus similaire que la vraie paire A–B. Le blocage doit conserver A–C comme candidate. L’étape de comparaison du module 4 doit ensuite reconnaître qu’il s’agit d’un autre produit.

Mais calculer le Jaccard de chaque paire exige encore de traiter toutes les paires. Il nous faut un raccourci.

Voici l’astuce, d’abord sous forme de jeu. Placez tous les fragments possibles dans une longue liste, dans un ordre aléatoire. Pour chaque titre, parcourez la liste et arrêtez-vous au premier fragment présent dans le titre. Notez-le. Faites cela pour les titres A et B.

Quelle est la probabilité que A et B donnent le même fragment? Chacun des 48 fragments présents dans A ou B a la même probabilité d’être le premier rencontré. A et B donnent le même fragment seulement si c’est l’un des 19 fragments partagés. La probabilité est donc 19 ÷ 48 : exactement la similarité de Jaccard.

Une partie donne seulement « identique » ou « différent ». Jouez donc 100 fois, avec un nouvel ordre aléatoire chaque fois. Les 100 résultats forment la signature MinHash du titre. La proportion de parties où A et B concordent estime leur Jaccard.

Dans le code, « un ordre aléatoire » est une fonction de hachage. Cette fonction transforme chaque fragment en un nombre qui semble aléatoire. « Le premier fragment dans l’ordre » est celui dont le hachage est le plus petit. C’est l’origine du nom : le hachage (hash) minimal.

Voici les 10 premières des 100 valeurs de A et B, tirées du code du cours :

Fonction de hachageABIdentiques?
151 792 71533 869 745non
253 569 09053 569 090oui
356 648 78256 648 782oui
4174 247 87024 318 687non
5794 414794 414oui
6106 014 239106 014 239oui
741 340 559110 631 880non
886 062 82056 026 171non
964 155 42363 732 843non
10124 509 585159 614 191non

A et B concordent sur 4 de ces 10 valeurs et sur 40 des 100 valeurs. Le Jaccard est 0,396. Le tableau des dix paires montre la même chose pour chaque paire. L’accord des 100 valeurs s’écarte du Jaccard de 0,03 au maximum.

Le point important : chaque signature est calculée à partir d’un seul titre. Aucune paire n’est comparée pour la créer. Une signature contient toujours 100 nombres, quelle que soit la longueur du titre.

Les signatures sont courtes, mais comparer chaque paire de signatures exige encore de traiter toutes les paires. La dernière étape, le hachage sensible à la localité (LSH), trouve les paires similaires sans boucle sur les paires.

Découpez chaque signature en bandes. Le projet utilise des signatures de 128 valeurs et 25 bandes de 5 valeurs chacune. Pour chaque bande, placez le titre dans un compartiment nommé selon ses 5 valeurs. Deux titres dans le même compartiment pour au moins une bande deviennent une paire candidate.

C’est encore du blocage : chaque bande est une clé, et les 25 bandes sont 25 clés combinées. Comme avec les cinq clés de la dernière leçon, une paire a besoin d’une seule bande en commun.

Deux titres, A : Mossway Vinyl Garden Hose 30 ft Brown, et B : gdn hose 9.1 m vinyl brown MOSSWAY. Étape 1, fragments : toutes les suites de 3 caractères, en minuscules; A en a 35, B en a 32, 19 sont partagés, 48 au total; Jaccard 19 / 48 = 0,396. Étape 2, signature : 100 fonctions de hachage; chacune conserve le plus petit hachage des fragments du titre; A et B concordent sur 40 valeurs sur 100, près du Jaccard de 0,40. Étape 3, bandes : le projet utilise 128 valeurs dans 25 bandes de 5 valeurs; les mêmes 5 valeurs dans une bande placent les deux titres dans le même compartiment, créant une paire candidate. Note : aucune paire n'est comparée aux étapes 1 à 3; chaque titre est traité seul; seules les paires qui partagent un compartiment sont comparées.
MinHash LSH en trois étapes, avec les titres A et B. Les étapes 1 et 2 utilisent 100 valeurs, comme l'exemple détaillé; le blocage du projet en utilise 128.
Description textuelle du diagramme

Les titres A et B passent par trois étapes. L’étape 1 découpe chaque titre en fragments de 3 caractères : 35 pour A et 32 pour B. Ils en partagent 19, sur 48 au total, donc la similarité de Jaccard est de 0,396. L’étape 2 crée une signature de 100 valeurs MinHash pour chaque titre. A et B concordent sur 40 valeurs, près du Jaccard. L’étape 3 découpe la signature en bandes de 5 valeurs. Les titres qui ont les mêmes 5 valeurs dans une bande se retrouvent dans le même compartiment. Ils deviennent une paire candidate. Aux étapes 1 à 3, chaque titre est traité seul. Seules les paires dans un compartiment sont comparées ensuite.

Pourquoi 5 valeurs par bande? Parce que cela crée une séparation nette entre les titres similaires et les autres.

Prenez une paire dont le Jaccard est s. Une valeur MinHash concorde avec une probabilité s. Les 5 valeurs d’une bande concordent avec une probabilité s⁵. La paire ne partage aucune bande seulement si les 25 bandes échouent toutes. Donc :

probabilité de devenir candidate = 1 − (1 − s⁵)²⁵

  • 25 bandes de 5 valeurs
  • Une bande de 5 valeurs (pointillés)
La probabilité qu'une paire devienne candidate, pour les 25 bandes de 5 valeurs du projet (seuil de 0,5). Calculée à partir de la formule, comme le fait datasketch pour choisir les bandes. Une seule bande (pointillés) est beaucoup trop stricte.
Description textuelle du graphique

Un graphique linéaire. L’axe horizontal représente la similarité de Jaccard de deux titres, de 0 à 1. L’axe vertical représente leur probabilité de devenir une paire candidate. La ligne pleine, 25 bandes de 5 valeurs, forme une courbe en S. Elle reste près de 0 jusqu’à une similarité de 0,2 (0,008). Elle atteint 0,059 à 0,3, 0,227 à 0,4, 0,548 à 0,5, 0,868 à 0,6, 0,99 à 0,7 et 1,0 dès 0,8. La ligne pointillée, une bande de 5 valeurs, reste basse : 0,03 à 0,5 et 0,17 à 0,7.

Lisez la courbe :

  • Une paire avec un Jaccard de 0,7 devient candidate 99 fois sur 100.
  • Une paire avec un Jaccard de 0,3 devient candidate environ 6 fois sur 100.
  • Une paire avec un Jaccard près de 0, comme le boyau et le pot de fleurs, ne devient presque jamais candidate.

Le milieu du S est le seuil. Le projet demande un seuil de 0,5 à datasketch. La bibliothèque choisit alors 25 bandes de 5 lignes pour 128 valeurs. Plus de lignes par bande rendent le S plus abrupt et le déplacent vers la droite. Plus de bandes le déplacent vers la gauche.

D–E, le pot de fleurs, a un Jaccard de 0,510, près du seuil. Avec ces bandes, sa probabilité de devenir candidate est d’environ 0,58. Pour une paire près du seuil, c’est environ une chance sur deux. A–B, le boyau, fait pire : avec un Jaccard de 0,396, sa probabilité est seulement d’environ 0,22. C’est une raison pour laquelle le MinHash du projet lit du texte nettoyé. Il lit la marque et les mots du titre, sans la taille ni le format, et « gdn » devient « garden ». Les unités comme « 30 ft » et « 9.1 m » ne réduisent alors plus la similarité.

Le projet offre trois méthodes de blocage pour les produits :

Fenêtre de terminal
match block --blocking p-brand
match block --blocking p-minhash
match block --blocking p-minhash-0.3
p-brand: 783,869 candidate pairs out of 15,614,460 possible pairs (7.27 s)
pair completeness 1.000 (2,750 of 2,750 true pairs kept); reduction ratio 0.949799
p-minhash: 118,700 candidate pairs out of 15,614,460 possible pairs (41.06 s)
pair completeness 0.999 (2,748 of 2,750 true pairs kept); reduction ratio 0.992398
p-minhash-0.3: 700,712 candidate pairs out of 15,614,460 possible pairs (24.96 s)
pair completeness 1.000 (2,750 of 2,750 true pairs kept); reduction ratio 0.955124

Il y a 4 460 × 3 501 = 15 614 460 paires possibles. Le projet apparie les produits seulement entre les deux flux. Un flux ne contient pas deux fois le même produit.

MinHash avec un seuil de 0,5 crée 6,6 fois moins de paires candidates que la marque. Il perd seulement 2 des 2 750 vraies paires. Le seuil plus bas de 0,3 les conserve toutes, mais crée presque autant de paires que la marque.

Les durées sont longues parce que notre portable était occupé. Le premier blocage de produits prépare aussi les produits. Sur un portable sans autre charge, p-minhash a pris 2,29 secondes.

Deux vraies paires sont perdues. Une clé peut-elle les retrouver? Certains produits ont un code-barres (GTIN) dans les deux flux. p-minhash+gtin ajoute le code-barres comme clé :

Fenêtre de terminal
match block --blocking p-minhash+gtin
p-minhash+gtin: 118,701 candidate pairs out of 15,614,460 possible pairs (10.64 s)
pair completeness 1.000 (2,749 of 2,750 true pairs kept); reduction ratio 0.992398

Une paire candidate de plus, et une vraie paire de plus. MinHash et les clés se combinent comme les clés entre elles : par une union. C’est le blocage par défaut du projet pour les produits. L’exhaustivité des paires s’affiche à 1,000, mais 1 vraie paire est encore perdue.

MinHash LSH trouve des voisins proches dans une grande collection sans comparer toutes les paires. Les moteurs de recherche trouvent des documents similaires de la même façon. Les plongements (embeddings), des listes de nombres qui décrivent le sens d’un texte, utilisent la même famille d’idées. Un index de plus proches voisins place les vecteurs similaires près les uns des autres. Une requête n’en examine donc que quelques-uns. Recherche et classement : trouver la meilleure correspondance utilise des plongements dans Recherche par le sens. RAG : créer une IA qui utilise vos données les utilise pour trouver des passages. Le module 6 essaie les plongements comme méthode de blocage pour les clients.

Utilisez-le pour les textes dont aucun champ n’est identique, mais qui partagent des mots : titres de produits, noms de sociétés, adresses sur une ligne, courtes descriptions.

Ne l’utilisez pas quand une bonne clé exacte existe. Pour les clients, les cinq clés conservent 0,9937 des vraies paires. Elles sont plus rapides et plus faciles à expliquer.

Ce que cela coûte :

  • Les paires près du seuil ont environ une chance sur deux. Choisissez le seuil selon le Jaccard de vos vraies paires et mesurez l’exhaustivité des paires.
  • Les textes courts sont bruités. Un nom de 10 caractères a seulement 8 fragments. Une faute de frappe en modifie jusqu’à 3.
  • Il voit les lettres, pas le sens. « 30 ft » et « 9.1 m » ne partagent aucun fragment. « Pack of 2 » en ajoute seulement quelques-uns. MinHash garde le boyau et son paquet de deux ensemble, ce qui convient au blocage. La décision revient à l’étape de comparaison.
  • Le texte doit être nettoyé. Le carnet applique le même seuil aux titres bruts, en minuscules, avec leurs tailles et leurs unités. Il conserve seulement 0,73 des vraies paires. Le texte nettoyé du projet, sans taille ni format, en conserve 0,9993.
  • Les mots courants créent de gros compartiments. Des mots comme « garden » ou « green » apparaissent dans des milliers de titres. Retirer la marque du texte, comme le fait le projet, ou les mots très courants garde les compartiments petits.

Erreur courante

Un seuil trop élevé

Symptôme : TermeTomásL’ingénieur en IA de Larkfield. Il propose souvent un raccourci rapide, et la leçon montre pourquoi il échoue. veut moins de paires candidates. Il fixe le seuil MinHash à 0,8. Le nombre de paires candidates baisse, tout comme le nombre de produits appariés. La paire de pots de fleurs D et E n’est jamais comparée.

Cause : le seuil est le milieu de la courbe en S. Avec un seuil de 0,8, une paire doit avoir un Jaccard d’environ 0,8 pour devenir candidate avec une probabilité de 50 %. Les pots de fleurs ont un Jaccard de 0,510, et le boyau dans deux unités, de 0,396. Les deux se trouvent bien en dessous du S. Beaucoup de vraies paires des flux leur ressemblent : mêmes mots dans un autre ordre, autre unité, autre casse.

Correction : choisissez le seuil selon vos vraies paires, pas selon le nombre de candidates. Examinez la similarité de Jaccard d’un échantillon de vraies paires étiquetées. Placez le seuil bien en dessous de la plupart de leurs valeurs. Puis mesurez l’exhaustivité des paires, comme le fait le projet avec match block. Le projet utilise 0,5.

Conséquence pour le travail en IA : un seuil de blocage règle le rappel de tout l’apparieur. Chaque vraie paire qu’il élimine est une correspondance manquée. Aucun modèle ultérieur, même excellent, ne peut la récupérer.

Vérifiez votre compréhension

Deux titres ont une similarité de Jaccard de 0,6. Avec les 25 bandes de 5 valeurs du projet, quelle est la probabilité qu'ils deviennent une paire candidate? Montrez le calcul.

Afficher la réponse

Une valeur concorde avec une probabilité de 0,6. Les 5 valeurs d’une bande concordent avec une probabilité de 0,6⁵ = 0,078. Une bande échoue avec une probabilité de 1 − 0,078 = 0,922. Les 25 bandes échouent avec une probabilité de 0,922²⁵ = 0,132. La paire devient donc candidate avec une probabilité de 1 − 0,132 = 0,868. La courbe en S montre la même valeur à 0,6.

Vérifiez votre compréhension

Pourquoi MinHash LSH ne compare-t-il pas toutes les paires, même s'il estime leur similarité de Jaccard?

Afficher la réponse

La signature de chaque titre se calcule uniquement à partir de ce titre : ses fragments et 128 fonctions de hachage. Ensuite, chaque titre entre dans un compartiment pour chaque bande, selon les valeurs de cette bande. Une recherche dans un dictionnaire trouve le compartiment, sans comparer les titres. Seuls les titres qui se retrouvent dans le même compartiment deviennent des paires candidates. Le travail augmente avec le nombre de titres et de bandes, pas avec le nombre de paires.

Vérifiez votre compréhension

MinHash fait du boyau A et de son paquet de deux, C, une paire candidate (Jaccard de 0,778). Hana dit : « Alors MinHash se trompe : ce sont des produits différents. » Que répondez-vous?

Afficher la réponse

Le blocage ne décide pas si les produits sont identiques. Il choisit seulement les paires à comparer. Les textes A et C sont très semblables, il faut donc les comparer. Un blocage qui les éliminerait éliminerait aussi beaucoup de vraies paires qui diffèrent de quelques mots. L’étape de comparaison doit repérer « Pack of 2 » (paquet de deux) et conclure que les produits sont différents. Le module 4 compare les tailles et les formats. Le module 6 montre que les plongements trouvent aussi ces deux titres très proches. Un blocage qui fait d’une mauvaise paire une candidate ne coûte qu’une comparaison. Un blocage qui élimine une vraie paire la perd définitivement.

Récapitulatif

  • Les fragments découpent un texte en suites de 3 caractères. La similarité de Jaccard de deux ensembles de fragments est le nombre de fragments communs ÷ le nombre total de fragments distincts. Titres A et B : 19 ÷ 48 = 0,396.
  • Une signature MinHash conserve le plus petit hachage des fragments pour chacune des nombreuses fonctions de hachage. La proportion de valeurs égales estime la similarité de Jaccard : A et B concordent sur 40 valeurs sur 100.
  • LSH découpe la signature en bandes et place chaque titre dans un compartiment par bande. Les titres qui partagent au moins un compartiment deviennent candidats. Avec 25 bandes de 5 valeurs, la probabilité est de 0,548 pour un Jaccard de 0,5 et de 0,99 pour 0,7.
  • Sur les flux de Larkfield, MinHash (0,5) produit 118 700 paires candidates sur 15 614 460 et conserve 2 748 vraies paires sur 2 750. Le code-barres comme clé supplémentaire en récupère une de plus.
  • MinHash voit les lettres, pas le sens ni les unités. Son seuil est un réglage du rappel.

Vous avez maintenant trois types de blocage : les clés, le voisinage trié et MinHash LSH. Ensuite, vous mesurez ce que chacun perd et choisissez des clés qui retrouvent les clients qui ont déménagé.

Leçon suivante : Ce que le blocage fait perdre