Técnicas LSH (Locality Sensitive Hashing)

En I2Talentia necesitamos buscar relaciones en grandes cantidades de datos, habitualmente textos que componen los distintos cursos. La búsqueda de relaciones entre datos es un asunto ampliamente estudiado en el ámbito de la Ingeniería del Software. Cuando el volumen de datos es relativamente pequeño, es sencillo encontrar estas relaciones mediante técnicas convencionales, basadas en la comparación e iteración de los elementos entre sí. Sin embargo, cuando el volumen de datos es considerable este tipo de aproximaciones no son adecuadas ya que el tiempo de procesamiento es excesivo e inaceptable.

Una de las técnicas empleadas para la resolución de este tipo de problemas es la estrategia Locality Sensitive Hashing (LSH) basada en la asociación de un mismo Hash a datos similares frente al comportamiento clásico de una función Hash, que evita colisiones entre los datos de entrada. Por lo tanto, con LSH elementos similares se clasificarán dentro del mismo “cubo” con una alta probabilidad. Es importante la apreciación de "alta probabilidad" ya que existe la posibilidad de que dos elementos muy parecidos caigan en cubos distintos por lo que a la hora de usar técnicas de LSH debe tenerse esto en cuenta.

La formulación matemática del problema es bastante compleja de manera que mediante ejemplos gráficos sencillos trataré de explicar brevemente en qué consiste la técnica LSH. En ningún caso trato de cubrir todos los aspectos de LSH, es simplemente un ejemplo de aplicación.

Imaginemos una nube de puntos que definidos como un par de coordenadas (x,y) para los que necesitamos encontrar aquellos puntos que son similares (próximos en distancia) a uno dado. Comparar iterativamente las distancias entre el punto objetivo y el resto es aceptable, como anteriormente comenté, cuando el número de puntos es relativamente pequeño. Sin embargo, si tuviéramos una nube de millones de ellos, esta solución no es nada eficiente.

Para abordar este problema usando la estrategia LSH, deberemos dividir el espacio dimensional (plano en este caso) en distintas regiones. En este ejemplo dividiré el plano en cuadrículas de igual tamaño aunque sería válida cualquier otro tipo de división.

Tal como se muestra en la figura, cada punto está contenido en una y sólo una cuadrícula. Si necesitamos obtener los puntos similares respecto a uno dado, simplemente identificaríamos todos aquellos que están en la misma cuadrícula o dicho de otro modo, aquellos que tienen el mismo valor de Hash.

A continuación describiré el procedimiento para analizar la similitud de un punto respecto a otro dato. Para ello utilizaré el concepto de vector cuyas coordenadas indicarán si un punto sobrepasa un determinado lado de estas cuadrículas en las que he dividido el espacio.

Al punto identificado en la figura de color verde, le asignaríamos un valor de Hash 11101100 en el que las primeras cuatro cifras se corresponderían con valores asociados al eje X y las siguientes cuatro al eje Y. El razonamiento para calcular el Hash de un punto es el siguiente:

Respecto al eje X, el punto verde está más a la derecha que los lados 1,2,3 y a la izquierda del lado 4, por tanto su valor sería 1110.

Siguiendo un razonamiento similar para el eje Y, el punto verde está más abajo de los lados 1,2 y más arriba de los lados 3, 4 siendo por tanto su valor 1100.

Uniendo ambos valores resultaría el valor del Hash 11101100.

De este modo, queda claro que los tres puntos rojos de la figura que están dentro de la misma cuadrícula compartirán el mismo valor de hash 11001100.

Si creamos un índice inverso que relacione hashes con los puntos ya tenemos todo lo necesario.

El índice inverso de este ejemplo sería:

11001100 = punto rojo 1, punto rojo 2, punto rojo 3
11101100 = punto verde
11111111 = punto negro

Si necesitásemos obtener los puntos parecidos a un nuevo punto muy cerca de los tres puntos rojos, simplemente calcularíamos el valor del Hash de este punto que, con alta probabilidad, sería también 11001100. Finalmente, a través del índice inverso obtendríamos los puntos rojos 1,2 y 3.

Tal como se observa esta operación es realmente ligera aún cuando el volumen de datos fuese enorme, millones o incluso billones de puntos.

Con este mecanismo, también sería posible calcular la similitud entre puntos que pertenezcan a distintas cuadrículas haciendo uso de lo que se denomina la distancia de Hamming que no es más que el número de posiciones en los que dos series (vectores) tienen distintos valores.

Por ejemplo, ¿cómo de distintos son los puntos rojos?

Punto rojo 1 = 11001100
Punto rojo 2 = 11001100
Punto rojo 3 = 11001100


La distancia de Hamming es 0 ya que todas las posiciones de los tres puntos tienen el mismo valor. Por tanto, decimos que los puntos son "iguales" en el sentido de que pertenecen a la misma cuadrícula.

La diferencia entre un punto rojo y el punto verde es:
Punto rojo 1 = 11001100
Punto verde  = 11101100

Sólo difieren en la tercera posición por lo que su distancia es 1.

La diferencia entre un punto rojo y el punto negro es:
Punto rojo 1 = 11001100
Punto negro  = 11111111

Difieren en la tercera, cuarta, séptima y octava posiciones por lo que su distancia es 4.

Claramente un punto rojo es más parecido al punto verde (distancia 1) que a al punto negro (distancia 4).

Ahora bien, ¿para qué puede ser útil buscar la similitud entre puntos? Bueno, a raíz de esta pregunta no se me ocurren demasiadas aplicaciones. Sin embargo, vamos a aplicar inteligencia lateral y darle la vuelta a la pregunta, ¿qué cosas podría querer comparar que puedan modelarse como puntos? Ahora sí que puedo ver aplicaciones prácticas.

Si por ejemplo en vez de X le llamo edad y en vez de Y le llamo nota, un punto podría ser una abstracción de un alumno de una determinada edad y una nota media = (edad, nota). Si parto de un alumno del que conozco su edad y su nota media y necesitara obtener todos los alumnos que tienen edades similares (no necesariamente la misma) y notas similares (no necesariamente la misma), podríamos aplicar los mismos conceptos vistos anteriormente para obtenerlos de forma rápida y sencilla.

Además, no tenemos por qué quedarnos en un espacio bidimensional, podemos usar el número de coordenadas que necesitemos, por ejemplo (x,y,z) o (x,y,z,h). Podemos por ejemplo, clasificar alumnos en función de la edad, nota y color de pelo o incluso de más categorías: edad, nota, color de pelo y nivel de estudios de sus padres. Los conceptos y aplicación de LSH serían los mismos.