Den BM25-Algorithmus für die Volltextsuche verstehen

• BM25-Algorithmus verstehen

  • BM25 ist ein weit verbreiteter Volltextsuchalgorithmus, der standardmäßig in Lucene/Elasticsearch und SQLite verwendet wird.
  • In jüngerer Zeit ist es üblich geworden, Volltextsuche mit Vektor-Ähnlichkeitssuche zu kombinieren, um eine „hybride Suche“ zu implementieren.
  • Ausgangspunkt ist die Frage, ob sich BM25-Scores zwischen mehreren Abfragen vergleichen lassen.

• Dokumente ranken

  • Das grundlegende Ziel von Volltextsuchalgorithmen ist es, die für eine Abfrage relevantesten Dokumente zu finden.
  • BM25 rankt Dokumente auf Grundlage der Wahrscheinlichkeit, dass ein Dokument für die Abfrage relevant ist.

• Bestandteile von BM25

  • Abfragebegriffe: Bei Abfragen, die aus mehreren Begriffen bestehen, wird für jeden Begriff ein separater Score berechnet und anschließend aufsummiert.
  • Inverse Document Frequency (IDF): Berechnet die Seltenheit eines bestimmten Suchbegriffs in der gesamten Dokumentensammlung.
  • Termhäufigkeit im Dokument: Berechnet, wie oft der Suchbegriff in einem bestimmten Dokument vorkommt.
  • Normalisierung der Dokumentlänge: Normalisiert die Länge eines Dokuments im Vergleich zu anderen Dokumenten.

• Die mathematische Darstellung von BM25

  • Der BM25-Algorithmus kann mathematisch komplex wirken, lässt sich aber leicht verstehen, wenn man die einzelnen Bestandteile kennt.
  • Die zentrale Formel wird berechnet, indem die Scores der einzelnen Abfragebegriffe aufsummiert werden.

• Die Besonderheit von BM25

  • Auf Wahrscheinlichkeit basierendes Ranking ohne Wahrscheinlichkeitsberechnung: BM25 rankt Dokumente auf Grundlage des probabilistischen Relevanz-Frameworks.
  • Annahme, dass die meisten Dokumente nicht relevant sind: BM25 geht davon aus, dass die meisten Dokumente für die Abfrage nicht relevant sind, und ist dadurch auch ohne Relevanzinformationen nützlich.

• Fazit

  • BM25-Scores lassen sich innerhalb derselben Sammlung zwischen verschiedenen Abfragen vergleichen.
  • BM25 konzentriert sich nicht darauf, die Relevanz eines Dokuments zu schätzen, sondern darauf, Dokumente nach ihrer Relevanz für eine Abfrage zu ranken.
  • Die BM25-Scores desselben Dokuments lassen sich innerhalb derselben Sammlung vergleichen.

• Weiterführende Lektüre

  • Wer mehr über Theorie und Geschichte von BM25 erfahren möchte, dem seien der Vortrag von Elastic-Ingenieurin Britta Weber aus dem Jahr 2016 sowie Stephen Robertsons und Hugo Zaragozas „The Probabilistic Relevance Framework: BM25 and Beyond“ empfohlen.