Understanding the BM25 Full Text Search Algorithm

• 0:00 Introduction & Motivation: The author is building a personalized content feed and explores BM25 to improve keyword matching in a hybrid search system (combining vector similarity and full-text search). The central question is whether BM25 scores can be compared across different queries. Initial responses from AI models were contradictory.

• 0:58 Probabilistic Ranking: BM25 aims to rank documents based on the probability of relevance to a query, using only characteristics of the query and documents. It differs from vector similarity search which leverages external semantic understanding.

• 1:53 BM25 Components: The algorithm incorporates:

  • Query terms: Scores for each term are summed.
  • Inverse Document Frequency (IDF): Rare words get higher weight, reflecting higher informational value.
  • Term frequency in the document: Higher frequency increases relevance, but with diminishing returns.
  • Document length normalization: Penalizes longer documents to prevent bias.

• 3:01 BM25 Equation: The complete BM25 equation is presented, detailing how the above components combine. Each part is broken down separately below.

• 3:29 Query Terms: The equation sums scores for each query term in a given document.

• 3:48 Inverse Document Frequency (IDF): The IDF component is described. The formula uses: N (total documents), n(qi) (documents containing query term). Common terms have a smaller impact (IDF), while rare terms have a larger impact (IDF).

• 4:36 Term Frequency in the Document: This component considers how often a query term appears in a document. The formula incorporates a tuning parameter (k1) to control diminishing returns of term repetition.

• 5:11 Document Length Normalization: This component adjusts the score based on document length relative to the average. A parameter (b) controls the strength of normalization; longer documents are penalized.

• 5:47 Putting It Together: The full BM25 equation is revisited, showing how IDF, term frequency, and document length normalization are combined to obtain a final score.

• 6:06 Cleverness of BM25: Two key aspects are highlighted:

  • Probability Ranking Without Probability Calculation: BM25 utilizes the Probability Ranking Principle but avoids direct probability computation, focusing on ranking order.
  • Assuming Most Documents Are Irrelevant: A crucial assumption simplifies the underlying theoretical model. The Robertson/Sparck Jones Weight, which requires knowledge of relevant documents, is simplified by assuming most documents are irrelevant (R=r=0). This leads to a near-equivalent of the IDF term in BM25.

• 8:12 Conclusion: BM25 scores can be compared within the same collection for the same document, but not across different collections or over time, as IDF and average document length change. The author can use this for their personalized feed.

• 9:00 Further Reading: The author provides links to additional resources for deeper understanding of BM25.