Den BM25-Algorithmus für die Volltextsuche verstehen
(emschwartz.me)- BM25 wird in der Volltextsuche, bei der exaktes Keyword-Matching nötig ist, weiterhin breit eingesetzt und bildet eine Säule der hybriden Suche, die die Vektorähnlichkeitssuche ergänzt
- Ohne Wahrscheinlichkeiten direkt zu berechnen, ordnet BM25 Dokumente ein, indem es Gewichte pro Query-Term addiert und so Dokumente mit höherer mutmaßlicher Relevanz weiter vorne platziert
- Der Score setzt sich aus IDF, der Termfrequenz im Dokument und der Normalisierung der Dokumentlänge zusammen; seltene Wörter werden stärker gewichtet, wiederholte Vorkommen zunehmend schwächer belohnt
k1steuert, wie schnell der Zusatznutzen wiederholter Vorkommen abnimmt,bdie Stärke der Dokumentlängen-Normalisierung; üblich sindk1=1.2~2undb=0.75- Da der BM25-Score keine tatsächliche Relevanzwahrscheinlichkeit ist, lässt er sich schlecht als allgemeiner Vergleichswert verwenden und ist sinnvoll beim Vergleich innerhalb derselben Dokumentensammlung
Welches Suchproblem BM25 lösen will
- BM25 oder Best Match 25 ist ein weit verbreiteter Algorithmus für die Volltextsuche
- Wird in Lucene/Elasticsearch und SQLite unter anderem als Standard verwendet
- In jüngerer Zeit ist hybride Suche, also die Kombination aus Volltextsuche und Vektorähnlichkeitssuche, üblich geworden
- In personalisierten Content-Feeds kann reine Vektorähnlichkeitssuche bei exakten Keywords unzureichend sein
- Wenn das Interesse etwa
Solid.jsgilt, kann bei ausschließlicher Nutzung von Vektorähnlichkeitssuche mehr React-bezogener Content erscheinen als Inhalte zu Solid
- Wenn das Interesse etwa
- Die zentrale Frage ist, ob sich der BM25-Score eines Dokuments über mehrere Queries hinweg vergleichen lässt, um zu bestimmen, zu welcher Query das Dokument am besten passt
Das probabilistische Ranking-Prinzip und der Ansatz von BM25
- Ziel der Volltextsuche ist es, bezogen auf eine Query aus einer möglichen Dokumentmenge die relevantesten Dokumente zu finden
- Da sich die tatsächliche Relevanz nicht sicher kennen lässt, versucht die Suche nach der Wahrscheinlichkeit zu sortieren, mit der ein Dokument zur Query relevant ist
- Diese Idee wird Probability Ranking Principle genannt
- Lexikalische Suche wie BM25 verwendet nur die Query und Eigenschaften der Dokumente innerhalb der Sammlung
- Vektorähnlichkeitssuche kann Embedding-Modelle nutzen, die auf externen Textkorpora trainiert wurden, um die Bedeutung von Queries und Dokumenten darzustellen
Bestandteile des BM25-Scores
- BM25 berechnet seinen Score, indem es mehrere Signale aus Query und Dokumentensammlung kombiniert
-
Query-Terme
- Besteht eine Suchanfrage aus mehreren Begriffen, wird zunächst für jeden Begriff ein Score berechnet und anschließend aufsummiert
-
Inverse Document Frequency (IDF)
- Zeigt an, wie selten ein bestimmter Suchbegriff in der gesamten Dokumentensammlung ist
- Häufige Wörter wie
theoderandgelten als informationsarm, während seltene Wörter stärker gewichtet werden
-
Termfrequenz im Dokument
- Berücksichtigt, wie oft der Suchbegriff in einem bestimmten Dokument vorkommt
- Mehrfache Wiederholung desselben Begriffs erhöht zwar tendenziell die Relevanz, doch BM25 wendet auf Wiederholungen einen abnehmenden Grenznutzen an
-
Dokumentlänge
- In langen Dokumenten kann ein Suchbegriff allein wegen der Länge häufiger vorkommen
- BM25 normalisiert die Dokumentlänge im Vergleich zur durchschnittlichen Dokumentlänge, damit lange Dokumente nicht unfair hohe Scores erhalten
Die einzelnen Teile der BM25-Formel
- Der Gesamtscore von BM25 entsteht für Dokument
Dund QueryQ, indem die Scores aller Query-Termeq_iaddiert werdenD: ZieldokumentQ: gesamte Queryn: Anzahl der Query-Termeq_i: jeweiliger Query-Term
-
IDF: Seltene Wörter in der Sammlung stärker gewichten
- Der IDF-Term berechnet, wie selten ein Query-Term in der gesamten Dokumentensammlung ist
N: Gesamtzahl der Dokumente in der Sammlungn(q_i): Anzahl der Dokumente, die den Query-Term enthaltenN - n(q_i): Anzahl der Dokumente, die den Query-Term nicht enthalten- Häufige Terme kommen in vielen Dokumenten vor und beeinflussen den Score daher weniger
- Seltene Terme kommen nur in wenigen Dokumenten vor und schlagen deshalb stärker zu Buche
- Die
0.5und1in der Formel dienen dazu, das Ergebnis abzumildern, damit es bei extrem seltenen oder extrem häufigen Termen nicht zu stark ausschlägt
-
Termfrequenz: Wiederholungen berücksichtigen, aber nicht unbegrenzt belohnen
- Die Termfrequenz im Dokument spiegelt wider, wie oft ein bestimmter Query-Term in einem bestimmten Dokument vorkommt
f(q_i, D): Häufigkeit, mit der Query-Termq_iin DokumentDvorkommtk1: ein Tuning-Parameter, der typischerweise zwischen1.2und2liegt- BM25 berücksichtigt Wiederholungen eines Terms im Score, aber der zusätzliche Anstieg des Scores wird mit jeder weiteren Wiederholung kleiner
k1steuert, wie schnell diese Belohnung für Wiederholungen abnimmt
-
Dokumentlängen-Normalisierung: Den Vorteil langer Dokumente ausgleichen
- Die Dokumentlängen-Normalisierung vergleicht die Länge des Zieldokuments mit der durchschnittlichen Dokumentlänge der Sammlung
|D|: Länge des Zieldokumentsavgdl: durchschnittliche Dokumentlänge der Sammlungb: ein Tuning-Parameter, der die Stärke der Dokumentlängen-Normalisierung steuert- Da Suchbegriffe in überdurchschnittlich langen Dokumenten mit höherer Wahrscheinlichkeit häufiger vorkommen, werden solche Dokumente im Nenner der Endformel benachteiligt
- Bei
b=0ist die Dokumentlängen-Normalisierung deaktiviert, beib=1wird sie vollständig angewendet bwird üblicherweise auf0.75gesetzt
Die Kernidee von BM25
- BM25 basiert auf dem Probability Ranking Principle, aber die echte Wahrscheinlichkeit der Dokumentrelevanz zu berechnen ist fast unmöglich
- Für die Suche ist die Reihenfolge der Dokumente wichtiger als ein exakter Wahrscheinlichkeitswert; daher entfernt man in der Formel Terme, die die Reihenfolge nicht verändern, um die Berechnung praktikabel zu machen
- Deshalb berechnet BM25 keine Wahrscheinlichkeit, sondern ein Gewicht
- Das Robertson/Sparck Jones Weight schätzt Wahrscheinlichkeiten anhand der Zahl relevanter Dokumente und der Zahl der Dokumente, die einen Query-Term enthalten
r: Zahl relevanter Dokumente, die den Query-Term enthaltenN: Gesamtzahl der Dokumente in der SammlungR: Zahl relevanter Dokumente in der Sammlungn: Zahl der Dokumente, die den Query-Term enthalten
- Eine große Einschränkung dieses Ansatzes ist, dass man zunächst wissen müsste, welche Dokumente relevant sind
Die Annahme „die meisten Dokumente sind nicht relevant“
- Die Entwickler von BM25 nehmen an, dass für eine beliebige Query die meisten Dokumente nicht relevant sind
- Wenn die Zahl relevanter Dokumente vernachlässigbar klein ist, kann man
R = r = 0setzen - Setzt man diese Werte in die Formel des Robertson/Sparck Jones Weight ein, ergibt sich nahezu dieselbe Form wie der in BM25 verwendete IDF-Term
- Weil dadurch keine vorab bekannten Relevanzinformationen nötig sind und die gleiche theoretische Grundlage erhalten bleibt, wurde BM25 deutlich praktikabler
- Victor Lavrenko bezeichnete das als "very impressive leap of faith"
Der Geltungsbereich von BM25-Score-Vergleichen
- BM25-Scores lassen sich im Allgemeinen nicht ohne Weiteres direkt vergleichen
- Sie erzeugen keine Wahrscheinlichkeitswerte zwischen 0 und 1
- BM25 ist auch kein Algorithmus, der die tatsächliche Wahrscheinlichkeit von Relevanz schätzen will
- Im Fokus steht vielmehr, innerhalb einer bestimmten Sammlung die Reihenfolge der wahrscheinlichen Relevanz zu einer Query anzunähern
- Ein höherer BM25-Score ist ein Signal dafür, dass ein Dokument wahrscheinlich relevanter ist, aber keine tatsächliche Relevanzwahrscheinlichkeit
- Für dasselbe Dokument innerhalb derselben Dokumentensammlung lassen sich BM25-Scores mehrerer Queries vergleichen
- Da BM25 die Scores der einzelnen Query-Terme aufsummiert, kann man semantisch keinen wesentlichen Unterschied zwischen dem Vergleich zweier Query-Term-Scores und dem Vergleich zweier vollständiger Query-Scores annehmen
- Die wichtige Einschränkung lautet: dasselbe Dokument, dieselbe Sammlung
- BM25 verwendet die IDF der Sammlung und die durchschnittliche Dokumentlänge
- Wenn sich die Sammlung ändert, können sich auch die Scores ändern; Vergleiche über längere Zeiträume hinweg sind daher nicht garantiert
- In personalisierten Content-Feeds kann man für die Interessen jedes Nutzers eine Volltextsuche ausführen und die BM25-Scores vergleichen, um zu beurteilen, welcher Content besser zu welchem Interesse passt
Weiterführende Materialien
- Wer tiefer in Theorie und Geschichte von BM25 einsteigen möchte, kann sich den Vortrag Improved Text Scoring with BM25 von Elastic-Ingenieurin Britta Weber aus dem Jahr 2016 ansehen
- The Probabilistic Relevance Framework: BM25 and Beyond von Stephen Robertson und Hugo Zaragoza behandelt den probabilistischen Relevanzrahmen von BM25
- Einen Vergleich von BM25 mit anderen Volltextsuchalgorithmen gibt es in Comparing full text search algorithms: BM25, TF-IDF, and Postgres
1 Kommentare
Meinungen auf Hacker News
Für die allgemeine Suche nutzen wir https://typesense.org/; da es inzwischen auch hybride Suche unterstützt, würde mich interessieren, ob jemand damit Erfahrung hat
Schön, Typesense hier erwähnt zu sehen. Für kleine RAG-Projekte passt es oft sehr gut, ist aber seltsamerweise eher wenig bekannt
Es ist einfach zu deployen, die Defaults sind sinnvoll, die Dokumentation ist gut, Clustering ist ebenfalls recht einfach, und wenn man tiefer einsteigen muss, ist es immer noch performant und leistungsfähig genug
Wenn man das Embedding-Modell allerdings bei einem externen Anbieter betreibt, ist die Latenz mit 500 ms+ absurd hoch; besser ist es, es direkt im Cluster selbst zu hosten
Die Qualität der hybriden Suche ist gut, aber die Tuning-Optionen sind sehr eingeschränkt, und die Scores sind abgesehen vom Ranking innerhalb der Ergebnismenge ziemlich undurchsichtig
Angesichts der jüngsten Fortschritte bei vektorbasierter semantischer Suche frage ich mich, welcher moderne Search-Stack heute für Hybridsuche aus Keyword- und semantischer Suche verwendet wird
Vor Kurzem bekamen wir etwa 3 Millionen Umfragen mit jeweils zehn Freitextfeldern und mussten darin Punkte finden, bei denen das Unternehmen handeln sollte
Wir nutzten ein paar kleine Klassifizierungsmodelle, entfernten manuell häufige Wörter anhand des Rauschens, das in den ersten 10.000 Einträgen sichtbar wurde, und gewichteten anschließend die Modellantworten; damit funktionierte es nahezu perfekt
So etwas ist weniger „Programmierung“ als vielmehr das Justieren der Blackbox-Ausgaben verschiedener Tools, bis sie für Testfälle und Kunden gut aussehen
Zur Einordnung: Wir haben das auf einem kleinen Server mit Node.js verarbeitet, indem wir mehrere kleine Hugging-Face-Modelle aneinandergereiht haben
Die Ergebnisse werden üblicherweise per Reciprocal Rank Fusion (RRF) zusammengeführt
Das RRF-Paper ist beeindruckend, weil es erstaunlich simpel ist, und es umfasst auch nur zwei Seiten: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
Für BM25-artige Aufgaben kann man Elasticsearch nutzen, für einfache und schnelle Vektorsuche Turbopuffer, und für vorab berechnete Ergebnisse bestimmter Queries oder dynamische Attribute, die sich häufig ändern, etwa Preise, auch Redis
Ich halte es für sinnvoll, solche Dinge im Scatter/Gather-Verfahren zu kombinieren
Außerhalb des Search-Stacks gibt es fast immer eine Inference-Service-Schicht für das Re-Ranking, die idealerweise ein einfacher Service ist, ähnlich wie andere Machine-Learning-Infrastruktur
Fast immer braucht man auch Routing, das Nutzeranfragen versteht und etwa „Nachschlagen per ID“ an ein System und „unscharfe semantische Suche“ an ein anderes System schickt
Diese haben sehr unterschiedliche Datenstrukturen, und Suche deckt im Allgemeinen eine breite Palette verschiedener Use Cases ab
Alles in ein einziges System zu pressen, halte ich für ein Antipattern
Jedes System passt zu anderen Workloads, und eingebaute Inference-Funktionen können beim Tempo kaum mit allgemeinen Machine-Learning-Tools mithalten, an die ML-Engineers gewöhnt sind
Ich habe es mit Elasticsearch Learning to Rank versucht, aber das war aussichtslos
Unter den Versuchen, breite Use Cases mit einem einzigen Stack abzudecken, ist Vespa aber vermutlich die beste Option
Als Autor von txtai: txtai implementiert in Python über das arrays-Paket einen performanten BM25-Index und speichert Termfrequenz-Vektoren in SQLite
Der hybride Indexierungsansatz von txtai unterstützt eine konvexe Kombination, wenn die BM25-Scores normalisiert sind, und Reciprocal Rank Fusion (RRF), wenn sie nicht normalisiert sind
[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/...
Sie nutzt mehrere Suchtechniken: lexikalische Suche (bm25, Fuzzy Search), semantische Suche (Embeddings), Re-Ranking (Cross-Encoder, Reciprocal Rank Fusion) sowie Re-Ranking für mehr Diversität und zur Minderung von Lost-in-the-Middle
[1] Langroid – ein Multi-Agent-LLM-Framework von Forschern der CMU/UW-Madison https://github.com/langroid/langroid
[2] DocChatAgent-Implementierung –
https://github.com/langroid/langroid/blob/main/langroid/agen...
Man kann bei der Methode answer_from_docs beginnen und von dort aus weiterverfolgen
Nebenbei: Falls du der Gründer von Kadoa bist, ist Kadoa-snack eines meiner täglich gern genutzten Tools, um LLM-bezogene HN-Diskussionen zu finden
Guter Artikel.
Wenn man noch etwas schwerer zu findenden Hintergrund ergänzt: BM25 steht für „Best Matching 25“, und „best matching“ bedeutet, dass es sich um eine Formel handelt, die die Begriffe der Anfrage und die Begriffe im Dokument abgleicht, um Ranking und Term-Gewichtungen zu bestimmen.
Die 25 ist schlicht eine laufende Nummer: Zuvor gab es 24 Varianten der Formel, und danach gab es weitere Varianten, aber Nummer 25 funktionierte am besten und wurde daher veröffentlicht.
Erdacht wurde sie von Stephen Robertson und Karen Spärck Jones (bekannt für IDF) und erstmals in Robertsons OKAPI-Forschungssystem für Information Retrieval implementiert.
Das OKAPI-System wurde über mehrere Jahre hinweg bei der jährlichen TREC (Text Retrieval Conference) des US-amerikanischen NIST gebenchmarkt; das kommt einer internationalen „Weltmeisterschaft“ für Suchmaschinenmethodik recht nahe.
Allerdings geht es bei dieser Veranstaltung eher um Vergleich und gegenseitiges Lernen als ums Gewinnen, und sie ist eine empfehlenswerte Veranstaltung, die jedes Jahr im November in Gaithersburg, Maryland, stattfindet.
Neben dem „Bag-of-Words“-Vektorraummodell (Sparse-Vektoren von Terms) und dem probabilistischen Modell, zu dem BM25 gehört, gibt es überraschend viele theoretische Rahmenwerke, um eine Dokumentmenge für eine gegebene Anfrage zu ranken, und es werden immer mehr.
Beispiele sind Divergence from Randomness, statistische Sprachmodellierung, Learning to Rank, Quantum Information Retrieval und neuronales Ranking.
Auf Konferenzen wie ICTIR oder SIGIR tauchen auch heute noch gelegentlich völlig neue Suchparadigmen auf.
Mit „statistischer Sprachmodellierung“ sind hier nicht die heute populären Large Language Models gemeint; diese fallen eher in die Kategorie „neuronale Suche“.
Außerdem kann es passieren, dass man bei der Suche nach „Quantum IR“ statt eines Tutorials zu Quantum Information Retrieval eher Infrarotspektroskopie oder ein gleichnamiges Zementunternehmen findet.
Auch im 21. Jahrhundert hat Suchtechnologie solche Feinheiten.
Wenn man BM25 und Alternativen selbst direkt vergleichen möchte, empfehle ich Terrier, eine an der University of Glasgow entwickelte Open-Source-Suchmaschine und Forschungsplattform.
BM25 ist zwar über 25 Jahre alt, hat sich aber weiterhin als schwer zu schlagende Baseline erwiesen und wird häufig als Bezugspunkt beim Vergleich neuer Methoden verwendet.
Die neuere Variante BM24F kann mehrere Felder wie Titel, Body und Hyperlinks sowie Hypertext verarbeiten.
Als empfohlener Artikel: 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 sowie der anschließende Part 2.
Leider ist er nicht Open Access.
Es hat am 18. begonnen und endet am 22.
Weitere Details: https://trec.nist.gov/
Mit Google und Google Scholar konnte ich dazu nichts Relevantes finden.
Peinlich, aber hier ist Eigenwerbung: https://github.com/jankovicsandras/plpgsql_bm25
https://github.com/jankovicsandras/bm25opt
https://github.com/softwaredoug/searcharray
Mit ähnlicher Zielsetzung bewerbe ich auch das sehr beliebte BM25S von Xing Han Lu:
https://github.com/xhluca/bm25s
Ich frage mich, ob es ein reines Python-Wrapper-Projekt zur Verwaltung vieler Texte und PDF-Dokumente gibt.
Ich hatte an Solr oder ElasticSearch gedacht, aber für das, was ich gerade machen will, wirken sie zu schwergewichtig.
Da SQLite BM25 verwendet, überlege ich, pysqlite3 zusammen mit PyPDF2 zu nutzen.
Das geht etwas am Thema vorbei, aber vermutlich suchen viele Leute nach Tools, um hybride BM25-/Vektorspeicher-/LLM-Anwendungen zu bauen.
Ich frage mich, ob die bei der Normalisierung der Dokumentlänge genannte durchschnittliche Dokumentlänge der Median ist.
Um die Gewichtung übermäßig langer Dokumente korrekt zu senken, müsste es meiner Meinung nach der Median sein; andernfalls würden sehr lange Dokumente den Durchschnitt doch unangemessen nach oben ziehen.
Den Median zu verwenden, wäre ebenfalls ein interessantes Experiment.
Ich frage mich, ob jemand ein Such-Dataset kennt, bei dem sich die Dokumentlängen sehr stark unterscheiden.
MSMarco zum Beispiel hat ziemlich gleichmäßige Längen.
Guter Artikel.
Ich würde wirklich gern lernen, solche Probleme in mathematischer Form zu denken und zu testen; gibt es dafür empfehlenswerte Materialien?
Hybride Suche löst die alte Herausforderung der Relevanz von Suchergebnissen.
Mit Rank Fusion zwischen Keywords und Vektoren lässt sich eine hybride Suche bauen, die in den meisten Situationen funktioniert.
BM25 ist ein alter Algorithmus, der in den 1970er-Jahren entwickelt wurde.
Im Grunde ist es ein grobes statistisches Modell, und heutige Statistiker können das deutlich besser.
Ich sehe Search als strikt von lernbasierten Methoden dominiert.
Natürlich kann Lernen Search als Eingabe verwenden.
Viele haben das noch nicht erkannt oder haben Anreize, alte Technik so lange wie möglich am Leben zu halten, aber der Marktdruck wird das letztlich ändern.
Ist es nicht genau diese Technik, wegen der man inzwischen an jede Suchanfrage „+reddit“ anhängt, um dem feindseligen SEO-Krieg auszuweichen?
Alt heißt nicht automatisch schlecht.
Man sollte auf den Nutzen einer Erfindung, Entdeckung oder Methode schauen, nicht auf ihr Alter; diese seltsame technizistische Fixierung aufs Alter bereitet mir Sorgen.
Welche konkreten modernen statistischen Ansätze hältst du für so überlegen, dass sie BM25 in realen Anwendungen ersetzen können?
Besonders interessiert mich, wie sie Randfälle wie seltene Begriffe und die Normalisierung der Dokumentlänge behandeln, die BM25 explizit adressieren wollte.
Ich stimme zu, dass lernbasierte Ansätze beeindruckende Ergebnisse gezeigt haben, aber ich würde gern genauer hören, was es bedeutet, dass Search von Lernmethoden „strikt dominiert“ wird.
Geht es um bestimmte Benchmarks oder um reale Produktionsfälle?
Viele Such-Experten würden dem vermutlich widersprechen.
Ein hervorragender Podcast von David Tippet (ehemals OpenSearch, jetzt Github) und Nicolay Gerold trägt den Titel:
„BM25 is the workhorse of search; vectors are its visionary cousin“
https://www.youtube.com/watch?v=ENFW1uHsrLM
Im Search-Bereich gab es während meiner gesamten Laufbahn unzählige Hypes und KI-bezogene Technologien.
Derzeit treiben mit viel VC-Geld ausgestattete Vektorsuche-Unternehmen mit Heerscharen von Technology Evangelists eine bestimmte Sichtweise voran.
Gleichzeitig ist die Menge an manueller Kuration sowie an grundlegenden, langweiligen manuellen Klassifikationssystemen enorm, die an Orten wie Google die „semantische Suche“ tatsächlich antreiben.
Nur sind solche Dinge nicht sexy und werden deshalb auf Konferenzen kaum thematisiert.