Ranking SVM

Learning a linear ranking function from statements that one document should rank above another. Ordinal regression as Herbrich, Graepel and Obermayer posed it, Joachims's optimization problem with one slack per pair, a proof that it is a support vector machine on difference vectors with no intercept, the margin and the support pairs solved exactly on three and four documents, the slack as a bound on misordered pairs and on Kendall's tau, preferences extracted from clicks, and experiments on Cranfield and LETOR's MQ2008. Worked problems on the one-pair solution, support pairs, clicks turned into constraints and the slack of a misordered pair.

For Cranfield query 185, experimental studies on panel flutter, BM25 ranks abstract 856 first and abstract 766 third. The judges graded 766 the better answer of the two. That judgment says nothing about what score either abstract deserves. It says only that 766 should stand above 856. A click in a search log says the same kind of thing, more weakly: the user preferred this result to the ones skipped on the way to it. How can a scoring function be learned from statements of the form "this should rank above that"?

The Ranking SVM answers by treating each such statement as a constraint on a linear scoring function and solving for the function that satisfies the constraints with the widest margin. Herbrich, Graepel and Obermayer (2000) derived the method for ordinal regression, the prediction of ordered grades. Joachims (2002) restated it for retrieval, where documents are compared only within a query, named it, and trained it on preferences extracted from clicks. The course article Learning to Rank states the optimization problem in one paragraph. This article is the full account behind that paragraph.

Here is the route. First we see why ordered grades call for pairs, and write the optimization problem. Then we prove that the problem is a support vector machine on difference vectors without an intercept, and solve it exactly for one pair, for three documents and for four. Next we show what the slack measures: it bounds the number of misordered pairs, and through that Kendall's tau. Then we follow Joachims from clicks to constraints. Finally we train the method on Cranfield and on LETOR's MQ2008 and compare it with RankNet. The article assumes the library's Support Vector Machines, which derives the margin $2/\lVert \mathbf{w} \rVert$, the soft margin and the hinge loss.

The numbers are computed by tools/experiments/ltr/ranking-svm.py in the site's repository. Its small cases are exact fractions. Its experiments are seeded.

Grades are ordered, and that is all

A judge who grades documents 2, 1 and 0 has ranked them. The judge has not said that the step from 0 to 1 is as large as the step from 1 to 2, or that a grade 2 for one query means what a grade 2 means for another. Two familiar formulations each get one of these facts wrong.

  • Classification treats the grades as unrelated classes. Predicting grade 0 for a grade 2 document then costs the same as predicting grade 1. Herbrich et al. (2000, §2.3) make this their argument against the classification loss: its risk does not depend on how far a wrong prediction is from the right grade.
  • Regression treats the grades as numbers and penalizes the squared distance from them. That invents distances between grades that the judge never stated.

Their proposal keeps only what the grades assert. A function $g$ from documents to grades induces an order on the documents, and the loss counts the pairs that $g$ puts in the wrong order: a pair of objects with different grades costs 1 if $g$ does not order them as their grades do, and 0 otherwise (their eq. 2.11). The risk is the expected number of such inversions. Their Theorem 2.1 states that this risk equals, up to a constant factor that does not depend on $g$, the ordinary classification risk of a derived classifier that takes a pair of objects and predicts which of the two has the higher grade. In their words, the problem "can be reduced to a classification problem on pairs of objects". The theorem is cited here, not proved. What this article proves is the concrete form the reduction takes for a linear scoring function, in the next two sections.

To get from a pair classifier back to a ranking, they model the grades as consecutive intervals of the real line and score each object by a linear function, their eq. 2.21, so that an object's grade is the interval its score falls in. Scoring a pair then needs only the difference of two scores.

Joachims (2002, §6) names the one thing that differs in retrieval. In ordinal regression "all objects interact and they are ranked on the same scale". In retrieval, "rankings need to be consistent only within a query, but not between queries". Two documents with the same feature vector may deserve rank 1 for one query and rank 50 for another. So pairs are formed only between documents retrieved for the same query. That is the unit's set $I$ of pairs, defined next.

The optimization problem

Fix the notation of this unit. A query $q$ has candidates $d_1, \dots, d_n$. The pair $(q, d_i)$ is described by a feature vector $\mathbf{x}_i \in \mathbb{R}^m$, which the course text writes $\psi(d_i, q)$ (Manning, Raghavan and Schütze, 2008, §15.4.2); Features for Ranking says what goes into it. The label $y_i$ is the grade, with larger meaning better. The model is linear, with score $s_i = \mathbf{w}^{\mathsf{T}}\mathbf{x}_i$. The set $I$ holds the ordered pairs $(i, j)$ of candidates of the same query with $y_i > y_j$, the more relevant document first. With several training queries the pairs of all of them are pooled, and a pair never joins documents of different queries.

A weight vector $\mathbf{w}$ ranks a pair correctly when $s_i > s_j$. Joachims (2002, §4.1) first asks for the $\mathbf{w}$ that ranks the largest number of pairs correctly, and notes that finding it is NP-hard. He then relaxes the count exactly as the soft-margin SVM relaxes the count of training errors. His Optimization Problem 1 (eqs. 12 to 14) is, in the unit's notation,

$$\min_{\mathbf{w},\, \xi}\ \tfrac{1}{2}\,\mathbf{w}^{\mathsf{T}}\mathbf{w} + C \sum_{(i,j) \in I} \xi_{ij} \qquad \text{subject to} \qquad \mathbf{w}^{\mathsf{T}}\mathbf{x}_i \ge \mathbf{w}^{\mathsf{T}}\mathbf{x}_j + 1 - \xi_{ij}, \quad \xi_{ij} \ge 0, \quad \text{for every } (i,j) \in I.$$

Each constraint asks the better document to outscore the other by at least 1. The slack $\xi_{ij}$ is the amount by which a pair falls short. The constant $C > 0$ is the price of a unit of slack, and $\tfrac{1}{2}\mathbf{w}^{\mathsf{T}}\mathbf{w}$ is the term that widens the margin. The course article explains each symbol and gives the textbook's version of the same problem. In this article $C$ always means this constant. (In RankNet, and in the rest of the unit, $C$ is a cost function instead.)

The reduction to classification on difference vectors

Here is the idea in one sentence: the constraint on a pair involves the two documents only through the difference of their feature vectors, so each pair can be replaced by one point, and the problem becomes a classifier's.

The formal version. Write the difference vector of a pair as

$$\Phi_{ij} = \mathbf{x}_i - \mathbf{x}_j .$$

Because the score is linear, $\mathbf{w}^{\mathsf{T}}\mathbf{x}_i - \mathbf{w}^{\mathsf{T}}\mathbf{x}_j = \mathbf{w}^{\mathsf{T}}\Phi_{ij}$. The constraint of a pair becomes

$$\mathbf{w}^{\mathsf{T}}\Phi_{ij} \ge 1 - \xi_{ij},$$

which is Joachims's eq. 15. Now compare with the soft-margin problem of Support Vector Machines: minimize $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2 + C \sum_p \xi_p$ subject to $y_p(\mathbf{w}^{\mathsf{T}}\mathbf{z}_p + b) \ge 1 - \xi_p$ and $\xi_p \ge 0$, for training points $\mathbf{z}_p$ with labels $y_p = \pm 1$. Take one training point for each pair, $\mathbf{z}_p = \Phi_{ij}$, give every point the label $+1$, and fix $b = 0$. The two problems are then the same problem, symbol for symbol. So the Ranking SVM is a support vector classifier, with three peculiarities, each of which is a short result.

1. Every label is $+1$. That looks like a classification problem with one class, which any $\mathbf{w}$ pointing roughly toward the points would solve. It is not degenerate, because there is no intercept: the boundary $\mathbf{w}^{\mathsf{T}}\mathbf{z} = 0$ must pass through the origin, and the constraints ask every difference vector to lie at least $1/\lVert \mathbf{w} \rVert$ on its positive side.

2. Mirroring the pairs changes nothing. One can also write every pair twice, as $\Phi_{ij}$ with label $+1$ and as $\Phi_{ji} = -\Phi_{ij}$ with label $-1$, which makes the two classes equal in size. The constraint of the mirrored point is $-1 \cdot \mathbf{w}^{\mathsf{T}}(-\Phi_{ij}) \ge 1 - \xi'_{ij}$, that is, $\mathbf{w}^{\mathsf{T}}\Phi_{ij} \ge 1 - \xi'_{ij}$: the same constraint again. At the optimum each slack is as small as its constraint allows, so $\xi'_{ij} = \xi_{ij}$, and the mirrored problem's objective is $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2 + 2C\sum \xi_{ij}$. Mirroring is therefore the original problem with $C$ doubled. The script uses this to hand the problem to a standard solver, with $C/2$.

3. An intercept could not help. Suppose the mirrored problem were given an intercept $b$ after all. A pair and its mirror image then contribute the slacks $\max(0,\, 1 - (\mathbf{w}^{\mathsf{T}}\Phi_{ij} + b))$ and $\max(0,\, 1 - (\mathbf{w}^{\mathsf{T}}\Phi_{ij} - b))$. Write $h(u) = \max(0, 1 - u)$, a convex function, and $u = \mathbf{w}^{\mathsf{T}}\Phi_{ij}$. Convexity gives $\tfrac{1}{2}h(u + b) + \tfrac{1}{2}h(u - b) \ge h\big(\tfrac{1}{2}(u + b) + \tfrac{1}{2}(u - b)\big) = h(u)$. So for every $\mathbf{w}$, each pair's two slacks add up to at least $2h(u)$, which is their sum at $b = 0$. The objective at $(\mathbf{w}, b)$ is never below the objective at $(\mathbf{w}, 0)$, and an optimal solution with $b = 0$ always exists. The reason behind the algebra is the one the course article gives: an intercept added to both scores of a pair cancels in their difference. The script checks the inequality on 2,000 random choices of $\mathbf{w}$ and $b$.

The same cancellation removes more than the intercept. Any feature that takes one value for all the candidates of a query, such as the query's length, contributes zero to every $\Phi_{ij}$, and its weight has no effect on any constraint. Features for Ranking proves the general statement and shows it on LETOR's data.

The margin

In a classifier, the margin is the distance from the boundary to the nearest training point. Here is what it is in a ranking. A linear score orders documents by their projection onto the direction of $\mathbf{w}$: the projection of $\mathbf{x}_i$ is $\mathbf{w}^{\mathsf{T}}\mathbf{x}_i / \lVert \mathbf{w} \rVert$. A pair that satisfies its constraint without slack has $\mathbf{w}^{\mathsf{T}}\mathbf{x}_i - \mathbf{w}^{\mathsf{T}}\mathbf{x}_j \ge 1$, so its two projections are at least $1/\lVert \mathbf{w} \rVert$ apart. Minimizing $\lVert \mathbf{w} \rVert$ makes that guaranteed gap as large as possible. Joachims (2002, §4.1) describes the margin in these terms: geometrically, it "is the distance between the closest two projections within all target rankings". The Ranking SVM chooses, among the directions that order the training pairs, the one along which the closest preferred pair is farthest apart.

One pair, solved

With a single pair and no slack the problem is to minimize $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2$ subject to $\mathbf{w}^{\mathsf{T}}\Phi \ge 1$. The solution is

$$\mathbf{w} = \frac{\Phi}{\lVert \Phi \rVert^2}.$$

Here is the proof. This $\mathbf{w}$ satisfies the constraint with equality, since $\Phi^{\mathsf{T}}\Phi / \lVert \Phi \rVert^2 = 1$. For any other $\mathbf{w}'$ with $\mathbf{w}'^{\mathsf{T}}\Phi \ge 1$, the Cauchy-Schwarz inequality gives $1 \le \mathbf{w}'^{\mathsf{T}}\Phi \le \lVert \mathbf{w}' \rVert\, \lVert \Phi \rVert$, so $\lVert \mathbf{w}' \rVert \ge 1/\lVert \Phi \rVert = \lVert \mathbf{w} \rVert$, with equality only when $\mathbf{w}'$ is a positive multiple of $\Phi$ and the constraint is tight, that is, only for $\mathbf{w}$ itself.

The course article's example has one usable pair, the device driver documents 2094 (relevant) and 3191 (nonrelevant), with cosine scores 0.030 and 0.027 and window widths 2 and 5. Its difference vector is $\Phi = (0.003, -3)$, with $\lVert \Phi \rVert^2 = 0.000009 + 9 = 9.000009$, so

$$\mathbf{w} = (0.000333,\ -0.333333).$$

The window width receives a thousand times the weight of the cosine. The course article's hand-set line, $100\,\alpha - \omega$, weighs the cosine a hundred times more than the window. Its score difference on this pair is 3.3, so it satisfies the constraint too, but with a far longer weight vector.

Example (the margin depends on the units). It is tempting to read the SVM's answer as a finding that the window width matters more. It is a statement about units. Measure the cosine in hundredths, so that the feature is $100\,\alpha$, and the difference vector becomes $(0.3, -3)$ with $\lVert \Phi \rVert^2 = 9.09$. The solution is then $(0.0330, -0.3300)$. Relative to the window's weight, the cosine's weight has grown a hundredfold in the new units, from 0.001 to 0.1 in magnitude. Converted back to the original cosine, the learned score is $3.30\,\alpha - 0.330\,\omega$, so in the original units the ratio went from 0.001 to 10, ten thousand times larger: one feature's units changed the direction of the solution. The margin is a Euclidean distance in feature space, so rescaling a feature changes which direction is "widest". This is one reason to bring features to comparable scales before training a Ranking SVM, as Support Vector Machines shows for classification and Features for Ranking for ranking.

Three documents, solved

Now take one query with three candidates and two features, on three grades:

Document $\mathbf{x}$ Grade $y$
$a$ $(4, 1)$ 2
$b$ $(2, 2)$ 1
$c$ $(1, 0)$ 0

The set $I$ has three pairs, with difference vectors $\Phi_{ab} = (2, -1)$, $\Phi_{bc} = (1, 2)$ and $\Phi_{ac} = (3, 1)$. The second feature alone puts $b$ above $a$; the first alone orders all three, but, as the solution shows, the widest margin uses both.

Only the adjacent pairs can bind. Since $\Phi_{ac} = \Phi_{ab} + \Phi_{bc}$, any $\mathbf{w}$ that satisfies the constraints of $(a, b)$ and $(b, c)$ without slack has $\mathbf{w}^{\mathsf{T}}\Phi_{ac} \ge 1 + 1 = 2$. The constraint of $(a, c)$ is implied, with room to spare, and can be dropped. The same argument applies to any chain of grades in the hard-margin problem (no slack, so every constraint holds): a pair two or more grades apart, with a document of each grade between, is never a constraint that holds with equality. With slack the argument fails: two adjacent pairs that each fall short by 0.5 leave the outer pair exactly on its margin.

So the problem is to minimize $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2$ subject to $2w_1 - w_2 \ge 1$ and $w_1 + 2w_2 \ge 1$. Suppose both hold with equality. Solving $2w_1 - w_2 = 1$ and $w_1 + 2w_2 = 1$ gives

$$\mathbf{w} = \big(\tfrac{3}{5},\ \tfrac{1}{5}\big), \qquad \text{scores } s_a = \tfrac{13}{5},\ s_b = \tfrac{8}{5},\ s_c = \tfrac{3}{5}.$$

The three scores are evenly spaced, one unit apart. That this is the minimum, and not merely a feasible point, follows from the multipliers. The library's SVM article derives that at the solution $\mathbf{w}$ is a combination of the training points with nonnegative coefficients, which are zero for constraints that are not tight; the next section proves the part of that needed here. Writing $\mathbf{w} = \alpha_{ab}\Phi_{ab} + \alpha_{bc}\Phi_{bc}$ gives $2\alpha_{ab} + \alpha_{bc} = \tfrac{3}{5}$ and $-\alpha_{ab} + 2\alpha_{bc} = \tfrac{1}{5}$, so $\alpha_{ab} = \alpha_{bc} = \tfrac{1}{5}$. Both are positive. The dual objective is $\alpha_{ab} + \alpha_{bc} - \tfrac{1}{2}\lVert \mathbf{w} \rVert^2 = \tfrac{2}{5} - \tfrac{1}{5} = \tfrac{1}{5}$, equal to the primal objective $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2 = \tfrac{1}{2} \cdot \tfrac{2}{5} = \tfrac{1}{5}$, and equal values certify the optimum, as the next section shows.

The pairs $(a, b)$ and $(b, c)$ are the support pairs: the pairs whose constraints hold with equality and that alone determine $\mathbf{w}$. The pair $(a, c)$ could be deleted without changing anything. The length of $\mathbf{w}$ is $\sqrt{2/5} = 0.632$, so the projections of consecutive documents are $1/\lVert \mathbf{w} \rVert = 1.581$ apart, and no other direction separates both adjacent pairs by more.

When no weight vector orders every pair

Real judgments are never perfectly orderable by a linear function of the features, and the slack variables are there for that. The question of this section is what the slack buys and what it measures.

Add a fourth candidate to the query, a document that looks good on both features and was judged nonrelevant:

Document $\mathbf{x}$ Grade $y$
$d$ $(3, 3)$ 0

Documents $c$ and $d$ share a grade, so they form no pair. The set $I$ now has five pairs:

Pair $(a, b)$ $(a, c)$ $(a, d)$ $(b, c)$ $(b, d)$
$\Phi$ $(2, -1)$ $(3, 1)$ $(1, -2)$ $(1, 2)$ $(-1, -1)$

No $\mathbf{w}$ orders all five. The proof is one identity:

$$3\,\Phi_{bc} + \Phi_{ab} + 5\,\Phi_{bd} = (3 + 2 - 5,\ 6 - 1 - 5) = (0, 0).$$

If some $\mathbf{w}$ had $\mathbf{w}^{\mathsf{T}}\Phi > 0$ for all three of these pairs, then $3\,\mathbf{w}^{\mathsf{T}}\Phi_{bc} + \mathbf{w}^{\mathsf{T}}\Phi_{ab} + 5\,\mathbf{w}^{\mathsf{T}}\Phi_{bd}$ would be positive. It is $\mathbf{w}^{\mathsf{T}}(0, 0) = 0$. In words: to put $b$ above $d$ the weights must favor small features, and to put $a$ above $b$ and $b$ above $c$ they must not. A positive combination of difference vectors that sums to zero is always such a certificate.

The solutions

With slack the problem has a solution for every $C$. Solved to nine decimals by the script:

$C$ $\mathbf{w}$ Slacks of $(a,b)$, $(a,c)$, $(a,d)$, $(b,c)$, $(b,d)$ Sum of slacks Objective Order by score
0.1 $(0.3900, -0.1700)$ 0.05, 0, 0.27, 0.95, 1.22 2.4900 0.3395 $a, d, b, c$
1 $(0.6000, -0.2000)$ 0, 0, 0, 0.8, 1.4 2.2000 2.4000 $a, d, b, c$
10 $(1.0000, 0.0000)$ 0, 0, 0, 0, 2 2.0000 20.5000 $a, d, b, c$

At every $C$ exactly one pair is misordered, $(b, d)$: the nonrelevant $d$ scores above $b$. What changes with $C$ is how the slack is spread. At $C = 10$ slack is expensive, and all of it sits on the one pair that cannot be fixed, at the cost of a longer $\mathbf{w}$. At $C = 0.1$ a short $\mathbf{w}$ is preferred, and four of the five pairs fall inside the margin. For $C = 1$ the multipliers are $\alpha = (0, 0, 0.6, 1, 1)$. They sort the pairs as the SVM article describes: $(a, b)$ and $(a, c)$ are satisfied with room to spare and have $\alpha = 0$; $(a, d)$ sits exactly on the margin with $0 < \alpha < C$; $(b, c)$ and $(b, d)$ are inside the margin or misordered and have $\alpha = C$.

Why equal objectives certify the solution

The table's solutions were found by a numerical method (coordinate ascent on the dual). How do we know they are the minimum? Here is the idea in one sentence: every choice of multipliers between 0 and $C$ gives a number that no feasible $(\mathbf{w}, \xi)$ can go below, so a feasible point that attains such a number is optimal.

The formal version. Index the pairs by $p$, and let $\alpha_p$ be any numbers with $0 \le \alpha_p \le C$. Define the dual objective

$$D(\alpha) = \sum_p \alpha_p - \tfrac{1}{2}\Big\lVert \sum_p \alpha_p \Phi_p \Big\rVert^2 .$$

Let $(\mathbf{w}, \xi)$ be feasible: $\mathbf{w}^{\mathsf{T}}\Phi_p - 1 + \xi_p \ge 0$ and $\xi_p \ge 0$ for every $p$. The primal objective is $P = \tfrac{1}{2}\lVert \mathbf{w} \rVert^2 + C\sum_p \xi_p$. Subtract two sums of nonnegative terms from it:

$$P \ \ge\ \tfrac{1}{2}\lVert \mathbf{w} \rVert^2 + C\sum_p \xi_p - \sum_p \alpha_p\big(\mathbf{w}^{\mathsf{T}}\Phi_p - 1 + \xi_p\big) - \sum_p (C - \alpha_p)\,\xi_p .$$

The terms in $\xi_p$ cancel: $C\xi_p - \alpha_p\xi_p - (C - \alpha_p)\xi_p = 0$. Writing $\mathbf{v} = \sum_p \alpha_p \Phi_p$, what remains is $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2 - \mathbf{w}^{\mathsf{T}}\mathbf{v} + \sum_p \alpha_p$. Completing the square, $\tfrac{1}{2}\lVert \mathbf{w} \rVert^2 - \mathbf{w}^{\mathsf{T}}\mathbf{v} = \tfrac{1}{2}\lVert \mathbf{w} - \mathbf{v} \rVert^2 - \tfrac{1}{2}\lVert \mathbf{v} \rVert^2 \ge -\tfrac{1}{2}\lVert \mathbf{v} \rVert^2$. So

$$P \ \ge\ \sum_p \alpha_p - \tfrac{1}{2}\lVert \mathbf{v} \rVert^2 = D(\alpha).$$

Every primal value is at least every dual value. If a feasible $(\mathbf{w}, \xi)$ and an $\alpha$ give $P = D(\alpha)$, then no feasible point has a smaller $P$, so $(\mathbf{w}, \xi)$ is optimal. Equality also needs each step to be tight: $\mathbf{w} = \mathbf{v} = \sum_p \alpha_p \Phi_p$, so $\mathbf{w}$ is a nonnegative combination of difference vectors; $\alpha_p = 0$ for every pair whose constraint is not tight; and $\alpha_p = C$ for every pair with positive slack. Those are the three groups seen at $C = 1$. In the table the primal and dual objectives agree to nine decimals at each $C$.

Two remarks complete the argument. First, the hard-margin problem (no slack variables, as in the three-document case and Problem 2 below) is covered by the same proof with any $\alpha_p \ge 0$ and no upper bound: the terms in $\xi_p$ are simply absent. In the three-document case the primal and dual values both equal $\tfrac{1}{5}$ exactly, which certifies that solution. Second, the proof shows that a certifying $\alpha$ works, not that one always exists. That an optimal solution always has such multipliers, so that the optimal $\mathbf{w}$ is always a nonnegative combination $\sum_p \alpha_p \Phi_p$, is the duality theory of the support vector machine, which the library's Support Vector Machines states with its sources (the dual problem and the Karush-Kuhn-Tucker conditions) for the classifier with an intercept, and which is not proved here. What carries over to the Ranking SVM, which has no intercept: in that article the form of $\mathbf{w}$ as a combination of the training vectors comes from setting the derivative of the Lagrangian with respect to $\mathbf{w}$ to zero, and here that derivative gives $\mathbf{w} = \sum_p \alpha_p \Phi_p$ in the same way; the dual's equality constraint $\sum_i \alpha_i y_i = 0$ comes from the derivative with respect to the intercept, so without an intercept it is simply absent, which is the dual used on this page.

What the slack measures

Substituting the smallest feasible slack, $\xi_{ij} = \max(0,\ 1 - \mathbf{w}^{\mathsf{T}}\Phi_{ij})$, turns the problem into the unconstrained minimization of a hinge loss on pairs plus a penalty, as for any SVM:

$$\min_{\mathbf{w}}\ \sum_{(i,j) \in I} \max\big(0,\ 1 - (s_i - s_j)\big) + \frac{1}{2C}\lVert \mathbf{w} \rVert^2 .$$

The total slack bounds the number of misordered pairs. A pair is misordered, or tied, when $s_i - s_j \le 0$, and then its slack is $1 - (s_i - s_j) \ge 1$. Every other pair has slack at least 0. So

$$\sum_{(i,j) \in I} \xi_{ij} \ \ge\ \#\{(i,j) \in I : s_i \le s_j\}.$$

In the table the bound reads $2.49 \ge 1$, $2.2 \ge 1$ and $2 \ge 1$. This is the sense in which the Ranking SVM minimizes ranking errors: it minimizes an upper bound on their number, and the bound is loose by the slack of pairs that are ordered correctly but inside the margin.

Misordered pairs are Kendall's tau. Joachims (2002, §3) measures the agreement of two strict orderings of $m$ documents by Kendall's tau. With $P$ the number of pairs they order alike (concordant) and $Q$ the number they order differently (discordant, or inversions), his eq. 2 is

$$\tau = \frac{P - Q}{P + Q} = 1 - \frac{2Q}{\binom{m}{2}} .$$

His example orders five documents as $d_1, d_2, d_3, d_4, d_5$ and as $d_3, d_2, d_1, d_4, d_5$. The discordant pairs are $\{d_2, d_3\}$, $\{d_1, d_2\}$ and $\{d_1, d_3\}$, so $Q = 3$, $P = 7$ and $\tau = 1 - 6/10 = 0.4$. For a fixed number of documents, maximizing $\tau$ is minimizing $Q$, the count the slack bounds.

Joachims also connects $Q$ to a measure used in retrieval. With binary relevance, $R$ relevant documents, and $Q$ the number of pairs in which a nonrelevant document stands above a relevant one, his Theorem 1 states

$$\mathrm{AvgPrec} \ \ge\ \frac{1}{R}\,\Big[Q + \binom{R + 1}{2}\Big]^{-1} \Big(\sum_{i=1}^{R} \sqrt{i}\Big)^{2}.$$

The proof is in his appendix and is not repeated here. The script checks the inequality on every ranking of 1 to 12 documents with at least one relevant, 8,178 rankings, and it holds on all of them. For relevant documents at ranks 2, 4 and 5 of six, $Q = 1 + 2 + 2 = 5$, the average precision is $\tfrac{1}{3}\big(\tfrac{1}{2} + \tfrac{2}{4} + \tfrac{3}{5}\big) = 0.533$, and the bound is $\tfrac{1}{3} \cdot 17.19 / (5 + 6) = 0.521$. Fewer inversions force a higher floor under average precision. The chain is: slack bounds inversions, and inversions bound average precision from below. Neither link says that minimizing slack maximizes average precision or nDCG, and LambdaRank and LambdaMART starts from that gap.

Hinge against logistic. RankNet replaces the hinge $\max(0, 1 - u)$ by the logistic cost $\log(1 + e^{-u})$ of the same score difference $u = s_i - s_j$. The hinge is exactly zero once a pair clears the margin, so the pairs that clear it drop out of the solution, which is what produces support pairs. The logistic cost is never zero, so every pair keeps pulling. Both grow linearly for a badly misordered pair. The experiment below measures how different the resulting weights are.

Kernels, and what the pairs cost

By the duality theory cited above, the optimal $\mathbf{w}$ has the form $\sum_p \alpha_p \Phi_p$, a combination of difference vectors, and the proof above shows that the certifying multipliers are the ones in that combination. The score of a new document is then $\mathbf{w}^{\mathsf{T}}\mathbf{x} = \sum_p \alpha_p\, \Phi_p^{\mathsf{T}}\mathbf{x}$, and the dual objective $D(\alpha)$ contains the data only through the products $\Phi_p^{\mathsf{T}}\Phi_{p'}$. Each such product expands into four products of feature vectors. For pairs $(i, j)$ and $(k, l)$,

$$(\mathbf{x}_i - \mathbf{x}_j)^{\mathsf{T}}(\mathbf{x}_k - \mathbf{x}_l) = \mathbf{x}_i^{\mathsf{T}}\mathbf{x}_k - \mathbf{x}_i^{\mathsf{T}}\mathbf{x}_l - \mathbf{x}_j^{\mathsf{T}}\mathbf{x}_k + \mathbf{x}_j^{\mathsf{T}}\mathbf{x}_l .$$

So the whole method needs only inner products of feature vectors, and each can be replaced by a kernel $k(\mathbf{x}, \mathbf{x}')$, as Support Vector Machines explains. Herbrich et al. (2000, eq. 2.25) write the resulting kernel on pairs as $k(\mathbf{x}_1, \mathbf{x}_3) - k(\mathbf{x}_1, \mathbf{x}_4) - k(\mathbf{x}_2, \mathbf{x}_3) + k(\mathbf{x}_2, \mathbf{x}_4)$, and Joachims (2002, eqs. 16 to 19) notes the same extension. Joachims's experiments, whose learned weights he reads off feature by feature (§5.4), and this article's use the linear case, in which the learned function is one weight vector and scoring a document is one inner product.

The price of the method is the number of pairs. A query with $n_k$ candidates of grade $k$ has $\sum_{k > k'} n_k n_{k'}$ pairs, which grows with the square of the number of candidates. Cranfield's 225 queries, with 100 candidates each, give 105,334 pairs. The pairs are also spread unevenly. A query with more relevant candidates has more pairs, so it has more constraints and more say in $\mathbf{w}$: the 22 Cranfield queries with the most pairs hold 23.3% of all pairs, and one query alone has 1,985 against a median of 388 (22 queries is a tenth of the 225, rounded down). On MQ2008 the concentration is far stronger, as the experiment shows.

Preferences from clicks

Expert grades are expensive. Joachims's paper is mostly about a cheaper source of pairs, and its treatment has three steps.

Clicks are not grades. A search engine can log, for each query, the ranking it presented and the links the user clicked, at almost no cost (§2.1). The temptation is to read a click as a judgment of relevance. Joachims (2002, Table 1) gives data against that reading, taken from earlier work on another search engine, LASER. For three retrieval functions that human judges considered substantially different in quality, the average rank of a clicked link was nearly the same: $6.26 \pm 1.14$, $6.18 \pm 1.33$ and $6.04 \pm 0.92$. Users click on the most promising of the links they look at, near the top, whatever the absolute quality of those links. A user "is less likely to click on a link low in the ranking, independent of how relevant it is" (§2.2).

Clicks are preferences. What a click does show is a comparison. In his Figure 1 a user receives ten links for the query support vector machine and clicks on links 1, 3 and 7. A user reading from the top saw link 2 before clicking link 3, and chose not to click it. So link 3 is preferred to link 2. His Algorithm 1 makes this a rule: for a presented ranking and a set of clicked ranks, extract the preference "link $i$ above link $j$" for every pair with $j < i$ where $i$ was clicked and $j$ was not. The clicks on 1, 3 and 7 give five preferences:

Clicked link Skipped links above it Preferences
1 none none
3 2 3 over 2
7 2, 4, 5, 6 7 over 2, 7 over 4, 7 over 5, 7 over 6

A click on the first link alone yields nothing, since nothing was skipped. A single click on link 10 yields nine preferences. The rule only ever says that a lower result beats a higher one: it produces evidence against the presented ranking, never for it.

Preferences are constraints. Each extracted preference is a pair for the set $I$, and the optimization problem is unchanged. Joachims states it as Optimization Problem 2: the same objective, with the constraints running over the observed preferences in place of a complete target ranking (§4.2). Nothing in the problem needed grades. This is the advantage of a pairwise method over a pointwise one: a classifier needs a label for each document, and clicks do not supply one.

What Joachims found

He built a meta-search engine, Striver, that sent each query to five search engines, took their top 100 links each, and ranked the union with the learned function (§5.1). The features described the match between the query and a result: the result's rank in each engine, cosines between the query and the words of the result's title and URL, and a large number of binary features for domains and URLs (§5.2). In an offline test on 112 of his own queries, the share of held-out preferences that the learned function violated fell to around 10 percent as the number of training queries grew (Figure 4).

The online test trained on 260 queries collected from about 20 users and then compared the learned ranking with Google, with MSNSearch and with a non-learning meta-search baseline, Toprank, by presenting the two rankings merged into one list, so that any top part of the list holds almost equally many links from each, and counting the clicks on each side's links (§5.1). Online evaluation describes the later methods of this kind, under the name interleaving. His Table 2:

Learned against More clicks on learned Fewer clicks on learned Tie or no click Queries Sign test $p$
Google 29 13 46 88 0.020
MSNSearch 18 4 18 40 0.004
Toprank 21 9 22 52 0.043

The last column is this article's computation, a two-sided binomial sign test on the queries with a preference, exact in the script. The paper reports that the first comparison is significant at the 95% level by that test and that the same holds for the other two, which the $p$ values confirm. The learned weights (his Table 3) are readable: the largest positive weights are on the cosine between query and abstract (0.60), on being in Google's top 10 (0.48) and on the cosine between query and URL (0.24), and the largest negative weights are on not being first in any engine ($-0.38$), on not being in any engine's top 10 ($-0.32$) and on the length of the URL ($-0.17$).

Two limits belong with the result. The users were a group of about 20 researchers and students of one university's AI unit (§5.3), and the function was fitted to them; Joachims presents the result as adaptation to "a group of users", and concludes that Google was beaten "for this group of users", not as a general improvement over the engines. And the preferences come only from results that were shown and looked at, so what the model learns depends on the ranking that collected the clicks. Learning from Clicks takes up that dependence, the position bias behind Table 1, and the correction for it.

Experiments

Two collections with expert grades let the method be compared with RankNet under one protocol. The first is the course article's: Cranfield's 225 queries, BM25's top 100 candidates for each, eight features rescaled to $[0, 1]$ within each query, and 5-fold cross-validation over queries repeated for 30 seeded assignments of queries to folds. The second is LETOR 4.0's MQ2008 (Qin and Liu, 2013): 784 queries, 15,211 judged documents with 46 features, grades 0 to 2, in five predefined folds, each with a training, a validation and a test part. Features for Ranking describes both sets of features.

On Cranfield, $C$ was chosen from $\{0.0001, 0.001, 0.01, 0.1, 1\}$ inside each training fold, on a quarter of its queries held out for the purpose. On MQ2008 it was chosen on each fold's validation part. The quadratic programs were solved by liblinear through scikit-learn, on mirrored pairs with $C/2$ as derived above; on the four-document example the same call returns $(0.6, -0.2)$, the exact solution.

Cranfield

Ranker MAP, median of 30 (IQR) nDCG@10, median (IQR)
BM25 alone 0.307 0.368
RankNet, linear 0.314 (0.313–0.315) 0.384 (0.383–0.384)
Ranking SVM 0.313 (0.312–0.314) 0.382 (0.382–0.384)

IQR is the interquartile range over the 30 fold assignments. The RankNet row is the course article's, recomputed by this unit's code on the same 30 fold assignments. Over BM25 alone, the Ranking SVM's medians are higher in MAP by 0.006 and nDCG@10 by 0.014. For the first fold assignment it improved average precision on 126 queries and harmed it on 84, compared with BM25 ($p = 0.44$ by a paired randomization test, as in significance testing).

Against RankNet, the Ranking SVM had higher MAP than RankNet in 8 of the 30 fold assignments and higher nDCG@10 in 6, so RankNet was usually ahead, by about a thousandth. The 30 assignments reuse the same 225 queries, so those counts are not 30 independent trials. On the first fold assignment, a paired randomization test on the difference in MAP between the two is far from significant ($p = 0.95$). On this data the two pairwise methods cannot be told apart by any margin that matters. Both also gain little over BM25. The course article found the same for its four rankers, and its explanation, that the eight features say nearly the same thing, is consistent with the training fit below, though the fit does not single it out (a richer model class could also be what is missing): fitted on all 225 queries and scored on those same queries, the Ranking SVM does barely better than on held-out queries.

Fitted on all 225 queries, the solution shows what $C$ controls:

$C$ $\lVert \mathbf{w} \rVert$ Pairs at or inside the margin Misordered pairs MAP on the training queries
0.0001 1.25 66,870 19,487 0.316
0.001 2.18 50,566 18,755 0.313
0.01 3.44 45,835 18,252 0.316
0.1 4.49 44,667 18,139 0.313
1 4.69 44,481 18,138 0.313

As $C$ grows, $\mathbf{w}$ lengthens and fewer pairs sit at or inside the margin, from 66,870 (63% of the pairs) to 44,481 (42%). The misordered pairs fall only from 19,487 to 18,138, and MAP on the training queries stays between 0.313 and 0.316. At $C = 1$ the total slack is 44,457, more than twice the number of misordered pairs it bounds, so on this data the bound is loose. A larger $C$ fits the training pairs a little more tightly and changes the training MAP very little. The selection inside the training folds chose the smallest value, $C = 0.0001$, in 58 of the 150 training folds, more often than any other.

The weights at $C = 0.01$, beside those of RankNet trained on the same 225 queries with the course article's settings:

Feature Ranking SVM, $C = 0.01$ RankNet
BM25 +2.16 +3.36
TF-IDF +1.33 +1.75
BIM +0.38 +0.70
QL (Dirichlet) −1.07 −2.01
title BM25 +1.82 +2.37
coverage −0.69 −1.11
proximity +0.60 +0.87
log length +0.04 −0.11

The two agree in sign on seven of the eight features, and the eighth, log length, is near zero in both. Scale apart (a ranking does not change when $\mathbf{w}$ is multiplied by a positive number), they point in nearly the same direction: the cosine between the two weight vectors is 0.99. On the training pairs, RankNet's weights misorder 18,216 pairs, against the SVM's 18,252 at $C = 0.01$. The hinge and the logistic cost, given the same pairs, arrived at nearly the same linear function.

MQ2008

Ranker nDCG@10 MAP
Best single feature (column 39) 0.689
RankNet, linear 0.703 0.665
Ranking SVM, all pairs equal 0.696 0.654
Ranking SVM, each query's pairs sharing weight 1 0.698 0.662

The values are means over the test queries of the five folds. Of the 784 queries, 220 have no relevant document among their candidates; nDCG and average precision are undefined for them, and they are left out, so each mean is over 564 queries. nDCG@10 uses gain $2^{y} - 1$. Both training procedures are deterministic for given folds, so there is one value per method, not a distribution over seeds. The RankNet row is from RankNet, trained on the same folds; the best single feature is the column that alone ranks the test queries best, a language model score of the whole document.

The pairs are concentrated in a few queries. Together the 784 queries of MQ2008 have 80,925 pairs, and the 78 queries with the most pairs hold 78.2% of them; the largest query has 4,133 pairs against a median of 20 among the queries that have any. With every pair counted equally, a tenth of the queries supplies most of the constraints, while nDCG@10 and average precision weigh every query alike. The second SVM row reweights the pairs so that each query's pairs share one unit of weight, scaled so that the mean weight of a pair is 1, which gives every query the same say in $\mathbf{w}$. In this run the reweighting raised nDCG@10 from 0.696 to 0.698 and MAP from 0.654 to 0.662, differences this article does not test for significance.

Against RankNet. Query by query, neither SVM differs reliably from the linear RankNet. Paired randomization tests on nDCG@10 over the 564 queries give, with all pairs counted equally, $p = 0.08$, and with each query's pairs sharing one unit of weight, $p = 0.33$; the first SVM was better on 128 queries and worse on 169. The value of $C$ chosen on the validation parts ran from 0.0001 to 1 across folds and versions. All three learned linear rankers scored above the best single feature.

What is proved, what is cited, what the experiments show

Proved on this page. The Ranking SVM is a soft-margin SVM on difference vectors with no intercept; mirroring the pairs is the same problem with $C$ doubled, and an intercept cannot lower the mirrored problem's objective (in the unmirrored problem, where every label is $+1$, an intercept would make it trivial). The one-pair solution is $\Phi / \lVert \Phi \rVert^2$. In the hard-margin problem on a chain of grades, only adjacent pairs can be support pairs. A positive combination of difference vectors summing to zero proves that no weight vector orders the pairs. Every dual value is a lower bound on every primal value, so equal values certify a solution, and at such a solution $\mathbf{w} = \sum_p \alpha_p \Phi_p$. That certifying multipliers always exist is cited (through the library's support vector machine article), not proved. The total slack is at least the number of misordered pairs.

Cited. Herbrich et al.'s Theorem 2.1, that the inversion risk of ordinal regression equals a classification risk on pairs up to a constant, and their margin bound (Theorem 2.2), which this article does not use. Joachims's statement that maximizing the number of correctly ordered pairs is NP-hard, his Theorem 1 bounding average precision (checked here on small cases, not proved), and all the results of his experiments.

Shown by the experiments. On Cranfield and MQ2008, with these features and linear models, the Ranking SVM and RankNet could not be told apart: RankNet was usually ahead by about a thousandth on Cranfield and by a few thousandths on MQ2008, and no paired test found the difference significant. On Cranfield the two learned weight vectors pointed in nearly the same direction. These are observations on two small collections. They do not show that the hinge and the logistic cost are interchangeable in general.

Worked problems

The problems are posed on this article's examples and on Joachims's click example; the unit has no course assignments. tools/experiments/ltr/ranking-svm.py recomputes each answer.

Problem 1 (one pair, in general and in numbers). A query has two candidates, $\mathbf{x}_1 = (0.9, 0.2)$ judged relevant and $\mathbf{x}_2 = (0.5, 0.5)$ judged nonrelevant. Find the hard-margin Ranking SVM solution, the two scores, and the distance between the documents' projections onto $\mathbf{w}$.

Solution. The solution is $\mathbf{w} = (1.6, -1.2)$. The difference vector is $\Phi = (0.4, -0.3)$, with $\lVert \Phi \rVert^2 = 0.16 + 0.09 = 0.25$. By the one-pair result, $\mathbf{w} = \Phi / 0.25 = (1.6, -1.2)$. The scores are $s_1 = 1.6 \times 0.9 - 1.2 \times 0.2 = 1.2$ and $s_2 = 1.6 \times 0.5 - 1.2 \times 0.5 = 0.2$, exactly 1 apart, as a tight constraint requires. The length of $\mathbf{w}$ is $\sqrt{2.56 + 1.44} = 2$, so the projections are $1/2$ apart, which is $\lVert \Phi \rVert = 0.5$: with one pair, the widest gap any direction can show is the distance between the two documents, attained along the line joining them.

Problem 2 (which pairs support the solution). A query has candidates $p = (4, 0)$ of grade 2, $q = (1, 0)$ of grade 1 and $r = (0, 1)$ of grade 0. Find the hard-margin solution and its support pairs.

Solution. The solution is $\mathbf{w} = (\tfrac{1}{2}, -\tfrac{1}{2})$, and $(q, r)$ is the only support pair. The difference vectors are $\Phi_{pq} = (3, 0)$, $\Phi_{qr} = (1, -1)$ and $\Phi_{pr} = (4, -1)$; the last is the sum of the first two, so its constraint is implied. Try both adjacent constraints tight, as in the three-document example: $3w_1 = 1$ and $w_1 - w_2 = 1$ give $\mathbf{w} = (\tfrac{1}{3}, -\tfrac{2}{3})$. Writing $\mathbf{w} = \alpha_{pq}(3, 0) + \alpha_{qr}(1, -1)$ gives $\alpha_{qr} = \tfrac{2}{3}$ and $3\alpha_{pq} + \tfrac{2}{3} = \tfrac{1}{3}$, so $\alpha_{pq} = -\tfrac{1}{9}$. A negative multiplier is not allowed, so this point is not the solution: the constraint of $(p, q)$ should not be tight. Drop it, and solve the one-pair problem for $(q, r)$: $\mathbf{w} = \Phi_{qr} / \lVert \Phi_{qr} \rVert^2 = (\tfrac{1}{2}, -\tfrac{1}{2})$. Check the dropped constraints: $\mathbf{w}^{\mathsf{T}}\Phi_{pq} = \tfrac{3}{2} \ge 1$ and $\mathbf{w}^{\mathsf{T}}\Phi_{pr} = \tfrac{5}{2} \ge 1$. All constraints hold, the multipliers are $\alpha_{qr} = \tfrac{1}{2}$ and zero for the others, and the primal objective $\tfrac{1}{2}(\tfrac{1}{4} + \tfrac{1}{4}) = \tfrac{1}{4}$ equals the dual $\tfrac{1}{2} - \tfrac{1}{4} = \tfrac{1}{4}$, which certifies it. The rejected point had objective $\tfrac{1}{2}(\tfrac{1}{9} + \tfrac{4}{9}) = \tfrac{5}{18}$, larger than $\tfrac{1}{4}$. Document $p$ is so far ahead of $q$ on the first feature that the pair needs no help; the solution is decided entirely by the close pair.

Problem 3 (clicks to constraints). A user is shown six links and clicks on links 2 and 5. List the preferences Algorithm 1 extracts, and write the constraint of one of them.

Solution. There are four preferences: 2 over 1, 5 over 1, 5 over 3 and 5 over 4. For clicked link 2, the unclicked links above it are $\{1\}$. For clicked link 5, the links above it are 1, 2, 3 and 4, of which 2 was clicked, leaving $\{1, 3, 4\}$. No preference is extracted between links 2 and 5, both clicked, and none involving link 6, which lies below the last click and may not have been seen. The preference "5 over 3" is the pair $(i, j) = (5, 3)$ in $I$, with constraint $\mathbf{w}^{\mathsf{T}}\mathbf{x}_5 \ge \mathbf{w}^{\mathsf{T}}\mathbf{x}_3 + 1 - \xi_{53}$, $\xi_{53} \ge 0$, where $\mathbf{x}_5$ and $\mathbf{x}_3$ are the feature vectors of those two links for this query.

Problem 4 (reading a soft-margin solution). For the four-document example at $C = 1$, with $\mathbf{w} = (0.6, -0.2)$, compute the four scores, the five slacks, the objective, and Kendall's tau between the learned order and the judged preferences.

Solution. The scores are $s_a = 2.4 - 0.2 = 2.2$, $s_b = 1.2 - 0.4 = 0.8$, $s_c = 0.6$ and $s_d = 1.8 - 0.6 = 1.2$, so the order is $a, d, b, c$. The score differences of the five pairs are $s_a - s_b = 1.4$, $s_a - s_c = 1.6$, $s_a - s_d = 1.0$, $s_b - s_c = 0.2$ and $s_b - s_d = -0.4$. The slacks are $\max(0, 1 - \text{difference})$: 0, 0, 0, 0.8 and 1.4, which sum to 2.2. The objective is $\tfrac{1}{2}(0.36 + 0.04) + 1 \times 2.2 = 0.2 + 2.2 = 2.4$, as in the table. One of the five judged pairs is discordant, $(b, d)$, and four are concordant, so over the judged pairs $\tau = (4 - 1)/5 = 0.6$. The pair $(b, c)$ is ordered correctly and still pays slack 0.8, because its score difference of 0.2 is inside the margin. The slack total, 2.2, exceeds the one misordered pair by that amount and by the 0.4 with which $(b, d)$ overshoots.

What we have learned

A Ranking SVM is a support vector machine whose training points are the difference vectors of preferred pairs, with every label $+1$ and no intercept. Its margin is the gap between the projections of the closest preferred pair, its support pairs are the pairs at or inside that gap, and its slack is an upper bound on the number of misordered pairs. Because it needs only preferences, it can be trained on clicks, which say that a clicked result beats the unclicked ones above it. On Cranfield and MQ2008 it could not be told apart from RankNet.

The hinge loss has no gradient where a pair sits exactly on the margin and a zero gradient beyond it, and solving the quadratic program gets harder as pairs multiply. RankNet keeps the pairs, replaces the hinge by a smooth cost that can be minimized by gradient descent for any differentiable model, and finds a factorization that makes the pairs cheap.

References

  • Herbrich, R., Graepel, T., and Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. In A. J. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans (Eds.), Advances in Large Margin Classifiers, 115–132. MIT Press. Equation, theorem and section numbers follow the first author's copy of the chapter, where it is chapter 2. record · 2 pages
  • Joachims, T. (2002). Optimizing search engines using clickthrough data. In Proceedings of KDD 2002, 133–142. record · 4 pages
  • 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