Bonjour à tous,
Avant de poser ma question, un peu de contexte : je travaille actuellement dans le cadre d'un projet où l'on utilise des fonctions de hachage. Je me suis penché en particulier sur la méthode de hachage nommée "Locality-Sensitive Hashing", utilisée pour résoudre le problème de recherche d'un plus proche voisin dans une base de données de départ. Cette méthode décrit plusieurs familles de fonctions différentes vérifiant toutes une propriété dite de "local-sensibilité" ou "local-sensitivity en anglais".
Cette propriété s'énonce de la façon suivante :
Soitl'ensemble de données de départ,
Cette famille est dite
Une des familles de fonctions de hachage les plus utilisées est la famille de fonctions suivante, connue sous le nom de "projection aléatoire" :
Je précise suite à une remarque que l'on m'a faite, que dans le cas présent, a et b sont des valeurs/vecteurs générés selon une loi aléatoire, mais qui ne changent pas pour une fonction donnée. On peut donc, si on le souhaite, les considérer comme des observations des dites lois.
J'ai choisi la norme euclidienne comme distance D. Cela est dû au fait que a est un vecteur de variables gaussiennes, et que cette loi est 2-stable, ce qui permet de résoudre une partie du problème. (je pourrais prendre n'importe quelle norme Lp et la distribution p-stable associée, cela ne changerait à priori pas).
Je souhaiterais avoir la démonstration que cette famille de fonction vérifie bien la propriété de local-sensibilité.
J'ai au départ cherché dans plusieurs papiers de recherche une démonstration permettant d'expliquer cela, et le papier disponible à l'adresse suivante donne déjà un début d'explication : https://www.cs.princeton.edu/courses...p253-datar.pdf
En particulier, mon attention s'est portée sur la probabilité de collision de deux vecteurs, c'est-à-dire la probabilité que deux vecteurs soient hachés par la même fonction à la même valeur de hachage. Dans le papier (page 3), les chercheurs prennent deux vecteurs v1 et v2, et posent
Où la fonction f2 est la densité de probabilité d'une variable gaussienne centrée réduite.
J'ai essayé de retrouver cette probabilité en refaisant la démonstration, et j'obtiens presque la même formule, mais sans le terme (1-t/w). J'ai procédé de la façon suivante :
L'égalité suivante implique qu'il existe un entier N tel que l'intérieur des parties entières soit compris entre N et N+1. Pris autrement, cela veut dire que la différence de l'intérieur des parties entières est inférieur à 1 en valeur absolue :
Ici, on justifie que par la propriété de 2-stabilité de la variable gaussienne, la variable
On obtient alors :
En procédant au changement de variable
Il y a donc deux différences avec la formule donnée dans le papier : le facteur 2 qui apparaît, et le terme (1-t/w) qui n'apparaît pas.
J'ai cherché une explication à ces différences et je suis tombé sur l'article suivant : https://cseweb.ucsd.edu/~dasgupta/25...s/lawrence.pdf.
La personne fait la démonstration pour une fonction de hachage page 3, et écrit la phrase suivante : "We get a collision if both |<x,g>-<q,g>| < w and a divider does NOT fall between <x,g> and <q,g>". (Ici, g = a, x = v1, q = v2).
Traduit, cela donne : "Nous obtenons une collision si |<x,g>-<q,g>| < w et si un diviseur ne tombe PAS entre <x,g> et <q,g>".
Après réflexion, j'ai déduit qu'il me manquait effectivement une deuxième condition au moment où je me défausse des parties entières, mais je n'arrive pas à la formaliser.
Je n'ai absolument aucune idée du diviseur dont cette personne parle, ni de ce qu'il est censé diviser. Je ne sais pas non plus pourquoi seule la première condition ne suffit pas. Je soupçonne que cela a à voir avec le biais uniforme b, mais je n'arrive pas à aller plus loin.
En bref, je souhaiterais donc savoir comment résoudre mon problème.
Merci d'avance pour votre aide.
Cordialement,
-----