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

Je suis une personne visuelle. Voici ce qui fonctionne pour moi en tant qu'intuition.

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

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

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

Nous pouvons maintenant comparer efficacement des chaînes de bits dans les logiciels. Une chaîne de bits de longueur fixe est plus ou moins comme une ligne dans une seule dimension.

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

L'astuce consiste à prendre les ombres de telle sorte qu'elles aient encore un sens dans la dimension inférieure, c'est-à-dire qu'elles ressemblent suffisamment à l'objet original pour être reconnues.

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

La façon dont je présente mon objet à la lumière déterminera si j'obtiendrai une bonne ombre reconnaissable ou non. Je considère donc qu'une "bonne" LSH est celle qui tournera mes objets devant une lumière de telle sorte que leur ombre soit la plus reconnaissable comme représentant mon objet.

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

Enfin, lorsque je veux rechercher si un objet que j'ai est similaire à d'autres objets que j'ai indexés, je prends les ombres de cet objet "de requête" en utilisant la même manière de présenter mon objet devant la lumière (ce qui finit par donner une chaîne de bits aussi). Et maintenant je peux comparer la similarité de cette chaîne de bits avec toutes mes autres chaînes de bits indexées, ce qui est un proxy pour la recherche de mes objets entiers si j'ai trouvé une bonne et reconnaissable façon de présenter mes objets à ma lumière.

Answer 2

Comme un très court, tldr réponse :

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 à hacher dans l'espace, et pour chaque plan, vous mesurez si le point est au-dessus ou en dessous (par exemple : 0 ou 1), et la réponse est le hachage. Ainsi, des points similaires dans l'espace auront un hachage similaire si on les mesure 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