Entendendo o algoritmo de busca full-text BM25

 (emschwartz.me)
1 pontos por GN⁺ 2024-11-21 | 1 comentários | Compartilhar no WhatsApp
  • BM25 ainda é amplamente usado em busca full-text quando é necessário correspondência exata de palavras-chave, e se tornou um dos pilares da busca híbrida que complementa a busca por similaridade vetorial
  • Sem calcular probabilidades diretamente para ordenar documentos, o BM25 soma pesos por termo da consulta para colocar na frente os documentos que parecem mais relevantes
  • A pontuação se divide em IDF, frequência do termo no documento e normalização pelo comprimento do documento; palavras raras têm mais peso, e repetições sucessivas recebem recompensa cada vez menor
  • k1 controla a velocidade da redução no ganho por repetições, e b controla a intensidade da normalização pelo comprimento do documento; normalmente usam-se k1=1.2~2 e b=0.75
  • Como a pontuação do BM25 não é uma probabilidade real de relevância, ela é difícil de usar como valor de comparação genérico e só faz sentido quando comparada dentro da mesma coleção de documentos

O problema de busca que o BM25 tenta resolver

  • BM25, ou Best Match 25, é um algoritmo amplamente usado em busca full-text
    • É usado como padrão em Lucene/Elasticsearch e SQLite, entre outros
    • Mais recentemente, a busca híbrida, que combina busca full-text com busca por similaridade vetorial, se tornou comum
  • Em feeds de conteúdo personalizados, a busca apenas por similaridade vetorial pode ser insuficiente para tratar palavras-chave exatas
    • Se o interesse for Solid.js, usar só busca por similaridade vetorial pode acabar retornando mais conteúdo relacionado a React do que a Solid
  • A pergunta central é se é possível comparar a pontuação BM25 de um documento entre várias consultas para determinar com qual consulta esse documento combina melhor

O princípio de ranqueamento probabilístico e a abordagem do BM25

  • O objetivo da busca full-text é encontrar os documentos mais relevantes dentro do conjunto possível de documentos com base em uma consulta
  • Como não é possível saber com certeza a relevância real, os sistemas de busca tentam ordenar com base na probabilidade de um documento ser relevante para a consulta
    • Essa ideia é chamada de Probability Ranking Principle
  • A busca lexical, como o BM25, usa apenas a consulta e as características dos documentos dentro da coleção
    • Já a busca por similaridade vetorial pode usar modelos de embeddings treinados em corpora externos para representar o significado da consulta e dos documentos

Os componentes da pontuação BM25

  • O BM25 calcula a pontuação combinando vários sinais da consulta e da coleção de documentos

  • Termos da consulta

    • Se a consulta for composta por vários termos, calcula-se a pontuação de cada termo e depois tudo é somado

  • Frequência inversa de documento (IDF)

    • Indica o quão raro um termo de busca é em toda a coleção de documentos
    • Palavras comuns como the e and são consideradas pouco informativas, então termos raros ganham mais importância

  • Frequência do termo no documento

    • Reflete quantas vezes o termo de busca aparece em um documento específico
    • Quanto mais o mesmo termo se repete, maior tende a ser a chance de relevância, mas o BM25 aplica retorno decrescente às repetições

  • Comprimento do documento

    • Documentos longos podem conter mais ocorrências do termo de busca simplesmente por serem longos
    • O BM25 normaliza o comprimento comparando-o com o comprimento médio dos documentos para evitar que documentos longos recebam pontuação injustamente alta

Cada parte da fórmula do BM25

  • A pontuação total do BM25 soma a pontuação de cada termo da consulta q_i para um documento D e uma consulta Q
    • D: documento alvo
    • Q: consulta completa
    • n: número de termos da consulta
    • q_i: cada termo da consulta

  • IDF: dar mais peso a palavras raras na coleção

    • O termo de IDF calcula o quão raro cada termo da consulta é em toda a coleção de documentos
    • N: número total de documentos da coleção
    • n(q_i): número de documentos que contêm o termo da consulta
    • N - n(q_i): número de documentos que não contêm o termo da consulta
    • Termos comuns aparecem em muitos documentos, então têm impacto menor na pontuação
    • Termos raros aparecem em poucos documentos, então pesam mais na pontuação
    • Os valores 0.5 e 1 na fórmula suavizam o resultado para que ele não oscile demais quando um termo é extremamente raro ou extremamente comum

  • Frequência do termo: conta repetição, mas sem recompensa infinita

    • A frequência do termo no documento reflete com que frequência um termo da consulta aparece em um documento específico
    • f(q_i, D): frequência com que o termo da consulta q_i aparece no documento D
    • k1: parâmetro de ajuste normalmente definido entre 1.2 e 2
    • O BM25 leva em conta a repetição do termo na pontuação, mas quanto mais ele se repete, menor é o ganho adicional de pontuação
    • k1 controla quão rápido essa recompensa por repetição diminui

  • Normalização pelo comprimento do documento: ajustando a vantagem de documentos longos

    • A normalização pelo comprimento do documento compara o comprimento do documento alvo com o comprimento médio da coleção
    • |D|: comprimento do documento alvo
    • avgdl: comprimento médio dos documentos da coleção
    • b: parâmetro de ajuste que controla a intensidade da normalização pelo comprimento do documento
    • Como documentos maiores têm mais chance de conter o termo de busca com mais frequência, eles sofrem penalização no denominador da fórmula final
    • Se b=0, a normalização pelo comprimento do documento é desativada; se b=1, ela é aplicada por completo
    • b normalmente é definido como 0.75

A ideia central do BM25

  • O BM25 se baseia no Probability Ranking Principle, mas é praticamente impossível calcular a probabilidade real de relevância de um documento
  • Como, em busca, o mais importante é a ordem dos documentos, e não o valor exato da probabilidade, a fórmula elimina termos que não afetam a ordenação para tornar o cálculo prático
  • Por isso, o BM25 calcula pesos, não probabilidades em si
  • Robertson/Sparck Jones Weight é uma forma de estimar probabilidades usando a quantidade de documentos relevantes e a quantidade de documentos que contêm o termo da consulta
    • r: número de documentos relevantes que contêm o termo da consulta
    • N: número total de documentos da coleção
    • R: número de documentos relevantes da coleção
    • n: número de documentos que contêm o termo da consulta
  • A grande limitação dessa abordagem é que ela exige saber de antemão quais documentos são relevantes

A hipótese de que “a maioria dos documentos não é relevante”

  • Os criadores do BM25 assumem que, para uma consulta arbitrária, a maioria dos documentos não é relevante
  • Se o número de documentos relevantes for pequeno a ponto de poder ser ignorado, podemos assumir R = r = 0
  • Ao substituir esses valores na fórmula de Robertson/Sparck Jones Weight, obtém-se uma forma muito próxima do termo de IDF usado no BM25
  • Como mantém a mesma base teórica sem exigir informação prévia de relevância, o BM25 se torna muito mais prático
  • Victor Lavrenko descreve isso como um "salto de fé muito impressionante"

O escopo de comparação da pontuação BM25

  • Em geral, pontuações BM25 não são fáceis de comparar diretamente
    • Elas não geram um escore probabilístico entre 0 e 1
    • O algoritmo também não tenta estimar a probabilidade real de um documento ser relevante
    • O foco é aproximar a ordem de probabilidade de relevância para uma consulta dentro de uma coleção específica
  • Uma pontuação BM25 mais alta é um sinal de que o documento provavelmente é mais relevante, mas não representa a probabilidade real de relevância
  • Para o mesmo documento dentro da mesma coleção, é possível comparar pontuações BM25 entre várias consultas
    • Como o BM25 soma as pontuações de cada termo da consulta, pode-se considerar que não há diferença semântica relevante entre comparar duas pontuações de termos e comparar duas pontuações de consultas completas
  • A restrição importante é: mesmo documento, mesma coleção
    • O BM25 usa o IDF da coleção e o comprimento médio dos documentos
    • Se a coleção mudar, a pontuação também pode mudar, então comparações ao longo do tempo não são garantidas
  • Em feeds de conteúdo personalizados, é possível executar busca full-text para cada interesse do usuário e comparar as pontuações BM25 para determinar a qual interesse um conteúdo se ajusta melhor

Leitura adicional

Leituras relacionadas

1 comentários

 
GN⁺ 2024-11-21
Opiniões no Hacker News

  • Tenho usado https://typesense.org/ para busca geral e, agora que ele também oferece suporte a busca híbrida, fiquei curioso para saber se alguém já testou

    • Usei para busca híbrida e funciona muito bem
      Fico feliz em ver o Typesense sendo mencionado aqui; para projetos de RAG de pequeno porte, ele costuma ser uma boa opção, mas por algum motivo é menos conhecido do que deveria
      É fácil de implantar, os padrões são razoáveis, a documentação é boa e o clustering também é relativamente simples; ainda assim, quando é preciso se aprofundar mais, ele continua sendo bastante performático e poderoso
    • Nós também usamos e, no geral, estamos satisfeitos
      Porém, se você usar um modelo de embeddings de um provedor externo, a latência fica absurdamente alta, acima de 500 ms, então é melhor hospedá-lo diretamente dentro do cluster
      A qualidade da busca híbrida é boa, mas as opções de ajuste são muito limitadas, e as pontuações também são bastante opacas fora do ranqueamento dentro do conjunto de resultados

  • Com os avanços recentes da busca semântica baseada em vetores, fico curioso para saber qual é a stack de busca mais atual usada hoje em dia para híbridos de palavra-chave + busca semântica

    • Uma estratégia de busca de uso geral muda completamente dependendo da tarefa que você está tentando resolver
      Recentemente recebemos cerca de 3 milhões de respostas de pesquisas, cada uma com 10 campos de texto livre, e precisávamos encontrar itens sobre os quais a empresa deveria agir
      Usamos alguns modelos classificadores pequenos; depois de observar o ruído nos primeiros 10 mil registros, removemos manualmente palavras comuns e atribuímos pesos às respostas dos modelos, e isso funcionou quase perfeitamente
      Esse tipo de coisa parece menos “programação” e mais ajustar as saídas de caixa-preta de várias ferramentas até que fiquem boas para os casos de teste e para o cliente
      Como referência, processamos tudo em Node.js em um servidor pequeno, encadeando vários modelos pequenos do Hugging Face
    • A maioria dos produtos de busca híbrida, comerciais e open source, parece usar BM25 + busca por similaridade vetorial baseada em embeddings
      Os resultados geralmente são combinados com Reciprocal Rank Fusion (RRF)
      O artigo de RRF é impressionante por ser surpreendentemente simples, e tem só 2 páginas: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
    • Não se prenda a uma única stack; é preciso estar preparado para usar a ferramenta mais adequada a cada tarefa
      Para trabalhos no estilo BM25, dá para usar Elasticsearch; para busca vetorial simples e rápida, Turbopuffer; para pré-computar resultados de determinadas consultas ou lidar com atributos dinâmicos que mudam com frequência, como preços, Redis também pode servir
      Acho melhor combinar essas coisas em um modelo scatter/gather
      Fora da stack de busca, quase sempre existe uma camada de serviço de inferência para reranking e, idealmente, ela se torna um serviço simples parecido com o restante da infraestrutura de machine learning
      Quase sempre também é necessário rotear consultas de usuários, por exemplo entendendo que “buscar por ID” deve ir para um sistema, enquanto “busca semântica fuzzy” deve ir para outro
      Essas estruturas de dados são muito diferentes, e busca costuma cobrir uma ampla variedade de casos de uso distintos
      Considero um antipadrão empurrar tudo para dentro de um único sistema
      Cada sistema se adapta a cargas de trabalho diferentes, e recursos de inferência embutidos dificilmente acompanham a velocidade das ferramentas gerais de machine learning com as quais engenheiros de ML estão acostumados
      Tentei fazer isso com Elasticsearch Learning to Rank, mas era uma tarefa sem futuro
      Ainda assim, entre as tentativas de resolver um conjunto amplo de casos de uso em uma única stack, Vespa provavelmente é a melhor
    • É um ótimo texto sobre BM25
      Como autor do txtai, o txtai implementa um índice BM25 performático em Python por meio do pacote arrays e armazena vetores de frequência de termos no SQLite
      A abordagem de índice híbrido do txtai oferece suporte a combinação convexa quando as pontuações BM25 estão normalizadas e a Reciprocal Rank Fusion (RRF) quando não estão
      [1] https://github.com/neuml/txtai
      [2] https://neuml.hashnode.dev/building-an-efficient-sparse-keyw...
      [3] https://neuml.hashnode.dev/benefits-of-hybrid-search
      [4] https://github.com/neuml/txtai/blob/master/src/python/txtai/...
    • A biblioteca de LLM Langroid[1] tem uma implementação de RAG limpa e extensível dentro do DocChatAgent[2]
      Ela usa várias técnicas de busca: busca lexical (bm25, busca fuzzy), busca semântica (embeddings), reranking (cross-encoder, Reciprocal Rank Fusion) e reranking para garantir diversidade e mitigar o problema de lost-in-the-middle
      [1] Langroid - framework multiagente de LLM criado por pesquisadores da CMU/UW-Madison https://github.com/langroid/langroid
      [2] Implementação do DocChatAgent -
      https://github.com/langroid/langroid/blob/main/langroid/agen...
      Basta começar pelo método answer_from_docs e seguir a partir dali
      A propósito, se você é o fundador da Kadoa, o Kadoa-snack é uma das ferramentas que uso com prazer todos os dias para encontrar discussões do HN relacionadas a LLMs

  • É um bom texto.
    Para acrescentar um contexto um pouco mais difícil de encontrar: BM25 é a sigla de “Best Matching 25”, e “best matching” significa que é uma fórmula que atribui rankings e pesos aos termos combinando os termos da consulta com os termos do documento.
    O 25 é simplesmente um número de sequência: antes dele houve 24 variações da fórmula, e depois também houve outras variações, mas a de número 25 foi publicada porque era a que funcionava melhor.
    Foi concebido por Stephen Robertson e Karen Spärck Jones (famosa pelo IDF) e implementado pela primeira vez no sistema de pesquisa em recuperação de informação OKAPI, de Robertson.
    O sistema OKAPI foi benchmarkado durante vários anos na TREC (Text Retrieval Conference) anual do NIST dos EUA, algo próximo de um “campeonato mundial” internacional de metodologias de mecanismos de busca.
    Porém, o objetivo do evento é mais a comparação e o aprendizado mútuo do que vencer; é um evento recomendável realizado todo mês de novembro em Gaithersburg, Maryland.
    Além do modelo de espaço vetorial “saco de palavras” (vetores esparsos de termos) e do modelo probabilístico ao qual o BM25 pertence, há uma quantidade surpreendente — e crescente — de arcabouços teóricos para ranquear um conjunto de documentos dada uma consulta.
    Por exemplo, há Divergence from Randomness, modelagem estatística de linguagem, Learning to Rank, recuperação de informação quântica, ranqueamento por redes neurais etc.
    Em conferências como ICTIR ou SIGIR, ainda aparecem de vez em quando paradigmas de busca completamente novos.
    Aqui, “modelagem estatística de linguagem” não se refere aos grandes modelos de linguagem que estão em alta hoje; estes entram na categoria de “busca neural”.
    Além disso, ao pesquisar por “Quantum IR”, você pode acabar vendo espectroscopia no infravermelho ou uma empresa de cimento com o mesmo nome, e não um tutorial de recuperação de informação quântica.
    Mesmo no século 21, a tecnologia de busca ainda tem essas sutilezas.
    Se quiser comparar diretamente o BM25 com alternativas, recomendo Terrier, um mecanismo de busca open source e plataforma de pesquisa desenvolvido pela University of Glasgow.
    O BM25 já tem mais de 25 anos, mas ainda se provou uma baseline difícil de superar e é frequentemente usado como ponto de referência ao comparar novos métodos.
    Uma variação mais recente, o BM24F, consegue lidar com vários campos, como título, corpo do texto e hyperlinks, além de hipertexto.
    O artigo recomendado é Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 1”. Information Processing & Management 36(6): 779–808, além da Part 2 posterior.
    Infelizmente, não é open access.

    • Por coincidência, a US NIST TREC está acontecendo agora.
      Começou no dia 18 e termina no dia 22.
      Mais detalhes: https://trec.nist.gov/
    • Fico curioso se há mais material sobre BM24F.
      Mesmo procurando no Google e no Google Scholar, não encontrei conteúdo relacionado.

  • Divulgação sem vergonha: https://github.com/jankovicsandras/plpgsql_bm25
    https://github.com/jankovicsandras/bm25opt

    • Se a onda é divulgar projetos de hobby sem vergonha, SearchArray é uma extensão do pandas para busca full-text (BM25) quando se quer fuçar coisas no Google Colab.
      https://github.com/softwaredoug/searcharray
      Também divulgo o BM25S, do Xing Han Lu, que é muito popular e tem um objetivo parecido.
      https://github.com/xhluca/bm25s
    • Ontem eu estava pensando em adicionar BM25 a um pequeno projeto paralelo; a divulgação veio em boa hora.
      Fico curioso se existe algum projeto wrapper em Python puro para gerenciar muitos textos e documentos PDF.
      Pensei em Solr ou ElasticSearch, mas eles parecem pesados demais para o que quero fazer agora.
      Como o SQLite usa BM25, estou considerando uma abordagem que combine pysqlite3 e PyPDF2.
      Fugindo um pouco do tópico, acho que muita gente procura ferramentas para criar aplicações híbridas de BM25 / armazenamento vetorial / LLM.

  • Fico curioso se o comprimento médio de documento mencionado na normalização por comprimento de documento é a mediana.
    Para reduzir corretamente o peso de documentos excessivamente longos, acho que deveria ser a mediana; caso contrário, documentos muito longos não puxariam a média para cima de forma injusta?

    • No caso do Lucene, é a média aritmética.
      Usar a mediana também parece ser um experimento interessante.
      Fico curioso se você conhece algum dataset de busca em que o comprimento dos documentos varie muito.
      Por exemplo, no MSMarco os comprimentos são bastante uniformes.

  • É um bom texto.
    Eu gostaria sinceramente de aprender a pensar nesse tipo de problema em forma matemática e a testá-lo; há algum material de referência recomendável?

  • A busca híbrida resolve o velho desafio da relevância dos resultados de busca.
    Usando fusão de ranking entre palavras-chave e vetores, é possível criar uma busca híbrida que funcione na maioria das situações.

  • O BM25 é um algoritmo antigo, desenvolvido na década de 1970
    Basicamente é um modelo estatístico rudimentar, e os estatísticos de hoje conseguem fazer muito melhor
    Vejo a busca como algo estritamente dominado por métodos baseados em aprendizado
    Claro que o aprendizado pode usar a busca como entrada
    Ainda há muita gente que não percebeu isso, ou que tem incentivos para manter tecnologias antigas pelo maior tempo possível, mas a pressão do mercado acabará mudando isso

    • Essa pressão do mercado é a mesma que levou o Google a abandonar, ou reaproveitar, tecnologias antigas de busca que funcionavam bem e migrar para uma nova e reluzente busca baseada em machine learning?
      Não foi por causa dessa tecnologia que passamos a acrescentar “+reddit” a cada consulta para escapar da guerra de SEO adversarial?
      Ser antigo não significa ser ruim
      O que importa é a utilidade de uma invenção, descoberta ou técnica, não sua idade; essa atitude tecnocrática estranha, obcecada pela idade, é preocupante
    • É verdade que o BM25 surgiu a partir de pesquisas iniciais dos anos 1970 e 1980, especialmente sobre o princípio probabilístico de ranqueamento, mas fico com algumas dúvidas
      Quais abordagens estatísticas modernas específicas você considera superiores a ponto de substituir o BM25 em aplicações reais?
      Em especial, tenho curiosidade sobre como elas lidam com casos-limite como termos raros e normalização por comprimento do documento, que o BM25 tentou tratar explicitamente
      Concordo que abordagens baseadas em aprendizado apresentaram resultados impressionantes, mas também gostaria de ouvir melhor o que exatamente significa dizer que a busca é “estritamente dominada” por métodos de aprendizado
      Você está se referindo a benchmarks específicos ou a casos reais em produção?
    • É uma opinião bem apimentada
      Acho que muitos especialistas em busca não concordariam
      Um excelente podcast de David Tippet (ex-OpenSearch, atualmente no Github) e Nicolay Gerold tem este título:
      “BM25 is the workhorse of search; vectors are its visionary cousin”
      https://www.youtube.com/watch?v=ENFW1uHsrLM
    • Também há claramente incentivos para vender o “novo”
      Durante todo o tempo em que trabalhei na área de busca, houve inúmeras modas e tecnologias relacionadas a IA
      Agora, empresas de busca vetorial com enormes investimentos de VC estão empurrando uma determinada visão com um exército de evangelistas técnicos
      Por outro lado, em lugares como o Google, é enorme a quantidade de curadoria manual e de taxonomias manuais básicas e tediosas que realmente fazem a “busca semântica” funcionar
      Só que essas coisas não são sexy, então quase não são discutidas em conferências