Detección de duplicados similares con similitud de Jaccard y MinHash

• En colecciones de documentos a gran escala, durante el rastreo web se puede recuperar la misma página varias veces o mezclar versiones con pequeñas modificaciones, por lo que la similitud de Jaccard y MinHash se vuelven métodos prácticos para encontrar documentos “casi iguales”
• La similitud de Jaccard convierte los documentos en conjuntos de características y luego calcula tamaño de la intersección / tamaño de la unión; los pares por encima de un umbral se consideran duplicados similares, aunque esta relación por lo general no es transitiva
• Comparar todos los pares de documentos cuesta O(n²) respecto del tamaño del corpus, por lo que MinHash resume cada documento en una firma de tamaño fijo para aproximar la similitud de forma probabilística
• Al usar k funciones hash, la similitud puede estimarse como la proporción de valores que coinciden en la misma posición entre las firmas de dos documentos, y para elegir las funciones hash son importantes condiciones como la independencia min-wise
• Usar la firma completa o partes de la firma como clave de agrupación permite controlar la probabilidad de que documentos similares caigan en el mismo bucket; la sensibilidad de detección y el costo dependen de los n-gramas y del método de tokenización

---

La dificultad de detectar duplicados similares

• El objetivo es encontrar, dentro de un gran conjunto de documentos, documentos que no son exactamente iguales, pero sí casi iguales
  • Si se rastrea la web durante cierto período, se puede recuperar la misma página varias veces con metadatos ligeramente distintos
  • También pueden existir varias versiones de una página con pequeñas modificaciones
• El enfoque básico consiste en definir una función de similitud S(A, B) entre dos documentos y considerar como duplicados similares los pares cuyo valor sea mayor o igual que un umbral Scrit
• “Casi idéntico” generalmente no es una relación transitiva
  • A y B, y B y C, pueden ser similares por encima del umbral
  • Al mismo tiempo, A y C pueden quedar por debajo del umbral
  • Por eso, la detección de duplicados similares a gran escala es más difícil de manejar que la detección de duplicados exactos

Definición de la similitud de Jaccard

• El índice de Jaccard expresa la similitud entre dos conjuntos finitos como tamaño de la intersección / tamaño de la unión

  [ J(A, B) = \frac{|A \cap B|}{|A \cup B|} ]

• Si dos conjuntos son parecidos, comparten la mayoría de los elementos, por lo que la unión crece poco y la intersección se reduce poco

• Si dos conjuntos están completamente separados, el tamaño de la intersección es 0, así que la similitud de Jaccard es 0

• Si dos conjuntos son idénticos, la intersección y la unión son el mismo conjunto, por lo que la similitud de Jaccard es 1

• Como los documentos reales suelen ser cadenas Unicode u otros formatos similares, primero hay que convertir cada documento en un conjunto de características

Problema de escalabilidad al comparar todos los pares

• Una vez convertido cada documento en un conjunto de características, la definición para encontrar pares con alta similitud de Jaccard es simple
• Pero comparar todos los pares de documentos hace que el costo crezca como O(n²) respecto del tamaño del corpus
• En la detección de duplicados exactos, este costo se evita hasheando los documentos y agrupando los que caen en el mismo bucket de hash
• Para detectar duplicados similares también se necesita un atajo parecido; en este campo se lo llama hash sensible a la localidad (locality-sensitive hash)
• Para la similitud de Jaccard existe una técnica adecuada para ese propósito, y su núcleo es MinHash

Aproximar la similitud de Jaccard con MinHash

• MinHash aproxima la similitud de Jaccard sin comparar siempre el conjunto completo, usando solo una pequeña firma (signature) precalculada para cada documento

• La idea básica es tomar de forma uniforme un elemento aleatorio de la unión y ver si ese elemento también pertenece a la intersección

• En la práctica, en lugar de una permutación aleatoria se usa una buena función hash H(x), y se guarda la característica con el menor valor hash de cada conjunto

  [ a_{min} \leftarrow \min_{x \in A} H(x) ]

  [ b_{min} \leftarrow \min_{x \in B} H(x) ]

• Como la operación min es asociativa, el menor valor hash de cada documento puede preprocesarse de manera independiente

• La probabilidad de que los menores valores hash de dos conjuntos sean iguales es igual a la similitud de Jaccard de esos dos conjuntos

Varias funciones hash y vectores de firma

• Si se usa una sola función hash, para dos documentos solo se puede obtener una estimación booleana de “igual/distinto”

• Si se usan k funciones hash distintas, cada documento puede resumirse como un vector de k valores MinHash

  [ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]

• La similitud de Jaccard se aproxima con la proporción de valores que coinciden en la misma posición entre las dos firmas

  [ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]

• Elegir la familia de funciones hash es un asunto sutil

  • El objetivo es aproximar una permutación aleatoria de todo el espacio de características
  • Las familias de funciones hash reales expresan solo una fracción muy pequeña de todas las permutaciones posibles
  • Hay que evitar correlaciones inapropiadas; la propiedad relacionada se conoce como independencia min-wise
  • Este problema ha sido relativamente bien estudiado y existen soluciones eficientes en la literatura

Encontrar pares candidatos en todo el corpus

• Al reducir cada documento a una huella de k valores hash, se puede aproximar eficientemente la similitud de Jaccard
• El problema restante es encontrar documentos con alta similitud en todo el corpus sin revisar todos los pares de documentos
• La estrategia consiste en agrupar los documentos por alguna clave y comparar solo dentro del mismo grupo
• La clave de agrupación debe hacer que los documentos similares se agrupen juntos con alta probabilidad y que los documentos no similares, en lo posible, no queden juntos

• Usar la firma MinHash completa como clave

  • El método más simple es usar los k valores MinHash completos como una sola clave de grupo
  • Dos documentos se consideran duplicados similares solo si coinciden todos sus valores MinHash
  • El artículo de GPT-3 usó eliminación de duplicados similares en su pipeline de preparación del dataset y, por la formulación citada, se interpreta que usó la implementación MinHashLSH de Spark con 10 hashes
  • La ventaja de este enfoque es su simplicidad y eficiencia
  • Agrupar por una única cadena de bytes de alta cardinalidad es fácil de escalar horizontalmente
  • Es un primitivo básico de las herramientas de procesamiento de datos, como el “shuffle” entre map y reduce en MapReduce
  • Si la similitud de Jaccard de dos documentos es J(A, B) y deben coincidir los k valores, la probabilidad de colisión para un solo par es J(A, B)^k
  • Con k = 10, los documentos con similitud de aproximadamente 0.6 o menos casi nunca colisionan
  • La probabilidad de coincidencia crece alrededor de una similitud de aproximadamente 0.95
  • Si el objetivo es encontrar documentos hermanos muy cercanos, puede ser suficiente
  • Este cálculo de J^k corresponde a un solo par de documentos
  • Si hay muchos documentos muy similares entre sí, las probabilidades por par no son independientes
  • En la práctica, los documentos muy similares suelen caer en no más de dos o tres buckets, lo que permite encontrar casi todos los duplicados

Detección de duplicados más laxa

• Si se quiere encontrar no solo documentos con similitud cercana a 1, sino también documentos con 0.8 o 0.7 o más, usar la firma completa como clave puede ser demasiado estricto

• Si se usa solo una parte de los k MinHash como clave de grupo, aumenta la probabilidad de colisión incluso con similitudes más bajas

  • Por ejemplo, se puede agrupar por los primeros 4 valores MinHash y, dentro del mismo bucket, usar todos los valores MinHash para estimar la similitud real

• Reducir la cantidad de hashes tiene límites

  • J^r siempre es menor que J
  • Si r se vuelve demasiado pequeño, puede haber demasiadas colisiones falsas

• En cambio, se pueden generar varias claves por documento y colocarlo en varios buckets

  • Por ejemplo, calcular k = 20 hashes, colocarlos en b = 4 buckets, y hacer que cada clave esté compuesta por r = 5 hashes

• La probabilidad de que dos documentos colisionen en al menos un bucket es la siguiente

  [ p = 1 - (1 - J^r)^b ]

• En el ejemplo con 4 grupos y 5 hashes por grupo, el punto donde la probabilidad de colisión es 50% se desplaza aproximadamente a J = 0.7

• Cuando r y b son ambos mayores que 1, la curva resultante suele tener forma de S, y ofrece espacio para ajustar sensibilidad, recall y costo de rendimiento

Relación con HyperLogLog

• El truco central de MinHash se parece a los algoritmos de sketch como HyperLogLog
• HyperLogLog hashea cada elemento de un stream y guarda el máximo observado del número de ceros iniciales en el valor hash
• Ambas técnicas mapean los elementos de entrada a una distribución uniforme mediante una función hash y luego calculan valores extremos observados para estimar propiedades distribucionales con solo un resumen de tamaño constante
• HyperLogLog puede verse, si se piensa invirtiendo el orden de los bits, como una forma de calcular el mínimo observado de log2(H(x)), mientras que MinHash usa el mínimo de H(x) en sí
• Ambas estructuras son duales en cierto sentido
  • Si se combinan dos estructuras HyperLogLog, se puede estimar el tamaño de la unión de dos conjuntos
  • Si se comparan dos estructuras MinHash, se puede estimar el tamaño relativo de la intersección de dos conjuntos
• Al combinar ambas estructuras, se puede construir un sketch capaz de responder preguntas sobre intersecciones y uniones de conjuntos arbitrarios
  • Esta idea ya se conocía para 2013, y existen literatura relacionada y trabajos posteriores

Cómo representar documentos como conjuntos

• Para usar Jaccard y MinHash, primero hay que convertir los documentos de texto en conjuntos de características
• Sea cual sea el método, se puede normalizar el documento como preprocesamiento
  • Convertir a una forma de normalización Unicode estándar
  • Aplicar case folding
  • Contraer espacios en blanco consecutivos
  • Transformaciones similares

• n-gramas o shingles

  • Un documento puede representarse como el conjunto de todos los n-gramas que aparecen en él
  • En la literatura de procesamiento de texto a gran escala también se usa el término “shingle”, pero aquí cumple el mismo rol que un n-grama
  • Elegir el valor de n implica un compromiso
  • Los valores pequeños comparan los documentos de forma más burda
  • Por ejemplo, la mayoría de los textos en inglés pueden verse bastante parecidos desde el punto de vista de bigramas
  • Los valores grandes producen características más distintivas y conjuntos más grandes
  • Si son demasiado grandes, la sensibilidad puede caer, aunque probablemente antes aparezcan problemas de rendimiento
  • Según Mining of Massive Datasets §3.2.2, en muchas aplicaciones parecen ser comunes valores entre n = 5 y 9

• Separación de palabras o tokens

  • También se puede dividir la entrada en “palabras” o “tokens” y usarlos como características
  • El extracto del artículo de GPT-3 menciona el tokenizer estándar de Spark, lo que parece referirse a pyspark.ml.feature.Tokenizer, que convierte la entrada a minúsculas y la divide por espacios en blanco
  • También se puede usar un tokenizer de NLTK más sofisticado
  • Después de tokenizar, también es posible usar un enfoque híbrido con n-gramas de tokens
  • Como los tokens individuales tienen mayor entropía que los bytes o caracteres, en este caso se usan valores de n más pequeños

[GN⁺]

Opiniones de Hacker News

• A muchos se les escapa que las métricas basadas en conjuntos, como la similitud de Jaccard (coeficiente de Tanimoto) o el puntaje F1 (coeficiente de Dice), también pueden usarse igual con conjuntos difusos.
  Eso sí, hay que elegir un par T-Norm / T-Conorm adecuado para expresar los conceptos de intersección y unión en conjuntos difusos, y hay infinitas variedades.
  Más bien, es una ventaja en el sentido de que se puede escoger el par que encaje con la semántica deseada.
  En la validación de segmentación de imágenes médicas, he tratado este tema cuando el resultado de la segmentación y la verdad de referencia no son máscaras binarias, sino formas probabilísticas/difusas: https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
  Normalmente se aplica un umbral de 0.5 para crear un conjunto binario y luego se usa la variante binaria de Jaccard/Dice, pero con eso parece que la precisión del operador de validación cae alrededor de dos órdenes de magnitud.
  Es como anunciar que un algoritmo mejora en 0.001 al estado del arte, mientras se ignora que el margen de error del operador de validación es 0.1.

• Para deduplicar registros de ciudadanos en una gran base de datos del gobierno francés, un cliente había creado una implementación propia en Python de esta técnica, y funcionaba bien.
  Hoy probablemente le habría dicho que usara datasketch: https://pypi.org/project/datasketch/
  Al buscar, vi que siguen apareciendo herramientas nuevas sobre este tema. Por ejemplo, https://pypi.org/project/rensa/ es una versión más especializada y rápida que el MinHash de datasketch, escrita en Rust con un poco de Python encima.

  • Para deduplicar personas, el modelo Fellegi-Sunter también es un enfoque potente. Splink es una biblioteca gratuita de Python que lo implementa para datasets grandes, y creo que también se podrían combinar partes de ambos enfoques.
    Declaro que soy el autor principal.
    También escribí un tutorial interactivo que explica cómo funciona: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
  • También existe gaoya. Lo hice yo, está escrito en Rust y ofrece bindings para Python.
    datasketch es excelente, pero no tenía suficiente rendimiento para mi caso de uso, y gaoya se usa en sistemas operativos de clustering a gran escala: https://github.com/serega/gaoya

• Qué gran coincidencia. Justo acabo de implementar un sistema MinHash que podría interesarle a alguien.
  El problema es encontrar la pseudoinversa de varias submatrices adecuadas dentro de una matriz cuadrada grande.
  Usando identidades matriciales como Woodbury y Banachiewicz, se puede actualizar la inversa de una submatriz “cercana” para calcular una nueva inversa a bajo costo.
  Basta con guardar las inversas ya calculadas usando los índices de filas/columnas como clave, y para cada nueva submatriz encontrar una inversa existente cercana que sirva como punto de partida para la actualización.
  Resolví este problema con MinHash, aplicando hash de mínimos a los índices para que las matrices cercanas tengan alta probabilidad de compartir el mismo hash.
  En mi implementación usé hashes multirresolución para poder ajustar la selectividad de búsqueda a medida que crece la cantidad de inversas ya calculadas.

• Para agregar un poco del contexto que le falta a este artículo: según tenía entendido, esta técnica se creó en los primeros días de Google para la deduplicación de conjuntos de crawling.
  También es interesante lo sorprendentemente parecido que es crear un LLM a crear un índice común de texto web.
  Se puede leer más en detalle en el libro gratuito de Jeffrey Ullman, “Mining Massive Datasets”, que explica muchas técnicas geniales e impresionantes usadas en aquella época para construir un índice de todo Internet.
  El material relacionado se puede encontrar gratis buscando “chapter 3 pdf mmds ullman”.
  Corrección: resulta que estaba equivocado y, según Wikipedia, fue inventado en DEC para AltaVista: https://en.wikipedia.org/wiki/MinHash
  En cualquier caso, el libro de Ullman tiene una buena explicación y también cubre cómo se usó en Google.

• Como me costaba entender MinHash y sus variantes, estoy creando una herramienta de visualización en línea: https://websla.sh/tools/minhash
  Todavía no está terminada y también quiero mostrar cosas como el cálculo de similitud de Jaccard, pero ya se pueden ingresar varias cadenas y ver directamente qué es realmente “minhash”.

• Usar hashing o redes neuronales pequeñas junto con motores de búsqueda vectorial y Tanimoto/Jaccard es una estrategia muy común para deduplicar datasets a gran escala.
  Puede ser más inteligente que usar trabajos MapReduce de complejidad lineal.
  Hay un buen proyecto de Google que usa el modelo RETSim de 500 mil parámetros y el motor USearch: https://github.com/google/unisim

• Ahora tengo un problema parecido en PostgreSQL. Tengo 600000 feed_items y el esquema es (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
  En particular, las columnas content y summary de algunos ítems de noticias son muy parecidas, pero no idénticas.
  Dado un par de esos ítems de noticias, quisiera reducirlos a uno solo. ¿Hay alguna buena forma de hacerlo?

  • Implementé un sistema similar a MinHash en BigQuery y pude calcular la similitud coseno entre todos los ítems de Stack Overflow en un tiempo razonable.
    El procedimiento aproximado es este:
    1. Concatenar todos los campos de texto y dividirlos en un arreglo de n-gramas, por ejemplo de 2 a n caracteres
    2. Declarar arreglos globales A y B de longitud n, y llenarlos con enteros aleatorios de 32 a 64 bits
    3. Hashear cada n-grama a un entero de 32 a 64 bits; luego multiplicar ese hash por cada valor aleatorio del arreglo A, calcular el residuo al dividir el resultado por cada valor aleatorio del arreglo B y tomar el valor mínimo
       El objetivo es obtener, por cada fila, un arreglo de enteros “minhashed” de la misma longitud que los arreglos del paso 2. Si declaras el arreglo global con longitud 64, el arreglo MinHash de cada fila también tendrá longitud 64.
    4. Con funciones de ventana, sumar N valores MinHash consecutivos para agrupar el arreglo de hashes en buckets. Por ejemplo, sumar de a 4 filas consecutivas
       Si todo salió bien, puedes expandir ese arreglo como “fila fuente” y hacer un join del dataset consigo mismo usando cada valor MinHash agrupado en buckets, lo que agrega una columna de “fila destino”.
       Si agrupas por las columnas fuente/destino y cuentas las ocurrencias, puedes estimar qué tan parecidas son dos filas.
       En esencia, mientras más seguido dos ítems se hasheen al mismo bucket, más similares son; y queda a tu criterio decidir a partir de qué punto calcular la similitud Jaccard o coseno real por pares.
  • Aquí podría ser útil usar embeddings de texto y similitud coseno: https://simonwillison.net/2023/Oct/23/embeddings/
  • Con MinHash puedes evitar la matriz de distancias O(N^2) completa, pero si solo tienes 600000 ítems, quizá puedas calcular toda la matriz por fuerza bruta en aras de la simplicidad.
    La clave es cuánto tiempo tienes disponible.
  • Si consideras que dos ítems tratan palabras clave muy parecidas, la distancia de Jaccard encajaría bien.
    Si consideras que dos ítems comparten texto muy parecido, vale la pena probar la distancia de Levenshtein.
  • Haz que un LLM cree un índice invertido de los ítems, pero imponle que mantenga baja la cardinalidad.
    Entonces puedes usar la similitud de Jaccard.

• Me gustó el artículo. En NVIDIA, nuestro equipo publicó hace poco una versión acelerada por GPU del algoritmo de deduplicación difusa descrito, y creo que a esta comunidad también podría interesarle.
  El repositorio está aquí: https://github.com/NVIDIA/NeMo-Curator/
  La documentación del script de deduplicación difusa está aquí: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
  También hay un ejemplo en Python: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
  Me gustaría escuchar comentarios.

• Estas técnicas son del tipo que no entiendo cuando las leo en un artículo, pero que asimilo de inmediato cuando meto mis datos varias veces en un ejemplo de código funcional y observo el proceso interno.
  Aprendí esta técnica por primera vez de Douglas Eck: https://research.google/people/douglas-eck/
  Se usaba en Google para agrupar canciones, y recuerdo que hablaba de hashing y vectores aleatorios.
  En ese momento me confundía, porque pensaba que una optimización con menos aleatoriedad funcionaría mejor.

  • La intuición clave, al menos para mí, es que si divides el objeto en una pila de piezas muy pequeñas y creas n formas de ordenar esas pilas, los objetos parecidos tendrán la misma pieza en la parte superior en varios ordenamientos.
    Si a eso le sumas banding y un poco de probabilidad, puedes aproximar la similitud de Jaccard en datasets enormes de una forma barata y muy fácil de paralelizar.

• Como técnica de clustering de documentos o de deduplicación de datasets, ¿qué tal queda el enfoque de “tirarle machine learning al problema” en calidad y rendimiento frente a un enfoque de algoritmo discreto más simple como este?
  Por ejemplo, crear embeddings vectoriales de documentos con un codificador LLM preentrenado, meter esos vectores en una base de datos vectorial y luego agruparlos con k-medias.

  • Un LLM es solo una de varias formas de generar embeddings.
    Para hacer k-medias igual tienes que elegir una función de distancia, como Jaccard, y k-medias probablemente no sea ideal para duplicados cercanos.
    También podrías usar MinHash como preprocesamiento para k-medias y acelerar el proceso.
    No creo que una base de datos vectorial aporte mucho.
    Si tienes cientos de millones de documentos, podría servir para consultar sketches MinHash rápidamente, pero en general probablemente sea una opción excesiva.
  • He visto que ese enfoque funciona mejor que LSH.
    Cada vez que embebes un documento, buscas vecinos cercanos aproximados antes de agregarlo, así que es O(N), como MinHash.
    Los índices vectoriales como HNSW y PQ tienen una mejor relación rendimiento/calidad que SimHash LSH, que es el equivalente de MinHash para distancia coseno.
    La calidad depende de cómo definas los duplicados cercanos y de qué modelo de embeddings uses.
    Los modelos modernos funcionan bien, y si tienes datos etiquetados puedes mejorarlos con fine-tuning.
    La principal desventaja es el costo adicional de embeber todos los documentos, especialmente si son largos.
    Pero gracias a modelos pequeños, mejores optimizaciones y hardware más rápido, este costo ha bajado muy rápido.