Comment comprendre le hachage sensible à la localité ?

Question

J'ai remarqué que LSH semble être un bon moyen de trouver des éléments similaires avec des propriétés de haute dimension.

Après avoir lu le document http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf Je suis toujours confus avec ces formules.

Quelqu'un connaît-il un blog ou un article qui explique cela de manière simple ?

Answer 1

Le meilleur tutoriel que j'ai vu pour LSH se trouve dans le livre : Mining of Massive Datasets. Consultez le chapitre 3 - Trouver des éléments similaires http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Je vous 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 de la similarité en cosinus.

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

• Dans la figure, il y a deux cercles w/ rouge y jaune colorés, représentant deux points de données bidimensionnels. Nous essayons de trouver leur similarité cosinus en utilisant LSH.
• Les lignes grises représentent des plans choisis uniformément au hasard.
• 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 ensemble de plans, vous pouvez coder les points de données avec leur emplacement respectif par rapport aux plans. Imaginez que lorsque nous avons plus de plans dans le pool, la différence angulaire encodée dans la signature est plus proche de la différence réelle. Parce que seuls les plans qui se trouvent entre les deux points donneront aux deux données une valeur binaire différente.

• Maintenant, nous regardons la signature des deux points de données. Comme dans l'exemple, nous utilisons seulement 6 bits (carrés) pour représenter chaque donnée. C'est le hachage LSH pour les données originales que nous avons.
• La distance de Hamming entre les deux valeurs hachées est de 1, car leurs signatures ne diffèrent que d'un bit.
• En considérant la longueur de la signature, nous pouvons calculer leur similarité angulaire comme le montre le graphique.

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

Answer 2

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

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

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

Et parce qu'une image vaut mille mots, regardez la photo ci-dessous :

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

J'espère que cela vous aidera. @mvogiatzis

Answer 3

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

Une photo de la vue d'ensemble (Il y en a beaucoup plus dans les diapositives) :

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

Near Neighbor Search in High Dimensional Data - Part2 : http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

Answer 4

• LSH est une procédure qui prend en entrée un ensemble de documents/images/objets et produit une sorte de table de hachage.
• Les index de cette table contiennent les documents de telle sorte que les documents qui se trouvent sur le même index sont considérés comme étant similaire et ceux qui sont sur des indices différents sont " dissimilaire ".
• Où similaire dépend du système métrique et également d'un seuil de similarité s qui agit comme un paramètre global de LSH.
• C'est à vous de définir ce qu'est le seuil adéquat. s est pour votre problème.

Il est important de souligner que les 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/

Answer 5

Lisez le chapitre 3 de Ullman - "TROUVER DES ARTICLES SIMILAIRES".

http://infolab.stanford.edu/~ullman/mmds.html