Ê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.
Proximité ontologique
Cours associés (3)
CS-450: Algorithms II
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
CS-422: Database systems
This course is intended for students who want to understand modern large-scale data analysis systems and database systems. It covers a wide range of topics and technologies, and will prepare students
Séances de cours associées (21)
Recherche du voisin le plus proche: Johnson-Lindenstrauss Lemma
Couvre l'algorithme de recherche le plus proche du voisin et le lemme de Johnson-Lindenstrauss pour la réduction de la dimensionnalité, en explorant les techniques de prétraitement et le hachage sensible à la localité.
Indépendance par paire: hachage et équilibrage de charge
Explore l'indépendance par paire dans le hachage pour éviter les collisions et atteindre l'équilibrage de charge.
La malédiction de la dimensionnalité dans l'apprentissage profond
Se penche sur les défis de l'apprentissage profond, en explorant la dimensionnalité, les performances et les phénomènes sur-adaptés dans les réseaux neuronaux.
Publications associées (33)
Personnes associées (6)
Concepts associés (6)
Recherche des plus proches voisins
La recherche des plus proches voisins, ou des k plus proches voisins, est un problème algorithmique classique. De façon informelle le problème consiste, étant donné un point à trouver, dans un ensemble d'autres points, quels sont les k plus proches. La recherche de voisinage est utilisée dans de nombreux domaines, tels la reconnaissance de formes, le clustering, l'approximation de fonctions, la prédiction de séries temporelles et même les algorithmes de compression (recherche d'un groupe de données le plus proche possible du groupe de données à compresser pour minimiser l'apport d'information).
Fléau de la dimension
Le fléau de la dimension ou malédiction de la dimension (curse of dimensionality) est un terme inventé par Richard Bellman en 1961 pour désigner divers phénomènes qui ont lieu lorsque l'on cherche à analyser ou organiser des données dans des espaces de grande dimension alors qu'ils n'ont pas lieu dans des espaces de dimension moindre. Plusieurs domaines sont concernés et notamment l'apprentissage automatique, la fouille de données, les bases de données, l'analyse numérique ou encore l'échantillonnage.
Réduction de la dimensionnalité
vignette|320x320px|Animation présentant la projection de points en deux dimensions sur les axes obtenus par analyse en composantes principales, une méthode populaire de réduction de la dimensionnalité La réduction de la dimensionnalité (ou réduction de (la) dimension) est un processus étudié en mathématiques et en informatique, qui consiste à prendre des données dans un espace de grande dimension, et à les remplacer par des données dans un espace de plus petite dimension.