Detecção de duplicatas aproximadas com similaridade de Jaccard e MinHash

• Em coleções grandes de documentos, o rastreamento da web pode buscar a mesma página várias vezes ou misturar versões com pequenas alterações, então a similaridade de Jaccard e o MinHash se tornam formas práticas de encontrar documentos “quase iguais”
• A similaridade de Jaccard converte documentos em conjuntos de características e então calcula tamanho da interseção / tamanho da união; pares acima de um limiar são tratados como duplicatas aproximadas, mas essa relação em geral não é transitiva
• Comparar todos os pares de documentos custa O(n²) em relação ao tamanho do corpus, então o MinHash resume cada documento em uma assinatura de tamanho fixo para aproximar a similaridade de forma probabilística
• Com k funções de hash, é possível estimar a similaridade pela proporção de posições iguais nas assinaturas dos dois documentos, e condições como min-wise independence são importantes na escolha das funções de hash
• Usar a assinatura inteira ou partes dela como chave de agrupamento permite controlar a probabilidade de documentos semelhantes caírem no mesmo bucket, e a forma de fazer n-gramas e tokenização determina a sensibilidade e o custo da detecção

---

A dificuldade da detecção de duplicatas aproximadas

• O objetivo é encontrar, em um grande conjunto de documentos, documentos que não são exatamente iguais, mas são quase iguais
  • Ao rastrear a web por um período, é possível baixar a mesma página várias vezes com metadados ligeiramente diferentes
  • Também podem existir várias versões com pequenas edições da mesma página
• A abordagem básica é definir uma função de similaridade S(A, B) entre dois documentos e considerar como duplicatas aproximadas os pares cujo valor seja maior ou igual a um limiar Scrit
• “Quase idêntico” em geral não é uma relação transitiva
  • A e B, e B e C, podem ser semelhantes acima do limiar
  • Ao mesmo tempo, A e C podem ficar abaixo do limiar
  • Por isso, detectar duplicatas aproximadas em larga escala é mais difícil do que detectar duplicatas exatas

Definição da similaridade de Jaccard

• O índice de Jaccard expressa a similaridade entre dois conjuntos finitos como tamanho da interseção / tamanho da união

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

• Se dois conjuntos são parecidos, eles compartilham a maioria dos elementos, então a união cresce pouco e a interseção diminui pouco

• Se dois conjuntos são totalmente separados, o tamanho da interseção é 0, então a similaridade de Jaccard é 0

• Se dois conjuntos são idênticos, interseção e união são o mesmo conjunto, então a similaridade de Jaccard é 1

• Como documentos reais têm a forma de strings Unicode e semelhantes, primeiro é preciso converter o documento em um conjunto de características

O problema de escalabilidade de comparar todos os pares

• Depois de converter documentos em conjuntos de características, a própria definição de encontrar pares com alta similaridade de Jaccard é simples
• Mas comparar todos os pares de documentos faz o custo crescer como O(n²) em relação ao tamanho do corpus
• Na detecção de duplicatas exatas, evita-se esse custo aplicando hash nos documentos e agrupando os que caem no mesmo bucket de hash
• A detecção de duplicatas aproximadas também precisa de um atalho parecido; nessa área isso é chamado de locality-sensitive hash
• Para similaridade de Jaccard, existe uma técnica adequada a esse objetivo, e o núcleo dela é o MinHash

Aproximando a similaridade de Jaccard com MinHash

• O MinHash aproxima a similaridade de Jaccard sem comparar o conjunto inteiro toda vez, usando apenas uma pequena assinatura (signature) pré-calculada de cada documento

• A ideia básica é amostrar um elemento aleatório de forma uniforme da união e verificar se esse elemento também está na interseção

• Na prática, em vez de uma permutação aleatória, usa-se uma boa função de hash H(x) e armazena-se, para cada conjunto, a característica com o menor valor de hash

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

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

• A operação min é associativa, então o menor hash de cada documento pode ser pré-processado de forma independente

• A probabilidade de os menores hashes de dois conjuntos serem iguais é a mesma que a similaridade de Jaccard entre eles

Várias funções de hash e vetor de assinatura

• Se usar apenas uma função de hash, só é possível obter uma estimativa booleana de “igual/diferente” entre dois documentos

• Com k funções de hash diferentes, cada documento pode ser resumido em um vetor de k valores de 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)) ]

• A similaridade de Jaccard é aproximada pela proporção de posições iguais nas duas assinaturas

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

• A escolha da família de funções de hash é sutil

  • O objetivo é aproximar uma permutação aleatória sobre todo o espaço de características
  • Famílias reais de funções de hash representam apenas uma fração muito pequena de todas as permutações possíveis
  • É preciso evitar correlações inadequadas, e essa propriedade relacionada é chamada de min-wise independence
  • Esse problema foi relativamente bem estudado, e há soluções eficientes na literatura

Encontrando pares candidatos em todo o corpus

• Ao reduzir cada documento a uma impressão digital de k valores de hash, é possível aproximar a similaridade de Jaccard com eficiência
• O problema restante é encontrar, em todo o corpus, documentos com alta similaridade sem olhar todos os pares
• A estratégia é agrupar os documentos por algum tipo de chave e comparar apenas os que estiverem no mesmo grupo
• A chave de agrupamento deve fazer com que documentos semelhantes tenham alta probabilidade de cair juntos, enquanto documentos não semelhantes idealmente não devem ser agrupados juntos

• Usar a assinatura MinHash completa como chave

  • A forma mais simples é usar os k valores de MinHash como uma única chave de agrupamento
  • Dois documentos são considerados duplicatas aproximadas apenas se todos os valores de MinHash coincidirem
  • O artigo do GPT-3 usou remoção de duplicatas aproximadas no pipeline de preparação do dataset e, pela formulação citada, isso é interpretado como uso da implementação MinHashLSH do Spark com 10 hashes
  • A vantagem dessa abordagem é a simplicidade e eficiência
  • Agrupar por uma única string de bytes de alta cardinalidade é algo fácil de escalar horizontalmente
  • Isso corresponde a uma primitiva básica das ferramentas de processamento de dados, como o “shuffle” entre map e reduce no MapReduce
  • Se a similaridade de Jaccard entre dois documentos é J(A, B) e os k valores precisam coincidir todos, então a probabilidade de colisão para um único par é J(A, B)^k
  • Com k = 10, documentos com similaridade de cerca de 0,6 ou menos quase nunca colidem
  • A probabilidade de correspondência cresce quando a similaridade se aproxima de 0,95
  • Se o objetivo é encontrar documentos extremamente próximos, isso pode ser suficiente
  • Esse cálculo J^k vale para um único par de documentos
  • Se houver muitos documentos muito parecidos entre si, as probabilidades por par não são independentes
  • Na prática, documentos muito semelhantes tendem a cair em no máximo dois ou três buckets, o bastante para encontrar quase todas as duplicatas

Detecção de duplicatas mais flexível

• Se você quiser encontrar não só documentos com similaridade próxima de 1, mas também documentos acima de 0,8 ou 0,7, usar a assinatura completa como chave pode ser rigoroso demais

• Usar apenas parte dos k valores de MinHash como chave de agrupamento aumenta a chance de colisão mesmo com similaridade menor

  • Por exemplo, é possível agrupar pelos 4 primeiros valores de MinHash e, dentro do mesmo bucket, usar a assinatura completa para estimar a similaridade real

• Reduzir a quantidade de hashes tem limites

  • J^r é sempre menor que J
  • Se r ficar pequeno demais, pode haver colisões falsas em excesso

• Em vez disso, é possível criar várias chaves por documento e colocá-lo em vários buckets

  • Por exemplo, pode-se calcular k = 20 hashes, distribuir em b = 4 buckets, e compor cada chave com r = 5 hashes

• A probabilidade de dois documentos colidirem em pelo menos um bucket é a seguinte

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

• No exemplo com 4 grupos e 5 hashes por grupo, o ponto em que a probabilidade de colisão chega a 50% se desloca para algo em torno de J = 0.7

• Quando r e b são ambos maiores que 1, a curva resultante tende a ter formato de S, oferecendo espaço para ajustar sensibilidade, recall e custo de desempenho

Relação com HyperLogLog

• O truque central do MinHash tem semelhanças com algoritmos de sketch como o HyperLogLog
• O HyperLogLog aplica hash a cada elemento do fluxo e armazena o máximo observado da quantidade de zeros à esquerda no valor de hash
• As duas técnicas mapeiam elementos de entrada para uma distribuição uniforme com funções de hash e então calculam um valor extremo observado, estimando propriedades distribucionais com apenas um resumo de tamanho constante
• Se pensarmos com a ordem dos bits invertida, o HyperLogLog pode ser visto como um método que calcula o mínimo observado de log2(H(x)), enquanto o MinHash usa o mínimo do próprio H(x)
• As duas estruturas são, em certo sentido, duais
  • Ao combinar duas estruturas HyperLogLog, é possível estimar o tamanho da união de dois conjuntos
  • Ao comparar duas estruturas MinHash, é possível estimar o tamanho relativo da interseção de dois conjuntos
• Ao combinar as duas estruturas, é possível construir sketches capazes de responder perguntas sobre interseção e união de conjuntos arbitrários
  • Essa ideia já era conhecida até 2013, e há literatura relacionada e trabalhos posteriores

Como representar documentos como conjuntos

• Para usar Jaccard e MinHash, primeiro é preciso converter o documento de texto em um conjunto de características
• Seja qual for o método, o documento pode passar por normalização no pré-processamento
  • Conversão para a Unicode normalization form padrão
  • Normalização de maiúsculas e minúsculas
  • Compressão de espaços em branco consecutivos
  • E transformações semelhantes

• n-grama ou shingle

  • O documento pode ser representado como o conjunto de todos os n-gramas que aparecem nele
  • Na literatura de processamento de texto em grande escala, também se usa o termo “shingle”, mas aqui ele cumpre o mesmo papel de um n-grama
  • Há trade-offs na escolha do valor de n
  • Valores pequenos comparam documentos de forma mais grosseira
  • Por exemplo, grande parte dos textos em inglês pode parecer bastante semelhante sob a ótica de bigramas
  • Valores maiores produzem características mais distintivas e conjuntos maiores
  • Se ficar grande demais, a sensibilidade pode cair, embora problemas de desempenho provavelmente apareçam antes disso
  • Segundo Mining of Massive Datasets §3.2.2, valores entre n = 5 e 9 parecem ser escolhas comuns em várias aplicações

• Separação por palavras ou tokens

  • Também é possível dividir a entrada em “palavras” ou “tokens” e usá-los como características
  • O trecho citado do artigo do GPT-3 menciona o tokenizer padrão do Spark, o que aparentemente se refere a pyspark.ml.feature.Tokenizer, que converte a entrada para minúsculas e a divide com base em espaços em branco
  • Também é possível usar um tokenizer mais sofisticado do NLTK
  • Uma abordagem híbrida também é possível, usando n-gramas de tokens após a tokenização
  • Tokens individuais têm entropia maior do que bytes ou caracteres, então nesse caso usa-se um valor de n menor

[GN⁺]

Comentários do Hacker News

• Muita gente deixa passar que métricas baseadas em conjuntos como a similaridade de Jaccard (coeficiente de Tanimoto) ou o score F1 (coeficiente de Dice) também podem ser usadas da mesma forma em conjuntos fuzzy
  Só que é preciso escolher um par adequado de T-Norm / T-Conorm para expressar os conceitos de interseção e união em conjuntos fuzzy, e há infinitas opções
  Na verdade, isso é até uma vantagem, já que dá para escolher o par que melhor se encaixa na semântica desejada
  Já vi isso ser tratado na validação de segmentação de imagens médicas, quando o resultado da segmentação e o gabarito não são máscaras binárias, mas sim probabilísticas/fuzzy: 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 aplica-se um limiar de 0,5 para criar um conjunto binário e depois usa-se a variante binária de Jaccard/Dice, mas isso aparentemente reduz a precisão do operador de validação em algo como duas casas decimais
  É como anunciar que um algoritmo é 0,001 melhor que o estado da arte, ignorando o fato de que a margem de erro do operador de validação é 0,1

• Para deduplicar registros de cidadãos em um grande banco de dados do governo francês, um cliente já fez uma implementação própria dessa técnica em Python, e funcionou bem
  Hoje em dia eu provavelmente recomendaria usar datasketch: https://pypi.org/project/datasketch/
  Fui procurar e vi que continuam surgindo ferramentas novas sobre esse tema. Por exemplo, https://pypi.org/project/rensa/ é uma versão mais especializada e mais rápida que o MinHash do datasketch, escrita em Rust com uma fina camada em Python por cima

  • Para deduplicação de pessoas, o modelo Fellegi-Sunter também é uma abordagem poderosa. Splink é uma biblioteca Python gratuita que implementa isso para grandes conjuntos de dados, e talvez dê até para combinar partes das duas abordagens
    Declaro que sou o autor principal
    Também escrevi um tutorial interativo explicando como funciona: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
  • Também existe o gaoya. Fui eu que fiz, é escrito em Rust e também oferece bindings para Python
    O datasketch é excelente, mas no meu caso de uso o desempenho não era suficiente, e o gaoya está sendo usado em um sistema operacional de clustering em grande escala: https://github.com/serega/gaoya

• Que coincidência incrível. Acabei de implementar um sistema de MinHash que alguém poderia achar interessante
  O problema é encontrar pseudoinversas de várias submatrizes adequadas em uma grande matriz quadrada
  Usando identidades matriciais como Woodbury e Banachiewicz, dá para atualizar a inversa de uma submatriz “próxima” e calcular de forma barata a nova inversa
  Basta armazenar as inversas já calculadas usando os índices de linha/coluna como chave e, para cada nova submatriz, encontrar uma inversa existente próxima para usar como ponto de partida da atualização
  Resolvi esse problema com MinHash, aplicando min-value hashing ao índice para aumentar a chance de matrizes próximas terem o mesmo hash
  Na minha implementação, usei hashing em múltiplas resoluções para poder ajustar a seletividade da busca à medida que o número de inversas já calculadas aumenta

• Para acrescentar um pouco do contexto que faltou no texto, eu entendia que essa técnica tinha sido criada nos primeiros tempos do Google para deduplicar conjuntos rastreados pelo crawler
  Também é interessante como o trabalho de construir LLMs e o de criar um índice comum de textos da web são surpreendentemente parecidos
  Dá para ler sobre isso em detalhe no livro gratuito de Jeffrey Ullman, “Mining Massive Datasets”, que explica muitas das técnicas legais e impressionantes usadas na época para indexar toda a internet
  Você pode encontrar o material gratuitamente procurando por “chapter 3 pdf mmds ullman”
  Edit: descobri que eu estava errado e, segundo a Wikipedia, isso foi inventado na DEC para o AltaVista: https://en.wikipedia.org/wiki/MinHash
  De todo modo, o livro do Ullman traz uma boa explicação e também cobre como isso foi usado no Google

• Como tive dificuldade para entender o MinHash e suas variantes, estou fazendo uma ferramenta de visualização online: https://websla.sh/tools/minhash
  Ainda não está pronta, e eu também queria mostrar coisas como o cálculo da similaridade de Jaccard, mas já dá para inserir várias strings e ver por si mesmo o que “minhash” realmente é

• Usar hashing ou pequenas redes neurais com motores de busca vetorial junto com Tanimoto/Jaccard é uma estratégia muito comum para deduplicação em grandes conjuntos de dados
  Pode ser mais inteligente do que usar um trabalho MapReduce de complexidade linear
  Há um bom projeto do Google que usa o modelo RETSim de 500 mil parâmetros e o mecanismo USearch: https://github.com/google/unisim

• Estou com um problema parecido no PostgreSQL agora. Tenho 600000 feed_items e o esquema é (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
  Em particular, as colunas content e summary de alguns itens de notícia são muito parecidas, mas não idênticas.
  Se eu tiver dois itens de notícia assim, gostaria de reduzi-los a um só — existe uma boa abordagem para isso?

  • Implementei um sistema parecido com MinHash no BigQuery e consegui calcular a similaridade de cosseno entre todos os itens do Stack Overflow em um tempo razoável.
    O procedimento aproximado é assim:
    1. Concatenar todos os campos de texto e dividi-los em um array de n-gramas, por exemplo, unidades de 2~n caracteres
    2. Declarar arrays globais A e B de tamanho n e preenchê-los com inteiros aleatórios de 32~64 bits
    3. Fazer hash de cada n-grama em um inteiro de 32~64 bits e, em seguida, multiplicar esse hash por cada valor aleatório do array A, tirar o resto da divisão do resultado por cada valor aleatório do array B e pegar o menor valor
       O objetivo é obter, para cada linha, um array de inteiros “minhashed” com o mesmo comprimento dos arrays da etapa 2. Se o comprimento do array global for 64, então o array MinHash de cada linha também terá comprimento 64.
    4. Usar uma window function para somar N valores consecutivos de MinHash e bucketizar o array de hashes. Por exemplo, somar grupos consecutivos de 4 linhas.
       Se tudo der certo, você pode expandir esse array para formar uma “linha de origem” e fazer um self-join do dataset usando cada valor bucketizado de MinHash, adicionando uma coluna de “linha de destino”.
       Se agrupar pelas colunas de origem/destino e contar as ocorrências, dá para estimar o quanto duas linhas são parecidas.
       Essencialmente, quanto mais dois itens caírem em buckets parecidos, mais semelhantes eles são; a partir de certo ponto, você decide por conta própria quando vale calcular a similaridade real par a par com Jaccard ou cosseno.
  • Aqui, pode ser útil usar embeddings de texto e similaridade de cosseno: https://simonwillison.net/2023/Oct/23/embeddings/
  • Usar MinHash permite evitar a matriz de distâncias O(N^2) inteira, mas se são “só” 600000 itens, talvez ainda dê para calcular a matriz completa na força bruta por simplicidade.
    A questão é quanto tempo você tem disponível.
  • Se você considera que dois itens tratam de palavras-chave muito parecidas, então a distância de Jaccard provavelmente se encaixa bem.
    Se você considera que dois itens compartilham texto muito parecido, então vale tentar a distância de Levenshtein.
  • Dá para pedir a um LLM que crie um índice invertido dos itens, forçando-o a manter a cardinalidade baixa.
    Aí você pode usar similaridade de Jaccard.

• Gostei do texto. Na NVIDIA, nossa equipe lançou recentemente uma versão acelerada por GPU do algoritmo de deduplicação difusa descrito, e achei que esta comunidade poderia se interessar.
  O repositório está aqui: https://github.com/NVIDIA/NeMo-Curator/
  A documentação do script de deduplicação difusa está aqui: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
  Também há um exemplo em Python: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
  Gostaria de ouvir feedback.

• Esse é o tipo de técnica que não faz sentido para mim quando leio sobre ela, mas que eu absorvo imediatamente depois de jogar meus dados em um exemplo de código funcionando algumas vezes e observar o processo por dentro.
  Aprendi essa técnica primeiro com Douglas Eck: https://research.google/people/douglas-eck/
  Ela foi usada no Google para clustering de músicas, e lembro que falavam sobre hashing e vetores aleatórios.
  Na época isso me confundiu, porque eu achava que uma otimização com menos aleatoriedade funcionaria melhor.

  • A intuição central, pelo menos para mim, é que, se você dividir os objetos em uma pilha de pedacinhos muito pequenos e criar n maneiras de ordenar essas pilhas, então objetos parecidos acabam tendo os mesmos pedaços subindo ao topo em várias ordenações.
    Com um pouco de banding e probabilidade básica, isso permite aproximar a similaridade de Jaccard em datasets enormes de um jeito barato e muito fácil de paralelizar.

• Pensando nisso como uma técnica de clustering de documentos ou de deduplicação de datasets, como a abordagem de “jogar aprendizado de máquina no problema” se compara a algoritmos discretos mais simples em termos de qualidade e desempenho?
  Por exemplo, gerar embeddings vetoriais dos documentos com um encoder de LLM pré-treinado, colocar esses vetores em um banco vetorial e depois fazer clustering com k-means.

  • LLM é só uma entre várias formas de gerar embeddings.
    Para fazer k-means, você ainda precisa escolher uma função de distância como Jaccard, e k-means provavelmente não é ideal para duplicatas próximas.
    Você também pode usar MinHash como pré-processamento do k-means para acelerar.
    Não vejo banco vetorial ajudando muito.
    Se você tiver centenas de milhões de documentos, talvez dê para usá-lo para acelerar consultas de sketches MinHash, mas, em geral, provavelmente seria uma escolha exagerada.
  • Já vi essa abordagem funcionar melhor que LSH.
    Como você faz uma busca aproximada de vizinho mais próximo antes de adicionar cada documento embutido, ela é O(N), como MinHash.
    Índices vetoriais como HNSW e PQ oferecem um compromisso melhor entre desempenho e qualidade do que o SimHash LSH, que seria o equivalente ao MinHash para distância de cosseno.
    A qualidade depende de como você define duplicatas próximas e de qual modelo de embedding usa.
    Os modelos mais recentes funcionam bem e, se você tiver dados rotulados, pode melhorar ainda mais com ajuste fino.
    A principal desvantagem é o custo extra de gerar embeddings para todos os documentos, especialmente os longos.
    Mas esse custo caiu muito rapidamente graças a modelos menores, otimizações melhores e hardware mais veloz.