The course article Learning to Rank describes each of BM25's top 100 abstracts for a Cranfield query by eight numbers: four retrieval scores, a title score, coverage, proximity and length. A row of LETOR's MQ2008 benchmark describes a web page for a query by 46. The datasets of the 2010 Yahoo! challenge used 700. Every method in this unit takes such a vector as given and learns to combine its entries. What should the entries be, and what has to be done to them before a model sees them?
A feature is a number computed from the query, from the document, or from both, that might help decide how the document should rank for the query. The methods of this unit differ in their loss functions, and the course article's experiment found that on eight similar features the loss hardly mattered. What a ranker can learn is bounded first by its features.
Here is the route. First we sort features into three kinds and prove that one kind is invisible to a linear ranker. Then we read the LETOR feature lists as a catalogue, and check the MQ2008 files against their documentation. Next we take up normalization within each query: what the benchmark does, what can be proved about its effect, and what an experiment shows. Finally we ask which features a trained model relies on, for tree ensembles, where the question has two standard answers. The article assumes the course article, BM25 and, for the last part, the library's regression trees and boosting.
The numbers are computed by tools/experiments/ltr/features-for-ranking.py in the site's repository, from the MQ2008 files of LETOR 4.0.
Three kinds of feature
Qin, Liu, Xu and Li (2010, §3.3.1) sort the features of LETOR into three classes by what each depends on. Chapelle and Chang (2011, §2) describe the feature vector of the Yahoo! data as having the same three parts.
- Query-document features depend on both. A BM25 score, the number of query terms in the title, the cosine between query and document, the smallest window holding all the query terms: each measures how well this document matches this query. Most of the eight Cranfield features and most of LETOR's are of this kind.
- Document features depend only on the document: its length, its PageRank, the number of slashes in its URL. They say something about the document's quality or type, whatever the query.
- Query features depend only on the query: its number of terms, the sum of its terms' IDF. They are the same for every candidate of a query.
The unit writes $\mathbf{x}_i \in \mathbb{R}^m$ for the feature vector of the pair formed by a query and its candidate $d_i$, $y_i$ for the candidate's label, and $s_i = f(\mathbf{x}_i)$ for its score.
A linear ranker cannot see a query feature
Qin et al. state this in one sentence: "a linear ranking function cannot make use of the class-Q features, since these features are the same for all the documents under a query". Here is the proof, and what it does not cover.
Claim. Let $f(\mathbf{x}) = \mathbf{w}^{\mathsf{T}}\mathbf{x}$, and suppose feature $k$ takes the same value $c_q$ for every candidate of query $q$. Then the order of the candidates of every query is the same for every value of $w_k$.
Proof. For two candidates $d_i$ and $d_j$ of the same query, $s_i - s_j = \sum_{l} w_l (x_{il} - x_{jl})$. The term for $l = k$ is $w_k(c_q - c_q) = 0$. So the difference of the two scores, and with it their order, does not depend on $w_k$. $\blacksquare$
The same computation shows that such a feature has no effect on any loss that depends on the scores only through differences within a query. The pairwise losses of the Ranking SVM and RankNet are of that form, and so are the softmax losses of Listwise Losses, since adding a constant to all scores of a list leaves a softmax unchanged. For those losses the gradient with respect to $w_k$ is exactly zero, and training never moves the weight.
Example (the claim is about linear models). A query feature is not useless in general: it can make the effect of the query-document features depend on the query, reversing the direction in which one of them counts or changing how two or more are traded off. (A model whose score increases with a single query-document feature $v$ in every query ranks each query's candidates in $v$'s order, whatever it does with the query feature, and a linear model with a positive weight on $v$ already does that. A model that need not be monotone in $v$, such as a regression tree, can do more.) First the reversal, with one query-document feature. Let $u$ be a query feature, the number of query terms, and let $v$ be a query-document feature. Query A has $u = 1$, a relevant candidate with $v = 1$ and a nonrelevant one with $v = 0$. Query B has $u = 5$, a relevant candidate with $v = 0$ and a nonrelevant one with $v = 1$. A linear model on $(u, v)$ adds the same $w_u u$ to both candidates of a query, so it orders A correctly only if $w_v > 0$, and B only if $w_v < 0$. A tree with a split on $u$ at its root can let $v$ count upward in one branch and downward in the other, and orders both; so does the score $v - \tfrac{1}{2}\,u\,v$, under which query A's candidates score 0.5 and 0, and query B's score 0 and $-1.5$, the relevant candidate first in each. Then the trade-off, with two query-document features: let $v_1$ and $v_2$ be a title match and a body match. Query A has $u = 1$, a relevant candidate with $(v_1, v_2) = (1, 0)$ and a nonrelevant one with $(0, 1)$. Query B has $u = 5$, a nonrelevant candidate with $(1, 0)$ and a relevant one with $(0, 1)$. A linear model on $(u, v_1, v_2)$ orders A correctly only if $w_{v_1} > w_{v_2}$, and B only if $w_{v_2} > w_{v_1}$, so it gets at least one query wrong, whatever its weight on $u$. A tree that splits on $u$ first can use $v_1$ in one branch and $v_2$ in the other, and orders both. So can a linear model given a product feature: with the score $v_1 + \tfrac{1}{2}\,u\,v_2$, query A's candidates score 1 and 0.5, and query B's score 1 and 2.5. The claim says that a linear model needs its interactions with the query built into the features.
A catalogue: the LETOR features
LETOR is a set of benchmark datasets released by Microsoft Research Asia, each a file of feature vectors with relevance labels and predefined folds, so that learning-to-rank methods could be compared on the same inputs. Its feature lists are the nearest thing the literature has to a standard catalogue of features built from text and links.
LETOR 3.0
Qin et al. (2010, §3.3) state the principles the features were chosen by: to cover as many classical retrieval features as possible, to reproduce features proposed in recent SIGIR papers that used the same corpora, and to keep the settings of the original papers. For the web corpus ".gov" there are 64 features (their Table 2). Each of the first forty is computed five times, once for each of five streams: the body, the anchor text of incoming links, the title, the URL, and the whole document.
| Feature ids | What is computed, for each of the five streams | Class |
|---|---|---|
| 1 to 5 | $\sum_{q_i \in q \cap d} c(q_i, d)$, the total term frequency of the query terms | query-document |
| 6 to 10 | $\sum_{q_i \in q} \mathit{idf}(q_i)$ | query |
| 11 to 15 | $\sum_{q_i \in q \cap d} c(q_i, d) \cdot \mathit{idf}(q_i)$ | query-document |
| 16 to 20 | $\lvert d \rvert$, the length of the stream | document |
| 21 to 25 | BM25 | query-document |
| 26 to 30 | LMIR.ABS, a language model score with absolute discounting | query-document |
| 31 to 35 | LMIR.DIR, with Dirichlet smoothing | query-document |
| 36 to 40 | LMIR.JM, with Jelinek-Mercer smoothing | query-document |
Here $c(q_i, d)$ is the number of occurrences of query term $q_i$ in the stream. The remaining 24 are not per stream:
| Feature ids | What is computed | Class |
|---|---|---|
| 41, 42 | Sitemap-based term and score propagation | query-document |
| 43 to 48 | Hyperlink-based score and feature propagation, six variants | query-document |
| 49, 50 | HITS authority and hub | query-document |
| 51, 52 | PageRank, HostRank | document |
| 53 to 55 | Topical PageRank, topical HITS authority and hub | query-document |
| 56, 57 | Number of inlinks, number of outlinks | document |
| 58 to 60 | Number of slashes in the URL, length of the URL, number of child pages | document |
| 61 to 64 | BM25 and the three language model scores of an extracted title | query-document, as rows 21 to 40 |
The paper gives the formulas and parameters behind several rows. The IDF is the Robertson-Sparck Jones form without the added 1 (its eq. 1),
$$\mathit{idf}(q_i) = \log \frac{\lvert C \rvert - \mathit{df}(q_i) + 0.5}{\mathit{df}(q_i) + 0.5},$$
with $\lvert C \rvert$ the number of documents in the collection and $\mathit{df}(q_i)$ the number whose stream contains the term. The paper writes $\log$ without a base; the worked problems below use the natural logarithm. BM25 is the form of Okapi BM25 with $k_1 = 2.5$, $b = 0.8$ and $k_3 = 0$ for these features, each stream using its own average length. The language model features follow language models for retrieval, with discount 0.7 for LMIR.ABS, $\mu = 2000$ for LMIR.DIR and $\lambda = 0.1$ for LMIR.JM. PageRank is multiplied by $10^5$ and HostRank by $10^3$ because the raw values are very small.
The medical corpus OHSUMED has 45 features (their Table 3), fifteen for each of three streams (title, abstract, and both together). They are ten variants of term frequency and IDF, among them $\sum \log(c(q_i, d) + 1)$ and forms normalized by the stream's length, then BM25, the logarithm of BM25, and the three language model scores. These logarithmic variants serve a point the course text makes (Manning, Raghavan and Schütze, 2008, §15.4.2): machine learning is "very good at producing optimal weights for features in a linear combination" but "not good at coming up with good nonlinear scalings of basic measurements", so the scalings are supplied as separate features. Burges et al. (2005, §6.1) did the same for their 569 features, replacing counts by their logarithms "both to reduce the range, and to allow the net to more easily learn multiplicative relationships".
Three things are worth reading off the catalogue.
- Most features are old ranking functions. Each of BM25 and the language models was a complete ranker in the probabilistic retrieval unit. Here each is one input, computed per stream, and the learner decides how much each stream's score counts. This is the per-field alternative to BM25F, which combines the fields inside one score.
- The raw ingredients are included too. Term frequency, IDF and length appear separately from the scores built from them, so that a model able to combine them nonlinearly can find its own scoring function.
- The authors list what is missing. Qin et al. (2010, §6) write that the list "is far away from comprehensive", that document features are absent from OHSUMED, and that "proximity features are not included in all the seven datasets". The course article's proximity feature, and the term dependence scores, have no counterpart in LETOR 3.0.
What a production feature set adds
Chapelle and Chang (2011, §4.2) could not disclose the 700 features of the Yahoo! datasets, but they describe them by category: web graph (PageRank and its relatives), document statistics, document classifiers (spam, adult content, language, topic, quality), query features, text match ("the largest category"), topical matching, click features, external references and time. Three categories have no counterpart in LETOR: the outputs of other trained classifiers, features computed from users' clicks, and freshness. The authors add that the released features "are the result of a feature selection step in which the most predictive features for ranking are kept". The Striver features of Joachims (2002), described in Ranking SVM, are a third kind of catalogue: for a meta-search engine, the main features of a result are its ranks in other engines.
LETOR 4.0 and the MQ2008 files
LETOR 4.0 (Qin and Liu, 2013) uses a larger web collection, Gov2, and the queries of the TREC Million Query tracks of 2007 and 2008. This unit's experiments use its smaller dataset, MQ2008: 784 queries and 15,211 judged query-document rows, with labels 0, 1 and 2 on 12,279, 2,001 and 931 rows. A query has between 5 and 121 judged documents, with a median of 8, and 403 of the 784 queries have fewer than ten. For 220 queries every label is 0.
The documented list has 46 features: the first forty rows of the LETOR 3.0 table above, then PageRank, inlink number, outlink number, number of slashes in the URL, length of the URL and number of child pages. The paper lists them in the order of the table: columns 21 to 25 are BM25 of body, anchor, title, URL and whole document, columns 26 to 30 LMIR.ABS, and so on.
The released files do not follow that order. The archive holds the raw feature values as well as the normalized ones, and the raw values can be tested against the list.
- A BM25 score of a stream is zero exactly when the stream contains no query term, that is, when the stream's term frequency (columns 1 to 5) is zero. Among columns 21 to 40, exactly five have that property, each for a different stream: columns 21, 25, 29, 33 and 37 are zero on exactly the rows where the term frequency of the body, the anchor, the title, the URL and the whole document is zero.
- The other fifteen columns are negative on more than 90% of rows and never positive, as sums of log probabilities are.
So columns 21 to 40 are grouped by stream, not by scoring function: a BM25 score followed by three language model scores for the body (21 to 24), then the same four for the anchor (25 to 28), the title (29 to 32), the URL (33 to 36) and the whole document (37 to 40). Which of the three smoothing methods is which within each group cannot be told from the values. The last six columns do not match their names either. The column documented as the length of the URL has a maximum of 33,032 and is zero on 15% of rows; the column documented as the number of slashes has non-integer values up to 11,508.3; and the column documented as the number of outlinks is zero on every row. These are observations about the files as archived from Microsoft's site, and the mismatch is with the list in the LETOR 4.0 paper. This article refers to MQ2008 features by column number, and names them only where the data settle the name.
Normalization within a query
What the benchmark does
Each LETOR dataset comes in three versions (Qin et al., 2010, §3.5; Qin and Liu, 2013). In the first, a feature that is absent for a document, such as a language model score for a stream that contains none of the query terms, is marked NULL. In the second, each NULL is replaced by the smallest value of that feature among the documents of the same query. The third, called QueryLevelNorm, is the one the predefined folds contain. The LETOR 3.0 paper motivates it in a clause, "the values of different features or different queries may vary largely", and neither paper gives the formula.
The formula can be recovered from the files. For each query and each feature, subtract the smallest value among the query's documents and divide by the range:
$$x'_{ik} = \frac{x_{ik} - \min_j x_{jk}}{\max_j x_{jk} - \min_j x_{jk}},$$
with the minimum and maximum over the candidates $j$ of the same query, and $x'_{ik} = 0$ when all of them are equal. Applied to the second version of MQ2008, this reproduces the normalized file to within 0.0000005 on every one of its 15,211 × 46 values, which is the precision the file is printed to. This is min-max normalization within a query, the rescaling the course article applied to its Cranfield features.
Here it is on one small query. Query 14527 has five judged documents, the last of them labeled 1. Their raw BM25 scores of the whole document (column 37) and the normalized values are:
| Document | Label | Raw BM25 (column 37) | Normalized |
|---|---|---|---|
| 1 | 0 | 25.06 | 0.967 |
| 2 | 0 | 3.80 | 0.000 |
| 3 | 0 | 22.69 | 0.860 |
| 4 | 0 | 25.78 | 1.000 |
| 5 | 1 | 24.39 | 0.937 |
The lowest score becomes 0 and the highest 1, and the order within the query is unchanged.
Example (a normalized 1.0 is not a strong match). A normalized value of 1 says only that the document has the largest value among this query's candidates. Every query has such a document for every feature, including the 220 queries of MQ2008 with nothing relevant. In the raw file the best BM25 score of a query ranges from 0.0 to 92.1 across queries, with quartiles 26.9, 33.5 and 43.1. After normalization all of those become 1. Normalization within a query deliberately discards how well a query's candidates match in absolute terms.
Why normalize at all
Two different things are at stake, and it helps to separate them.
Scale across features. A raw term frequency runs into the thousands and a raw IDF sum into the tens. Methods that measure distance in feature space, or that take gradient steps, depend on those units. The Ranking SVM article shows the margin changing when one feature is measured in different units, and gradient descent with one learning rate moves fastest along the features with the largest values. Any rescaling that brings the features to comparable ranges addresses this. It need not be done within queries: standardizing each feature over the whole training set does it too.
Level across queries. Raw scores are not comparable between queries. A BM25 score sums over the query's terms, so a query with more terms, or rarer ones, has higher scores for good and bad documents alike. For Cranfield's 225 queries the top BM25 score ranges from 10.5 to 69.4. On MQ2008, 17.2% of the documents labeled 2 have a raw BM25 score below the median score of documents labeled 0 (18.75). A model that reads a raw score on one scale for all queries must treat those documents as weak candidates, although within their own queries they may be the best. After normalization within the query the share is 12.1%. This is the argument specific to ranking, and it is the one the next three results sharpen.
What normalization can change: three results
Here is the idea in one sentence: min-max normalization within a query does two things to a feature, it subtracts a number that depends on the query and it divides by another, and for the models of this unit the subtraction changes nothing while the division changes which functions the model can represent.
Result 1 (shifts within a query do not matter to a linear model trained on differences). Let $f(\mathbf{x}) = \mathbf{w}^{\mathsf{T}}\mathbf{x}$, and replace each feature vector by $\mathbf{x}_i + \mathbf{c}_q$, where the vector $\mathbf{c}_q$ may be different for each query but is the same for all candidates of a query. Then every score difference within a query is unchanged, for every $\mathbf{w}$.
Proof. For candidates $i$ and $j$ of query $q$, $\mathbf{w}^{\mathsf{T}}(\mathbf{x}_i + \mathbf{c}_q) - \mathbf{w}^{\mathsf{T}}(\mathbf{x}_j + \mathbf{c}_q) = \mathbf{w}^{\mathsf{T}}(\mathbf{x}_i - \mathbf{x}_j)$. $\blacksquare$
Consequently every ranking is unchanged, and so is any loss that depends on within-query score differences only, with its gradient: pairwise hinge, RankNet's cost, the softmax losses. Training such a model on shifted features follows the same path, step for step, as training on the original ones. The script confirms it on MQ2008's first fold: adding a random constant to each feature of each query changes the RankNet gradient by less than $10^{-10}$. The proof of the previous section, that a query feature is invisible, is this result applied to one coordinate.
So subtracting the query's minimum is, for these models, no operation at all. A pointwise model is different. A regression or a classifier compares each score with a label on an absolute scale, the shift changes the scores, and the result does not apply.
Result 2 (scaling within a query changes the model). Dividing feature $k$ by a query-dependent range $r_{qk}$ turns the linear score $\sum_k w_k x_{ik}$ into $\sum_k (w_k / r_{qk})\, x_{ik}$: in terms of the raw features, each query gets its own weight vector, tied to the others through the ranges. With one feature this changes no ranking: dividing a single feature by a positive number never changes the order of a query's candidates, so a linear ranker on that feature orders every query alike before and after normalization. With two features or more it does, and in both directions.
Raw can, normalized cannot. Query A has $a_1 = (1, 0)$ and $a_2 = (0, 1)$; query B has $b_1 = (1, 0)$ and $b_2 = (0, 10)$. Suppose $a_1$ should rank above $a_2$, and $b_2$ above $b_1$. On the raw features $\mathbf{w} = (2, 1)$ does both: $a_1$ scores 2 and $a_2$ 1, $b_1$ scores 2 and $b_2$ 10. After min-max within each query both queries become $(1, 0), (0, 1)$, so every linear ranker on the normalized features orders A and B alike and gets one of them wrong.
Normalized can, raw cannot. Query C has $c_1 = (1, 0)$, $c_2 = (0, 1)$, $c_3 = (0, 0)$; query D has $d_1 = (1, 0)$, $d_2 = (0, 1)$, $d_3 = (10, 0)$. Suppose $c_1$ should rank above $c_2$, and $d_2$ above $d_1$. On the raw features both comparisons are decided by the sign of $w_1 - w_2$, so no $\mathbf{w}$ gets both right. After min-max, C is unchanged and D becomes $(0.1, 0), (0, 1), (1, 0)$, and $\mathbf{w} = (2, 1)$ scores $c_1$ at 2 above $c_2$ at 1, and $d_2$ at 1 above $d_1$ at 0.2.
So neither class of linear rankers contains the other, and which ranks better on real data is an empirical question. (Problem 2 below makes a different point, about pointwise models.)
Result 3 (a tree ignores any increasing rescaling of a feature, but not a rescaling within queries). A tree uses a feature only through tests of the form $x_k \le t$. Let $g$ be a strictly increasing function, and replace feature $k$ by $g(x_k)$ on all rows.
Claim. Every partition of the training rows that a split on $x_k$ can produce, a split on $g(x_k)$ can produce too, and conversely. So a tree grown by choosing at each node the best partition is the same tree, with thresholds $g(t)$ in place of $t$, and it gives every training row the same prediction.
Proof. Since $g$ is strictly increasing, $x_k \le t$ holds exactly when $g(x_k) \le g(t)$. So the rows sent left by the test $x_k \le t$ are the rows sent left by the test $g(x_k) \le g(t)$. Conversely, a threshold $t'$ on $g(x_k)$ sends left the rows with $g(x_k) \le t'$, and the same rows are sent left by the test $x_k \le t$ with $t$ the largest value of $x_k$ among them. The candidate partitions at every node are therefore the same, the criterion that chooses among them depends only on the partition and the labels, and by induction on the depth the two trees partition the rows identically. $\blacksquare$
Taking logarithms, standardizing over the training set, and any other increasing transformation applied to the whole column leave a tree, and hence a boosted ensemble of trees, exactly as it was. (Two qualifications. The proof places each threshold at an observed training value; an implementation that places it midway between two observed values can send a new row differently after a nonlinear $g$, since $g$ of a midpoint is not the midpoint of the $g$ values. And an implementation that bins feature values before searching for splits, as this unit's does, can differ slightly because the bins change.) Normalization within a query is not such a transformation. It maps a raw value of 20 to 1.0 in one query and to 0.3 in another, so it is not a function of the raw value at all. The test "normalized BM25 above 0.8" means "near the top of this query's candidates", which no threshold on the raw score expresses. For trees, normalization within the query is a new set of features, and the raw ones are another.
An experiment on MQ2008
MQ2008 provides both versions, so the question can be put to data. Three models were trained on the five predefined folds; the first two were stopped at the best nDCG@10 on the fold's validation part:
- a linear RankNet, trained by the Adam variant of gradient descent (learning rate 0.05, decay rates 0.9 and 0.999, up to 600 steps, validation checked every 10), on the mean pair cost. Adam's step for each weight does not depend on that feature's units, but the step's effect on the scores does (a feature multiplied by $c$ moves the scores $c$ times as far for the same step), so this choice does not remove the scale problem discussed above;
- gradient-boosted regression trees fitted to the labels by squared error, a pointwise method (150 trees at most, depth 3, learning rate 0.1, at least 10 rows in a leaf, each feature cut into at most 64 bins at quantiles of its training values, the number of trees chosen every 5 trees on validation), as derived in the library's boosting;
- a least-squares regression of the label on the features, the simplest pointwise method, with no tuning.
nDCG@10 uses gain $2^y - 1$ and is averaged over the 564 queries that have a relevant document.
| Model | Features | nDCG@10 | MAP |
|---|---|---|---|
| Linear RankNet | min-max within query (as released) | 0.696 | 0.658 |
| Linear RankNet | raw, standardized over the training set | 0.699 | 0.665 |
| Linear RankNet | signed logarithm of raw, standardized | 0.703 | 0.671 |
| Linear RankNet | z-score within query | 0.703 | 0.664 |
| Least squares | min-max within query (as released) | 0.677 | 0.634 |
| Least squares | raw, standardized over the training set | 0.690 | 0.648 |
| Least squares | signed logarithm of raw, standardized | 0.690 | 0.653 |
| Least squares | z-score within query | 0.700 | 0.659 |
| Boosted trees | min-max within query (as released) | 0.702 | 0.664 |
| Boosted trees | raw | 0.706 | 0.668 |
| Boosted trees | both, side by side (92 columns) | 0.706 | 0.669 |
The signed logarithm is $\operatorname{sign}(x)\log(1 + \lvert x \rvert)$, and the z-score subtracts the query's mean and divides by its standard deviation. These runs are deterministic. RankNet trains the first row's model by plain gradient descent in place of Adam and reports 0.703 for it. The two procedures differ only in how the weights are moved and when training is stopped (on validation parts of 105 to 122 usable queries), and that difference alone is as large as the differences between the rows of this table. With half of the rows drawn at random for each tree, 30 seeded runs of the boosted trees on the released version gave a median nDCG@10 of 0.698 (0.696–0.700), ranging from 0.693 to 0.703, so differences of a few thousandths between rows of the table are within the spread of the training procedure itself.
For the pairwise linear model, normalization within the query made no detectable difference. The released min-max version scored 0.696 and the raw features, standardized once over the training set, 0.699. Query by query, min-max was better on 196 queries and worse on 208, and a paired randomization test gives $p = 0.66$. This is what Result 1 leads one to expect: the pairwise cost already ignores each query's level, so the only thing left for normalization to change is the scale within each query, and on this data that did not help. The two variants that scored slightly higher, by amounts within that spread, change the shape of the features (the logarithm) or use a different scale (the standard deviation in place of the range).
For the pointwise model, min-max was the worst choice. The z-score within queries scored highest (0.700), the standardized raw features 0.690, and min-max within queries 0.677, worse than no query-level normalization at all. Paired randomization tests on nDCG@10 over the 564 queries support the three comparisons with min-max and not the comparison of the other two: min-max against the z-score, $p < 0.001$ (z-score better on 231 queries and worse on 165); min-max against the standardized raw features, $p = 0.02$; min-max against the signed logarithm, $p = 0.04$ (signed logarithm better on 224 queries and worse on 202); the z-score against the standardized raw features, $p = 0.12$. These $p$-values are not adjusted for making four comparisons; with a Bonferroni correction at the 5 percent level, which asks each $p$ to be below $0.05/4 = 0.0125$, only the comparison with the z-score would stand. So on this data min-max within queries hurt the regression, clearly against the z-score and less firmly against the other two, and whether the z-score helps it, compared with no query-level normalization, is not settled. A plausible reason for min-max's poor showing is the size of the queries. With a median of 8 documents, a query's minimum and maximum are single documents, and one unusual document sets the scale for all the others; the mean and standard deviation are less at the mercy of one value. The experiment does not test that explanation.
For the trees, the raw features did as well as the normalized ones. The difference, 0.706 against 0.702, is smaller than the spread between seeded runs. Two things a tree on raw features can do that one on the released features cannot may explain it, though the experiment does not separate them: it can use the query features, since the IDF columns are still present (they are zero in the released file), and it can split on document features whose raw values mean the same in every query.
So on MQ2008 the normalization that the benchmark applies was not needed by any of the three models, and for one of them it was harmful. That is a finding about one dataset with very short candidate lists, not about normalization in general. Problem 2 below constructs a case where a pointwise model cannot work without it, and the scale argument for margin and gradient methods stands. What the results do support is narrower advice: rescale features to comparable ranges by some means, treat normalization within the query as a modeling choice to be tested, and prefer a statistic that does not hang on one document when lists are short.
Which features does a model use?
A fitted linear model can be read from its weights, with the caution of the course article: correlated features trade weight freely, so a weight describes the combination and not the feature. A boosted ensemble of hundreds of trees has no weights to read. Two summaries are standard, and the library's random forests article introduces both for classification. This section gives the proof behind the first, adapts the second to ranking, and shows on MQ2008 how both respond to correlated features.
Split gain
A regression tree is grown by repeatedly splitting a node's rows in two so as to reduce the sum of squared errors as much as possible (regression trees). The reduction achieved by a split is its gain. For a node with rows $t$, mean label $\bar y_t$ and squared error $\mathrm{SSE}(t) = \sum_{i \in t} (y_i - \bar y_t)^2$, split into a left part $L$ and a right part $R$,
$$\mathrm{gain} = \mathrm{SSE}(t) - \mathrm{SSE}(L) - \mathrm{SSE}(R).$$
The gain has a closed form. With $n_L$ and $n_R$ rows on the two sides and means $\bar y_L$ and $\bar y_R$,
$$\mathrm{gain} = \frac{n_L\, n_R}{n_L + n_R}\,(\bar y_L - \bar y_R)^2 .$$
Proof. For any set of rows, $\mathrm{SSE} = \sum y_i^2 - n\bar y^2$. The sums of squares of $L$ and $R$ add up to that of $t$, so $\mathrm{gain} = n_L \bar y_L^2 + n_R \bar y_R^2 - n \bar y_t^2$ with $n = n_L + n_R$. Since $n\bar y_t = n_L \bar y_L + n_R \bar y_R$,
$$n\,\mathrm{gain} = (n_L + n_R)(n_L \bar y_L^2 + n_R \bar y_R^2) - (n_L \bar y_L + n_R \bar y_R)^2 = n_L n_R \bar y_L^2 + n_L n_R \bar y_R^2 - 2 n_L n_R \bar y_L \bar y_R = n_L n_R (\bar y_L - \bar y_R)^2. \ \blacksquare$$
A split gains most when it separates two large groups with very different mean labels. The gain is never negative.
The gains of a tree add up to the error it removes. Give each split its gain, and add the gains of all the internal nodes of a tree. Each internal node contributes $\mathrm{SSE}(\text{node}) - \mathrm{SSE}(\text{left child}) - \mathrm{SSE}(\text{right child})$. In the sum, the error of every node other than the root appears once with a minus sign, as a child, and, if it is internal, once with a plus sign, as a parent. Those cancel, leaving
$$\sum_{\text{internal nodes}} \mathrm{gain} = \mathrm{SSE}(\text{root}) - \sum_{\text{leaves}} \mathrm{SSE}(\text{leaf}).$$
The right side is the squared error of predicting the overall mean minus the squared error of the tree's own predictions. So the gains are a complete accounting: they split the error the tree removes among its splits, and nothing is left over.
The split-gain importance of a feature is the sum of the gains of all the splits that use it, over all the trees of an ensemble. By the identity, the importances of one tree sum to the error that tree removes from its targets. As of November 2026, LightGBM, a gradient-boosting library, reports this quantity as the importance of type "gain", which the documentation of its Booster.feature_importance describes as "total gains of splits which use the feature"; its default type, "split", gives the "numbers of times the feature is used in a model" (LightGBM, Python package source, 2026).
By hand. Six documents have a feature $x_1$ with values 1 to 6, a second feature $x_2$ with values 0, 0, 1, 0, 1, 0, and labels 0, 0, 1, 0, 2, 2. The mean label is $5/6$ and the squared error at the root is $9 - 25/6 = 29/6$. The best first split is $x_1 \le 4$: the left side has labels 0, 0, 1, 0 with mean $1/4$, the right side 2, 2 with mean 2, and the gain is $\tfrac{4 \times 2}{6}(2 - \tfrac{1}{4})^2 = 49/12$. On the left side, splitting on $x_2$ isolates the document labeled 1, with gain $\tfrac{3 \times 1}{4}(1 - 0)^2 = 3/4$. Every leaf is now pure, and $49/12 + 3/4 = 58/12 = 29/6$, the whole error at the root, as the identity requires. The importance of $x_1$ is $49/12$, or 0.845 of the total, and that of $x_2$ is $3/4$, or 0.155. Had the tree split on $x_2$ first, that split would have gained $4/3$, not $3/4$: the same feature, credited differently, because gain depends on where in the tree a feature is used.
On MQ2008 the identity can be seen on a real tree. The first tree of the boosted model for fold 1 was fitted to the labels minus their mean, whose squared error over the 9,630 training rows was 2974.4. After the tree it was 2534.1, and the tree's seven split gains sum to 440.3, the difference.
Permutation importance, within queries
Split gain measures how much a feature was used in fitting the training data. It does not say how much the ranking on new queries depends on the feature. Permutation importance does. Breiman (2001, §10) introduced it for random forests: shuffle the values of one variable among the cases not used to grow a tree, run them through the tree, and record how much the error rate rises.
For a ranker the natural version shuffles a feature's values among the test documents and records the fall in nDCG@10. There is a choice that classification does not have: shuffle among all test documents, or only among the documents of each query.
- Shuffling across queries gives a document a value from some other query. For a feature normalized within queries the pool of values is alike in every query, but for a raw feature it replaces a value by one on another query's scale.
- Shuffling within each query keeps each query's own set of values and only breaks the link between value and document. It asks the ranking question directly: does it matter which of this query's candidates has the high value?
A feature the model never splits on has permutation importance exactly zero, by either scheme: no test in any tree reads it, so every prediction, and with it every ranking, is unchanged. The converse fails, as the next section shows.
On MQ2008
Boosted regression trees were fitted on the released (normalized) features, one model of 100 trees per fold (test nDCG@10 0.697). Split-gain importance was normalized to sum to 1 within each model and averaged over the five models. Permutation importance is the fall in mean test nDCG@10, averaged over the five folds, with the median and interquartile range over 30 seeded permutations.
| Column | Split gain | Permutation within queries | Permutation across queries |
|---|---|---|---|
| 39 | 0.260 | 0.022 (0.020–0.025) | 0.022 (0.021–0.026) |
| 23 | 0.116 | 0.009 (0.007–0.011) | 0.009 (0.008–0.010) |
| 37 | 0.060 | 0.014 (0.011–0.016) | 0.015 (0.013–0.018) |
| 40 | 0.051 | 0.008 (0.008–0.010) | 0.008 (0.007–0.010) |
| 29 | 0.049 | 0.007 (0.005–0.008) | 0.007 (0.006–0.008) |
| 25 | 0.041 | 0.009 (0.008–0.011) | 0.008 (0.007–0.012) |
| 20 | 0.033 | 0.004 (0.003–0.006) | 0.004 (0.002–0.006) |
| 21 | 0.032 | 0.004 (0.002–0.006) | 0.004 (0.002–0.005) |
By the grouping established above, columns 37 to 40 are the BM25 score and the three language model scores of the whole document, 21 to 24 the same for the body, 25 and 29 the BM25 scores of the anchor text and the title, and 20 the length of the whole document. The eight columns hold 64% of all split gain. Six columns were never used in any fold: the five IDF columns and column 43, which are zero throughout the normalized file.
The two measures agree on the first feature and not on the order below it. Column 39, a language model score of the whole document, leads by both; alone, it ranks the test queries with nDCG@10 0.689, the best of any single column. Below it the orders differ. Column 23 has twice the split gain of column 37 and less permutation importance. Split gain says how much a feature was used to fit the training labels; permutation says what is lost on held-out queries when the feature is scrambled and the rest are left intact.
Permuting within or across queries made no difference here. The two columns of the table agree within their spreads. A plausible reason, not tested here: the features are normalized within queries, so every query's values lie in the same range, and a value borrowed from another query may be as plausible to the model as one borrowed from the same query. On raw features the two schemes need not agree.
Example (a perfect copy with zero importance). Split gain cannot be read as "how informative is this feature". Add to the 46 columns an exact copy of column 39, the most important one, and refit. The original keeps its split gain of 0.260 and the copy gets 0.000, and the model's nDCG@10 is unchanged at 0.697. The two columns are identical, so every split on one is equally available on the other, and the tree builder breaks the tie by taking the first column it examined. Had the copy come first in the file it would have had all the gain, and an implementation that samples columns at random would divide the gain between them. The same holds for permutation: scrambling the original lowers nDCG@10 by 0.020, and scrambling the copy lowers it by 0.000, because the model never reads the copy. Among the real features, columns 21 and 37, BM25 of the body and of the whole document, have a correlation of 0.983 in the normalized file (0.993 in the raw one), and their importances, 0.032 and 0.060 by gain, may be shares of one piece of evidence divided by which column happened to offer the slightly better split (the copy experiment shows the mechanism for identical columns; for these two it is not tested). This is the tree counterpart of the course article's warning about the weights of correlated features: an importance describes the fitted model's use of a column, not the value of the information in it.
What is proved, what is cited, what the experiments show
Proved on this page. A feature constant within each query cannot affect the ranking of a linear model or any loss built on within-query score differences. Shifting features by query-dependent constants changes neither such a model's rankings nor its training; scaling them by query-dependent factors changes the class of rankers. A tree is unchanged by any strictly increasing transformation of a feature. The gain of a split is $\frac{n_L n_R}{n_L + n_R}(\bar y_L - \bar y_R)^2$, and the gains of a tree sum to the squared error it removes. A feature never used in a split has permutation importance zero.
Cited. The LETOR feature lists, formulas and parameters (Qin et al., 2010; Qin and Liu, 2013), the description of the Yahoo! features (Chapelle and Chang, 2011), the remark on nonlinear scalings (Manning, Raghavan and Schütze, 2008), permutation importance (Breiman, 2001), and LightGBM's definitions of its importance types.
Observed in the files. That LETOR's query-level normalization is min-max within the query; that columns 21 to 40 and 41 to 46 of MQ2008 do not follow the documented order; that six columns of the normalized file are zero throughout.
Shown by the experiments. On MQ2008, the choice between features normalized within queries and raw features changed nDCG@10 by a few thousandths for a linear pairwise model and for boosted trees. A pointwise regression did worst with the released min-max values, by margins that paired tests support against each of the three other versions before correction for multiple comparisons, and after a Bonferroni correction only against the z-score; its gain from z-scores over standardized raw features was not significant. Split-gain and permutation importance agreed on the leading feature and disagreed below it, and an exact copy of the leading feature received no importance at all. These are results for one small dataset and the models described.
Worked problems
The problems are posed on LETOR's formulas and on small exact cases; the unit has no course assignments. The script recomputes each answer.
Problem 1 (LETOR's IDF and BM25 features). A collection has 1,000,000 documents with an average body length of 1,000 words. A one-term query's term occurs in the body of 2,500 documents. Compute LETOR's IDF feature, and the BM25 feature of the body for a document of 500 words containing the term 3 times, with $k_1 = 2.5$, $b = 0.8$ and $k_3 = 0$. What is the largest value the BM25 feature can take for this query? What is the IDF feature for a term in 600,000 documents?
Solution. The IDF is 5.989, the BM25 feature is 13.97, its ceiling is 20.96, and the common term's IDF is $-0.405$. By the paper's eq. 1, $\mathit{idf} = \log\frac{1{,}000{,}000 - 2{,}500 + 0.5}{2{,}500 + 0.5} = \log 398.92 = 5.989$. With $k_3 = 0$ the query-side factor $\frac{(k_3 + 1)\,c(q_i, q)}{k_3 + c(q_i, q)}$ is 1, so the BM25 feature for one term is
$$\mathit{idf} \cdot \frac{c\,(k_1 + 1)}{c + k_1\big(1 - b + b\,\lvert d \rvert / \mathit{avgdl}\big)} = 5.989 \times \frac{3 \times 3.5}{3 + 2.5\,(0.2 + 0.8 \times 0.5)} = 5.989 \times \frac{10.5}{4.5} = 13.97 .$$
The same three occurrences in a document of 2,000 words give $5.989 \times 10.5/7.5 = 8.38$, since length normalization raises the denominator, and 30 occurrences in the 500-word document give $5.989 \times 105/31.5 = 19.96$. As the term frequency grows the fraction approaches $k_1 + 1 = 3.5$, so the ceiling is $5.989 \times 3.5 = 20.96$. For a term in 600,000 documents, $\mathit{idf} = \log\frac{400{,}000.5}{600{,}000.5} = -0.405$: this form of IDF is negative for a term in more than half the documents. Column 6 of MQ2008, documented as this IDF summed over the query's terms, is negative on 0.1% of rows, which this form allows and a form that adds 1 inside the logarithm would not. Okapi BM25 discusses the forms of IDF that avoid this.
Problem 2 (two queries that need different scales). Query A has three candidates with raw scores 12, 9 and 3 on its one useful feature and labels 2, 1, 0. Query B has candidates with raw scores 60, 45 and 30 and labels 2, 1, 0. (a) Normalize the feature by min-max within each query. (b) Does a linear ranker on the raw feature order both queries correctly? (c) A pointwise classifier must separate label 2 from the rest by one threshold on the feature. Is there such a threshold on the raw feature? On the normalized feature?
Solution. (a) Query A: $(12 - 3)/9 = 1$, $(9 - 3)/9 = 0.667$, $0$. Query B: $(60 - 30)/30 = 1$, $(45 - 30)/30 = 0.5$, $0$. (b) Yes. With any positive weight the raw feature orders each query by its labels, since within each query the scores decrease with the labels. A ranking never compares a document of A with one of B. (c) On the raw feature, no: the label-2 document of A scores 12, below both lower-labeled documents of B (45 and 30), so any threshold that admits A's best document admits those too. On the normalized feature any threshold between 0.667 and 1 separates the two label-2 documents, at 1, from the rest. This is the difference between Result 1 and the remark after it. The ranker needed nothing from normalization. The classifier, which compares scores across queries, needed it entirely.
Problem 3 (the z-score variant). Normalize the two queries of Problem 2 by z-score within the query, using the population standard deviation. Do the two normalizations agree on which document of each query is best? Do they give the middle documents the same relative position?
Solution. Query A has mean 8 and standard deviation $\sqrt{(16 + 1 + 25)/3} = 3.742$, giving $1.069$, $0.267$ and $-1.336$. Query B has mean 45 and standard deviation $\sqrt{(225 + 0 + 225)/3} = 12.247$, giving $1.225$, $0$ and $-1.225$. Both normalizations preserve the order within each query, as any increasing rescaling of one query's values must. They differ in what they equalize: min-max gives both best documents exactly 1, while the z-score gives them 1.069 and 1.225. Each is an affine map of a query's values, so each keeps the middle document's relative position: A's middle document sits two thirds of the way up its range under both, and B's exactly halfway.
Problem 4 (a query feature in a linear model). A linear model has weights $(2, -1, 5)$ on three features, the third of which is the number of terms in the query. Query A, with 2 terms, has candidates $(0.9, 0.4)$ and $(0.5, 0.1)$ on the first two features. Compute the scores, then change the third weight to $-100$ and compute them again.
Solution. With weight 5, the scores are $2(0.9) - 0.4 + 5(2) = 11.4$ and $2(0.5) - 0.1 + 10 = 10.9$. With weight $-100$ they are $1.4 - 200 = -198.6$ and $0.9 - 200 = -199.1$. Both times the first candidate leads by 0.5: the third feature adds the same amount, $2w_3$, to both scores, and the difference is $2(0.9 - 0.5) - (0.4 - 0.1) = 0.5$ whatever $w_3$ is. A pairwise loss would report a zero gradient for $w_3$ on this and every query.
What we have learned
A feature is a number computed from the query, the document or both, and a linear ranker can use only those that vary among a query's candidates. LETOR's lists show the standard construction: term frequency, IDF, length, BM25 and three language model scores, each computed per stream, plus link-based document features. Normalization within a query, as LETOR applies it, is min-max over the query's candidates. For a linear model trained on within-query differences its subtraction is no operation and its division changes the model class; for trees it creates features that no threshold on the raw values can express. On MQ2008 the released normalization helped none of the three models tried. The gains of a tree's splits add up exactly to the squared error it removes, which makes split gain a complete but training-bound record of the fitted model's use of each feature, and permutation within queries measures what the ranking depends on.
With features in hand, the unit turns to the losses. Ranking SVM learns a linear combination of features from pairs of documents by maximizing a margin.
References
- Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. record · 2 pages
- Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and Hullender, G. (2005). Learning to rank using gradient descent. In Proceedings of ICML 2005, 89–96. record · 6 pages
- Chapelle, O., and Chang, Y. (2011). Yahoo! Learning to Rank Challenge overview. In Proceedings of the Learning to Rank Challenge, PMLR 14, 1–24. record · 7 pages
- Joachims, T. (2002). Optimizing search engines using clickthrough data. In Proceedings of KDD 2002, 133–142. record · 4 pages
- LightGBM, Python package source (2026). Docstring of
lightgbm.Booster.feature_importance, filepython-package/lightgbm/basic.pyof github.com/microsoft/LightGBM, master branch (read November 2026); the same text is published at lightgbm.readthedocs.io. record - Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 15.4.2. Cambridge University Press. record · 102 pages
- Qin, T., and Liu, T.-Y. (2013). Introducing LETOR 4.0 datasets. arXiv:1306.2597. record · 6 pages
- Qin, T., Liu, T.-Y., Xu, J., and Li, H. (2010). LETOR: A benchmark collection for research on learning to rank for information retrieval. Information Retrieval, 13(4), 346–374. Section, table and equation numbers follow the authors' preprint. record · 2 pages