Entender BM25, el algoritmo de búsqueda de texto completo

• BM25 sigue siendo ampliamente usado en búsquedas de texto completo que requieren coincidencias exactas de palabras clave, y se convirtió en uno de los pilares de la búsqueda híbrida, que complementa la búsqueda por similitud vectorial
• Para ordenar documentos sin calcular probabilidades directamente, BM25 suma pesos por cada término de la consulta y coloca primero los documentos que parecen más relevantes
• La puntuación se divide en IDF, frecuencia del término dentro del documento y normalización por longitud del documento; las palabras raras pesan más y las apariciones repetidas se recompensan cada vez menos
• k1 controla qué tan rápido disminuye la recompensa por apariciones repetidas, y b controla la intensidad de la normalización por longitud del documento; normalmente se usan k1=1.2~2 y b=0.75
• La puntuación BM25 no es una probabilidad real de relevancia, por lo que es difícil usarla como un valor de comparación universal; tiene sentido al compararla dentro de la misma colección de documentos

---

El problema de búsqueda que BM25 intenta resolver

• BM25, o Best Match 25, es un algoritmo ampliamente usado en búsquedas de texto completo
  • Se usa como valor predeterminado en Lucene/Elasticsearch y SQLite, entre otros
  • Recientemente se volvió común la búsqueda híbrida, que combina búsqueda de texto completo con búsqueda por similitud vectorial
• En feeds de contenido personalizado, la búsqueda por similitud vectorial por sí sola puede ser insuficiente para manejar palabras clave exactas
  • Si el interés es Solid.js, al usar solo búsqueda por similitud vectorial puede aparecer más contenido relacionado con React que con Solid
• La pregunta central es si se puede comparar la puntuación BM25 de un documento entre varias consultas para determinar con qué consulta encaja mejor ese documento

El principio de ranking probabilístico y el enfoque de BM25

• El objetivo de la búsqueda de texto completo es encontrar los documentos más relevantes dentro del conjunto de documentos posible para una consulta
• Como no se puede conocer con certeza la relevancia real, la búsqueda intenta ordenar según la probabilidad de que un documento sea relevante para la consulta
  • Esta idea se conoce como Probability Ranking Principle
• Las búsquedas basadas en vocabulario, como BM25, usan solo las características de la consulta y de los documentos dentro de la colección
  • La búsqueda por similitud vectorial puede usar modelos de embeddings entrenados con corpus de texto externos para representar el significado de consultas y documentos

Componentes de la puntuación BM25

• BM25 calcula una puntuación combinando varias señales de la consulta y de la colección de documentos

• Términos de la consulta

  • Si la consulta de búsqueda está compuesta por varios términos, se calcula una puntuación para cada término y luego se suman

• Frecuencia inversa de documento (IDF)

  • Indica qué tan raro es un término de búsqueda específico en toda la colección de documentos
  • Considera que palabras comunes como the y and aportan poca información, y aumenta la importancia de las palabras raras

• Frecuencia del término dentro del documento

  • Refleja cuántas veces aparece el término de búsqueda en un documento específico
  • Se asume que si el mismo término se repite más veces, la probabilidad de relevancia aumenta, pero BM25 aplica un efecto decreciente a las apariciones repetidas

• Longitud del documento

  • En documentos largos, los términos de búsqueda pueden aparecer más veces simplemente por ser largos
  • BM25 normaliza la longitud del documento comparándola con la longitud promedio de los documentos, para que los documentos largos no reciban una puntuación injustamente alta

Cada parte de la fórmula de BM25

• La puntuación total de BM25 para un documento D y una consulta Q se obtiene sumando la puntuación de cada término de consulta q_i
  • D: documento objetivo
  • Q: consulta completa
  • n: cantidad de términos de la consulta
  • q_i: cada término de la consulta

• IDF: dar más peso a las palabras raras dentro de la colección

  • El componente IDF calcula qué tan raro es un término de consulta dentro de toda la colección de documentos
  • N: número total de documentos en la colección
  • n(q_i): número de documentos que contienen el término de consulta
  • N - n(q_i): número de documentos que no contienen el término de consulta
  • Como los términos comunes aparecen en muchos documentos, su impacto en la puntuación se reduce
  • Como los términos raros aparecen solo en pocos documentos, se reflejan con más peso en la puntuación
  • Los valores 0.5 y 1 en la fórmula sirven para suavizar el resultado, de modo que no fluctúe demasiado cuando un término es muy raro o muy común

• Frecuencia del término: refleja la repetición, pero no la recompensa infinitamente

  • La frecuencia del término dentro del documento refleja qué tan seguido aparece un término de consulta específico en un documento determinado
  • f(q_i, D): frecuencia con la que el término de consulta q_i aparece en el documento D
  • k1: parámetro de ajuste que normalmente se configura entre 1.2 y 2
  • BM25 refleja la repetición de términos en la puntuación, pero a medida que aumentan las repeticiones, el incremento adicional de la puntuación disminuye
  • k1 controla qué tan rápido se reduce la recompensa por repetición de términos

• Normalización por longitud del documento: ajustar la ventaja de los documentos largos

  • La normalización por longitud del documento compara la longitud del documento objetivo con la longitud promedio de los documentos de la colección
  • |D|: longitud del documento objetivo
  • avgdl: longitud promedio de los documentos de la colección
  • b: parámetro de ajuste que controla la intensidad de la normalización por longitud del documento
  • Como en los documentos más largos que el promedio es más probable que los términos de búsqueda aparezcan con más frecuencia, reciben una penalización en el denominador de la fórmula final
  • Si b=0, la normalización por longitud del documento se desactiva; si b=1, se aplica por completo
  • b normalmente se configura en 0.75

La idea central de BM25

• BM25 se basa en el Probability Ranking Principle, pero calcular la probabilidad real de relevancia de un documento es casi imposible
• En búsqueda, lo importante es el orden de los documentos más que el valor exacto de probabilidad, por lo que se vuelve práctico el cálculo eliminando de la fórmula los términos que no afectan el orden
• Por eso BM25 no calcula la probabilidad en sí, sino pesos
• Robertson/Sparck Jones Weight es un método que estima probabilidades usando la cantidad de documentos relevantes y la cantidad de documentos que contienen un término de consulta
  • r: número de documentos relevantes que contienen el término de consulta
  • N: número total de documentos en la colección
  • R: número de documentos relevantes en la colección
  • n: número de documentos que contienen el término de consulta
• Una gran limitación de este método es que primero hay que saber qué documentos son relevantes

La suposición de que “la mayoría de los documentos no son relevantes”

• Los desarrolladores de BM25 asumieron que, para una consulta cualquiera, la mayoría de los documentos no son relevantes
• Si se considera que la cantidad de documentos relevantes es despreciablemente pequeña, se puede tomar R = r = 0
• Al sustituir estos valores en la fórmula de Robertson/Sparck Jones Weight, aparece una forma casi igual al componente IDF que usa BM25
• Como no requiere información previa sobre relevancia y aun así mantiene la misma base teórica, BM25 se volvió mucho más práctico
• Victor Lavrenko lo describió como un "very impressive leap of faith"

Alcance de la comparación de puntuaciones BM25

• En general, las puntuaciones BM25 son difíciles de comparar directamente
  • No producen una puntuación probabilística entre 0 y 1
  • Tampoco son un algoritmo que intente estimar la probabilidad real de que un documento sea relevante
  • Se enfocan en aproximar el orden de relevancia probable para una consulta dentro de una colección específica
• Una puntuación BM25 más alta es una señal de que el documento tiene más probabilidad de ser relevante, pero no es una probabilidad real de relevancia
• Para el mismo documento dentro de la misma colección de documentos, se pueden comparar las puntuaciones BM25 de varias consultas
  • Como BM25 suma las puntuaciones de cada término de consulta, puede considerarse que no hay una diferencia semántica entre comparar las puntuaciones de dos términos de consulta y comparar las puntuaciones de dos consultas completas
• La restricción importante es que sean el mismo documento y la misma colección
  • BM25 usa el IDF y la longitud promedio de documento dentro de la colección
  • Si la colección cambia, las puntuaciones pueden cambiar, por lo que no se garantiza la comparación de puntuaciones a lo largo del tiempo
• En feeds de contenido personalizado, puede usarse para ejecutar búsquedas de texto completo por cada interés del usuario y comparar las puntuaciones BM25, a fin de determinar qué contenido encaja mejor con qué interés

Lecturas adicionales

• Para profundizar en la teoría y la historia de BM25, se puede ver la presentación de 2016 de Britta Weber, ingeniera de Elastic, Improved Text Scoring with BM25
• The Probabilistic Relevance Framework: BM25 and Beyond, de Stephen Robertson y Hugo Zaragoza, trata el marco probabilístico de relevancia de BM25
• Una comparación entre BM25 y otros algoritmos de búsqueda de texto completo puede verse en Comparing full text search algorithms: BM25, TF-IDF, and Postgres

[GN⁺]

Opiniones de Hacker News

• Para búsquedas generales estamos usando https://typesense.org/, y ahora que también soporta búsqueda híbrida, me da curiosidad saber si alguien ya lo probó

  • Lo probé para búsqueda híbrida y funciona bastante bien
    Me alegra ver que se mencione Typesense aquí; suele encajar bien en proyectos RAG pequeños, pero curiosamente no es tan conocido
    Es fácil de desplegar, los valores por defecto son razonables, la documentación es buena y el clustering también es relativamente sencillo; aun cuando necesitas profundizar más, tiene buen rendimiento y es potente
  • Nosotros también lo usamos y en general estamos satisfechos
    Eso sí, si usas un modelo de embeddings de un proveedor externo, la latencia de 500 ms o más es absurdamente alta, así que conviene alojarlo directamente dentro del clúster
    La calidad de la búsqueda híbrida es buena, pero las opciones de ajuste son muy limitadas, y las puntuaciones son bastante opacas salvo para ordenar dentro del conjunto de resultados

• Con los avances recientes en la búsqueda semántica basada en vectores, me pregunto cuál es el stack de búsqueda más actual que se usa hoy para híbridos de palabras clave + búsqueda semántica

  • Una estrategia de búsqueda de propósito general en realidad cambia por completo según la tarea que se quiera resolver
    Hace poco recibimos unos 3 millones de encuestas, cada una con unos 10 campos de texto libre, y teníamos que encontrar elementos sobre los que la empresa pudiera tomar acción
    Usamos algunos modelos clasificadores pequeños, eliminamos manualmente palabras comunes a partir del ruido observado en los primeros 10 mil registros y luego ponderamos las respuestas del modelo; funcionó casi a la perfección
    Este tipo de trabajo se parece menos a “programar” y más a ajustar la salida de caja negra de varias herramientas hasta que se vea bien frente a los casos de prueba y al cliente
    Como referencia, lo procesamos en Node.js en un servidor pequeño, encadenando varios modelos pequeños de Hugging Face
  • La mayoría de los productos comerciales y open source de búsqueda híbrida parecen usar BM25 + búsqueda de similitud vectorial basada en embeddings
    Los resultados normalmente se combinan con fusión recíproca de rangos (RRF)
    El paper de RRF impresiona por lo sorprendentemente simple que es, y además solo tiene 2 páginas: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
  • No hay que concentrarse en un único stack; hay que estar listo para usar la herramienta más adecuada para cada tarea
    Para trabajos tipo BM25 puedes usar Elasticsearch; para búsqueda vectorial simple y rápida, Turbopuffer; y para precalcular resultados de ciertas consultas o manejar atributos dinámicos que cambian con frecuencia, como precios, también puedes usar Redis
    Creo que conviene combinar estas cosas con un enfoque de scatter/gather
    Fuera del stack de búsqueda casi siempre hay una capa de servicios de inferencia para reordenar resultados, que idealmente termina siendo un servicio simple parecido al resto de la infraestructura de machine learning
    Casi siempre también necesitas enrutar las consultas de usuario, entendiendo si “buscar por ID” va a un sistema y “búsqueda semántica difusa” va a otro
    Sus estructuras de datos son muy distintas, y la búsqueda en general cubre un abanico amplio de casos de uso diferentes
    Meter todo en un solo sistema me parece un antipatrón
    Cada sistema se ajusta a cargas de trabajo distintas, y las funciones de inferencia integradas difícilmente alcanzan la velocidad de las herramientas generales de machine learning a las que están acostumbrados los ingenieros de ML
    Lo intenté con Elasticsearch Learning to Rank, pero fue una causa perdida
    Aun así, entre los intentos de resolver casos de uso amplios con un solo stack, Vespa probablemente sea lo mejor
  • Es un excelente artículo sobre BM25
    Como autor de txtai, txtai implementa un índice BM25 de alto rendimiento en Python mediante el paquete arrays, y almacena los vectores de frecuencia de términos en SQLite
    El enfoque de índice híbrido de txtai soporta combinación convexa cuando las puntuaciones BM25 están normalizadas, y fusión recíproca de rangos (RRF) cuando no lo están
    [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/...
  • La biblioteca de LLM Langroid[1] tiene una implementación RAG limpia y extensible dentro de DocChatAgent[2]
    Usa varias técnicas de búsqueda: búsqueda léxica (bm25, búsqueda difusa), búsqueda semántica (embeddings), reranking (cross-encoder, fusión recíproca de rangos), e incluso reranking para asegurar diversidad y mitigar el efecto lost-in-the-middle
    [1] Langroid - framework LLM multiagente creado por investigadores de CMU/UW-Madison https://github.com/langroid/langroid
    [2] Implementación de DocChatAgent -
    https://github.com/langroid/langroid/blob/main/langroid/agen...
    Puedes empezar por el método answer_from_docs y seguir desde ahí
    Además, si eres fundador de Kadoa, Kadoa-snack es una de las herramientas que uso con gusto todos los días para encontrar discusiones de HN sobre LLM

• Muy buen artículo.
  Para agregar un poco de contexto que es más difícil de encontrar, BM25 es la abreviatura de “Best Matching 25”, y “best matching” significa que es una fórmula que hace coincidir los términos de la consulta con los términos del documento para asignar ranking y ponderaciones a los términos.
  El 25 es simplemente un número de serie: antes hubo 24 variantes de la fórmula, y también hubo variantes posteriores, pero la número 25 fue la que funcionó mejor y se publicó.
  Fue ideado por Stephen Robertson y Karen Spärck Jones (famosa por IDF), y se implementó por primera vez en el sistema experimental de recuperación de información OKAPI de Robertson.
  El sistema OKAPI fue evaluado durante varios años en TREC (Text Retrieval Conference), la conferencia anual del NIST de EE. UU., algo bastante cercano a un “campeonato mundial” internacional de metodologías de motores de búsqueda.
  Sin embargo, el objetivo de este evento es más la comparación y el aprendizaje mutuo que ganar, y es un evento recomendable que se celebra cada noviembre en Gaithersburg, Maryland.
  Además del modelo de espacio vectorial de “bolsa de palabras” (vectores dispersos de términos) y del modelo probabilístico al que pertenece BM25, existen muchísimos marcos teóricos para ordenar un conjunto de documentos dada una consulta, y siguen apareciendo más.
  Por ejemplo, divergencia de la aleatoriedad, modelado estadístico del lenguaje, Learning to Rank, recuperación de información cuántica y ranking con redes neuronales.
  En conferencias como ICTIR o SIGIR, todavía de vez en cuando aparecen paradigmas de búsqueda completamente nuevos.
  Aquí, “modelado estadístico del lenguaje” no se refiere a los grandes modelos de lenguaje de moda hoy; esos entran más bien en la categoría de “búsqueda neuronal”.
  Además, si buscas “Quantum IR”, puede que en vez de tutoriales sobre recuperación de información cuántica encuentres espectroscopía infrarroja o una empresa cementera con el mismo nombre.
  Incluso en el siglo XXI, la tecnología de búsqueda tiene estas sutilezas.
  Si quieres comparar directamente BM25 con sus alternativas, recomiendo Terrier, un motor de búsqueda open source y plataforma de investigación desarrollados por la University of Glasgow.
  BM25 tiene más de 25 años, pero sigue demostrando ser una línea base difícil de superar, y se usa con frecuencia como punto de referencia al comparar métodos nuevos.
  Una variante más reciente, BM24F, puede manejar varios campos como título, cuerpo e hipervínculos, además de hipertexto.
  El artículo recomendado es 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, así como la Part 2 posterior.
  Lamentablemente, no es de acceso abierto.

  • Por coincidencia, US NIST TREC se está celebrando ahora mismo.
    Empezó el día 18 y termina el 22.
    Más detalles: https://trec.nist.gov/
  • Me pregunto si hay más material sobre BM24F.
    Busqué en Google y Google Scholar, pero no encontré contenido relacionado.

• Me da un poco de vergüenza, pero hago promoción: https://github.com/jankovicsandras/plpgsql_bm25
  https://github.com/jankovicsandras/bm25opt

  • Si estamos en la onda de promocionar sin vergüenza proyectos de hobby, SearchArray es una extensión de pandas para búsqueda de texto completo (BM25) cuando quieres experimentar con cosas en Google Colab.
    https://github.com/softwaredoug/searcharray
    También promociono BM25S, de Xing Han Lu, que es muy popular y tiene un objetivo similar.
    https://github.com/xhluca/bm25s
  • Ayer estaba pensando en agregar BM25 a un pequeño proyecto paralelo, así que la promoción llegó en buen momento.
    Me pregunto si existe algún proyecto wrapper en Python puro para administrar muchos textos y documentos PDF.
    Pensé en Solr o ElasticSearch, pero parecen demasiado pesados para lo que quiero hacer ahora.
    Como SQLite usa BM25, estoy considerando usar pysqlite3 junto con PyPDF2.
    Aunque se sale un poco del tema, creo que mucha gente estará buscando herramientas para crear aplicaciones híbridas de BM25 / almacén vectorial / LLM.

• Me pregunto si la longitud promedio de documento que se menciona en la normalización por longitud de documento es la mediana.
  Para reducir correctamente el peso de documentos excesivamente largos, parecería que debería ser la mediana; si no, ¿no terminan los documentos demasiado largos elevando injustamente el promedio?

  • En Lucene, es la media aritmética.
    Usar la mediana también podría ser un experimento interesante.
    Me pregunto si conoces algún dataset de búsqueda con diferencias muy grandes en la longitud de los documentos.
    Por ejemplo, MSMarco tiene longitudes bastante uniformes.

• Muy buen artículo.
  De verdad quiero aprender a pensar este tipo de problemas en forma matemática y cómo probarlos; ¿hay algún material de referencia recomendable?

• La búsqueda híbrida resuelve el viejo desafío de la relevancia en los resultados de búsqueda.
  Si usas fusión de rankings entre palabras clave y vectores, puedes crear una búsqueda híbrida que funcione en la mayoría de las situaciones.

• BM25 es un algoritmo antiguo, desarrollado en la década de 1970.
  Básicamente es un modelo estadístico rudimentario, y los estadísticos de hoy podrían hacerlo mucho mejor.
  Considero que la búsqueda está estrictamente dominada por métodos basados en aprendizaje.
  Claro que el aprendizaje puede usar la búsqueda como entrada.
  Todavía hay mucha gente que no se ha dado cuenta de esto, o que tiene incentivos para mantener tecnologías antiguas tanto tiempo como sea posible, pero la presión del mercado terminará cambiándolo.

  • ¿Esa “presión del mercado” es la misma que hizo que Google abandonara o reconvirtiera tecnologías de búsqueda antiguas que funcionaban bien y se pasara a la flamante búsqueda basada en machine learning?
    ¿No es por esa tecnología que terminamos agregando “+reddit” a cada consulta para esquivar la guerra de SEO adversarial?
    Que algo sea viejo no lo hace malo.
    Deberíamos fijarnos en la utilidad de una invención, descubrimiento o técnica, más que en su edad; me preocupa esa extraña actitud tecnocrática obsesionada con la antigüedad.
  • Es cierto que BM25 surgió a partir de investigaciones tempranas de los años 70 y 80, especialmente del principio de ranking probabilístico, pero tengo varias dudas.
    ¿Cuáles son los enfoques estadísticos modernos concretos que consideran lo bastante superiores como para reemplazar a BM25 en aplicaciones reales?
    En particular, me interesa cómo manejan casos límite como los términos raros y la normalización por longitud de documento, que BM25 intentaba abordar explícitamente.
    Estoy de acuerdo en que los enfoques basados en aprendizaje han mostrado resultados impresionantes, pero también me gustaría entender mejor qué significa exactamente que la búsqueda esté “estrictamente dominada” por métodos de aprendizaje.
    ¿Se refieren a benchmarks específicos o a casos reales en producción?
  • Es una opinión bastante picante.
    Creo que muchos expertos en búsqueda no estarían de acuerdo.
    El excelente podcast de David Tippet (ex OpenSearch, ahora en Github) y Nicolay Gerold tiene este título:
    “BM25 is the workhorse of search; vectors are its visionary cousin”
    https://www.youtube.com/watch?v=ENFW1uHsrLM
  • También hay, claramente, incentivos para vender “lo nuevo”.
    En el ámbito de la búsqueda, durante todo el tiempo que llevo trabajando, hubo montones de modas y tecnologías relacionadas con IA.
    Ahora hay empresas de búsqueda vectorial con enormes inversiones de VC que impulsan cierto punto de vista mediante ejércitos de evangelistas técnicos.
    En cambio, la cantidad de curaduría manual y de taxonomías manuales básicas y aburridas que realmente hacen funcionar la “búsqueda semántica” en lugares como Google es enorme.
    Solo que esas cosas no son sexys, así que casi no se habla de ellas en conferencias.