4ft algorithm analysis analytics bm25 bm25f engine index information ir link nlp okapi ranking relevance relevancy retrieval search tfidf trecvid

My tags:

From Wikipedia, the free encyclopedia

In information retrieval, Okapi BM25 is a ranking function used by search engines to rank matching documents according to their relevance to a given search query. It is based on the probabilistic retrieval framework developed in the 1970s and 1980s by Stephen E. Robertson, Karen Spärck Jones, and others.

The name of the actual ranking function is BM25. To set the right context, however, it usually referred to as "Okapi BM25", since the Okapi information retrieval system, implemented at London's City University in the 1980s and 1990s, was the first system to implement this function.

BM25, and its newer variants, e.g. BM25F (a version of BM25 that can take document structure and anchor text into account), represent state-of-the-art retrieval functions used in document retrieval, such as Web search.

Contents 1 The ranking function 2 IDF Information Theoretic Interpretation 3 Links 4 References

[edit] The ranking function

BM25 is a bag-of-words retrieval function that ranks a set of documents based on the query terms appearing in each document, regardless of the inter-relationship between the query terms within a document (e.g., their relative proximity). It is not a single function, but actually a whole family of scoring functions, with slightly different components and parameters. One of the most prominent instantiations of the function is as follows.

Given a query Q, containing keywords q₁,...,q_n, the BM25 score of a document D is:

where f(q_i,D) is q_i's term frequency in the document D, | D | is the length of the document D in words, and avgdl is the average document length in the text collection from which documents are drawn. k₁ and b are free parameters, usually chosen as k₁ = 2.0 and b = 0.75. IDF(q_i) is the IDF (inverse document frequency) weight of the query term q_i. It is usually computed as:

where N is the total number of documents in the collection, and n(q_i) is the number of documents containing q_i.

There are several interpretations for IDF and slight variations on its formula. In the original BM25 derivation, the IDF component is derived from the Binary Independence Model (see BM25 tutorial).

[edit] IDF Information Theoretic Interpretation

Here is an interpretation from information theory. Suppose a query term q appears in n(q) documents. Then a randomly picked document D will contain the term with probability (where N is again the cardinality of the set of documents in the collection). Therefore, the information content of the message "D contains q" is:

Now suppose we have two query terms q₁ and q₂. If the two terms occur in documents entirely independently of each other, then the probability of seeing both q₁ and q₂ in a randomly picked document D is:

and the information content of such an event is:

With a small variation, this is exactly what is expressed by the IDF component of BM25.

[edit] Links

• The Probabilistic Relevance Method: BM25 and beyond (2007 SIGIR Tutorial) : http://barcelona.research.yahoo.net/dokuwiki/doku.php?id=prm
• BM25 implementation for Lucene

[edit] References

• Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. Okapi at TREC-3. In Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA, November 1994.

• Stephen E. Robertson, Steve Walker, and Micheline Hancock-Beaulieu. Okapi at TREC-7. In Proceedings of the Seventh Text REtrieval Conference. Gaithersburg, USA, November 1998.

• Karen Spärck Jones, Steve Walker, and Stephen E. Robertson. A Probabilistic Model of Information Retrieval: Development and Comparative Experiments (parts 1 and 2). Information Processing and Management, 36(6):779-840. 2000.

• Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge at TREC-14: Enterprise Track. In Proceedings of the Fourteenth Text REtrieval Conference (TREC 2005). Gaithersburg, USA, November 2005. Describes application and tuning of Okapi BM25F.