Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Locality sensitive hashing
Résumé
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...
Une famille LSH est définie pour un espace métrique , un seuil et un facteur d'approximation
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 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 .
LSH a été appliqué dans plusieurs domaines, en particulier pour la , la comparaison de sequence d'ADN, la recherche par similarité de documents audios.
L'échantillonnage de bit 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 i coordonnée de .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.