BM25: The Family of Document Ranking Functions and Minych's Keyword Density Metric

Okapi BM25 — a ranking function used by search engines to order documents by their relevance to a given search query. It is based on a probabilistic model developed in the 1970s and 1980s by Stephen Robertson, Karen Spärck Jones, and others.

The function itself is called BM25 (BM from "best match"), but it is often called «Okapi BM25», after the name of the Okapi search system, created at London City University in the 1980s and 1990s, in which this function was first applied.

BM25 and its various later modifications (such as BM25F) are modern TF-IDF-like ranking functions that are widely used in practice in search engines. In web search, these ranking functions are often included as components of a more complex, often machine-learned, ranking function.

The ranking function (algorithm)

BM25 — a search function over an unordered set of terms (a «bag of words») and a set of documents, which it scores based on the occurrence of the query words in each document, without taking into account the relationships between them (such as proximity). It is not a single function, but a family of functions with various components and parameters. One of the common forms of this function is described below.

Let there be a query , containing the words , then the BM25 function gives the following relevance score of document to query :

where is the frequency of the word (term frequency, TF) in document , is the length of the document (the number of words in it), and — the average document length in the collection. and — free coefficients, usually chosen as and .

is the inverse document frequency (IDF) of the word . There are several interpretations of IDF and small variations of its formula. Classically, it is defined as:

where is the total number of documents in the collection, and — the number of documents containing . But «smoothed» variants of this formula are used more often, for example:

Note that the above IDF formula has the following drawback. For words that occur in more than half of the documents in the collection, the IDF value is negative. Thus, given any two nearly identical documents, one of which contains a word while the other does not, the second one may receive a higher score.

In other words, frequently occurring words will spoil the final score of the document. This is undesirable, so in many applications the above formula can be adjusted in the following ways:

• Ignore all negative terms in the sum entirely (which is equivalent to adding all the corresponding high-frequency words to a stop list and ignoring them);
• Impose a lower bound on IDF : if IDF is less than , consider it equal to .
• Use a different IDF formula that does not take negative values.

Interpretation of IDF in information theory

Suppose that the search word occurs in documents. Then a randomly chosen document contains the word with probability (where is the cardinality of the set of documents in the collection). In this case the information value of the phrase « contains » is as follows:

Now suppose there are two search words and . If they occur in a document independently of each other, then the probability of finding them in a randomly chosen document is as follows:

and the information content of this event

This is roughly what is expressed by the IDF component in BM25.

Modifications

• At extreme values of the coefficient in the BM25 function, ranking functions known as BM11 (at ) and BM15 (at ) are obtained.
• BM25F — a modification of BM25 in which a document is treated as a collection of several fields (such as, for example, headings, body text, anchor text), whose lengths are normalized independently, and each of which can be assigned its own degree of importance in the resulting ranking function.

Drawbacks of TF-IDF and BM-25

The «bag-of-words» model used does not take into account:

• • the mutual arrangement of words (whether the keywords are in the same sentence or scattered throughout the text);
  • the position of a word relative to the beginning of the document (a keyword in the first sentence);
  • the word form (matching of the word's inflected form).
  • the position of the keyword in the document (the document zone).

Therefore, the BM25 formula alone, in its pure form, was not used for evaluating document relevance.

Deciphering BM25

Although Robertson claims that a probabilistic model was used to derive the formula, some experts consider it to be a «fitting» to the desired result. Free coefficients that can take various values are built into the BM25 function. They are chosen so as to «fit» the search results to already available data. Documents are first evaluated by assessors, who determine what is bad and what is good. Then, based on this data, the aforementioned coefficients are chosen so as to arrange the documents in the same way the assessors did – the so-called «monkey principle». The relevance score of document D for query Q , containing the words qi=q1,q2…qn, according to the BM25 formula:

Where:

For IDF a smoothed formula is used:

Where:

The formula for

TF

also changed:

The relevance for query Q is equal to the sum of the relevances for all the words qi=q1,q2…qn in the query. At first glance, the operating principle is the same as TF-IDF:

• if a word from the query is absent from the document, f(qi,D)=0, then the term in the formula score(D,Qi) will also equal 0;
• the more query words occur in the document, and the higher their frequency of use, the higher the final score will be.

But there are also differences:

• As occurrences increase, TF asymptotically approaches a value determined by the coefficients b,k1. Whereas in the classical formula TF tends to infinity.

Percentage growth of BM25 relative to the number of occurrences

• IDF takes on negative values for words occurring in more than half of the documents. Frequently occurring words significantly spoil the final score of the document. Given two nearly identical documents that differ only by one frequently used word, priority will go to the document that does not contain it. This fact is far from providing an adequate assessment of document quality, so one of two approaches is used:

a) negative values in the sum are simply ignored;

b) a lower bound is imposed, upon reaching which the IDF value is treated as a fixed number;

• Short documents reach TF score saturation much faster. After a certain threshold is reached, a further increase in term frequency in the document does not lead to growth of the TF score. Long documents, on the contrary, reach saturation much later.

• The Score value depends on the length of document D. The more words in the document, the lower the final score for the document will be.

Dependence of Score on text volume (TF decreases).

• If we take into account only relative relevance, i.e., the relevance of several documents for one query, the IDF multiplier is reduced. When calculating the Score of two texts with the same 2% occurrence of a single-word keyword (TF fixed), a text of 2300 characters will get a Score = 7.45 (≈-6%), while a text of 20,000 characters – a Score = 7.86% (≈+6%). If we take a two-word query, the Score for the long text will already be +12%. This is precisely why creating text «doorstoppers» was, for a long time, the norm for SEO specialists.

Few remember the «golden era of SEO», when webmasters spammed keywords, achieved higher relevance through sheer quantity, and, having added a thousand SAPE links on top of all that, reached the TOP within a couple of weeks.

Calculating BM-25

Let us take the same texts and calculate the number of documents containing the query words, and the average document length.

Next, let us find the IDF for each word in the query

As a result, we obtain the following TF value and Score for the query «Textual relevance of a document in search»:

A clear example of how IDF can take negative values for words that occur in more than half of the documents. Instead of a negative IDF value, a fixed IDF=0.01 was used. «Document 3» received the highest score, whereas in the classical TF-IDF formula it was document 1, which now has the lowest Score under BM25. Distribution of scores across different queries:

Up to this point we have been looking at a limited sample, in which it is known in advance that the documents are roughly on-topic. For a better understanding of the formula, let us consider an example with a non-topical collection of documents. Let us find the Score in a sample of 20,000 documents.

The IDF for the word «document» is significantly higher than for the words «relevance» and «textual». Now let us increase the frequency of the word «document» in doc2 from 2% to 5%.

We see a significant increase in TF and Score while IDF remains unchanged. Let us increase the frequency of «textual» to 6% in doc 1.

The sum of the frequencies of each query word in document 1 and document 2 is the same and amounts to 13%, but the term «document» is used less often in the collection. From the final score, we can say that the significance of narrowly specialized words is considerably higher than that of other terms from the query.

Document keyword density («nausea») according to Minych

In 2006-2007, based on the methodology of a user with the handle Minych on the Searchengines forum, it was concluded that Yandex used similar formulas when calculating relevance:

Where:

We see that, according to this formula, maximum relevance is achieved when the promoted query ti is the most frequent word in the document, n(ti,d)=nmax, while keyword density has no effect on the score at all. Minych was the first to introduce the concept of «keyword nausea». In his methodology, nausea W=max(√7,√nmax) – the square root of the frequency of the most frequently used word nmax in the document. If nmax is less than 7, then W=√7. When a certain spam threshold was exceeded for a specific word, for example W>25, a penalty was imposed on the document.

See also

• Link-based ranking‎
• HITS algorithm [[b9528]]
• Learning to rank
• TF-IDF
• Ranking (information retrieval)
• Divergence from randomness model
• Okapi BM25
• Search algorithm
• PageRank
• Yandex ranking (ROMIP 2006)
• [[b6539]]
• Content-based image retrieval
• Multimedia information retrieval
• Image search
• Triplet loss

See also

• The HITS Algorithm
• Page Ranking Algorithms for Search Engines