Comprendre l’algorithme de recherche en texte intégral BM25

• Comprendre l’algorithme BM25

  • BM25 est un algorithme de recherche en texte intégral largement utilisé par défaut dans Lucene/Elasticsearch et SQLite, entre autres.
  • Ces derniers temps, il est devenu courant d’implémenter une « recherche hybride » en combinant la recherche en texte intégral et la recherche de similarité vectorielle.
  • Le point de départ est une question : peut-on comparer les scores BM25 entre plusieurs requêtes ?

• Classer les documents

  • L’objectif fondamental d’un algorithme de recherche en texte intégral est de trouver les documents les plus pertinents pour une requête.
  • BM25 classe les documents en fonction de la probabilité qu’ils soient pertinents pour la requête.

• Les composants de BM25

  • Termes de requête : pour une requête composée de plusieurs termes, un score distinct est calculé pour chaque terme puis additionné.
  • Fréquence inverse de document (IDF) : calcule la rareté d’un terme de recherche donné dans l’ensemble de la collection de documents.
  • Fréquence du terme dans le document : calcule la fréquence d’apparition du terme recherché dans un document donné.
  • Normalisation de la longueur du document : normalise la longueur d’un document en la comparant à celle des autres documents.

• Expression mathématique de BM25

  • L’algorithme BM25 peut sembler mathématiquement complexe, mais il devient facile à comprendre une fois ses différents composants assimilés.
  • La formule principale est calculée en additionnant les scores de chaque terme de la requête.

• L’originalité de BM25

  • Un classement fondé sur la probabilité sans calcul explicite de probabilité : BM25 classe les documents à partir d’un cadre probabiliste de pertinence.
  • L’hypothèse que la plupart des documents ne sont pas pertinents : BM25 part du principe que la majorité des documents ne sont pas liés à la requête, ce qui le rend utile même sans information explicite sur la pertinence.

• Conclusion

  • Les scores BM25 peuvent être comparés entre différentes requêtes au sein d’une même collection.
  • BM25 ne cherche pas à estimer la pertinence absolue d’un document, mais se concentre sur son rang de pertinence pour une requête.
  • On peut comparer les scores BM25 d’un même document au sein de la même collection.

• Pour aller plus loin

  • Si vous voulez en savoir plus sur la théorie et l’histoire de BM25, il est recommandé de consulter la conférence donnée en 2016 par l’ingénieure Elastic Britta Weber ainsi que "The Probabilistic Relevance Framework: BM25 and Beyond" de Stephen Robertson et Hugo Zaragoza.