¿Cómo entender el Hashing sensible a la localidad?

Noté que LSH parece una buena manera de encontrar elementos similares con propiedades de alta dimensión.

Después de leer el periódico http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf , todavía estoy confundido con esas fórmulas.

¿Alguien sabe un blog o artículo que explica que la manera fácil?

El mejor tutorial que he visto para LSH está en el libro: Minería de conjuntos de datos masivos. Consulte el Capítulo 3: Búsqueda de artículos similares http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

También recomiendo la siguiente diapositiva: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . El ejemplo en la diapositiva me ayuda mucho a comprender el hash para la similitud del coseno.

Tomo prestados dos diapositivas de Benjamin Van Durme y Ashwin Lall, ACL2010 e intento explicar un poco las intuiciones de LSH Families para Cosine Distance.

• En la figura, hay dos círculos con rojo y amarillo , que representan dos puntos de datos bidimensionales. Estamos tratando de encontrar su similitud de coseno usando LSH.
• Las líneas grises son algunos planos elegidos aleatoriamente de manera uniforme.
• Dependiendo de si el punto de datos se ubica arriba o debajo de una línea gris, marcamos esta relación como 0/1.
• En la esquina superior izquierda, hay dos filas de cuadrados blancos / negros, que representan la firma de los dos puntos de datos, respectivamente. Cada cuadrado corresponde a un bit 0 (blanco) o 1 (negro).
• Entonces, una vez que tenga un grupo de planos, puede codificar los puntos de datos con su ubicación respectiva a los planos. Imagine que cuando tenemos más planos en el grupo, la diferencia angular codificada en la firma está más cerca de la diferencia real. Porque solo los planos que residen entre los dos puntos darán a los dos datos un valor de bit diferente.

• Ahora miramos la firma de los dos puntos de datos. Como en el ejemplo, usamos solo 6 bits (cuadrados) para representar cada dato. Este es el hash LSH para los datos originales que tenemos.
• La distancia de hamming entre los dos valores hash es 1, porque sus firmas solo difieren en 1 bit.
• Considerando la longitud de la firma, podemos calcular su similitud angular como se muestra en el gráfico.

Tengo un código de muestra (solo 50 líneas) en Python aquí que usa similitud de coseno. https://gist.github.com/94a3d425009be0f94751

Los tweets en el espacio vectorial pueden ser un gran ejemplo de datos de alta dimensión.

Echa un vistazo a mi publicación de blog sobre la aplicación de Locality Sensitive Hashing a los tweets para encontrar otros similares.

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

Y debido a que una imagen es mil palabras, verifique la imagen a continuación:

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

Espero eso ayude. @mvogiatzis

Aquí hay una presentación de Stanford que lo explica. Hizo una gran diferencia para mí. La segunda parte es más sobre LSH, pero la primera parte también lo cubre.

Una imagen del resumen (hay mucho más en las diapositivas):

Búsqueda de vecinos cercanos en datos de alta dimensión - Parte 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Búsqueda de vecinos cercanos en datos de alta dimensión - Parte 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

• LSH es un procedimiento que toma como entrada un conjunto de documentos / imágenes / objetos y genera una especie de tabla hash.
• Los índices de esta tabla contienen los documentos de manera que los documentos que están en el mismo índice se consideran similares y los que están en índices diferentes son " diferentes " ".
• Donde similar depende del sistema métrico y también de un umbral de similitud s que actúa como un parámetro global de LSH.
• Depende de usted para definir cuál es el umbral adecuado es es para su problema.

Es importante subrayar que diferentes medidas de similitud tienen diferentes implementaciones de LSH.

En mi blog, traté de explicar a fondo LSH para los casos de minHashing (medida de similitud de jaccard) y simHashing (medida de distancia cosenoidal). Espero que lo encuentre útil: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Soy una persona visual Esto es lo que funciona para mí como intuición.

Digamos que cada una de las cosas que desea buscar aproximadamente son objetos físicos como una manzana, un cubo, una silla.

Mi intuición para un LSH es que es similar tomar las sombras de estos objetos. Al igual que si tomas la sombra de un cubo 3D, obtienes un cuadrado 2D en una hoja de papel, o una esfera 3D te dará una sombra en forma de círculo en una hoja de papel.

Eventualmente, hay muchas más de tres dimensiones en un problema de búsqueda (donde cada palabra en un texto podría ser una dimensión) pero la sombra analogía de todavía es muy útil para mí.

Ahora podemos comparar de manera eficiente cadenas de bits en software. Una cadena de bits de longitud fija es más o menos, como una línea en una sola dimensión.

Entonces, con un LSH, proyecto las sombras de los objetos eventualmente como puntos (0 o 1) en una sola línea de longitud fija / cadena de bits.

Todo el truco consiste en tomar las sombras de modo que aún tengan sentido en la dimensión inferior, por ejemplo, se parezcan al objeto original de una manera suficientemente buena que pueda reconocerse.

Un dibujo 2D de un cubo en perspectiva me dice que este es un cubo. Pero no puedo distinguir fácilmente un cuadrado 2D de una sombra de cubo 3D sin perspectiva: ambos me parecen un cuadrado.

La forma en que presente mi objeto a la luz determinará si obtengo una buena sombra reconocible o no. Así que pienso en un "buen" LSH como el que convertirá mis objetos frente a una luz de tal manera que su sombra sea mejor reconocible como representando mi objeto.

Para resumir: pienso en cosas para indexar con un LSH como objetos físicos como un cubo, una mesa o una silla, y proyecto sus sombras en 2D y eventualmente a lo largo de una línea (una cadena de bits). Y una "buena" función "LSH" es cómo presento mis objetos frente a una luz para obtener una forma aproximadamente distinguible en la llanura 2D y más tarde mi cadena de bits.

Finalmente, cuando quiero buscar si un objeto que tengo es similar a algunos objetos que indicé, tomo las sombras de este objeto de "consulta" usando la misma forma para presentar mi objeto frente a la luz (eventualmente termina con un poco cadena también). Y ahora puedo comparar cuán similar es esa cadena de bits con todas mis otras cadenas de bits indexadas, que es un proxy para buscar todos mis objetos si encuentro una forma buena y reconocible de presentar mis objetos a mi luz.

Como muy corto, tldr respuesta :

Un ejemplo de hashing sensible a la localidad podría ser establecer primero planos aleatoriamente (con rotación y desplazamiento) en su espacio de entradas a hash, y luego soltar sus puntos a hash en el espacio, y para cada plano que mida si el punto es arriba o abajo (por ejemplo: 0 o 1), y la respuesta es el hash. Entonces, puntos similares en el espacio tendrán un hash similar si se mide con la distancia del coseno antes o después.

Puede leer este ejemplo usando scikit-learn: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer