A short explanation of TF-IDF, BM25 and their differences. And as usual, a quick list of useful references.

Intro

TFIDF (term frequency-inverse document frequency: wiki link) and BM25 (Okapi Best Matching 25: wiki link) are two methods for document searchs.

The typical use case is when you have 1000 documents, and you want to retrieve the best matching document for the search query “dog”. The solution is to look at every document, and score them with a “ranking function” that will put a high score on documents talking about dogs.

TF-IDF

The ranking formula for TF-IDF is:
Score = result2 = result2

One assumption has to be made : the more times a document contains a term, the more likely it is to be about that term (the more relevant). In practise, it works surprinsingly well. Not always of course, but for the price of this solution, it’s very efficient.

Why the log ? => only to smooth the function for low values.

BM25

This is a TFIDF upgrade : we’ll replace TF x,y and IDF with refinements

TF tuning

IDF tunning

Reasearch came up with a “probabilistic IDF” to replace IDF with:
log((N - DF + .5)/(DF + .5))

This function takes a sharp drop for terms that are in most of the documents. Stopword like “and” or “or” will be discredited.

But to avoid having negative values (a word should never count less than if simply absent, with mean 0), Lucene added 1 :

So here is the formula :
log(1 + (N - DF + .5)/(DF + .5))

Conclusion

TF-IDF rewards term frequency and penalizes document frequency.

BM25 goes beyond this to account for document length and term frequency saturation.

Reference

Understanding TF-IDF and BM25 : kmwllc Blog post