Understanding the BM25 Full Text Search Algorithm

• Motivation: The author, building a personalized content feed, explores BM25 to determine if its scores can be compared across different queries to assess a document's best match. Initial AI responses were contradictory.

• Probabilistic Ranking: BM25 ranks documents based on the probability of relevance to a query, utilizing only query and document characteristics (unlike vector similarity search which uses external semantic understanding).

• BM25 Components: The algorithm uses:

  • Query Terms: Scores for each query term are summed.
  • Inverse Document Frequency (IDF): Rare words are weighted more heavily than common ones. The formula uses the number of documents with and without the term to calculate this.
  • Term Frequency: The frequency of a term in a document is considered, but with diminishing returns for repeated terms (controlled by the k1 parameter).
  • Document Length Normalization: Longer documents are penalized to prevent bias, controlled by the b parameter.

• BM25 Equation: The complete BM25 equation is presented and its components are explained in detail.

• Cleverness of BM25:

  • Probability Ranking without Probability Calculation: BM25 cleverly ranks by weight, not by calculating true probability of relevance, simplifying the equation without losing ranking effectiveness. This builds on the Probability Ranking Principle.
  • Assumption of Irrelevant Documents: BM25 overcomes the reliance on knowing relevant documents (a problem in earlier algorithms) by assuming most documents are irrelevant, leading to a simplified equation that closely approximates IDF.

• Conclusion: BM25 scores can be compared across queries within the same document collection, but not across different collections or over time (due to changes in IDF and average document length).

• Further Reading: The author recommends Britta Weber's 2016 talk and a paper by Robertson and Zaragoza for a deeper dive into BM25. A link to a comparison of BM25 with other algorithms is also provided.