Hachage sensible à la localité

But : trouver les documents ayant une similarité Jaccard d’au moins t

L’idée générale de LSH est de trouver un algorithme tel que si nous entrons les signatures de 2 documents, il nous dise que ces 2 documents forment une paire candidate ou non c’est-à-dire que leur similarité est supérieure à un seuil t. Rappelons que nous prenons la similarité des signatures comme un proxy de la similarité de Jaccard entre les documents originaux.

Spécifiquement pour la matrice de signature min-hash:

• Hachage des colonnes de la matrice de signature M en utilisant plusieurs fonctions de hachage
• Si 2 documents hachent dans le même bucket pour au moins une des fonctions de hachage nous pouvons prendre les 2 documents comme une paire candidate

Maintenant la question est de savoir comment créer différentes fonctions de hachage. Pour cela nous faisons une partition de bande.

Partition par bandes

Voici l’algorithme :

• Diviser la matrice de signature en b bandes, chaque bande ayant r lignes
• Pour chaque bande, hacher sa portion de chaque colonne vers une table de hachage avec k buckets
• Les paires de colonnes candidates sont celles qui hachent vers le même bucket pour au moins 1 bande
• Tune b et r pour attraper la plupart des paires similaires mais peu de paires non similaires

Il y a quelques considérations ici. Idéalement, pour chaque bande, nous voulons prendre k comme étant égal à toutes les combinaisons possibles de valeurs qu’une colonne peut prendre dans une bande. Cela sera équivalent à une correspondance d’identité. Mais de cette façon, k sera un nombre énorme, ce qui est infaisable sur le plan informatique. Par exemple, si une bande contient 5 rangées. Maintenant si les éléments de la signature sont des entiers de 32 bits alors k dans ce cas sera (2³²)⁵ ~ 1.4615016e+48. Vous pouvez voir quel est le problème ici. Normalement, k est pris autour de 1 million.

L’idée est que si 2 documents sont similaires alors ils apparaîtront comme paire de candidats dans au moins une des bandes.

Choix de b & r

Si on prend b grand c’est-à-dire plus de fonctions de hachage, alors on réduit r car b*r est une constante (nombre de lignes dans la matrice de signature). Intuitivement, cela signifie que nous augmentons la probabilité de trouver une paire de candidats. Ce cas est équivalent à prendre un petit t (seuil de similarité)

Disons que votre matrice de signature a 100 lignes. Considérons 2 cas :

b1 = 10 → r = 10

b2 = 20 → r = 5

Dans le 2e cas, il y a plus de chances que 2 documents apparaissent dans le même seau au moins une fois car ils ont plus d’opportunités (20 vs 10) et moins d’éléments de la signature se font comparer (5 vs 10).

Un b plus élevé implique un seuil de similarité plus faible (faux positifs plus élevés) et un b plus faible implique un seuil de similarité plus élevé (faux négatifs plus élevés)

Essayons de comprendre cela à travers un exemple.

Mise en place:

• 100k documents stockés comme signature de longueur 100
• Matrice de signature : 100*100000
• La comparaison par force brute des signatures donnera lieu à 100C2 comparaisons = 5 milliards (pas mal !)
• Prenons b = 20 → r = 5

Seuil de similarité (t) : 80%

Nous voulons que 2 documents (D1 & D2) avec 80% de similarité soient hachés dans le même godet pour au moins une des 20 bandes.

P(D1 & D2 identiques dans une bande particulière) = (0,8)⁵ = 0,328

P(D1 & D2 ne sont pas similaires dans les 20 bandes) = (1-0,328)^20 = 0,00035

Ce qui signifie que dans ce scénario nous avons ~.035% de chance d’un faux négatif @ 80% de documents similaires.

En outre, nous voulons que 2 documents (D3 & D4) avec 30% de similarité ne soient pas hachés dans le même godet pour l’une des 20 bandes (seuil = 80%).

P(D3 & D4 identiques dans une bande particulière) = (0,3)⁵ = 0.00243

P(D3 & D4 sont similaires dans au moins une des 20 bandes) = 1 – (1-0,00243)^20 = 0,0474

Ce qui signifie que dans ce scénario nous avons ~4,74% de chance d’avoir un faux positif @ 30% de documents similaires.

On voit donc que nous avons quelques faux positifs et peu de faux négatifs. Ces proportions vont varier avec le choix de b et r.

Ce que nous voulons ici est quelque chose comme ci-dessous. Si nous avons 2 documents qui ont une similarité supérieure au seuil alors la probabilité qu’ils partagent le même godet dans au moins une des bandes devrait être de 1 sinon 0.

Le pire cas sera si nous avons b = nombre de lignes dans la matrice de signature comme indiqué ci-dessous.

Le cas généralisé pour tout b et r est montré ci-dessous.

Choisir b et r pour obtenir la meilleure courbe S i.e minimum de taux de faux négatifs et de faux positifs

Résumé de l’HLS

• Tune M, b, r pour obtenir presque toutes les paires de documents avec des signatures similaires, mais éliminer la plupart des paires qui n’ont pas de signatures similaires
• Vérifier en mémoire principale que les paires candidates ont vraiment des signatures similaires

.