ConceptDBISAI-written · not yet proofread

BM25

Also Okapi BM25 · Best Match 25

BM25 is the tf.idf-style posting score tf* · log2(N / df) whose modified term frequency tf* = tf · (k + 1) / (k · α + tf), α = 1 − b + b · DL / AVDL, saturates in tf and normalizes by document length.

Know these firstTF-IDF Term Frequency

Definition

BM25 (“best match”) scores word $w$ in document $D$ by

\text{BM25}(w, D) = \mathrm{tf}^* \cdot \log_2 \frac{N}{\mathrm{df}_w}, \qquad \mathrm{tf}^* = \frac{\mathrm{tf} \cdot (k+1)}{k \cdot \alpha + \mathrm{tf}}, \qquad \alpha = 1 - b + b \cdot \frac{\mathrm{DL}}{\mathrm{AVDL}},

where $\mathrm{tf} = \mathrm{tf}(w, D)$ is the term frequency, $N$ the number of documents, $\mathrm{df}_w$ the number of documents containing $w$ , $\mathrm{DL}$ the length of $D$ and $\mathrm{AVDL}$ the average document length (both in words), and $k \ge 0$ , $b \in [0, 1]$ are parameters. It improves on tf.idf by (1) bounding the influence of tf and (2) normalizing for document length.

Formula#

The idf factor $\log_2(N/\mathrm{df}_w)$ is the same as in tf.idf; only $\mathrm{tf}$ is replaced by $\mathrm{tf}^*$ . Rewriting shows that $\alpha$ acts as a normalization of $\mathrm{tf}$ :

\mathrm{tf}^* = \frac{\mathrm{tf} \cdot (k+1)}{k \cdot \alpha + \mathrm{tf}} = \frac{\mathrm{tf}}{\alpha} \cdot \frac{k+1}{k + \mathrm{tf}/\alpha}.

Parameters:

$b$ controls the length normalization: $b = 0$ gives $\alpha = 1$ (none), $b = 1$ gives $\alpha = \mathrm{DL}/\mathrm{AVDL}$ (full, “too extreme”); $b$ interpolates between the two.
$k$ controls the saturation: $\mathrm{tf}^* \to k + 1$ as $\mathrm{tf} \to \infty$ .
Standard setting: $k = 1.75$ , $b = 0.75$ .

Special cases (lecture):

$k = 0$ : $\mathrm{tf}^* = 1$ for every $\mathrm{tf} > 0$ (binary: presence only), so the score is the idf.
$k \to \infty$ , $b = 0$ : $\alpha = 1$ and $\mathrm{tf}^* \to \mathrm{tf}$ , i.e. plain tf.idf. (For general $b$ , $\mathrm{tf}^* \to \mathrm{tf}/\alpha$ , a length-normalized tf.)

Properties#

Plausibility argument for $\mathrm{tf}^*$ (DBIS_VL02 > Plausibility argument): the “simplest” function with

$\mathrm{tf}^* = 0 \iff \mathrm{tf} = 0$ ,
$\mathrm{tf}^*$ increasing in $\mathrm{tf}$ (strictly for $k > 0$ ),
$\mathrm{tf}^* \to$ a fixed limit ( $k + 1$ ) as $\mathrm{tf} \to \infty$ (fixes the linearity problem of tf.idf),

for any $\alpha > 0$ ; choosing $\alpha$ from $\mathrm{DL}/\mathrm{AVDL}$ fixes the length problem.

Property	tf.idf	BM25
tf factor	$\mathrm{tf}$ , unbounded and linear	$\mathrm{tf}^* \le k + 1$ , saturating
Length normalization	none	via $\alpha$ (strength $b$ )
idf factor	$\log_2(N/\mathrm{df})$	same
Use	simple baseline	standard, outperformed other formulas on benchmarks for many years

Implementation (DBIS_VL02 > Implementation advice): build the inverted lists with tf scores, compute $\mathrm{DL}$ per document and $\mathrm{AVDL}$ in the same pass, then make a second pass over the lists and replace each tf by $\mathrm{tf}^* \cdot \log_2(N/\mathrm{df})$ , where $\mathrm{df}$ is the length of the list.

Vector space view: with BM25 scores as entries of the term-document matrix $A$ , the dot product $q^T A$ gives exactly the same ranking as the inverted-index ranking (DBIS_VL11 > Variant 1: dot product with BM25 scores); BM25 already accounts for document length, which the plain dot product with tf would not.

Example#

Example $\mathrm{tf}^*$ with $k = 1$ , $b = 0$ , $\mathrm{idf} = 1$ (exam WS 23/24 retake, Task 1.1)

With $b = 0$ , $\alpha = 1$ and $\mathrm{tf}^* = 2 \cdot \mathrm{tf} / (1 + \mathrm{tf})$ : $\mathrm{tf} = 1 \mapsto 1$ , $\mathrm{tf} = 2 \mapsto 4/3$ , $\mathrm{tf} = 3 \mapsto 3/2$ . $D_1$ = b a c c, $D_2$ = c a b d b c, $D_3$ = c b a d c b c, $D_4$ = c b a d d:

word	postings $(D, \mathrm{tf}^*)$
a	$(D_1, 1), (D_2, 1), (D_3, 1), (D_4, 1)$
b	$(D_1, 1), (D_2, 4/3), (D_3, 4/3), (D_4, 1)$
c	$(D_1, 4/3), (D_2, 4/3), (D_3, 3/2), (D_4, 1)$
d	$(D_2, 1), (D_3, 1), (D_4, 4/3)$

ExampleEffect of length normalization

$N = 8$ , $\mathrm{df}_w = 2$ (so $\mathrm{idf}_w = 2$ ), $k = 1$ , $b = 0.5$ , $\mathrm{AVDL} = 4$ , and $\mathrm{tf}(w, D) = 3$ in two documents:

long document, $\mathrm{DL} = 8$ : $\alpha = 0.5 + 0.5 \cdot 2 = 1.5$ , $\mathrm{tf}^* = \frac{3 \cdot 2}{1.5 + 3} = \frac{4}{3}$ , score $\frac{8}{3} \approx 2.67$ ;
short document, $\mathrm{DL} = 2$ : $\alpha = 0.5 + 0.5 \cdot 0.5 = 0.75$ , $\mathrm{tf}^* = \frac{3 \cdot 2}{0.75 + 3} = 1.6$ , score $3.2$ .

The same tf counts more in the shorter document; with tf.idf both would score $3 \cdot 2 = 6$ .

Sources#

Slides 02, p. 14 (problems of tf.idf), Slides 02, p. 15 (formula), Slides 02, pp. 16–17 (plausibility), Slides 02, p. 18 (implementation)
Slides 03, p. 5 (ES2 tuning results), Slides 11, p. 11
DBIS_VL02 > BM25, DBIS_VL03 > Organisation, DBIS_VL11 > Variant 1: dot product with BM25 scores
Exams: DBIS Exam WS2324-2 (not published) Task 1.1

Connections

Mentioned in inline links10

Overfitting (IR Evaluation)
Let $M(\theta, Q)$ be a quality measure (e.g. MAP) of a system with parameters $\theta$ (e.g. the BM25 parameters $k, b$ ) on the query set $Q$ . Choosing §
TF-IDF
BM25 fixes both by replacing $\mathrm{tf}$ with a saturating, length-normalized $\mathrm{tf}^*$ and keeps the same idf factor. §
Term Frequency
Longer documents have larger tf without being more relevant, and relevance does not grow linearly with tf. Fix: the saturating, length-normalized $\mathrm{tf}^*$ of BM25. §
Vector Space Model
The dot product with tf entries reproduces the tf score sum of Lecture 2; with BM25 entries it gives exactly the BM25 ranking of the inverted index (Slides 11, p. 11). Worth a line under Retrieval. §
VL02 – Ranking and Evaluation
BM25 is a tf.idf-style formula that became famous for outperforming other formulas on standard benchmarks over many years. §
BM25 — tf.idf with saturating, length-normalized $\mathrm{tf}^*$ ; implemented and tuned in ES2 §
VL03 – Database Basics
ES2 results (BM25 tuning): values of $b$ close to (but not) zero and $k \approx 1$ worked best; $k = 1$ maps $\mathrm{tf}^* \in [1, 2]$ for $\mathrm{tf} > 0$ . Baseline MP@3 = 58 %, MP@R = 42 %, MAP = 42 %; best submissions MP@3 = 76 %, MP@… §
VL11 – Vector Space Model, Word Embeddings
Each row corresponds to a word, each column to a document. A non-zero entry is the score of that word in that document; the lecture uses tf scores, ES11 uses BM25 scores. §
Problem with the plain dot product: documents with more and/or higher entries (longer documents, more repetitions) get larger scores. One remedy is to use BM25 scores as matrix entries: BM25 was designed to account for document length and… §
Evaluation
Honest evaluation. Parameters such as $k, b$ of BM25 are tuned on a training benchmark; the test benchmark is used once at the end (Overfitting (IR Evaluation)). Typical numbers (ES2): baseline MAP 42 %, best tuned 48 %. §
Inverted Index and Ranking
BM25 — tf.idf with saturating, length-normalized tf; the standard score §
| BM25 | $\mathrm{tf}^* \cdot \log_2(N/\mathrm{df})$ | tf saturates at $k+1$ , normalized by $\mathrm{DL}/\mathrm{AVDL}$ | parameters $k, b$ must be tuned (on a training set) | §
Word Embeddings and Language Models
| dot product | BM25 | handled by BM25’s length normalization | exactly the BM25 ranking of the Inverted Index (Lecture 2) | ES11, Ex. 1 | §

Search in these mentions →