LSH Flashcards
Que problema viene a solucionar LSH?
LSH (Locality Sensitive Hashing) es una solución muy eficiente al problema de los vecinos más cercanos (nearest neighbors). Anteriormente desarrollamos este problema y vimos que la solución por fuerza bruta es muy ineficiente ya que por cada punto se tiene que calcular la distancia contra todos los demás puntos para encontrar el más cercano o los k más cercanos. Este problema aplica no solo a algoritmos como KNN sino a una enorme cantidad de otros algoritmos que necesitan encontrar el punto más cercano o los k puntos más cercanos a un cierto punto de nuestro set de datos. LSH nos brinda una solución aproximada a este problema pero de forma mucho más rápida que la búsqueda por fuerza bruta.
Desarrolle el concepto de LSH.
El concepto detrás de LSH es muy simple: aplicar a los puntos una función de hashing de forma tal que los puntos que son parecidos (cercanos) colisionen. Si logramos construir esta función es entonces sencillo resolver el problema de los vecinos más cercanos. Dado un punto ”query” aplicamos la función de hashing y accedemos al bucket de la tabla de hash indicado por la misma, luego calculamos la distancia entre nuestro punto ”query” y todos los puntos dentro del bucket devolviendo el más cercano o los k más cercanos según el caso.
Que tipo de funciones de hash es necesario para LSH? Que nombre reciben?
A estas funciones las vamos a llamar ”Minhashes”. En concreto para que una función de hashing sea un minhash vamos a pedirle las siguientes condiciones:
- La probabilidad de que dos claves colisionen debe depender de la distancia entre las claves.
- La función debe ser monótona y continua.
- Debe existir una forma eficiente de calcular la función.
- Debe ser posible randomizar la función de forma tal de poder obtener muchos minhash diferentes para la misma clave.
Explique falsos positivos y falsos negativos en LSH.
Analicemos ahora qué pasarı́a si usáramos la función minhash planteada. Para objetos a distancia 0.2 nuestra probabilidad de colisión es 0.8, es decir que a partir de hashear un query podemos recuperar un 80% de los objetos que están a distancia 0.2 o menor. El 20% de objetos que son cercanos pero no recuperamos lo denominamos falsos negativos.
Por otro lado si nuestros objetos están a distancia 0.6 o mayor entonces la probabilidad de recuperarlos es 0.4. Si consideramos que objetos a distancia 0.6 o mayor no son cercanos igual vamos a estar recuperando un 40% de ellos al acceder a nuestra tabla de hashing. Estos objetos que no son cercanos pero que igualmente colisionan los llamamos falso positivos. A estos objetos debemos examinarlos y descartarlos luego.
Explique reduccion de falsos positivos.
Es posible reducir la cantidad de falsos positivos usando más de una función minhash sobre la misma tabla. Si usamos r funciones minhash en la misma tabla cada una de ellas nos dará como resultado un bucket. Los documentos candidatos surgen entonces de la intersección de los documentos que están en los r buckets que visitamos.
Si la probabilidad de colisionar es p entonces la probabilidad de colisionar en los r buckets es igual a p^r.
Podemos ver que la cantidad de falsos positivos disminuye a valores tan bajos como querramos pero también aumenta la cantidad de falsos negativos.
En este momento es importante notar que el tamaño de la tabla de hashing también es importante e influye en la cantidad de falsos positivos y negativos, ya que si la tabla es pequeña pueden producirse colisiones entre elementos que no son similares. En general el tamaño de la tabla de hashing se elige en función de la función minhash a utilizar.
Explique reduccion de falsos negativos.
Reducir los falsos negativos implica poder recuperar más objetos. Es decir, que no se nos escapen objetos que son similares a la query pero no son recuperados por LSH. La idea consiste en usar más de una tabla de hashing. Si usamos b tablas de hashing podemos entonces considerar objetos candidatos a aquellos que son candidatos en alguna de las b tablas.
Si la probabilidad de que dos claves colisionen es p entonces la probabilidad de que dos claves no colisionen es 1 − p y la probabilidad de que dos claves no colisionen en ninguna de las b tablas es (1 − p)^b. Por lo tanto, la probabilidad de que colisionen en alguna de las b tablas es 1 − (1 − p)^b.
Como se combinan los metodos para reducir falsos posit. y negat. al mismo tiempo?
Podemos lograr un número tan bajo como deseemos de falsos positivos y falsos negativos usando ambos métodos combinados, es decir b tablas de hashing y r minhashes sobre cada tabla. La cantidad total de minhashes es entonces b ∗ r.
Si la probabilidad de colisión es p entonces la probabilidad de colisionar usando b tablas de hashing y r minhashes por tabla es: 1 - (1 - p^r)^b.
Minhash para distancia de Jaccard.
Leer apunte.
Que operacion sirve como medida de distancia entre vectores? Como se calcula?
El coseno.
cos(theta) = XY / (|X| |Y|)
Por que motivo tienen especial importancia los metodos LSH basados en la distancia angular?
En la práctica muchos métodos LSH basados en la distancia angular funcionan bien para la distancia euclideana. Esto no tiene ninguna justificación teórica sino que simplemente funciona(!). Es por esto que los minhashes para la distancia angular son de particular importancia.
Nombre posibles metodos que se pueden usar para aproximar la distancia angular.
- método de los hiperplanos
- Voronoi Hashing
- Método de los Polı́topos
método de los hiperplanos
Para generar un minhash válido para la distancia angular vamos a calcular el producto interno entre nuestro vector y un vector aleatorio. Este vector aleatorio puede estar formado simplemente por valores +1 y -1, ya que estos son suficientes para definir un hiperplano aleatorio. El valor del minhash va a ser 1 si el resultado del producto interno es positivo y -1 si el resultado es negativo.
Interpretemos ahora el significado del minhash. La probabilidad de que dos vectores proyectados al azar sobre un hiperplano tengan diferente signo es igual al ángulo entre ellos dividido 180. θ/180 ya que cuanto más chico es el ángulo más probable es que las proyecciones tengan igual sentido. Por lo tanto, la probabilidad de que los minhashes coincidan para dos vectores es: 1 − θ/180.
Por lo tanto con un solo minhash el método de las proyecciones aleatorias nos define la siguiente familia de funciones LSH:
(d 1 , d 2 , 1 − d 1 /π, 1 − d 2 /π)
En donde d1 y d2 son las distancias angulares entre los vectores.
En la práctica como cada minhash nos define un valor ±1 podemos decir que cada minhash nos define un bit y calculamos un hashmin de k − bits usando k hiperplanos aleatorios. De esta forma tenemos un minhash que puede devolvernos valores entre 0 y 2 k , siendo este el valor de cada una de las b tablas de hash que vamos a usar. Notemos que a mayor valor de k aumentan los falsos negativos ya que necesitamos que los puntos estén del mismo lado de los k hiperplanos usados para que el valor del minhash coincida.
La distancia angular se puede estimar en función de la cantidad de minhash que coinciden.
En realidad ni el ángulo ni el coseno realmente importan ya que lo que usaremos es la familia LSH de la misma forma que lo hacı́amos con la distancia Jaccard: usando b grupos de r minhashes cada uno.
Voronoi Hashing
En Voronoi hashing vamos a usar un conjunto de T vectores aleatorios en donde los elementos de estos vectores surgen de una distribución normal, es decir T vectores gaussianos. Vamos a calcular el producto interno entre cada uno de estos vectores y nuestro vector query, y nos vamos a quedar con el ı́ndice del vector que nos da el máximo producto interno como valor del minhash.
h(x) = arg max < G i , x >
Que hace Voronoi Hashing geometricamente?
Notemos que lo que este método está haciendo geometricamente es distribuyendo T puntos al azar sobre la hiper-esfera unitaria y luego comparando cuál es el punto más cercano al punto hasheado.
En que casos es similar Voronoi al metodo de los hiperplanos?
Es interesante destacar que si usamos solo 2 hiperplanos T = 2, el método de Voronoi es idéntico al de los hiperplanos usando como hiperplano al que bisecte los dos puntos elegidos al azar por Voronoi. En general Voronoi con T = 2^k gaussianos es igual al método de los hiperplanos con k hiperplanos.
