Best Match 25 (BM25)

BM25 considers both term frequency (TF) and document length normalization to determine the relevance of a dcoument to a given query.

This follows probabilistic retrieval framework, which assumes that relevant and non-relevant documents follow different statistical distributions.

$$\text{BM25}(D,Q)=\sum _{i=1}^n\text{IDF}(q_i)\cdot \frac{\text{TF}(q_i,D)\cdot (k_1+1)}{\text{TF}(q_i,D)+k_1\cdot \left(1-b+b\cdot \frac{|D|}{\text{avgdl}}\right)}$$

where:

• $\text{IDF}(q_i)$ is the inverse document frequency of query term $q_i$
• $\text{TF}(q_i,D)$ is the modified term frequency of $q_i$ in document $D$
• $|D|$ is the length of document $D$ (total word count including repeats)
• $\text{avgdl}$ is the average document length in the corpus (average of 4 documents, including repeats)
• $k_1$ and $b$ are tunable constants, where $k_1$ controls term frequency saturation and $b$ controls document length normalisation
• term frequency saturation, $k_1$ is an asymptote where we limit the $BM25$ as $tf$ tends to infinite

$$\underset{tf\to \infty }{\lim }\frac{tf(k_1+1)}{tf+k_1}=k_1+1$$

• document length normalization, $b$, tries to fix long documents winning every query
• because it is long, it will naturally contain more words which will have a higher chance on winning almost every query
• we divide the length of document by the average and the multiply it to the $b$
• we can choose between 0-1
• if $b=0$, we completely ignore the length of the document
• if $b=1$, we apply the full length correction
• most of the time we use $b=0.75$

Code

from rank_bm25 import BM25Okapi
 
corpus = [
    "I will take the Ring, though I do not know the way .",
    "I will help you bear this burden, Frodo Baggins, as long as it is yours to bear .",
    "If by my life or death I can protect you, I will ."
]
 
tokenized_corpus = [doc.split(" ") for doc in corpus]
 
bm25 = BM25Okapi(tokenized_corpus)
 
query = "will take"
tokenized_query = query.split(" ")
 
doc_scores = bm25.get_scores(tokenized_query)
print(doc_scores)

Output:

[0.61409996 0.06520301 0.07574482]

Notes:

• rank_bm25 needs a tokenised corpus, so each document must be a list of tokens rather than a raw string
• BM25Okapi uses defaults of k1=1.5 and b=0.75, and both can be passed as arguments
• get_scores returns one score per document for the given query, so the array has the same length as the corpus
• doc 1 scores 0.614 because it is the only one containing "take", and "take" has a high IDF
• doc 2 scores 0.065 and doc 3 scores 0.076, and both contain only "will", so the difference between them comes purely from document length, since doc 3 is shorter

Advantages and Limitations

Advantages	Limitations
Information retrieval: BM25 is effective for information retrieval tasks, and it often outperforms traditional TF-IDF weighting, especially on large and diverse text corpora	No semantics: like TF-IDF, BM25 does not take the semantics of a document into account
Balanced term frequency: BM25 addresses term frequency saturation with the parameter $k$, which makes it more robust on documents with varying term frequencies, and prevents common terms from dominating the score	Sparse data: BM25 may perform worse on very sparse data or extremely short documents, because it relies on term frequencies and document lengths to calculate scores

BM25 adds document length normalisation on top of the idea used by Term Frequency-Inverse Document Frequency (TF- IDF).