El hashing sensible a la localidad (LSH) es un método que es una forma de generar códigos hash para puntos de datos con la propiedad de que puntos de datos similares tendrán los mismos códigos hash. Una buena manera de entender lo que está haciendo LSH es pensarlo geométricamente en un espacio de características 2D de juguete. Imagine intersectar un espacio de características 2D con (digamos K) líneas generadas aleatoriamente que pasan por el origen. Digamos que nuestro espacio tiene N puntos de datos. En el siguiente diagrama de ejemplo, N = 4 y K = 3. Las flechas pequeñas que se muestran en las líneas son los vectores normales de los segmentos de línea. También se muestran los códigos hash LSH para los puntos de datos en una región particular (por ejemplo, A, B tienen el código hash 110, mientras que D tiene el código hash 001 y C tiene el código hash). Los puntos de datos con el mismo color están relacionados entre sí (por ejemplo, documentos que hablan sobre el mismo tema o imágenes que representan un tigre). Idealmente, nos gustaría que los documentos / imágenes similares tengan los mismos códigos hash para que podamos usar los códigos hash para indexar en una tabla hash para una búsqueda rápida. La salsa secreta de LSH es cómo se generan estos códigos hash para preservar la similitud de los puntos de datos.
Intuitivamente, los puntos de datos que están muy juntos en el espacio (por ejemplo, que comparten palabras en común en el caso de documentos, o tienen características similares en el caso de las imágenes) tienen una probabilidad menor de estar separados por una línea dada que aquellos que son menos -imilares entre sí (ya que estarán más separados en el espacio de características). Por ejemplo, los puntos de datos A y B en la figura de ejemplo están muy juntos y no están divididos entre sí por una línea, mientras que el punto de datos D (que está lejos por la distancia angular) está separado de A, B por los 3 líneas. Ahora, para cada punto de datos, verificamos en qué lados de las líneas K cae el punto de datos (el principio aquí es que los puntos de datos cercanos generalmente caerán en los mismos lados de las líneas). Si el punto de datos está en un lado de la línea, sacamos un 1, si no, sacamos un 0. Si repetimos esto para todas las líneas K y si concatenamos todas las salidas 0/1 podemos construir una K -bit hashcode para un punto de datos. Este procedimiento puede repetirse para todos los N puntos de datos y terminamos esencialmente con N = 4 conservando códigos hash de similitud para todos los puntos de datos en nuestro conjunto de datos. Por lo tanto, los puntos de datos que están muy juntos en el espacio tendrán, con alta probabilidad, los mismos códigos hash.
En el momento de la consulta, para una búsqueda rápida, podemos usar este código hash como índice en un depósito de tabla hash, y la esperanza es que solo examinando ese depósito podamos recuperar vecinos más cercanos a un punto de datos en tiempo constante (como lo hacemos no tiene que buscar exhaustivamente a través de todo el conjunto de datos, solo aquellas pequeñas fracciones de puntos de datos que colisionan en el mismo grupo). Intuitivamente, cada región del espacio que dividimos con las líneas K puede considerarse un grupo de tabla hash y el código hash asociado puede considerarse como una codificación de la posición geométrica (en el espacio de características) de los puntos de datos en ese grupo.
En una implementación típica de LSH en el mundo real, el espacio se divide de esta manera, no una vez, sino varias (L) veces utilizando diferentes semillas aleatorias y, por lo tanto, obtenemos L diferentes particiones del espacio (imagine L copias de la figura anterior pero con diferentes líneas dibujadas al azar). Estas L particiones diferentes del espacio son efectivamente tablas hash L. En el diagrama de ejemplo, L = 1 y solo tenemos una tabla hash. La esperanza es que, al usar diferentes particiones aleatorias, los puntos de datos que están muy juntos y que están separados accidentalmente por una línea en una tabla hash (por ejemplo, A y C en el diagrama de ejemplo), no se separen en otra tabla hash. Para capitalizar múltiples tablas hash de esta manera, LSH devuelve todos los puntos de datos que colisionan con un punto de datos dado en todos los cubos de tablas hash. Esto tiene el efecto de reducir la tasa de falsos negativos (es decir, el número de vecinos más cercanos verdaderos que se encuentran en diferentes segmentos).
En un paso final de procesamiento posterior, para garantizar la calidad de los vecinos devueltos, generalmente todos los puntos de datos en colisión se comparan con el punto de datos de consulta utilizando una métrica de interés de similitud (por ejemplo, similitud de coseno) y se descartan los que están por debajo de un umbral. Para una implementación LSH adecuada, no debería haber demasiados puntos de datos para comparar en este paso final de filtrado.
Aparte de L, el número de líneas (que también es la longitud del código hash) es el otro parámetro LSH importante y el aumento de K disminuirá la tasa de falsos positivos (intuitivamente, cuantas más líneas, más improbable es para puntos de datos distantes caer en el mismo lado de todas las líneas K). La configuración apropiada de los parámetros K, L es específica de la aplicación y su configuración realmente puede afectar la precisión y la velocidad de una implementación práctica de LSH.
Lo que he descrito aquí es el esquema LSH para la similitud coseno (angular), que ha demostrado ser eficaz para aplicaciones de texto (por ejemplo, detección de primer piso en Twitter). En pocas palabras, eso es todo lo que hay para LSH! El esquema se extiende fácilmente a dimensiones superiores, en cuyo caso una línea se convierte en un “hiperplano”. Las ventajas de LSH son la velocidad de indexación (solo particione aleatoriamente el espacio de sus características y tome el producto de punto de los puntos de datos con los vectores normales de hiperplano para obtener los códigos hash), y la búsqueda rápida (examinar los cubos de tabla hash L es muy rápido). Las desventajas incluyen la memoria requerida para contener las tablas hash L, y la precisión potencialmente menor en comparación con más esquemas de particionamiento basados en datos.
Si está interesado en obtener más información, consulte este sitio web sobre esquemas de aprendizaje automático para el hash, incluidos enlaces a muchos recursos recientes en el campo (documentos, códigos, conjuntos de datos y artículos de revisión) (descargo de responsabilidad: soy el autor de este sitio !).
