Prueba de cálculo de MinHash

Question

Estoy leyendo sobre MinHash para estimar la similitud entre 2 conjuntos: Dados los conjuntos A y B, h es la función hash y $h_\min(S)$ es el hash mínimo del conjunto S, es decir $h_\min(S) = \min(h(s))$ para s en S. Tenemos la ecuación: $$ p(h_\min(A) = h_\min(B)) = \frac{|A \cap B|}{|A \cup B|} $$ Lo que significa que la probabilidad de que el hash mínimo de A sea igual al hash mínimo de B es la similitud de Jaccard de $A$ y $B$ .

Estoy tratando de probar la ecuación anterior y llegar a una prueba, que es: para $a \in A$ y $b \in B$ tal que $h(a) = h_\min(A)$ y $h(b) = h_\min(B)$ . Por lo tanto, si $h_\min(A) = h_\min(B)$ entonces $h(a) = h(b)$ . Supongamos que la función hash h puede convertir claves en valores hash distintos, por lo que $h(a) = h(b)$ sólo si $a = b$ que es $\frac{|A \cap B|}{|A \cup B|}$ . Sin embargo, mi prueba no es completa ya que la función hash puede devolver el mismo valor para diferentes claves. Por lo tanto, pido su ayuda para encontrar una prueba que se puede aplicar independientemente de la función hash. Muchas gracias.

L

Answer 1

Parece que es una suposición subyacente en esta fórmula que los diferentes elementos se asignan a hashes distintos. De lo contrario, simplemente haga que su función hash mapee todos a 0. La probabilidad que está buscando sería 1 independientemente de cualquier conjunto.

Answer 2

Existe una conexión notable entre el minhashing y la similitud de Jaccard de los conjuntos que son minhashed.

- La probabilidad de que la función minhash para una permutación aleatoria de filas produzca el mismo valor para dos conjuntos es igual a la similitud de Jaccard de dichos conjuntos.

Para ver por qué, tenemos que imaginar las columnas de esos dos conjuntos. Si nos limitamos a las columnas de los conjuntos S1 y S2, las filas pueden dividirse en tres clases:

1. Las filas de tipo X tienen 1 en ambas columnas.
2. Las filas de tipo Y tienen 1 en una de las columnas y 0 en la otra.
3. Las filas de tipo Z tienen 0 en ambas columnas.

Dado que la matriz es dispersa, la mayoría de las filas son de tipo Z. Sin embargo, es el cociente del número de filas de tipo X y de tipo Y lo que determina tanto SIM(S1, S2) como la probabilidad de que h(S1) = h(S2). Sean x filas de tipo X e y filas de tipo Y . Entonces SIM(S1, S2) = x/(x + y). La razón es que x es el tamaño de S1 ∩ S2 y x + y es el tamaño de S1 ∪ S2.

Consideremos ahora la probabilidad de que h(S1) = h(S2). Si imaginamos las filas permutadas aleatoriamente, y procedemos desde arriba, la probabilidad de que encontremos de encontrar una fila de tipo X antes de encontrar una fila de tipo Y es x/(x + y). Pero si la primera fila desde arriba que no sea de tipo Z es de tipo X, entonces seguramente h(S1) = h(S2). Por otra parte, si la primera fila que no es del tipo Z es una fila de tipo Y, entonces el conjunto con un 1 obtiene esa fila como valor minhash. valor. Sin embargo, el conjunto con un 0 en esa fila seguramente obtendrá alguna fila más abajo en la lista permutada. la lista permutada. Por lo tanto, sabemos que h(S1) 6= h(S2) si primero encontramos una fila de tipo Y. Concluimos que la probabilidad de que h(S1) = h(S2) es x/(x + y), que también es la similitud de Jaccard entre S1 y S2. ( del libro Mining of Massive Datasets )