Source-linked AI summary
Direct Optimization of Ranking Measures
Quoc Le, Alexander Smola
TL;DR
Ranking methods have difficulty optimizing complex performance measures directly, although those measures emphasize the ordering of top results. The paper applies structured estimation with a convex upper bound and reports stronger web-search results for directly optimized ranking measures.
Problem
Existing ranking approaches focus on pairwise comparisons or have difficulty expressing complex evaluation measures, despite users' emphasis on top results.
Source: §1 · pp. 1–2Method
The paper uses structured-output estimation with a convex upper bound on ranking loss and a kernelized scoring function.
Source: §1 · p. 2, §2 · p. 2, §2.3 · p. 4Results
With 100 training queries, DORM beats all other methods trained on 1000 queries for NDCG@10, while DORM for MRR beats other methods by 1% to 2%.
Source: §6.3 · p. 17, §6.4 · p. 18Takeaways & Limitations
The authors report that directly minimizing multivariate performance measures, or convex upper bounds on them, yields computational savings and better performance.
Source: §7 · p. 22Strict empirical-risk minimization can overfit, so good training-set performance does not ensure good performance on unseen test data.
Source: §2.1 · p. 3
Abstract
from arXiv · showhide
Web page ranking and collaborative filtering require the optimization of sophisticated performance measures. Current Support Vector approaches are unable to optimize them directly and focus on pairwise comparisons instead. We present a new approach which allows direct optimization of the relevant loss functions. This is achieved via structured estimation in Hilbert spaces. It is most related to Max-Margin-Markov networks optimization of multivariate performance measures. Key to our approach is that during training the ranking problem can be viewed as a linear assignment problem, which can be solved by the Hungarian Marriage algorithm. At test time, a sort operation is sufficient, as our algorithm assigns a relevance score to every (document, query) pair. Experiments show that the our algorithm is fast and that it works very well.
1 Introduction
Ranking evaluation emphasizes the ordering of top results, but existing graph-based approaches struggle to express complex performance measures. The paper applies structured-output estimation to optimize ranking criteria directly and reports fast, effective results on web search and collaborative filtering.
1 Introduction
- Users care especially about top-ranked results, motivating ranking measures such as NDCG, MRR, Precision@n, and ERU.The paper frames ranking as learning an ordering of documents, while noting that users are most concerned with the top part of the returned list.Source: §1 · p. 1
- Graph-based methods encode ordering errors as costs on directed-acyclic-graph edges, but struggle to express complex performance measures.Source: §1 · p. 2
- DORM uses structured-output SVM estimation to handle non-convex ranking measures and covers existing criteria in a plug-and-play scheme.The approach also extends to position-dependent ranking and diversity-based scores.Source: §1 · p. 2
- Prior structured-output SVM work optimized Precision@n and AUC, while DORM uses a related strategy with inequalities from Tsochantaridis et al..Burges et al. instead directly optimize nonconvex costs through their gradients.Source: §1 · p. 2
- Experiments on web search and collaborative filtering indicate that DORM is fast and works well.Source: §1 · p. 2
2 Structured Estimation
Structured estimation turns ranking into a function-scoring problem and uses a convex upper bound with regularization to manage difficult empirical-risk minimization. The method uses feature maps and kernels, then column generation and a linear-assignment formulation to optimize efficiently.
2.1 Problem Setting
- Ranking maps a query with its document set to a permutation, and the scoring function should favor the correct permutation.Structured estimation replaces direct mapping from inputs to outputs with a real-valued function over input-output pairs.Source: §2.1 · p. 3
- Direct empirical-risk minimization is difficult because it is nonconvex and can overfit, so the method adds regularization and computes a convex loss upper bound.The paper states that strict empirical-risk minimization virtually ensures poor test-set performance.Source: §2.1 · p. 3
2.2 Convex Upper Bound
- A structured loss constraint yields a convex upper bound on ranking loss, tight when the reference output is the prediction and the minimal feasible slack is used.The inequality constraints on the scoring function and slack variables are linear.Source: §2.2 · pp. 3–4
2.3 Kernels
- The scoring function is linear in a feature map and weight vector; kernels permit implicit feature-space computation and control complexity through the weight norm.Different feature maps can incorporate prior knowledge, and kernelization permits infinite-dimensional spaces with finitely many optimization parameters.Source: §2.3 · p. 4
2.4 Optimization
- Column generation avoids searching all permutation constraints directly, and the ranking search can be cast as a linear assignment problem.The optimization problem has prohibitively many variables for large output spaces, while column generation finds an approximate solution in polynomial time.Source: §2.4 · p. 5
- The optimization algorithm terminates after at most max(2nΔ̄/ε, 8CΔ̄R^2/ε^2) steps, with Δ̄ bounding loss and R bounding feature-map norms.The bound follows from the cited column-generation convergence result.Source: §2.4 · p. 5
3 Ranking and Loss Functions
The section formulates ranking as choosing a document ordering to perform well under permutation-based measures, including measures that emphasize top results. It defines scoring functions and losses that also accommodate position-specific costs.
3.1 A Formal Description
- The goal is a single ranking whose ordering of new documents agrees with relevance labels under a chosen performance measure.The measures are permutation-based, comparing the predicted and reference orderings.Source: §3.1 · p. 6
3.2 Scores and Loss
- NDCG discounts lower-ranked results, while Expected Rank Utility is used in collaborative filtering; both fit the section’s ranking-score framework.Precision@n gives equal weight to the top n answers, unlike NDCG’s decay factor.Source: §3.2 · p. 8
3.3 Scoring Function
- A decreasing sequence of position weights paired with document-query relevance scores makes sorting by those scores maximize the ranking function.The relevance score is assigned independently to each document-query pair.Source: §3.3 · p. 8
3.4 General Position Dependent Loss
- Position-dependent loss assigns each document-position placement a cost, allowing specific ranks to carry distinct meanings.Using a separate scoring function for each position makes estimation and optimization more costly than sorting one list of relevance scores.Source: §3.4 · p. 9
4 Learning Ranking
The learning method decomposes ranking features into document-query contributions and searches for violated ranking constraints. Its training subproblem is a linear assignment problem, while test rankings can be obtained by sorting relevance scores.
4.1 The Featuremap
- The feature map decomposes into document-query terms, so test rankings sort their relevance scores in O(l log l) time.For only the top n results, a QuickSort-style procedure takes O(l + n log n) time.Source: §4.1 · p. 9
4.2 Finding Violated Constraints
- Finding a violated ranking constraint becomes a linear assignment problem solvable by the Kuhn–Munkres algorithm in cubic time.When a = c, the problem has a special case that reduces to sorting, though that choice may be undesirable if a has many zero terms.Source: §4.2 · p. 10
4.3 Solving the Linear Assignment Problem
- Relaxing the assignment variables from integral to nonnegative values preserves an integral solution, enabling the constraint-checking subroutine to replace the corresponding SVMStruct subroutine.The relaxation preserves the solution because the constraint matrix is totally unimodular.Source: §4.3 · pp. 10–11
4.4 In a Nutshell
- Algorithm 2 solves the structured optimization problem, and test documents are ranked by g(d, q) = ⟨w, φ(d, q)⟩.The test-time score is computed for each document and query pair.Source: §4.4 · p. 11, §4.3 · p. 11
5 Extensions
The extensions add source-diversity constraints to top-n ranking and adapt ranking losses to collaborative-filtering matrix factorization. The latter evaluates each user’s row with a ranking score rather than indiscriminately minimizing rating error.
5.1 Diversity Constraints
- The top-n diversity formulation allows at most one retrieved document per source and avoids the exponential cost of item-interaction constraints.Its linear-programming relaxation has an integral solution; more general overlapping, non-integral topic weights cannot be relaxed easily.Source: §5.1 · pp. 12–13
5.2 Ranking Matrix Factorization
- For matrix factorization, the method evaluates a ranking score over each user’s row, focusing on preferences for desirable objects rather than indiscriminate rating error.The resulting objective is highly nonconvex, but a convex upper bound can be optimized in alternating U and V steps; details of optimizing V are left to future research.Source: §5.2 · pp. 13–14
6 Experiments
Across web-search and collaborative-filtering experiments, DORM performs well on several ranking measures, often outperforming comparison methods. Its results include gains with smaller training samples and runtime faster than most compared methods.
6.2 UCI Datasets
- DORM outperforms SVM classification, Precision@n, and ROCArea on UCI datasets when evaluated with NDCG@10.The comparison uses c_i = 1/(i+1); the table marks results with paired t-test significance p < 0.0001 in bold.Source: §6.2 · p. 15, Table 1 · p. 15
6.3 NDCG for Web Search
- On the web search dataset, DORM consistently outperforms other ranking methods by 2–3% in average prediction NDCG scores across truncation levels 1 to 10, with performance reported on the designated test set.Source: Figure 2 · p. 16, §6.3 · p. 17
- With 100 training queries, DORM exceeds every competing method trained on 1,000 queries for NDCG@10.For many methods, doubling sample size increases NDCG by less than 1%.Source: Figure 3 · p. 16, §6.3 · p. 17
6.4 MRR and WTA for Web Search
- Across sample sizes 100–1000, with c_i = 1/(i + 1) and C selected on validation data, DORM for MRR outperformed all other models, including DORM for NDCG, by 1%–2%.The authors call this significant because doubling the dataset size yields only around a 1% gain.Source: §6.4 · p. 18
- Modified WTA optimization (mWTA) significantly outperforms other methods, whereas direct WTA optimization performs unsatisfactorily.mWTA minimizes an adaptive NDCG variant to use more label information.Source: §6.4 · p. 18, Figure 6 · p. 19
6.5 Runtime Performance
- DORM is faster than most compared methods, except multiclass SVM and BM25, and its prediction time is under 0.5 seconds for 1,000 queries.The reported runtime comparison ignores file I/O; the authors also describe DORM as faster because it has a sparser solution.Source: §6.5 · pp. 18, 20, Figure 7 · p. 20, Table 2 · p. 21
6.6 EachMovie and Collaborative Filtering
- On EachMovie, DORM outperforms JRank and PRank on ERU, using the same kernels and experimental protocol as the JRank study.The comparison averages 100 trials with 100 training users, 2,000 input users, and 800 training items.Source: §6.6 · p. 20, Table 3 · p. 21
- On EachMovie NDCG, DORM performs well at predicting rankings for new items, especially with few labeled items.The experiment compares six methods after selecting 10, 20, or 50 labeled items per user.Source: §6.6 · pp. 20, 22, Table 4 · p. 21
7 Summary and Discussion
The paper proposes directly optimizing multivariate ranking measures, or convex upper bounds on them, and reports computational savings and better performance. It also describes extensions and settings where the framework could be applied.
7 Summary and Discussion
- The proposed scheme directly minimizes multivariate performance measures, or convex upper bounds on them, with computational savings and better performance.The authors frame this as estimating desired quantities rather than optimizing a surrogate.Source: §7 · p. 22
- The loss is generic and can replace losses in many settings, although the paper does not use sophisticated language models to parse queries.The authors say they ignored language models for query parsing.Source: §7 · p. 22
- The ranking-focused method can be generalized to optimize other complicated multivariate loss functions.Source: §7 · p. 22
- The authors suggest applying the method to information retrieval and authorship identification queries.For authorship identification, a query could consist of documents written by one author.Source: §7 · p. 22
- Personalized ranking can incorporate user data into the feature map φ(q_i, d_i, u_i).Source: §7 · p. 22
- Online algorithms could be accommodated to handle massive datasets.The authors point to online methods along the lines of.Source: §7 · p. 22
- Graph matching can be handled by extending the linear assignment problem to a quadratic one, but that optimization is NP hard and the Hungarian Marriage algorithm is infeasible.Source: §7 · p. 22
- The Hilbert-space choice is for convenience; the large-margin formulation can also use neural networks, though the authors find kernels well suited.Source: §7 · p. 22