Comment comprendre le hachage sensible à la localité?

J'ai remarqué que LSH semble un bon moyen de trouver des articles similaires avec des propriétés de grande dimension.

Après avoir lu l'article http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf , je suis toujours confus avec ces formules.

Est-ce que quelqu'un connaît un blog ou un article qui explique cela de manière simple?

Le meilleur tutoriel que j'ai vu pour LSH est dans le livre: Mining of Massive Datasets. Consultez le chapitre 3 - Recherche d'articles similaires http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Je recommande également la diapositive ci-dessous: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . L'exemple de la diapositive m'aide beaucoup à comprendre le hachage pour la similitude cosinus.

J'emprunte deux diapositives à Benjamin Van Durme & Ashwin Lall, ACL2010 et j'essaie d'expliquer un peu les intuitions des familles LSH pour la distance cosinus.

• Sur la figure, il y a deux cercles de couleur rouge et jaune , représentant deux points de données bidimensionnels. Nous essayons de trouver leur similitude cosinus en utilisant LSH.
• Les lignes grises sont des avions choisis au hasard de manière uniforme.
• Selon que le point de données se situe au-dessus ou au-dessous d'une ligne grise, nous marquons cette relation comme 0/1.
• Dans le coin supérieur gauche, il y a deux rangées de carrés blancs / noirs, représentant respectivement la signature des deux points de données. Chaque carré correspond à un bit 0 (blanc) ou 1 (noir).
• Ainsi, une fois que vous avez un pool d'avions, vous pouvez encoder les points de données avec leur emplacement respectif par rapport aux plans. Imaginez que lorsque nous avons plus de plans dans la piscine, la différence angulaire encodée dans la signature est plus proche de la différence réelle. Parce que seuls les plans qui résident entre les deux points donneront aux deux données une valeur de bit différente.

• Regardons maintenant la signature des deux points de données. Comme dans l'exemple, nous n'utilisons que 6 bits (carrés) pour représenter chaque donnée. Il s'agit du hachage LSH pour les données originales dont nous disposons.
• La distance de martelage entre les deux valeurs hachées est de 1, car leurs signatures ne diffèrent que d'un bit.
• Compte tenu de la longueur de la signature, nous pouvons calculer leur similitude angulaire comme indiqué dans le graphique.

J'ai ici un exemple de code (seulement 50 lignes) en python qui utilise la similitude cosinus. https://gist.github.com/94a3d425009be0f94751

Les tweets dans l'espace vectoriel peuvent être un excellent exemple de données de grande dimension.

Consultez mon article de blog sur l'application du hachage sensible à la localité aux tweets pour en trouver des similaires.

http://micvog.com/2013/09/08/storm-first-story-detection/

Et parce qu'une image vaut mille mots, vérifiez l'image ci-dessous:

http://micvog.files.wordpress.com/2013/08/lsh1.png

J'espère que ça aide. @mvogiatzis

Voici une présentation de Stanford qui l'explique. Cela a fait une grande différence pour moi. La deuxième partie est plus consacrée au LSH, mais la première la couvre également.

Une image de l'aperçu (il y en a beaucoup plus dans les diapositives):

Recherche de voisins proches dans les données haute dimension - Partie 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Recherche de voisins proches dans les données haute dimension - Partie 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

• LSH est une procédure qui prend en entrée un ensemble de documents / images / objets et génère une sorte de table de hachage.
• Les index de ce tableau contiennent les documents tels que les documents qui se trouvent sur le même index sont considérés comme similaires et ceux qui se trouvent sur des index différents sont " différents ».
• Là où la similitude dépend du système métrique et également d'un seuil de similarité s qui agit comme un paramètre global de LSH.
• Il vous appartient de définir ce seuil suffisant s est pour votre problème.

Il est important de souligner que différentes mesures de similarité ont des implémentations différentes de LSH.

Dans mon blog, j'ai essayé d'expliquer en détail LSH pour les cas de minHashing (mesure de similarité jaccard) et simHashing (mesure de distance cosinus). J'espère que vous le trouverez utile: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Je suis une personne visuelle. Voici ce qui fonctionne pour moi comme intuition.

Dites que chacune des choses que vous souhaitez rechercher approximativement sont des objets physiques tels qu'une pomme, un cube, une chaise.

Mon intuition pour un LSH est qu'il est similaire de prendre les ombres de ces objets. Comme si vous prenez l'ombre d'un cube 3D, vous obtenez un carré 2D sur un morceau de papier, ou une sphère 3D vous donnera une ombre en forme de cercle sur un morceau de papier.

Finalement, il y a beaucoup plus de trois dimensions dans un problème de recherche (où chaque mot dans un texte pourrait être une dimension) mais l' ombre analogie de est toujours très utile pour moi.

Maintenant, nous pouvons comparer efficacement des chaînes de bits dans un logiciel. Une chaîne de bits de longueur fixe est un peu, plus ou moins, comme une ligne dans une seule dimension.

Donc, avec un LSH, je projette les ombres des objets éventuellement sous forme de points (0 ou 1) sur une seule ligne / chaîne de bits de longueur fixe.

L'astuce consiste à prendre les ombres de manière à ce qu'elles aient encore un sens dans la dimension inférieure, par exemple elles ressemblent à l'objet d'origine d'une manière suffisamment bonne pour être reconnues.

Un dessin 2D d'un cube en perspective me dit que c'est un cube. Mais je ne peux pas distinguer facilement un carré 2D d'une ombre de cube 3D sans perspective: ils ressemblent tous les deux à un carré pour moi.

La façon dont je présente mon objet à la lumière déterminera si j'obtiens une bonne ombre reconnaissable ou non. Je pense donc à un «bon» LSH comme celui qui fera tourner mes objets devant une lumière de telle sorte que leur ombre soit le mieux reconnaissable comme représentant mon objet.

Donc pour récapituler: je pense aux choses à indexer avec un LSH comme des objets physiques comme un cube, une table ou une chaise, et je projette leurs ombres en 2D et éventuellement le long d'une ligne (une petite chaîne). Et une "bonne" fonction "LSH" est la façon dont je présente mes objets devant une lumière pour obtenir une forme à peu près reconnaissable dans le flatland 2D et plus tard ma chaîne de bits.

Enfin quand je veux chercher si un objet que j'ai est similaire à certains objets que j'ai indexés, je prends les ombres de cet objet "requête" en utilisant de la même manière pour présenter mon objet devant la lumière (finissant finalement par un peu chaîne aussi). Et maintenant, je peux comparer à quel point cette chaîne de bits est similaire à toutes mes autres chaînes de bits indexées, ce qui est un proxy pour rechercher mes objets entiers si je trouvais un moyen efficace et reconnaissable de présenter mes objets à ma lumière.

En guise de réponse très courte, tldr :

Un exemple de hachage sensible à la localité pourrait être de définir d'abord des plans de manière aléatoire (avec une rotation et un décalage) dans votre espace d'entrées à hacher, puis de déposer vos points en hachage dans l'espace, et pour chaque plan que vous mesurez si le point est au-dessus ou en dessous (par exemple: 0 ou 1), et la réponse est le hachage. Ainsi, les points similaires dans l'espace auront un hachage similaire s'ils sont mesurés avec la distance cosinus avant ou après.

Vous pouvez lire cet exemple en utilisant scikit-learn: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer