BM25 (1994) › The Solution: A Probabilistic Framework

BM25 addressed these limitations within a probabilistic framework. "BM" stands for "Best Matching," while "25" indicates the 25th iteration of the model developed by Robertson and Spärck Jones.

BM25 follows the probabilistic ranking principle: documents should be ordered by their estimated probability of relevance. Its scoring function approximates this ordering with contributions for term rarity and saturated term frequency, adjusted for document length.

For a query $Q$ containing terms $q_1, q_2, \ldots, q_n$, the BM25 score for document $D$ is:

$$\text{BM25}(D,Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{\text{avgdl}})}$$

The $\text{IDF}(q_i)$ term assigns more weight to terms that occur in fewer documents. The fraction containing $f(q_i, D)$ saturates as term frequency rises, preventing repeated occurrences from increasing the score without bound.

The normalization factor addresses document-length bias. The parameter $b$ controls its strength: $b = 0$ applies no length normalization, while $b = 1$ applies full normalization. The ratio $\frac{|D|}{\text{avgdl}}$ compares the current document's length with the collection average.

The parameter $k_1$ controls how quickly term frequency saturates. When $k_1 = 0$, term frequency does not affect the contribution beyond presence; larger values delay saturation and give repeated occurrences more influence.

BM25 is derived from probabilistic information retrieval theory and extends the binary independence model. Its assumptions connect the scoring terms to a model of relevant and non-relevant documents rather than only to a similarity heuristic.

The probabilistic derivation begins with the assumption that we can model the probability of a document being relevant given a query. Using Bayes' theorem, this probability can be expressed as:

$$P(\text{relevant} | D, Q) = \frac{P(D, Q | \text{relevant}) \cdot P(\text{relevant})}{P(D, Q)}$$

Computing this probability directly is impractical, so BM25 uses simplifying assumptions to approximate the log-odds of relevance as a sum of term-level contributions. Each contribution reflects how well a term distinguishes relevant from non-relevant documents.

Relevance judgments can be used to tune BM25's parameters for a collection and query distribution. This made the model practical in evaluations and applications where such feedback was available.

BM25 has two main tuning parameters. The value of $k_1$ controls term-frequency saturation, while $b$ controls document-length normalization. Both can be selected for a particular collection and query set.

The $k_1$ parameter controls term-frequency saturation and is often set between 1.2 and 2.0. Lower values saturate quickly, reducing the effect of repeated boilerplate or specifications. Higher values give term counts more influence when repeated occurrences correlate with relevance in the target collection.

The $b$ parameter controls document length normalization, typically ranging from 0.0 to 1.0. When $b = 0$, the algorithm performs no length normalization, which might be appropriate for collections where document length is a meaningful indicator of comprehensiveness. When $b = 1$, the algorithm performs full length normalization, which is generally preferred for most applications where users want the most relevant content regardless of document length.

BM25 often performs reasonably across a range of parameter settings. Collection-specific tuning can improve results, but useful baselines are possible without an exhaustive parameter search.