Détection de quasi-doublons avec la similarité de Jaccard et MinHash

 (blog.nelhage.com)
1 points par GN⁺ 2024-07-06 | 1 commentaires | Partager sur WhatsApp
  • Dans de grandes collections de documents, le crawling web peut récupérer plusieurs fois la même page ou y mêler de petites variantes, ce qui fait de la similarité de Jaccard et de MinHash une méthode pratique pour trouver des documents « presque identiques »
  • La similarité de Jaccard transforme les documents en ensembles de caractéristiques, puis calcule la taille de l’intersection / la taille de l’union ; les paires au-dessus d’un certain seuil sont considérées comme des quasi-doublons, mais cette relation n’est généralement pas transitive
  • Comparer toutes les paires de documents coûte O(n²) par rapport à la taille du corpus ; MinHash résume donc chaque document en une signature de taille fixe afin d’approximer probabilistiquement la similarité
  • Avec k fonctions de hachage, on peut estimer la similarité à partir de la proportion de positions identiques dans les signatures de deux documents, et le choix des fonctions de hachage dépend de propriétés importantes comme la min-wise independence
  • Utiliser la signature complète ou certaines de ses parties comme clé de groupement permet d’ajuster la probabilité que des documents similaires tombent dans le même bucket, tandis que les n-grammes et la tokenisation déterminent la sensibilité de détection et le coût

La difficulté de la détection de quasi-doublons

  • L’objectif est de trouver, dans un grand ensemble de documents, des documents qui ne sont pas exactement identiques mais presque
    • Lorsqu’on crawl le web sur une certaine période, on peut récupérer plusieurs fois la même page avec des métadonnées légèrement différentes
    • Il peut aussi exister plusieurs petites révisions d’une même page
  • L’approche de base consiste à définir une fonction de similarité S(A, B) entre deux documents, puis à considérer comme quasi-doublons les paires dont la valeur dépasse un seuil Scrit
  • Le fait d’être « presque identique » n’est généralement pas une relation transitive
    • A et B, ainsi que B et C, peuvent être similaires au-dessus du seuil
    • Mais A et C peuvent en même temps se situer en dessous du seuil
    • C’est pourquoi la détection de quasi-doublons à grande échelle est plus difficile à traiter que la détection de doublons exacts

Définition de la similarité de Jaccard

  • Le Jaccard index exprime la similarité entre deux ensembles finis comme la taille de l’intersection / la taille de l’union

    [ J(A, B) = \frac{|A \cap B|}{|A \cup B|} ]

  • Si deux ensembles se ressemblent, ils partagent la plupart de leurs éléments ; leur union augmente donc peu et leur intersection diminue peu

  • Si deux ensembles sont totalement disjoints, la taille de l’intersection est 0, donc la similarité de Jaccard vaut 0

  • Si deux ensembles sont identiques, l’intersection et l’union correspondent toutes deux au même ensemble, donc la similarité de Jaccard vaut 1

  • Comme les documents réels prennent la forme de chaînes Unicode ou équivalent, il faut d’abord les transformer en ensembles de caractéristiques

Le problème de passage à l’échelle des comparaisons toutes paires

  • Une fois les documents transformés en ensembles de caractéristiques, la définition consistant à chercher les paires à forte similarité de Jaccard est simple en soi
  • Mais comparer toutes les paires de documents fait croître le coût en O(n²) par rapport à la taille du corpus
  • Pour la détection de doublons exacts, on évite ce coût en hachant les documents et en regroupant ceux qui tombent dans le même bucket de hachage
  • La détection de quasi-doublons a elle aussi besoin d’un contournement similaire ; dans ce domaine, on parle de hachage sensible à la localité (locality-sensitive hash)
  • Pour la similarité de Jaccard, il existe une technique adaptée à cet usage, dont le cœur est MinHash

Approximer la similarité de Jaccard avec MinHash

  • MinHash permet d’approximer la similarité de Jaccard sans comparer l’ensemble complet à chaque fois, en utilisant seulement une petite signature précalculée pour chaque document

  • L’idée de base est un échantillonnage consistant à tirer uniformément un élément aléatoire dans l’union, puis à vérifier si cet élément appartient aussi à l’intersection

  • En pratique, au lieu d’une permutation aléatoire, on utilise une bonne fonction de hachage H(x) et on conserve, pour chaque ensemble, la caractéristique dont la valeur de hachage est la plus petite

    [ a_{min} \leftarrow \min_{x \in A} H(x) ]

    [ b_{min} \leftarrow \min_{x \in B} H(x) ]

  • L’opération min étant associative, on peut prétraiter indépendamment la valeur de hachage minimale de chaque document

  • La probabilité que les valeurs minimales de hachage de deux ensembles soient identiques est égale à leur similarité de Jaccard

Plusieurs fonctions de hachage et vecteurs de signature

  • Avec une seule fonction de hachage, on n’obtient pour deux documents qu’une estimation booléenne de type « identique / différent »

  • Avec k fonctions de hachage différentes, chaque document peut être résumé en un vecteur de k valeurs MinHash

    [ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]

  • On approxime la similarité de Jaccard à partir de la proportion de positions égales dans les deux signatures

    [ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]

  • Le choix de la famille de fonctions de hachage est subtil

    • L’objectif est d’approximer une permutation aléatoire sur tout l’espace des caractéristiques
    • En pratique, une famille de fonctions de hachage ne représente qu’une infime partie de toutes les permutations possibles
    • Il faut éviter des corrélations inappropriées, et la propriété associée est appelée min-wise independence
    • Ce problème a été relativement bien étudié, et la littérature propose des solutions efficaces

Trouver les paires candidates dans l’ensemble du corpus

  • Réduire chaque document à une empreinte de k valeurs de hachage permet d’approximer efficacement la similarité de Jaccard
  • Le problème restant est de trouver, dans tout le corpus, les documents à forte similarité sans examiner toutes les paires
  • La stratégie consiste à regrouper les documents selon une certaine clé, puis à ne comparer qu’à l’intérieur de chaque groupe
  • La clé de groupement doit être conçue pour que les documents similaires aient une forte probabilité d’être regroupés ensemble, tandis que les documents dissemblables doivent autant que possible éviter de l’être

  • Utiliser la signature MinHash complète comme clé

    • La méthode la plus simple consiste à utiliser l’ensemble des k valeurs MinHash comme une seule clé de groupement
    • Deux documents ne sont considérés comme quasi-doublons que si toutes leurs valeurs MinHash coïncident
    • L’article GPT-3 indique que le pipeline de préparation du dataset utilisait une suppression des quasi-doublons et, d’après la formulation citée, cela semble renvoyer à l’implémentation MinHashLSH de Spark avec 10 fonctions de hachage
    • L’avantage de cette méthode est sa simplicité et son efficacité
    • Les opérations de groupement sur une unique chaîne d’octets à forte cardinalité se répartissent facilement horizontalement
    • Cela correspond aux primitives de base des outils de traitement de données, comme le « shuffle » entre map et reduce dans MapReduce
    • Si la similarité de Jaccard entre deux documents vaut J(A, B) et que les k valeurs doivent toutes coïncider, la probabilité de collision pour une paire donnée est J(A, B)^k
    • Avec k = 10, les documents de similarité inférieure à environ 0,6 entrent rarement en collision
    • La probabilité de correspondance devient importante aux alentours de 0,95 de similarité
    • Si l’objectif est de repérer des documents extrêmement proches, cela peut suffire
    • Ce calcul en J^k concerne une seule paire de documents
    • Lorsqu’il existe de nombreux documents très similaires, les probabilités par paire ne sont pas indépendantes
    • En pratique, des documents très similaires finissent souvent concentrés dans deux ou trois buckets au plus, ce qui permet de retrouver presque tous les doublons

Détection de doublons plus souple

  • Si l’on veut trouver non seulement des documents dont la similarité est proche de 1, mais aussi ceux à 0,8 ou 0,7 et plus, utiliser la signature complète comme clé peut être trop strict

  • Utiliser seulement une partie des k valeurs MinHash comme clé de groupement augmente la probabilité de collision même à plus faible similarité

    • Par exemple, on peut regrouper selon les 4 premières valeurs MinHash, puis estimer la similarité réelle à l’intérieur du même bucket à partir de la signature MinHash complète

  • Réduire le nombre de fonctions de hachage a toutefois ses limites

    • J^r est toujours plus petit que J
    • Si r devient trop petit, le nombre de collisions incorrectes peut devenir excessif

  • On peut à la place créer plusieurs clés par document et l’insérer dans plusieurs buckets

    • Par exemple, calculer k = 20 hachages, répartir dans b = 4 buckets, et construire chaque clé à partir de r = 5 hachages

  • La probabilité que deux documents entrent en collision dans au moins un bucket est alors la suivante

    [ p = 1 - (1 - J^r)^b ]

  • Dans cet exemple avec 4 groupes et 5 hachages par groupe, le point où la probabilité de collision atteint 50 % se déplace vers J = 0.7 environ

  • Quand r et b sont tous deux supérieurs à 1, la courbe résultante prend en général une forme en S, offrant un espace de réglage entre sensibilité, rappel et coût de performance

Lien avec HyperLogLog

  • L’astuce centrale de MinHash ressemble à celle d’algorithmes de sketch comme HyperLogLog
  • HyperLogLog hache chaque élément d’un flux et conserve le maximum courant du nombre de zéros initiaux dans la valeur de hachage
  • Les deux techniques projettent les éléments d’entrée vers une distribution uniforme via une fonction de hachage, puis calculent un extrême courant pour estimer des propriétés distributionnelles à partir d’un résumé de taille constante
  • Si l’on raisonne en inversant l’ordre des bits, HyperLogLog peut être vu comme le calcul du minimum courant de log2(H(x)), tandis que MinHash utilise le minimum de H(x) lui-même
  • Les deux structures sont en un certain sens duales
    • Combiner deux structures HyperLogLog permet d’estimer la taille de l’union de deux ensembles
    • Comparer deux structures MinHash permet d’estimer la taille relative de l’intersection de deux ensembles
  • En combinant les deux structures, on peut construire un sketch capable de répondre à des questions sur l’intersection et l’union d’ensembles arbitraires

Comment représenter un document comme un ensemble

  • Pour utiliser Jaccard et MinHash, il faut d’abord transformer un document textuel en ensemble de caractéristiques
  • Quelle que soit la méthode choisie, on peut normaliser le document au prétraitement

  • n-grammes ou shingles

    • On peut représenter un document comme l’ensemble de tous les n-grammes qu’il contient
    • Dans la littérature sur le traitement de texte à grande échelle, on emploie aussi le terme « shingle », mais il joue ici le même rôle que n-gramme
    • Le choix de la valeur de n implique un compromis
    • Une petite valeur compare les documents de façon plus grossière
    • Par exemple, une grande partie des textes anglais peuvent sembler assez similaires du point de vue des bigrammes
    • Une grande valeur produit des caractéristiques plus discriminantes et des ensembles plus volumineux
    • Si elle devient trop grande, la sensibilité peut baisser, mais des problèmes de performance risquent d’apparaître avant cela
    • D’après Mining of Massive Datasets §3.2.2, des valeurs comprises entre n = 5 et 9 sont un choix courant dans plusieurs applications

  • Découpage en mots ou en tokens

    • On peut aussi découper l’entrée en « mots » ou en « tokens », puis les utiliser comme caractéristiques
    • L’extrait de l’article GPT-3 mentionne le tokenizer standard de Spark, ce qui semble renvoyer à pyspark.ml.feature.Tokenizer, qui convertit l’entrée en minuscules puis la sépare sur les espaces
    • On peut également utiliser un tokenizer NLTK plus sophistiqué
    • Une approche hybride consistant à utiliser des n-grammes de tokens après tokenisation est également possible
    • Les tokens individuels ont une entropie plus élevée que les octets ou les caractères ; on utilise donc dans ce cas une valeur de n plus petite

À lire aussi

1 commentaires

 
GN⁺ 2024-07-06
Commentaires sur Hacker News

  • On oublie souvent que des métriques ensemblistes comme la similarité de Jaccard (coefficient de Tanimoto) ou le score F1 (coefficient de Dice) s’appliquent aussi telles quelles aux ensembles flous
    Il faut simplement choisir une paire appropriée de T-Norm / T-Conorm pour exprimer les notions d’intersection et d’union des ensembles flous, et il en existe une infinité
    C’est même plutôt un avantage, car cela permet de sélectionner une paire adaptée à la sémantique recherchée
    J’ai déjà abordé ce sujet dans le cadre de la validation de segmentation en imagerie médicale, lorsque le résultat de segmentation et la vérité terrain ne sont pas des masques binaires mais des formes probabilistes/floues : https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
    En général, on applique un seuil de 0.5 pour obtenir un ensemble binaire, puis on utilise une variante binaire de Jaccard/Dice, mais cela semble faire perdre environ deux chiffres de précision à l’opérateur de validation
    On annonce qu’un algorithme est meilleur de 0.001 que l’état de l’art, tout en ignorant que la marge d’erreur de l’opérateur de validation est en réalité de 0.1

  • Pour dédupliquer des enregistrements de citoyens dans une grande base de données du gouvernement français, un client avait autrefois développé sa propre implémentation Python de cette technique, et cela fonctionnait bien
    Aujourd’hui, je recommanderais sans doute datasketch : https://pypi.org/project/datasketch/
    En cherchant, j’ai vu que de nouveaux outils continuaient d’apparaître sur ce sujet. Par exemple, https://pypi.org/project/rensa/ est une version plus spécialisée et plus rapide du MinHash de datasketch, écrite en Rust avec une légère couche Python par-dessus

    • Pour la déduplication de personnes, le modèle de Fellegi-Sunter est aussi une approche puissante. Splink est une bibliothèque Python gratuite qui l’implémente pour de grands jeux de données, et il semble possible de combiner certains éléments des deux approches
      Je précise que j’en suis l’auteur principal
      J’ai aussi rédigé un tutoriel interactif expliquant son fonctionnement : https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
    • Il y a aussi gaoya. C’est moi qui l’ai créé, c’est écrit en Rust et cela propose également des bindings Python
      datasketch est excellent, mais les performances n’étaient pas suffisantes pour mon cas d’usage, et gaoya est utilisé dans un système de production de clustering à grande échelle : https://github.com/serega/gaoya

  • Quelle coïncidence incroyable. Je viens justement d’implémenter un système MinHash que quelqu’un pourrait trouver intéressant
    Le problème consiste à trouver la pseudo-inverse de plusieurs sous-matrices appropriées dans une grande matrice carrée
    En utilisant des identités matricielles comme Woodbury ou Banachiewicz, on peut mettre à jour l’inverse d’une sous-matrice « proche » pour calculer à faible coût une nouvelle inverse
    Il suffit de stocker les inverses déjà calculées en utilisant les indices de lignes/colonnes comme clé, puis de trouver pour chaque nouvelle sous-matrice une inverse existante proche servant de point de départ à la mise à jour
    J’ai résolu ce problème avec MinHash, en appliquant un min-hash aux indices afin d’augmenter la probabilité que des matrices proches aient le même hash
    Dans mon implémentation, j’ai utilisé un hash multi-résolution afin de pouvoir ajuster la sélectivité de recherche à mesure que le nombre d’inverses déjà calculées augmentait

  • Pour ajouter un peu de contexte absent de l’article, je pensais que cette technique avait été créée aux débuts de Google pour la déduplication des ensembles crawlés
    Il est aussi intéressant de voir à quel point construire des LLM ressemble étonnamment à la création d’un index classique de textes du web
    On peut en lire davantage dans le livre gratuit de Jeffrey Ullman, “Mining Massive Datasets”, qui décrit en détail beaucoup de techniques remarquables et impressionnantes utilisées à l’époque pour indexer l’ensemble d’Internet
    On peut trouver gratuitement les ressources associées en cherchant « chapter 3 pdf mmds ullman »
    Correction : il s’avère que j’avais tort et que, selon Wikipedia, cela a été inventé chez DEC pour AltaVista : https://en.wikipedia.org/wiki/MinHash
    Quoi qu’il en soit, le livre d’Ullman contient une bonne explication et couvre aussi son utilisation chez Google

  • En essayant de comprendre MinHash et ses variantes, j’avais du mal à me le représenter mentalement, donc je suis en train de créer un outil de visualisation en ligne : https://websla.sh/tools/minhash
    Ce n’est pas encore terminé et j’aimerais aussi montrer des choses comme le calcul de similarité de Jaccard, mais on peut déjà y saisir plusieurs chaînes et voir concrètement ce qu’est un « minhash »

  • L’usage du hashing ou de petits réseaux de neurones avec un moteur de recherche vectorielle et Tanimoto/Jaccard est une stratégie très courante pour la déduplication de grands jeux de données
    Cela peut être plus intelligent que d’utiliser un job MapReduce de complexité linéaire
    Il existe un bon projet de Google qui utilise le modèle RETSim à 500 000 paramètres et le moteur USearch : https://github.com/google/unisim

  • J’ai actuellement un problème similaire dans PostgreSQL. J’ai 600000 feed_items avec le schéma (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
    En particulier, les colonnes content et summary de certains éléments d’actualité sont très proches, mais pas identiques
    Étant donné deux éléments d’actualité de ce type, j’aimerais les réduire à un seul ; y a-t-il une bonne méthode pour cela ?

    • J’ai implémenté dans BigQuery un système proche de MinHash, et j’ai pu calculer la similarité cosinus entre tous les éléments de Stack Overflow dans un temps raisonnable
      La procédure est à peu près la suivante
      1. concaténer tous les champs de texte et les découper en un tableau de n-grammes, par exemple en unités de 2 à n caractères
      2. déclarer des tableaux globaux A et B de longueur n, et les remplir avec des entiers aléatoires de 32 à 64 bits
      3. hacher chaque n-gramme en un entier de 32 à 64 bits, puis multiplier ce hash par chacune des valeurs aléatoires du tableau A et prendre le reste de la division du résultat par chacune des valeurs aléatoires du tableau B, puis retenir le minimum
        L’objectif est d’obtenir, pour chaque ligne, un tableau d’entiers « minimisés par hash » de la même longueur que les tableaux de l’étape 2. Si la longueur des tableaux globaux est fixée à 64, alors le tableau MinHash de chaque ligne aura aussi une longueur de 64
      4. utiliser une fonction de fenêtre pour additionner N valeurs MinHash consécutives et répartir le tableau de hash dans des buckets. Par exemple, additionner chaque groupe de 4 lignes consécutives
        Si tout se passe bien, on peut déplier ce tableau pour en faire une « ligne source », puis faire une auto-jointure du dataset sur chaque valeur MinHash regroupée en buckets afin d’ajouter une colonne « ligne cible »
        En groupant par colonnes source/cible et en comptant les occurrences, on peut estimer à quel point deux lignes se ressemblent
        En substance, plus deux éléments sont hachés dans des buckets similaires, plus ils se ressemblent, et c’est à vous de décider à partir de quel seuil calculer la vraie similarité de Jaccard ou cosinus paire par paire
    • Ici, il pourrait être utile d’utiliser des embeddings de texte et la similarité cosinus : https://simonwillison.net/2023/Oct/23/embeddings/
    • MinHash permet d’éviter la matrice de distances O(N^2) complète, mais avec seulement 600000 éléments, il est peut-être acceptable de calculer toute la matrice de façon brutale pour garder les choses simples
      Tout dépend du budget temps disponible
    • Si vous considérez que les deux éléments traitent de mots-clés très proches, la distance de Jaccard conviendra probablement bien
      Si vous considérez qu’ils partagent un texte très proche, cela vaut la peine d’essayer la distance de Levenshtein
    • On peut demander à un LLM de construire un index inversé sur les éléments, tout en le contraignant à garder une cardinalité faible
      Cela permet ensuite d’utiliser la similarité de Jaccard

  • J’aime beaucoup cet article. Chez NVIDIA, notre équipe a récemment publié une version accélérée par GPU de l’algorithme de déduplication floue décrit, et je pense que cette communauté pourrait être intéressée
    Le dépôt est ici : https://github.com/NVIDIA/NeMo-Curator/
    La documentation du script de déduplication floue est ici : https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
    Il y a aussi un exemple Python : https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
    Je serais ravi d’avoir vos retours

  • Ce genre de technique est du type que je ne comprends pas en la lisant, mais que j’assimile immédiatement après avoir injecté mes données dans quelques exemples de code fonctionnels et observé le fonctionnement interne
    J’ai découvert cette technique pour la première fois grâce à Douglas Eck : https://research.google/people/douglas-eck/
    Elle a été utilisée chez Google pour le clustering de chansons, et je me souviens qu’on parlait de hashing et de vecteurs aléatoires
    À l’époque, cela me troublait, car je pensais qu’une optimisation avec moins d’aléatoire fonctionnerait mieux

    • L’intuition essentielle, du moins pour moi, est que si l’on découpe un objet en un tas de très petits fragments et que l’on crée n façons de trier ces tas, alors des objets similaires feront remonter les mêmes fragments en tête dans plusieurs tris
      En y ajoutant du banding et un peu de probabilité, on peut approximer la similarité de Jaccard sur d’énormes datasets de façon peu coûteuse et très facile à paralléliser

  • Si l’on considère cela comme une technique de clustering de documents ou de déduplication de datasets, comment l’approche consistant à « jeter du machine learning sur le problème » se compare-t-elle, en qualité et en performance, à une méthode algorithmique discrète plus simple comme celle-ci ?
    Par exemple, créer des embeddings vectoriels de documents avec un encodeur LLM préentraîné, placer ces vecteurs dans une vector DB, puis faire du clustering avec k-means

    • Un LLM n’est qu’une méthode parmi d’autres pour générer des embeddings
      Pour faire du k-means, il faut quand même choisir une fonction de distance comme Jaccard, et k-means n’est probablement pas idéal pour les quasi-doublons
      On peut aussi utiliser MinHash en prétraitement de k-means pour accélérer les choses
      Je ne pense pas qu’une vector DB apporte grand-chose
      Si vous avez des centaines de millions de documents, elle peut servir à accélérer les recherches de sketchs MinHash, mais dans l’ensemble ce sera probablement un choix excessif
    • J’ai déjà vu ce type d’approche mieux fonctionner que LSH
      Comme on recherche des plus proches voisins approximatifs avant d’ajouter chaque document embarqué, c’est en O(N), comme MinHash
      Les index vectoriels comme HNSW et PQ offrent de meilleurs compromis performance/qualité que SimHash LSH, l’équivalent de MinHash pour la distance cosinus
      La qualité dépend de la façon dont on définit les quasi-doublons et du modèle d’embedding utilisé
      Les modèles récents fonctionnent bien, et si vous avez des données annotées, un fine-tuning peut encore améliorer les résultats
      Le principal inconvénient est le coût supplémentaire d’embedding de tous les documents, particulièrement lourd pour les documents longs
      Mais ce coût a diminué très rapidement grâce aux petits modèles, à de meilleures optimisations et à un matériel plus rapide