Okapi BM25

<h2 id="the-ranking-function">The ranking function</h2>
BM25 is a <a href="/facts/Bag_of_words_model/TlhIx600">bag-of-words</a> retrieval function that ranks a set of documents based on the query terms appearing in each document, regardless of their proximity within the document. It is a 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
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 q
 
 n
 
 
 
 
 {\displaystyle q_{1},...,q_{n}}
 
, the BM25 score of a document D is:

score
        
        (
        D
        ,
        Q
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          IDF
        
        (
        
          q
          
            i
          
        
        )
        ⋅
        
          
            
              f
              (
              
                q
                
                  i
                
              
              ,
              D
              )
              ⋅
              (
              
                k
                
                  1
                
              
              +
              1
              )
            
            
              f
              (
              
                q
                
                  i
                
              
              ,
              D
              )
              +
              
                k
                
                  1
                
              
              ⋅
              
                (
                
                  1
                  −
                  b
                  +
                  b
                  ⋅
                  
                    
                      
                        
                          |
                        
                        D
                        
                          |
                        
                      
                      avgdl
                    
                  
                
                )
              
            
          
        
      
    
    {\displaystyle {\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot {\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}}

where 
 
 
 
 f
 (
 
 q
 
 i
 
 
 ,
 D
 )
 
 
 {\displaystyle f(q_{i},D)}
 
 is the number of times that the keyword 
 
 
 
 
 q
 
 i
 
 
 
 
 {\displaystyle q_{i}}
 
 occurs in the document D, 
 
 
 
 
 |
 
 D
 
 |
 
 
 
 {\displaystyle |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
 
 1
 
 
 
 
 {\displaystyle k_{1}}
 
 and b are free parameters, usually chosen, in absence of an advanced optimization, as 
 
 
 
 
 k
 
 1
 
 
 ∈
 [
 1.2
 ,
 2.0
 ]
 
 
 {\displaystyle k_{1}\in [1.2,2.0]}
 
 and 
 
 
 
 b
 =
 0.75
 
 
 {\displaystyle b=0.75}
 
.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 
 
 
 
 
 IDF
 
 (
 
 q
 
 i
 
 
 )
 
 
 {\displaystyle {\text{IDF}}(q_{i})}
 
 is the IDF (<a href="/facts/Inverse_document_frequency/JDzc5Jnr">inverse document frequency</a>) weight of the query term 
 
 
 
 
 q
 
 i
 
 
 
 
 {\displaystyle q_{i}}
 
. It is usually computed as:

IDF
        
        (
        
          q
          
            i
          
        
        )
        =
        ln
        ⁡
        
          (
          
            
              
                
                  N
                  −
                  n
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                  +
                  0.5
                
                
                  n
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                  +
                  0.5
                
              
            
            +
            1
          
          )
        
      
    
    {\displaystyle {\text{IDF}}(q_{i})=\ln \left({\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}}+1\right)}

where N is the total number of documents in the collection, and 
 
 
 
 n
 (
 
 q
 
 i
 
 
 )
 
 
 {\displaystyle n(q_{i})}
 
 is the number of documents containing 
 
 
 
 
 q
 
 i
 
 
 
 
 {\displaystyle 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 <a href="/facts/Binary_Independence_Model/JMXl0g8G">Binary Independence Model</a>.

<h2 id="idf-information-theoretic-interpretation">IDF information theoretic interpretation</h2>
Here is an interpretation from information theory. Suppose a query term 
 
 
 
 q
 
 
 {\displaystyle q}
 
 appears in 
 
 
 
 n
 (
 q
 )
 
 
 {\displaystyle n(q)}
 
 documents. Then a randomly picked document 
 
 
 
 D
 
 
 {\displaystyle D}
 
 will contain the term with probability 
 
 
 
 
 
 
 n
 (
 q
 )
 
 N
 
 
 
 
 {\displaystyle {\frac {n(q)}{N}}}
 
 (where 
 
 
 
 N
 
 
 {\displaystyle N}
 
 is again the cardinality of the set of documents in the collection). Therefore, the <a href="/facts/Information/3LdrzXtJ">information</a> content of the message "
 
 
 
 D
 
 
 {\displaystyle D}
 
 contains 
 
 
 
 q
 
 
 {\displaystyle q}
 
" is:

−
        log
        ⁡
        
          
            
              n
              (
              q
              )
            
            N
          
        
        =
        log
        ⁡
        
          
            N
            
              n
              (
              q
              )
            
          
        
        .
      
    
    {\displaystyle -\log {\frac {n(q)}{N}}=\log {\frac {N}{n(q)}}.}

Now suppose we have two query terms 
 
 
 
 
 q
 
 1
 
 
 
 
 {\displaystyle q_{1}}
 
 and 
 
 
 
 
 q
 
 2
 
 
 
 
 {\displaystyle q_{2}}
 
. If the two terms occur in documents entirely independently of each other, then the probability of seeing both 
 
 
 
 
 q
 
 1
 
 
 
 
 {\displaystyle q_{1}}
 
 and 
 
 
 
 
 q
 
 2
 
 
 
 
 {\displaystyle q_{2}}
 
 in a randomly picked document 
 
 
 
 D
 
 
 {\displaystyle D}
 
 is:

n
              (
              
                q
                
                  1
                
              
              )
            
            N
          
        
        ⋅
        
          
            
              n
              (
              
                q
                
                  2
                
              
              )
            
            N
          
        
        ,
      
    
    {\displaystyle {\frac {n(q_{1})}{N}}\cdot {\frac {n(q_{2})}{N}},}

and the information content of such an event is:

∑
          
            i
            =
            1
          
          
            2
          
        
        log
        ⁡
        
          
            N
            
              n
              (
              
                q
                
                  i
                
              
              )
            
          
        
        .
      
    
    {\displaystyle \sum _{i=1}^{2}\log {\frac {N}{n(q_{i})}}.}

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

<h2 id="modifications">Modifications</h2>
<ul><li>At the extreme values of the coefficient b BM25 turns into ranking functions known as BM11 (for 
 
 
 
 b
 =
 1
 
 
 {\displaystyle b=1}
 
) and BM15 (for 
 
 
 
 b
 =
 0
 
 
 {\displaystyle b=0}
 
).<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>BM25F<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> (or the BM25 model with Extension to Multiple Weighted Fields<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>) is a modification of BM25 in which the document is considered to be composed from several fields (such as headlines, main text, anchor text) with possibly different degrees of importance, term relevance saturation and length normalization. BM25F defines each type of field as a stream, applying a per-stream weighting to scale each stream against the calculated score.</li></ul>
<ul><li>BM25+<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> is an extension of BM25. BM25+ was developed to address one deficiency of the standard BM25 in which the component of term frequency normalization by document length is not properly lower-bounded; as a result of this deficiency, long documents which do match the query term can often be scored unfairly by BM25 as having a similar relevancy to shorter documents that do not contain the query term at all. The scoring formula of BM25+ only has one additional free parameter 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 (a default value is 1.0 in absence of a training data) as compared with BM25:</li></ul>

score
        
        (
        D
        ,
        Q
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          IDF
        
        (
        
          q
          
            i
          
        
        )
        ⋅
        
          [
          
            
              
                
                  f
                  (
                  
                    q
                    
                      i
                    
                  
                  ,
                  D
                  )
                  ⋅
                  (
                  
                    k
                    
                      1
                    
                  
                  +
                  1
                  )
                
                
                  f
                  (
                  
                    q
                    
                      i
                    
                  
                  ,
                  D
                  )
                  +
                  
                    k
                    
                      1
                    
                  
                  ⋅
                  
                    (
                    
                      1
                      −
                      b
                      +
                      b
                      ⋅
                      
                        
                          
                            
                              |
                            
                            D
                            
                              |
                            
                          
                          avgdl
                        
                      
                    
                    )
                  
                
              
            
            +
            δ
          
          ]
        
      
    
    {\displaystyle {\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot \left[{\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}+\delta \right]}

<h2 id="general-references">General references</h2>
<ul><li>Stephen E. Robertson; Steve Walker; Susan Jones; Micheline Hancock-Beaulieu & Mike Gatford (November 1994). <a href="http://trec.nist.gov/pubs/trec3/papers/city.ps.gz">Okapi at TREC-3</a>. <a href="http://trec.nist.gov/pubs/trec3/t3_proceedings.html">Proceedings of the Third Text REtrieval Conference (TREC 1994)</a>. Gaithersburg, USA.</li>
<li>Stephen E. Robertson; Steve Walker & Micheline Hancock-Beaulieu (November 1998). <a href="http://trec.nist.gov/pubs/trec7/papers/okapi_proc.pdf.gz">Okapi at TREC-7</a>. <a href="http://trec.nist.gov/pubs/trec7/t7_proceedings.html">Proceedings of the Seventh Text REtrieval Conference</a>. Gaithersburg, USA.</li>
<li><a href="/facts/Karen_Sp%25C3%25A4rck_Jones/NLFBuKaf">Spärck Jones, K.</a>; Walker, S.; <a href="/facts/Stephen_Robertson_(computer_scientist)/Vhy5FcFE">Robertson, S. E.</a> (2000). "A probabilistic model of information retrieval: Development and comparative experiments: Part 1". Information Processing & Management. 36 (6): 779–808. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.6108">10.1.1.134.6108</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0306-4573%2800%2900015-7">10.1016/S0306-4573(00)00015-7</a>.</li>
<li><a href="/facts/Karen_Sp%25C3%25A4rck_Jones/NLFBuKaf">Spärck Jones, K.</a>; Walker, S.; <a href="/facts/Stephen_Robertson_(computer_scientist)/Vhy5FcFE">Robertson, S. E.</a> (2000). "A probabilistic model of information retrieval: Development and comparative experiments: Part 2". Information Processing & Management. 36 (6): 809–840. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0306-4573%2800%2900016-9">10.1016/S0306-4573(00)00016-9</a>.</li>
<li>Stephen Robertson & Hugo Zaragoza (2009). <a href="http://dl.acm.org/citation.cfm?id=1704810">"The Probabilistic Relevance Framework: BM25 and Beyond"</a>. Foundations and Trends in Information Retrieval. 3 (4): 333–389. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5282">10.1.1.156.5282</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1561%2F1500000019">10.1561/1500000019</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:207178704">207178704</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Stephen_Robertson_(computer_scientist)/Vhy5FcFE">Robertson, Stephen</a>; Zaragoza, Hugo (2009). <a href="http://staff.city.ac.uk/~sb317/papers/foundations_bm25_review.pdf">The Probabilistic Relevance Framework: BM25 and Beyond</a> (PDF). NOW Publishers, Inc. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-60198-308-4.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"OKAPI". smcse.city.ac.uk. Retrieved 2023-10-16.{{cite web}}: CS1 maint: url-status (link) <a href="https://smcse.city.ac.uk/doc/cisr/web/okapi/okapi.html" target="_blank">https://smcse.city.ac.uk/doc/cisr/web/okapi/okapi.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Stephen Robertson & Hugo Zaragoza (2009). "The Probabilistic Relevance Framework: BM25 and Beyond". Foundations and Trends in Information Retrieval. 3 (4): 333–389. CiteSeerX 10.1.1.156.5282. doi:10.1561/1500000019. S2CID 207178704. <a href="http://dl.acm.org/citation.cfm?id=1704810" target="_blank">http://dl.acm.org/citation.cfm?id=1704810</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. An Introduction to Information Retrieval, Cambridge University Press, 2009, p. 233. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"The BM25 Weighting Scheme". <a href="http://xapian.org/docs/bm25.html" target="_blank">http://xapian.org/docs/bm25.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria, and Stephen Robertson. Microsoft Cambridge at TREC-13: Web and HARD tracks. In Proceedings of TREC-2004. <a href="http://trec.nist.gov/pubs/trec13/papers/microsoft-cambridge.web.hard.pdf" target="_blank">http://trec.nist.gov/pubs/trec13/papers/microsoft-cambridge.web.hard.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Stephen Robertson & Hugo Zaragoza (2009). "The Probabilistic Relevance Framework: BM25 and Beyond". Foundations and Trends in Information Retrieval. 3 (4): 333–389. CiteSeerX 10.1.1.156.5282. doi:10.1561/1500000019. S2CID 207178704. <a href="http://dl.acm.org/citation.cfm?id=1704810" target="_blank">http://dl.acm.org/citation.cfm?id=1704810</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Robertson, Stephen; Zaragoza, Hugo; Taylor, Michael (2004-11-13). "Simple BM25 extension to multiple weighted fields". Proceedings of the thirteenth ACM international conference on Information and knowledge management. CIKM '04. New York, NY, USA: Association for Computing Machinery. pp. 42–49. doi:10.1145/1031171.1031181. ISBN 978-1-58113-874-0. S2CID 16628332. <a href="978-1-58113-874-0" target="_blank">978-1-58113-874-0</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Yuanhua Lv and ChengXiang Zhai. Lower-bounding term frequency normalization. In Proceedings of CIKM'2011, pages 7-16. <a href="http://sifaka.cs.uiuc.edu/~ylv2/pub/cikm11-lowerbound.pdf" target="_blank">http://sifaka.cs.uiuc.edu/~ylv2/pub/cikm11-lowerbound.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Okapi BM25 open-in-new

Okapi BM25