"Fossies" - the Fresh Open Source Software Archive

Member "xapian-core-1.4.14/docs/bm25.rst" (23 Nov 2019, 3549 Bytes) of package /linux/www/xapian-core-1.4.14.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format (assuming markdown format). Alternatively you can here view or download the uninterpreted source code file. A member file download can also be achieved by clicking within a package contents listing on the according byte size field.

The BM25 Weighting Scheme

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".

We'll follow the evolution from the "traditional" probabilistic weighting scheme (as described in the 1976 Robertson/Sparck Jones paper) through to BM25.

The Traditional Probabilistic Weighting Scheme

In its most general form, the traditional probabilistic term weighting function is:


$$\frac{(k_3+1)q}{(k_3+q)}\text{ * }\frac{(k_1+1)f}{(k_1L+f)}\text{ * }\log\frac{(r+0.5)(N-n-R+r+0.5)}{(n-r+0.5)(R-r+0.5)}...(1)$$

where

The factors (k3 + 1) and (k1 + 1) are unnecessary here, but help scale the weights, so the first component is 1 when q = 1 etc. But they are critical below when we add an extra item to the sum of term weights.

BM11

Stephen Robertson's BM11 uses formula (1) for the term weights, but adds an extra item to the sum of term weights to give the overall document score:


$$k_2 n_q \frac{(1-L)}{(1+L)} ...(2)$$

where:

Note that this extra item is zero when L = 1.

BM15

BM15 is BM11 with the k1 + f in place of k1L + f in (1).

BM25

BM25 combines the B11 and B15 with a scaling factor, b, which turns BM15 into BM11 as it moves from 0 to 1:


$$\frac{(k_3+1)q}{(k_3+q)}\text{ * }\frac{(k_1+1)f}{(K+f)}\text{ * }\log\frac{(r+0.5)(N-n-R+r+0.5)}{(n-r+0.5)(R-r+0.5)}...(3)$$

where:

K = k1(bL + (1 − b))

BM25 originally introduced another constant, as a power to which f and K are raised. However, Stephen remarks that powers other than 1 were 'not helpful', and other tests confirm this, so Xapian's implementation of BM25 ignores this.

(2) and (3) make up BM25, with which Stephen has had so much recent success.

This does all seem somewhat ad-hoc, with so many unknown constants in the formula. But note that with k2 = 0 and b = 1 we get the traditional formula anyway.

The default parameter values Xapian uses are k1 = 1, k2 = 0, k3 = 1,and b = 0.5. 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.

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 k2nq (constant for a given query) to (2) to give:


$$\frac{2k_2n_q}{(1+L)}...(4)$$