c machine-learning hashmap nearest-neighbor locality-sensitive-hash

¿Cómo entender Hashing Sensitive de Locality?



machine-learning hashmap (5)

Noté que LSH parece una buena manera de encontrar artículos similares con propiedades de gran dimensión.

Después de leer el documento 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 lo explica de 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 diapositiva siguiente: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . El ejemplo en la diapositiva me ayuda mucho a entender el hashing para la similitud del coseno.

Pido prestadas dos diapositivas de Benjamin Van Durme y Ashwin Lall, ACL2010 y trato de explicar un poco las intuiciones de LSH Families for Cosine Distance.

  • En la figura, hay dos círculos con colores rojo y amarillo , que representan dos puntos de datos bidimensionales. Estamos tratando de encontrar su similitud coseno usando LSH.
  • Las líneas grises son algunos planos recogidos de forma aleatoria.
  • 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 conjunto 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 aviones 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, utilizamos 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.
  • Teniendo en cuenta la longitud de la firma, podemos calcular su similitud angular como se muestra en el gráfico.

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

Soy una persona visual. Aquí está lo que funciona para mí como una intuición.

Supongamos que cada una de las cosas que quiere buscar son objetos físicos, como una manzana, un cubo o una silla.

Mi intuición para un LSH es que es similar a tomar las sombras de estos objetos. Al igual que si tomas la sombra de un cubo 3D, obtienes un 2D en forma de cuadrado en un trozo de papel, o una esfera 3D te dará una sombra circular en un trozo 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 analogía de la shadow sigue siendo muy útil para mí.

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

Entonces, con un LSH, proyecto las sombras de los objetos 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 sigan teniendo sentido en la dimensión inferior, por ejemplo, se asemejan al objeto original de una manera lo suficientemente buena como para que puedan reconocerse.

Un dibujo 2D de un cubo en perspectiva me dice que esto es un cubo. Pero no puedo distinguir fácilmente un cuadrado 2D de una sombra de cubo 3D sin perspectiva: ambos se ven como cuadrados para mí.

Cómo presento mi objeto a la luz determinará si obtengo una buena sombra reconocible o no. Así que pienso en un "buen" LSH como el que hará que mis objetos se vuelvan frente a una luz de tal manera que su sombra sea mejor reconocible como la representación de mi objeto.

Entonces, para recapitular: pienso en cosas para indexar con un LSH como objetos físicos como un cubo, una mesa o una silla, y proyecté sus sombras en 2D y finalmente a lo largo de una línea (una cadena de bits). Y una "buena" función de "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 en mi cadena de bits.

Finalmente, cuando quiero buscar si un objeto que tengo es similar a algunos objetos que indexé, tomo las sombras de este objeto de "consulta" de la misma manera para presentar mi objeto frente a la luz (eventualmente terminando 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 mis objetos completos si encuentro una forma buena y reconocible de presentar mis objetos a mi luz.

  • LSH es un procedimiento que toma como entrada un conjunto de documentos / imágenes / objetos y genera un tipo 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 una similitud de umbral s que actúa como un parámetro global de LSH.
  • Depende de usted definir cuál es el umbral adecuado para su problema.

Es importante subrayar que las diferentes medidas de similitud tienen implementaciones diferentes 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 de coseno). Espero que lo encuentres útil: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/