Locality sensitive hashing

Locality sensitive hashing (LSH) est une méthode de recherche approximative dans des espaces de grande dimension. C'est une solution au problème de la malédiction de la dimension qui apparait lors d'une recherche des plus proches voisins en grande dimension. L'idée principale est d'utiliser une famille de fonction de hachage choisies telles que des points proches dans l'espace d'origine aient une forte probabilité d'avoir la même valeur de hachage. La méthode a de nombreuses applications en vision artificielle, traitement automatique de la langue, bio-informatique[citation nécessaire]

DéfinitionModifier

Une famille LSH   est définie pour un espace métrique  , un seuil   et un facteur d'approximation   [1],[2]. En pratique, on a souvent  .

  est une famille de fonctions   satisfaisant les conditions suivantes pour deux points quelconques  , et une fonction   choisie aléatoirement parmi la famille   :

  • si  , alors  
  • si  , alors  

Par construction, les fonctions de hachage doivent permettre aux points proches d'entrer fréquemment en collision (i.e.  ) et inversement, les points éloignés ne doivent entrer que rarement en collision. Pour que la famille LSH soit intéressante, il faut donc  . La famille   est alors appelée  -sensitive. La famille est d'autant plus intéressante si   est très supérieure à  .

Une définition alternative[3] est définie par rapport à un univers   possédant une fonction de similarité  . Une famille LSH est alors un ensemble de fonctions de hachage   et une distribution de probabilité   sur les fonctions, telle qu'une fonction   choisie selon   satisfait la propriété   pour tout  .

ApplicationsModifier

LSH a été appliqué dans plusieurs domaines, en particulier pour la recherche d'image par le contenu, la comparaison de sequence d'ADN[4], la recherche par similarité de documents audios.

MéthodesModifier

Échantillonnage par bit pour la distance de HammingModifier

L'échantillonnage de bit[2],[5] est une méthode simple permettant de construire une famille LSH. Cette approche est adaptée à la distance de Hamming dans un espace binaire de dimension   , i.e. quand un point de l'espace appartient à  . La famille   de fonctions de hachage est alors l'ensemble des projections sur une des   coordonnées, i.e.,  , où   est la ie coordonnée de  . Une fonction aléatoire   de   ne fait donc que sélectionner un bit au hasard dans le vecteur   d'origine.

Cette famille possède les paramètres suivants :

  •  
  •  .

L'algorithme LSH pour la recherche de plus proches voisinsModifier

L'application principale de LSH est de fournir un algorithme efficace de recherche des plus proches voisins.

L'algorithme donne une méthode de construction d'une famille LSH   utilisable, c'est-à-dire telle que  , et ceci à partir d'une famille LSH   de départ. L'algorithme a deux paramètres principaux : le paramètre de largeur   et le nombre de tables de hachage  .

Pré-traitement

En pré-traitement, l'algorithme définit donc une nouvelle famille   de fonctions de hachage  , où chaque fonction   est obtenue par concaténation de   fonctions   de  , i.e.,  . En d'autres termes, une fonction de hachage aléatoire   est obtenue par concaténation de   fonctions de hachage choisies aléatoirement dans  .

L'algorithme construit ensuite   tables de hachage, correspondant chacune à une fonction de hachage  . La je table de hachage contient alors les points de   hachés par la fonction  . Seules les positions non-vides des tables de hachage sont conservées, en utilisant un hachage standard des valeurs de  . Les tables de hachage résultats n'ont alors que   entrées (non-vides), réduisant l'espace mémoire par table à   et donc   pour la structure de donnée totale.

Recherche d'un point requête  

Pour un point requête  , l'algorithme itère sur les   fonctions de hachage  . Pour chaque   considérée, on trouve les points hachés à la même position que le point requête   dans la table correspondante. Le processus s'arrête dès qu'un point r est trouvé tel que  .

Étant donné les paramètres   et  , l'algorithme a les garanties de performance suivantes :

  • temps de pré-traitement :  , où   est le temps d'évaluation d'une fonction   d'un point  ;
  • mémoire :  
  • temps de requête :  ;
  • l'algorithme a une probabilité de trouver un point à une distance   de la requête   (si un tel point existe) avec une probabilité  .

Notes et référencesModifier

  1. (en) Gionis, P. Indyk et Rajeev Motwani, « Similarity Search in High Dimensions via Hashing », Proceedings of the 25th Very Large Database (VLDB) Conference,‎ (lire en ligne)
  2. a et b (en) Piotr Indyk et Rajeev Motwani, « Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. », Proceedings of 30th Symposium on Theory of Computing,‎ (lire en ligne)
  3. (en) Moses S. Charikar, « Similarity Estimation Techniques from Rounding Algorithms », Proceedings of the 34th Annual ACM Symposium on Theory of Computing 2002,‎ , (ACM 1–58113–495–9/02/0005)… (DOI 10.1145/509907.509965, lire en ligne, consulté le 21 décembre 2007)
  4. Jeremy Buhler, Efficient large-scale sequence comparison by locality-sensitive hashing, Bioinformatics 17: 419-428.
  5. (en) Alexandr Andoni et Piotr Indyk, « Near-optimal hashing algorithm for approximate nearest neighbour in high dimensions », Communications of the ACM, Vol. 51,‎ (lire en ligne)

Voir aussiModifier

Articles connexesModifier

Liens externesModifier