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.
Método de los Polı́topos
En este método, si nuestros puntos están en d dimensiones, primero aplicamos a nuestro punto una rotación al azar de d a d 0 dimensiones. Es decir, multiplicamos el punto que queremos hashear por una matrix aleatoria de dxd 0 . Una vez que hicimos esto buscamos cuál es el vértice del polı́topo de d 0 dimensiones más cercano y ese es el valor del minhash.
En que casos es el metodo de los politopos igual al de Voronoi?
El método del polı́topo es equivalente al método de Voronoi si en lugar de tomar el producto interno máximo tomamos el máximo valor absoluto y el signo como minhash. Es decir que con T gaussianos en el método de Voronoi generamos un número entre 0 y 2T ya que ahora además del ı́ndice del gaussiano el signo es parte del minhash. En general el método de los polı́topos en d’ dimensiones es igual al método de Voronoi con 2d’ gaussianos.
Nombre posibles metodos que se pueden usar para aproximar la distancia euclidea.
- Método de las Proyecciones Aleatorias
- Métodos basados en K-Means: KLSH
- Métodos basados en K-Means: K-Means jerárquico
Método de las Proyecciones Aleatorias
Vamos a usar proyecciones aleatorias, en este caso los hiperplanos aleatorios surgirán de una distribución p-estable, una distribución normal funciona perfectamente. Cada vector lo vamos a multiplicar por un hiperplano aleatorio para obtener un número. Y el número obtenido lo vamos a discretizar a un número de bucket dividiendo por un cierto parámetro w. El resultado es el número de bucket o minhash para la distancia euclideana.
La fórmula para calcular el minhash es entonces: floor((x * v_i + a)/(w))
w: un hiper-parámetro que depende de los datos
a: un número entre 0 y w − 1
v_i: un vector aleatorio de igual dimensionalidad que nuestros puntos.
Cada proyección aleatoria implica un particionamiento del espacio en el cual estamos trabajando. Diferentes proyecciones generan diferentes particiones.
En cada proyección los puntos que están en una misma franja son considerados similares. El parámetro w regula el ancho de las bandas y la forma de discretizar. Es dependiente de los datos, es decir que tenemos que calcularlo para nuestro set de datos especı́ficamente.
Métodos basados en K-Means: KLSH
ver apunte.
Métodos basados en K-Means: K-Means jerárquico
ver apunte.
Cual es el objetivo de multi-probe?
Multi-probe intenta aumentar la precisión de una función LSH sin necesitar una cantidad de tablas de hash muy grande.
La idea es no acceder a un solo bucket por tabla sino a varios, siendo la probabilidad de acceder a un bucket proporcional a la distancia entre el query y los puntos del bucket, distancia que por supuesto desconocemos.
El objetivo es entonces dado un query q determinar cuáles son los buckets en donde hay mayor probabilidad de encontrar vecinos cercanos y acceder a una cierta cantidad T de estos buckets. El bucket más probable sabemos encontrarlo simplemente aplicando una función de hashing a los r minhashes de q. El problema es cómo determinar cuáles son los mejores buckets a probar además de éste.
La respuesta depende, por supuesto, de la métrica empleada.
Multi-Probing para la distancia euclideana, método de proyecciones aleatorias
En este caso el minhash surge de la división por w, por lo tanto los valores que nos interesan son los vecinos al resultado del minhash. Es decir que si el minhash es (4) nos interesa el bucket 4 y luego el 3 y 5, luego el 2 y el 6, etc. Si usamos r minhashes podemos entonces generar buckets candidatos modificando +/- 1 el valor de cada minhash.
Multi-Probing para la distancia euclideana, métodos basados en K-Means
En este caso, el esquema es muy simple ya que calculamos la distancia entre el query y cada centroide para saber el valor del minhash (que es el centroide que está a menor distancia). Por lo tanto, los minhashes alternativos son los números de centroides que siguen ordenados por distancia decreciente.
En todos los métodos basados en K-Means podemos implementar Multi-Probing de forma sencilla accediendo a T centroides en lugar de uno solo.
