Comprendre l’algorithme de recherche plein texte BM25

 (emschwartz.me)
1 points par GN⁺ 2024-11-21 | 1 commentaires | Partager sur WhatsApp
  • BM25 reste largement utilisé pour la recherche plein texte nécessitant une correspondance exacte des mots-clés, et constitue l’un des piliers de la recherche hybride, en complément de la recherche par similarité vectorielle
  • Sans calculer directement des probabilités, BM25 classe les documents en additionnant des pondérations pour chaque terme de la requête afin de placer en tête ceux qui semblent les plus pertinents
  • Le score se décompose en IDF, fréquence du terme dans le document et normalisation de la longueur du document ; les mots rares pèsent davantage, tandis que les occurrences répétées sont progressivement moins récompensées
  • k1 contrôle la vitesse de saturation de la récompense liée aux occurrences répétées, et b l’intensité de la normalisation par la longueur du document ; on utilise généralement k1=1.2~2 et b=0.75
  • Le score BM25 n’étant pas une probabilité réelle de pertinence, il est difficile de l’utiliser comme valeur de comparaison universelle ; il a du sens lorsqu’on compare des éléments au sein de la même collection de documents

Le problème de recherche que BM25 cherche à résoudre

  • BM25, ou Best Match 25, est un algorithme largement utilisé en recherche plein texte
    • Il est utilisé par défaut dans Lucene/Elasticsearch, SQLite, entre autres
    • Récemment, la recherche hybride, qui combine recherche plein texte et recherche par similarité vectorielle, est devenue courante
  • Dans les flux de contenu personnalisés, la recherche par similarité vectorielle seule peut être insuffisante pour traiter précisément les mots-clés
    • Si un centre d’intérêt est Solid.js, utiliser uniquement la recherche par similarité vectorielle peut faire remonter plus de contenus liés à React qu’à Solid
  • La question centrale est de savoir si l’on peut comparer le score BM25 d’un même document entre plusieurs requêtes afin de déterminer à quelle requête ce document correspond le mieux

Le principe de classement probabiliste et l’approche de BM25

  • L’objectif de la recherche plein texte est de trouver les documents les plus pertinents dans l’ensemble de documents possibles pour une requête donnée
  • Comme il est impossible de connaître avec certitude la pertinence réelle, la recherche tente de trier les documents selon la probabilité qu’un document soit pertinent pour la requête
    • Cette idée est appelée Probability Ranking Principle
  • Une recherche lexicale comme BM25 n’utilise que les caractéristiques de la requête et des documents dans la collection
    • La recherche par similarité vectorielle peut utiliser un modèle d’embeddings entraîné sur un corpus de textes externe pour représenter le sens de la requête et des documents

Les composants du score BM25

  • BM25 calcule un score en combinant plusieurs signaux issus de la requête et de la collection de documents

  • Termes de la requête

    • Lorsqu’une requête de recherche se compose de plusieurs termes, le score de chaque terme est calculé puis additionné

  • Fréquence inverse de document (IDF)

    • Indique à quel point un terme de recherche donné est rare dans l’ensemble de la collection de documents
    • Les mots fréquents comme the ou and sont considérés comme peu informatifs, tandis que l’importance des mots rares est renforcée

  • Fréquence du terme dans le document

    • Reflète le nombre d’occurrences d’un terme de recherche dans un document donné
    • Plus un même terme est répété, plus la probabilité de pertinence est considérée comme élevée, mais BM25 applique un effet de saturation aux occurrences répétées

  • Longueur du document

    • Dans un document long, un terme de recherche peut apparaître plus souvent simplement parce que le document est plus long
    • BM25 normalise la longueur du document par rapport à la longueur moyenne des documents afin d’éviter qu’un document long n’obtienne un score indûment élevé

Les différentes parties de la formule BM25

  • Le score global de BM25 consiste à additionner, pour un document D et une requête Q, les scores de chaque terme de requête q_i
    • D : document cible
    • Q : requête complète
    • n : nombre de termes dans la requête
    • q_i : chaque terme de la requête

  • IDF : donner plus de poids aux mots rares dans la collection

    • Le terme IDF calcule à quel point un terme de la requête est rare dans l’ensemble de la collection de documents
    • N : nombre total de documents dans la collection
    • n(q_i) : nombre de documents contenant le terme de requête
    • N - n(q_i) : nombre de documents ne contenant pas le terme de requête
    • Les termes fréquents apparaissant dans de nombreux documents ont donc un effet plus faible sur le score
    • Les termes rares, n’apparaissant que dans peu de documents, pèsent davantage dans le score
    • Les 0.5 et 1 de la formule jouent un rôle d’amortissement pour éviter que le résultat ne varie trop fortement lorsque le terme est très rare ou très fréquent

  • Fréquence du terme : tenir compte des répétitions sans les récompenser indéfiniment

    • La fréquence du terme dans le document reflète la fréquence à laquelle un terme de requête donné apparaît dans un document donné
    • f(q_i, D) : fréquence d’apparition du terme de requête q_i dans le document D
    • k1 : paramètre de réglage généralement fixé entre 1.2 et 2
    • BM25 tient compte des répétitions d’un terme dans le score, mais plus les répétitions augmentent, plus le gain de score supplémentaire diminue
    • k1 contrôle la rapidité avec laquelle la récompense liée aux répétitions du terme diminue

  • Normalisation de la longueur du document : ajuster l’avantage des documents longs

    • La normalisation de la longueur du document compare la longueur du document cible à la longueur moyenne des documents de la collection
    • |D| : longueur du document cible
    • avgdl : longueur moyenne des documents de la collection
    • b : paramètre de réglage contrôlant l’intensité de la normalisation par la longueur du document
    • Comme les documents plus longs que la moyenne ont plus de chances de contenir plus souvent le terme de recherche, ils sont pénalisés dans le dénominateur de la formule finale
    • Si b=0, la normalisation par la longueur du document est désactivée ; si b=1, elle est appliquée entièrement
    • b est généralement fixé à 0.75

L’idée centrale de BM25

  • BM25 repose sur le Probability Ranking Principle, mais il est presque impossible de calculer la vraie probabilité de pertinence d’un document
  • Ce qui compte en recherche est davantage l’ordre des documents que la valeur exacte de probabilité ; BM25 rend donc le calcul praticable en supprimant de la formule les termes qui n’influencent pas l’ordre
  • C’est pourquoi BM25 ne calcule pas une probabilité elle-même, mais une pondération
  • Le Robertson/Sparck Jones Weight est une méthode qui estime une probabilité à partir du nombre de documents pertinents et du nombre de documents contenant un terme de requête
    • r : nombre de documents pertinents contenant le terme de requête
    • N : nombre total de documents dans la collection
    • R : nombre de documents pertinents dans la collection
    • n : nombre de documents contenant le terme de requête
  • La grande limite de cette approche est qu’elle suppose de savoir à l’avance quels documents sont pertinents

L’hypothèse selon laquelle « la plupart des documents ne sont pas pertinents »

  • Les créateurs de BM25 partent du principe que, pour une requête arbitraire, la plupart des documents ne sont pas pertinents
  • Si l’on considère que le nombre de documents pertinents est négligeable, on peut poser R = r = 0
  • En substituant ces valeurs dans la formule du Robertson/Sparck Jones Weight, on obtient une forme presque identique au terme IDF utilisé dans BM25
  • Comme BM25 ne demande pas d’informations préalables sur la pertinence tout en conservant le même fondement théorique, il devient beaucoup plus pratique
  • Victor Lavrenko a qualifié cela de « very impressive leap of faith »

Portée de la comparaison des scores BM25

  • Les scores BM25 sont généralement difficiles à comparer directement
    • Ils ne produisent pas un score de probabilité entre 0 et 1
    • BM25 n’est pas non plus un algorithme qui cherche à estimer la probabilité réelle qu’un document soit pertinent
    • Il vise à approximer, au sein d’une collection donnée, l’ordre de probabilité de pertinence des documents pour une requête
  • Un score BM25 plus élevé indique qu’un document a plus de chances d’être pertinent, mais ce n’est pas une probabilité réelle de pertinence
  • Pour un même document dans une même collection de documents, il est possible de comparer les scores BM25 de plusieurs requêtes
    • Comme BM25 additionne les scores de chaque terme de requête, on peut considérer qu’il n’y a pas de différence sémantique entre comparer les scores de deux termes de requête et comparer les scores de deux requêtes complètes
  • La contrainte importante est : même document, même collection
    • BM25 utilise l’IDF et la longueur moyenne des documents au sein de la collection
    • Si la collection change, les scores peuvent changer eux aussi ; la comparaison des scores dans le temps n’est donc pas garantie
  • Dans un flux de contenu personnalisé, on peut lancer une recherche plein texte pour chaque centre d’intérêt utilisateur et comparer les scores BM25 afin de déterminer quel contenu correspond le mieux à quel centre d’intérêt

Pour aller plus loin

À lire aussi

1 commentaires

 
GN⁺ 2024-11-21
Avis sur Hacker News

  • J’utilise https://typesense.org/ pour la recherche classique, et comme il prend désormais aussi en charge la recherche hybride, je me demande si certains l’ont essayé

    • Je l’ai utilisé pour de la recherche hybride et ça fonctionne plutôt bien
      Ça fait plaisir de voir Typesense mentionné ici ; il convient souvent très bien aux petits projets RAG, mais il reste étonnamment peu connu
      Il est facile à déployer, ses valeurs par défaut sont raisonnables, la documentation est bonne et le clustering est assez simple ; et quand il faut aller plus loin, il reste suffisamment performant et puissant
    • Nous l’utilisons aussi et en sommes globalement satisfaits
      En revanche, si l’on utilise un fournisseur externe pour le modèle d’embeddings, la latence dépasse les 500 ms, ce qui est absurdement élevé ; mieux vaut donc l’héberger soi-même dans le cluster
      La qualité de la recherche hybride est bonne, mais les options de réglage sont très limitées, et les scores restent assez opaques en dehors du classement à l’intérieur de l’ensemble de résultats

  • Avec les progrès récents de la recherche sémantique vectorielle, je me demande quelle est aujourd’hui la stack de recherche moderne utilisée pour l’hybride mots-clés + recherche sémantique

    • Une stratégie de recherche généraliste dépend en réalité entièrement de la tâche visée
      Récemment, nous avons reçu environ 3 millions de réponses à une enquête comportant chacune une dizaine de champs en texte libre, et nous devions identifier les éléments sur lesquels l’entreprise devait agir
      En utilisant quelques petits modèles de classification, en supprimant manuellement des mots fréquents après avoir observé le bruit apparu dans les 10 000 premiers enregistrements, puis en pondérant les réponses des modèles, cela a fonctionné presque parfaitement
      Ce genre de travail relève moins de la « programmation » que de l’ajustement des sorties en boîte noire de divers outils jusqu’à ce qu’elles paraissent bonnes aux tests et aux clients
      Pour info, nous avons chaîné plusieurs petits modèles Hugging Face avec Node.js sur un petit serveur
    • La plupart des produits de recherche hybride, commerciaux comme open source, semblent utiliser BM25 + recherche de similarité vectorielle basée sur des embeddings
      Les résultats sont généralement combinés avec la fusion réciproque des rangs (RRF)
      L’article sur RRF est étonnamment simple, ce qui est impressionnant, et il ne fait que 2 pages : https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
    • Il ne faut pas se focaliser sur une seule stack ; il faut être prêt à utiliser l’outil le plus adapté à chaque tâche
      Pour les tâches de type BM25, Elasticsearch ; pour une recherche vectorielle simple et rapide, Turbopuffer ; pour précalculer les résultats de certaines requêtes ou gérer des attributs dynamiques qui changent souvent, comme les prix, Redis peut aussi convenir
      À mon avis, il vaut mieux combiner tout cela avec une approche scatter/gather
      En dehors de la stack de recherche, il y a presque toujours une couche de services d’inférence pour le reranking, idéalement un service simple comparable au reste de l’infrastructure de machine learning
      Il faut aussi presque toujours router les requêtes utilisateur en les comprenant : par exemple envoyer une « recherche par ID » vers un système, et une « recherche sémantique floue » vers un autre
      Leurs structures de données sont très différentes, et la recherche couvre en général un large éventail de cas d’usage distincts
      Essayer de tout faire entrer dans un seul système est, à mon sens, un anti-pattern
      Chaque système correspond à des charges de travail différentes, et les fonctions d’inférence intégrées ont du mal à suivre le rythme des outils de machine learning généraux auxquels les ingénieurs ML sont habitués
      J’ai essayé avec Elasticsearch Learning to Rank, mais c’était une impasse
      Cela dit, parmi les tentatives de couvrir un large éventail de cas d’usage avec une seule stack, Vespa est probablement la meilleure
    • Excellent article sur BM25
      En tant qu’auteur de txtai, txtai implémente en Python un index BM25 performant via le package arrays, et stocke les vecteurs de fréquence des termes dans SQLite
      La méthode d’indexation hybride de txtai prend en charge une combinaison convexe lorsque les scores BM25 sont normalisés, et la fusion réciproque des rangs (RRF) lorsqu’ils ne le sont pas
      [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 bibliothèque LLM Langroid[1] contient, dans DocChatAgent[2], une implémentation RAG propre et extensible
      Elle utilise plusieurs techniques de recherche : recherche lexicale (bm25, recherche floue), recherche sémantique (embeddings), reranking (cross-encoder, fusion réciproque des rangs), ainsi que du reranking pour assurer la diversité et atténuer le phénomène de lost-in-the-middle
      [1] Langroid - un framework LLM multi-agent créé par des chercheurs de CMU/UW-Madison https://github.com/langroid/langroid
      [2] Implémentation de DocChatAgent -
      https://github.com/langroid/langroid/blob/main/langroid/agen...
      Il suffit de partir de la méthode answer_from_docs et de suivre le fil
      Au passage, si vous êtes le fondateur de Kadoa, Kadoa-snack est l’un des outils que j’utilise volontiers au quotidien pour trouver des discussions HN liées aux LLM

  • Excellent article.
    Pour ajouter un peu de contexte plus difficile à trouver, BM25 est l’abréviation de « Best Matching 25 », et « best matching » signifie qu’il s’agit d’une formule qui fait correspondre les termes de la requête avec ceux des documents afin d’établir un classement et de pondérer les termes.
    Le 25 est simplement un numéro de série : il y avait eu auparavant 24 variantes de la formule, puis d’autres ensuite, mais la numéro 25 fonctionnait le mieux et c’est celle qui a été publiée.
    Elle a été conçue par Stephen Robertson et Karen Spärck Jones, connue pour l’IDF, et implémentée pour la première fois dans le système expérimental de recherche d’information OKAPI de Robertson.
    Le système OKAPI a été benchmarké pendant plusieurs années lors de la TREC (Text Retrieval Conference) annuelle du NIST américain, qui ressemble assez à un « championnat du monde » international des méthodologies de moteurs de recherche.
    Cela dit, l’objectif de cet événement est davantage la comparaison et l’apprentissage mutuel que la victoire ; il a lieu chaque année en novembre à Gaithersburg, dans le Maryland, et mérite d’être recommandé.
    Outre le modèle d’espace vectoriel en « sac de mots » (vecteurs creux de termes) et les modèles probabilistes auxquels appartient BM25, il existe un nombre étonnamment grand, et toujours croissant, de cadres théoriques pour classer un ensemble de documents étant donnée une requête.
    Par exemple, la divergence from randomness, la modélisation statistique du langage, le Learning to Rank, la recherche d’information quantique et le ranking neuronal.
    Dans des conférences comme ICTIR ou SIGIR, il arrive encore aujourd’hui que des paradigmes de recherche entièrement nouveaux apparaissent.
    Ici, « modélisation statistique du langage » ne désigne pas les grands modèles de langage à la mode aujourd’hui ; ceux-ci relèvent plutôt de la catégorie de la « recherche neuronale ».
    Par ailleurs, si vous cherchez « Quantum IR », vous risquez de tomber non pas sur un tutoriel de recherche d’information quantique, mais sur de la spectroscopie infrarouge ou sur une cimenterie du même nom.
    Même au XXIe siècle, la technologie de recherche comporte ce genre de subtilités.
    Si vous voulez comparer directement BM25 à ses alternatives, je recommande Terrier, un moteur de recherche open source et une plateforme de recherche développés par l’University of Glasgow.
    BM25 a plus de 25 ans, mais il s’est encore imposé comme une baseline difficile à dépasser, et il est souvent utilisé comme point de référence pour comparer de nouvelles méthodes.
    Une variante plus récente, BM24F, peut gérer plusieurs champs comme le titre, le corps du texte et les hyperliens, ainsi que l’hypertexte.
    L’article recommandé est 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, ainsi que la Part 2 qui suit.
    Malheureusement, il n’est pas en open access.

    • Par coïncidence, US NIST TREC a lieu en ce moment.
      Il a commencé le 18 et se termine le 22.
      Plus de détails : https://trec.nist.gov/
    • Je me demande s’il existe davantage de ressources sur BM24F.
      Même en cherchant sur Google et Google Scholar, je n’ai rien trouvé de pertinent.

  • Un peu honteux, mais je fais ma pub : https://github.com/jankovicsandras/plpgsql_bm25
    https://github.com/jankovicsandras/bm25opt

    • Puisqu’on est dans une dynamique de promotion sans honte de projets perso, SearchArray est une extension pandas pour la recherche plein texte (BM25) quand on bidouille diverses choses dans Google Colab.
      https://github.com/softwaredoug/searcharray
      J’en profite aussi pour promouvoir BM25S de Xing Han Lu, très populaire et avec un objectif similaire.
      https://github.com/xhluca/bm25s
    • Justement, hier je pensais ajouter BM25 à un petit side project ; cette promo tombe à pic.
      Je me demande s’il existe un projet wrapper en pur Python pour gérer beaucoup de textes et de documents PDF.
      J’avais pensé à Solr ou ElasticSearch, mais cela semble trop lourd pour ce que je veux faire maintenant.
      Comme SQLite utilise BM25, j’envisage d’utiliser pysqlite3 avec PyPDF2.
      C’est un peu hors sujet, mais je pense que beaucoup de gens cherchent des outils pour créer des applications hybrides BM25 / stockage vectoriel / LLM.

  • Je me demande si la longueur moyenne des documents mentionnée dans la normalisation de la longueur des documents est la médiane.
    Pour réduire correctement le poids des documents excessivement longs, il me semble que cela devrait être la médiane ; sinon, les documents trop longs ne tirent-ils pas indûment la moyenne vers le haut ?

    • Dans Lucene, c’est la moyenne arithmétique.
      Utiliser la médiane serait aussi une expérience intéressante.
      Je me demande si vous connaissez un dataset de recherche où les longueurs de documents varient énormément.
      Par exemple, MSMarco a des longueurs plutôt régulières.

  • Excellent article.
    J’aimerais vraiment apprendre à penser ce genre de problème sous une forme mathématique et à le tester ; auriez-vous des ressources à recommander ?

  • La recherche hybride résout le vieux problème de la pertinence des résultats de recherche.
    En utilisant une fusion des classements entre mots-clés et vecteurs, on peut construire une recherche hybride qui fonctionne dans la plupart des situations.

  • BM25 est un ancien algorithme développé dans les années 1970
    À la base, c’est un modèle statistique assez rudimentaire, et les statisticiens d’aujourd’hui peuvent faire bien mieux
    Je pense que la recherche est strictement dominée par les méthodes fondées sur l’apprentissage
    Bien sûr, l’apprentissage peut utiliser la recherche comme entrée
    Beaucoup de gens ne l’ont pas encore compris, ou ont intérêt à maintenir les anciennes technologies aussi longtemps que possible, mais la pression du marché finira par changer les choses

    • Cette pression du marché, c’est celle-là même qui a poussé Google à abandonner, ou à réaffecter, son ancienne technologie de recherche qui fonctionnait bien, pour passer à une nouvelle recherche basée sur le machine learning toute brillante ?
      N’est-ce pas à cause de cette technologie qu’on se retrouve à ajouter “+reddit” à chaque requête pour éviter la guerre du SEO hostile ?
      Ce n’est pas parce que c’est ancien que c’est mauvais
      Il faut juger l’utilité d’une invention, d’une découverte ou d’une technique plutôt que son âge ; cette étrange attitude techniciste obsédée par l’âge m’inquiète
    • Il est vrai que BM25 est issu des premiers travaux des années 1970-1980, notamment du principe de classement probabiliste, mais je me pose plusieurs questions
      Quelles approches statistiques modernes précises considères-tu comme suffisamment supérieures pour remplacer BM25 dans des applications réelles ?
      Je suis particulièrement curieux de savoir comment elles gèrent les cas limites que BM25 cherchait explicitement à traiter, comme les termes rares et la normalisation de la longueur des documents
      Je suis d’accord pour dire que les approches fondées sur l’apprentissage ont donné des résultats impressionnants, mais j’aimerais aussi comprendre plus précisément ce que signifie dire que la recherche est « strictement dominée » par les méthodes d’apprentissage
      Parles-tu de benchmarks spécifiques, ou de cas d’exploitation en production ?
    • C’est une opinion assez tranchée
      Je pense que beaucoup de spécialistes de la recherche ne seraient pas d’accord
      Un excellent podcast de David Tippet (ex-OpenSearch, aujourd’hui chez Github) et Nicolay Gerold porte ce titre :
      “BM25 is the workhorse of search; vectors are its visionary cousin”
      https://www.youtube.com/watch?v=ENFW1uHsrLM
    • Il y a clairement aussi des incitations à vendre du « nouveau »
      Dans le domaine de la recherche, j’ai vu passer quantité de modes et de technologies liées à l’IA tout au long de ma carrière
      En ce moment, des entreprises de recherche vectorielle massivement financées par le capital-risque poussent un certain point de vue avec des armées d’évangélistes techniques
      À l’inverse, chez Google et ailleurs, la quantité de curation manuelle et de taxonomies basiques, ennuyeuses et faites à la main qui font réellement fonctionner la « recherche sémantique » est énorme
      C’est juste que ce n’est pas sexy, donc on en parle peu dans les conférences