Locality-Sensitive Hashing et calcul de probabilité d'une fonction aléatoire.

[Kikumachi]

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 :

Soit l'ensemble de données de départ, une distance (ou norme), U l'ensemble des valeurs possibles des images des fonctions de hachage, et une famille de fonctions de hachage.

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" : avec :



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 , et ils trouvent alors une valeur de :
.

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 possède la même distribution que la variable , avec c la norme 2 de v1-v2 et A une variable aléatoire gaussienne.
On obtient alors :



En procédant au changement de variable , on obtient alors :



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,
-----

[minushabens]

bonjour, tu introduis des ensembles X,U,H mais dans ta définition de la sensibilité intervient un ensemble S dont tu n'as pas parlé. D'autre part, peux-tu préciser ce que tu entends par "fonction de hachage" et par "collision"?

[Kikumachi]

Bonjour,

Pour l'ensemble Il s'agit d'une erreur de ma part, c'est en fait l'ensemble , qui dans mon cas équivaut à un sous-ensemble de l'espace . dans la définition j'aurais donc du marquer
L'ensemble dépend des familles de fonctions de hachage que l'on prend, mais ici comme on prend des entiers il s'agit de l'ensemble des entiers relatifs .
L'ensemble est donc l'ensemble des fonctions associant un élément de à un élément de .

Une fonction de hachage est, dans le cas général, une fonction de compression des données d'un espace à plusieurs dimensions dans un espace à moins de dimensions, on les utilise lorsque notre sous-ensemble d'éléments de départ couvre de façon assez disparate l'ensemble de départ, afin de pouvoir ensuite procéder à des classifications. Très souvent, ça revient à associer à un élément de départ multidimensionnel une chaîne de caractères ou un chiffre, qui sont de dimension 1.

Une "collision" définit le phénomène qui se passe quand, pour une fonction de hachage donnée, deux éléments distincts de l'ensemble de départ se voient associés la même valeur de hachage.

Il peut exister des fonctions de hachage cryptographiques, comme des fonctions de hachage non-cryptographiques. La différence majeure entre ces deux catégories est que l'on cherche à ce qu'il soit impossible d'avoir une collision pour une fonction de hachage cryptographique, tandis que des fonctions non-cryptographiques peuvent entraîner des collisions, et que l'on essaie en général de contrôler ce phénomène, sans l'éliminer, comme dans le cas présent où l'on souhaite utiliser une fonction qui permet d'augmenter la probabilité de collision au fur et à mesure que deux vecteurs sont de plus en plus proches.

[minushabens]

ok je comprends. Si X est une partie finie de R^n et si tu le projettes sur une droite aléatoire, alors la probabilité que cette fonction ne soit pas injective (i.e. qu'il y ait collision) est nulle. La non injectivité vient bien sûr quand tu prends la partie entière de la projection. La fonction partie entière est tout sauf injective. Si tu as le choix de w tu peux faire en sorte de faire disparaître les collisions.

[A voir en vidéo sur Futura]

[Kikumachi]

Mon but n'est pas de faire disparaître les collisions, mais d'augmenter la probabilité de collision pour deux vecteurs proches d'au plus une certaine distance r1. Je prends deux vecteurs v1 et v2 tels que v1 appartienne à la boule de centre v2 et de rayon r1, et je cherche à calculer mathématiquement la probabilité qu'il y ait collision, ce qui se traduit par la démonstration que j'ai postée plus haut.

Vous dites que la probabilité que la fonction ne soit pas injective est nulle. Mais ayant déjà implémenté un algorithme pour n = 4, j'obtiens des collisions (grâce à cette partie entière). Je suis donc un peu perdu suite à votre dernière réponse.

[minushabens]

bonjour, le facteur 2 vient du fait que dans l'article les auteurs prennent pour f_2 la densité de la valeur absolue d'une variable gaussienne.

ensuite tu écris que [x]=[y] ssi |x-y|<=1 (je note [.] la partie entière) mais ça n'est pas vrai.

[Kikumachi]

Bonjour,

le facteur 2 vient du fait que dans l'article les auteurs prennent pour f_2 la densité de la valeur absolue d'une variable gaussienne.

Je viens de relire l'article et en effet, ce détail m'avait échappé, merci beaucoup.

ensuite tu écris que [x]=[y] ssi |x-y|<=1 (je note [.] la partie entière) mais ça n'est pas vrai.

Oui, j'ai écrit cela, mais j'ai effectivement remarqué un peu plus tard qu'il manquait une condition à droite du "ssi" pour qu'il y ait équivalence. Prenons les événements suivants :

A : "[x] = [y]".
B : "|x-y|<=1"
Je sais que A => B, mais B =/> A, il doit donc exister un évènement C tel que : A <=> (B ET C), et donc P(A) = P(B ET C)

Mais je n'arrive pas à formaliser l'événement C et c'est ce qui me bloque dans la poursuite de la démonstration.

[minushabens]

je pense que tu as éliminé b dans ton calcul alors qu'en fait il joue un rôle.

[Kikumachi]

J'y ai pensé, mais je ne vois pas comment formaliser ce rôle. J'ai pensé à quelque chose comme une probabilité conditionnelle sur b, ou une loi conjointe sur a/b, mais je n'ai vraiment aucune idée.

Dans le second papier, il est fait mention d'un "diviseur" ou "dividende" mais c'est expliqué de façon tellement opaque que cela m'embrouille encore plus.

[minushabens]

Il faut je pense écrire [x]=[y] = U([x]=n et [y]=n) (l'union porte sur n entier). Ensuite il faut prendre l'espérance par rapport à la loi conjointe de a et b. Je suppose qu'ils sont indépendants, donc la densité va être le produit des densités.

[Kikumachi]

En suivant vos conseils, j'obtiens la formule :



Ensuite vous me dites de prendre l'espérance, mais prendre l'espérance de quoi exactement ? Je dois faire en sorte de rajouter un "n" à côté de la formule pour avoir quelque chose s'apparentant à une espérance ?

[minushabens]

l'espérance c'est la probabilité ici.

[Kikumachi]

l'espérance c'est la probabilité ici.

J'avoue avoir du mal à comprendre, mais soit...

a et b sont bien indépendants en tout cas. Si j'ai bien compris, j'ai donc :



Ensuite comment je fais pour retrouver la partie incomplète de ma démonstration ?

[minushabens]

Le passage de première à la deuxième ligne n'est pas correct car les événements ne sont pas indépendants. Mais je me demande si je ne t'ai pas induit en erreur. Tu n'es peut-être pas obligé de développer en somme sur n. Je vais y réfléchir si j'ai le temps. En tout cas le facteur qui manque dans l'intégrale vient clairement de la loi de b, et je ne vois pas comment l'introduire sans passer par la somme sur n (pour le moment).

[Kikumachi]

Le passage de première à la deuxième ligne n'est pas correct car les événements ne sont pas indépendants. Mais je me demande si je ne t'ai pas induit en erreur. Tu n'es peut-être pas obligé de développer en somme sur n. Je vais y réfléchir si j'ai le temps. En tout cas le facteur qui manque dans l'intégrale vient clairement de la loi de b, et je ne vois pas comment l'introduire sans passer par la somme sur n (pour le moment).

Je vois, je vous remercie.