<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML> <HEAD> <TITLE>Xapian: BM25 Weighting Scheme</TITLE> </HEAD> <BODY BGCOLOR="white" TEXT="black"> <H1>The BM25 Weighting Scheme</H1> <p> This is a technical note about the BM25 weighting scheme, which is the default weighting scheme used by Xapian. Recent TREC tests have shown BM25 to be the best of the known probabilistic weighting schemes. In case you're wondering, the BM simply stands for "Best Match". </p> <p> We'll follow the evolution from the traditional probabilistic weighting scheme through to BM25. </p> <H2>The Traditional Probabilistic Weighting Scheme</H2> <p> In its most general form, the traditional probabilistic term weighting function is: </p> <table border=0><tr valign=center> <td> <tt><center> <u>(k<sub>3</sub>+1)q</u><br>(k<sub>3</sub>+q)</center></tt> </td> <td><tt>·</tt></td> <td> <tt><center> <u>(k<sub>1</sub>+1)f</u><br>(k<sub>1</sub>L+f)</center></tt> </td> <td><tt>·log</tt></td> <td><tt><center> <u>(r+0.5)(N-n-R+r+0.5)</u><br>(n-r+0.5)(R-r+0.5)</center></tt> </td> <td> <tt> ...(1) </tt> </td> </tr></table> <p>where:</p> <p> <tt>k<sub>1</sub>, k<sub>3</sub> are constants.<br> q is the wqf, the within query frequency,<br> f is the wdf, the within document frequency,<br> n is the number of documents in the collection indexed by this term,<br> N is the total number of documents in the collection,<br> r is the number of relevant documents indexed by this term,<br> R is the total number of relevant documents,<br> L is the normalised document length (i.e. the length of this document divided by the average length of documents in the collection). </tt> </p> <p> The factors <tt>(k<sub>3</sub> + 1)</tt> and <tt>(k<sub>1</sub> + 1)</tt> are unnecessary here, but help scale the weights, so the first component is 1 when <tt>q = 1</tt> etc. But they are critical below when we add an extra item to the sum of term weights. </p> <H2>BM11</H2> <p> Stephen Robertson's BM11 uses formula <tt>(1)</tt> for the term weights, but adds an extra item to the sum of term weights to give the overall document score: </p> <table border=0><tr valign=center> <td><tt>k<sub>2</sub> n<sub>q</sub></tt></td> <td> <tt><center> <u>(1-L)</u><br>(1+L)</center></tt> </td> <td> <tt> ...(2) </tt> </td> </tr></table> <p>where:</p> <p> <tt>n<sub>q</sub> is the number of terms in the query (the query length),<br> k<sub>2</sub> is yet another constant. </tt> </p> <p> Note that this extra item is zero when <tt>L = 1</tt>. </p> <H2>BM15</H2> <p>BM15 is BM11 with the <tt>k<sub>1</sub>+f</tt> in place of <tt>k<sub>1</sub>L+f</tt> in <tt>(1)</tt>.</p> <H2>BM25</H2> <p>BM25 combines the B11 and B15 with a scaling factor, b, which turns BM15 into BM11 as it moves from 0 to 1: </p> <table border=0><tr valign=center> <td> <tt><center> <u>(k<sub>3</sub>+1)q</u><br>(k<sub>3</sub>+q)</center></tt> </td> <td><tt>·</tt></td> <td> <tt><center> <u>(k<sub>1</sub>+1)f</u><br>(K+f)</center></tt> </td> <td><tt>·log</tt></td> <td><tt><center> <u>(r+0.5)(N-n-R+r+0.5)</u><br>(n-r+0.5)(R-r+0.5)</center></tt> </td> <td> <tt> ...(3) </tt> </td> </tr></table> <p>where:</p> <p> <tt>K = k<sub>1</sub>(bL + (1-b))</tt> </p> <p> BM25 originally introduced another constant, as a power to which f and K are raised. However, Stephen remarks that powers other than 1 were <i>'not helpful'</i>, and other tests confirm this, so Xapian's implementation of BM25 ignores this. </p> <p> <tt>(2)</tt> and <tt>(3)</tt> make up BM25, with which Stephen has had so much recent success. </p> <p> This does all seem somewhat ad-hoc, with so many unknown constants in the formula. But note that with <tt>k<sub>2</sub> = 0</tt> and <tt>b = 1</tt> we get the traditional formula anyway. </p> <p> The default parameter values Xapian uses are <tt>k<sub>1</sub> = 1</tt>, <tt>k<sub>2</sub> = 0</tt>, <tt>k<sub>3</sub> = 1</tt>, and <tt>b = 0.5</tt>. These are reasonable defaults, but the optimum values will vary with both the documents being searched and the type of queries, so you may be able to improve the effectiveness of your search system by tuning the values of these parameters. </p> <p> In Xapian, we also apply a floor to L (0.5 by default) which helps stop tiny documents get ridiculously high weights. And the matcher wants the extra item in the sum to be positive, so we add <tt>k<sub>2</sub>n<sub>q</sub></tt> (constant for a given query) to (2) to give: </p> <table border=0><tr valign=center> <td> <tt><center> <u>2 k<sub>2</sub> n<sub>q</sub></u><br>(1 + L)</center></tt> </td> <td> <tt> ...(4) </tt> </td> </tr></table> <!-- FOOTER $Author: olly $ $Date: 2007-12-04 14:43:10 +0000 (Tue, 04 Dec 2007) $ $Id: bm25.html 9806 2007-12-04 14:43:10Z olly $ --> </BODY> </HTML>
