Source-linked AI summary
Scalable Learning of Non-Decomposable Objectives
Elad ET. Eban, Mariano Schain, Alan Mackey, Ariel Gordon, Rif A. Saurous, Gal Elidan
TL;DR
Retrieval systems are evaluated on ranking measures that can be difficult to optimize at scale, so they are often trained for classification accuracy instead. This paper uses direct bounds on per-example true- and false-positive quantities to build scalable objectives, and reports improved performance over log-loss on larger real-life problems with convergence comparable to vanilla SGD.
Problem
Ranking-based retrieval objectives often do not decompose over examples, making them harder to optimize at scale and leading systems to train for accuracy instead of the metric of interest.
Source: §1 · p. 1Method
The framework bounds per-example true-positive and false-positive quantities to construct global bounds for ranking objectives that support mini-batch stochastic optimization.
Source: §1 · p. 2Results
Across several larger real-life problems, the approach improved performance over log-loss and achieved convergence indistinguishable from vanilla SGD.
Source: §1 · p. 2Takeaways & Limitations
The same building blocks support a wide range of ranking objectives, including AUCROC, AUCPR, P@R, R@P, Fβ, and objectives over selected precision or recall ranges.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Modern retrieval systems are often driven by an underlying machine learning model. The goal of such systems is to identify and possibly rank the few most relevant items for a given query or context. Thus, such systems are typically evaluated using a ranking-based performance metric such as the area under the precision-recall curve, the $F_\beta$ score, precision at fixed recall, etc. Obviously, it is desirable to train such systems to optimize the metric of interest. In practice, due to the scalability limitations of existing approaches for optimizing such objectives, large-scale retrieval systems are instead trained to maximize classification accuracy, in the hope that performance as measured via the true objective will also be favorable. In this work we present a unified framework that, using straightforward building block bounds, allows for highly scalable optimization of a wide range of ranking-based objectives. We demonstrate the advantage of our approach on several real-life retrieval problems that are significantly larger than those considered in the literature, while achieving substantial improvement in performance over the accuracy-objective baseline.
1 Introduction
Ranking objectives used in retrieval often do not decompose over examples, making them harder to optimize and leaving systems trained for accuracy instead. The paper introduces a scalable framework based on bounds for optimizing a wide range of such objectives and reports improved performance on larger real-life problems.
1 Introduction
- Non-decomposable ranking objectives are harder to optimize, so retrieval systems often train for accuracy instead, which can produce inferior results on the metric of interest.The paper's goal is an approach for a wide range of rank-based objectives that scales as well as accuracy optimization.Source: §1 · p. 1
- Prior methods faced computational scalability limits or covered only particular metrics; Joachims' gradient computation is generally quadratic in training examples, while MAP optimization can require costly cutting-plane training.Figure 1 illustrates the possible mismatch: a 90%-accurate classifier reaches 50% precision at 95% recall, whereas another classifier reaches about 65% precision at that recall.Source: §1 · pp. 1–2, Figure 1 · p. 2
- Direct bounds on per-example true-positive and false-positive quantities yield global bounds for ranking objectives that can be optimized with mini-batch stochastic methods for saddle-point problems.The authors describe these methods as having favorable convergence rates and suitable for massive-scale systems where full-batch optimization is intractable.Source: §1 · p. 2
- On several real-life problems larger than those previously considered, the approach improved performance over log-loss and had convergence indistinguishable from vanilla SGD.The abstract also reports substantial improvement over an accuracy-objective baseline.Source: §1 · p. 2
- The framework covers AUCROC, AUCPR, P@R, R@P, and Fβ, and can also optimize area-under-the-curve objectives over a specified precision or recall range.The paper presents this as a unified approach using the same building blocks.Source: §1 · p. 2
2 Related Works
Prior work addressed rank-based objectives but often traded off scalability, metric coverage, or practical training cost. The section contrasts these approaches with the paper's stochastic-gradient formulation.
2 Related Works
- Joachims used structured optimization for Fβ, P@R, and AUCROC, but gradient computation is generally quadratic and always super-linear in training examples.Even in the best case, the loss and its gradient take at least linear time to compute.Source: §2 · p. 2
- Direct AUCPR and MAP methods face scalability costs: AP-SVM uses costly cutting-plane constraint identification, and heuristic speedups do not remove the underlying issue.The cited deep-network generalization [23] has the same complexity as.Source: §2 · p. 2
- Other approaches scale by restricting model classes or targeting specific objectives; is scalable and general but omits constrained metrics such as P@R and R@P.The distributed method requires an optimization problem per instance, while [12] uses a minibatch buffer that may be infeasible for extremely multi-label problems.Source: §2 · pp. 2–3
3 Building Block Bounds
The framework builds global ranking measures from bounds on true-positive and false-positive quantities. It separates score-based ranking from threshold-based classification and uses surrogate losses to obtain tractable bounds.
3 Building Block Bounds
- Bounds on true-positive and false-positive statistics form the building blocks for global non-decomposable ranking measures, including AUCROC, AUCPR, and Fβ.The section identifies these statistics as the basis for the objectives developed throughout the paper.Source: §3 · p. 3
- The notation uses X for explanatory features, Y for the target label, and Y+ and Y− for positive and negative examples..Source: §3 · p. 3
- A classification rule uses a score function f and threshold b; the score ranks examples, while the threshold sets the positive-versus-negative decision boundary.The model parameters embedded in f are separated from the decision threshold.Source: §3 · p. 3
- Precision and recall are defined from the true-positive, false-positive, and false-negative counts.The section names these counts tp, fp, and fn, respectively.Source: §3 · p. 3
- The method lower-bounds tp and upper-bounds fp using zero-one loss expressions and a surrogate such as hinge loss; fn can be eliminated from recall using |Y+| = tp + fn.Hinge loss is used for simplicity; convex surrogates yield convex optimization problems, while non-convex surrogates can also be used.Source: §3 · p. 3
4 Maximizing Recall at Fixed Precision
The section makes recall-at-fixed-precision tractable by optimizing a concave lower-bound surrogate built from bounds on true and false positives. It also derives a related precision-at-fixed-recall objective and connects the fixed-precision formulation to weighted SVMs.
4 Maximizing Recall at Fixed Precision
- The R@Pα surrogate lower-bounds the original objective by lower-bounding true positives and upper-bounding false positives.Its objective is concave, with convex, piecewise-linear constraints.Source: §4 · p. 4
- The relaxed R@Pα problem becomes a saddle-point objective that can be optimized with stochastic gradient updates.The procedure converges to a fixed point when L+ and L− are convex.Source: §4 · p. 4
- For fixed λ, minimizing the Equation 6 objective over f is a weighted SVM, and its positive-example weight is monotonic in λ.The single dual parameter can therefore also be solved by binary search.Source: §4 · p. 4
4.1 Maximizing P@R
- The P@R derivation yields an equivalent formulation with the same minimizer as Equation 8, but not the same objective value.Minimizing 1/P rather than −P gives the expected reweighting of positives and negatives through λ.Source: §4.1 · pp. 4–5
5 Maximizing AUCPR
The section constructs an AUCPR surrogate from the fixed-precision recall formulation. It approximates the AUCPR integral with precision anchors and extends the same building-block approach to AUCROC and restricted metric ranges.
5 Maximizing AUCPR
- AUCPR is approximated by a discrete sum of recall-at-precision values over a set of precision anchors.The anchors need not be uniformly spaced.Source: §5 · p. 5
- Relaxing the building-block statistics and applying Lagrange multipliers produces a saddle-point problem solvable by SGD.The construction builds on the R@P optimization objective.Source: §5 · p. 5
- Replacing R@P with true positive rate at fixed false positive rate gives a similar algorithm for AUCROC.The framework can also optimize AUCROC or AUCPR over a limited range, such as precision above a desired threshold.Source: §5 · p. 5
6 Optimizing the Fβ Measure
The section extends the building-block bounds to optimize Fβ, a retrieval score that weights recall relative to precision. It gives both a lower-bound surrogate and alternative optimization formulations.
6 Optimizing the Fβ Measure
- The building-block bounds can optimize the Fβ retrieval score, which weights recall β times as much as precision.The score measures retrieval effectiveness for a user with that relative weighting.Source: §6 · p. 5
- Rewriting Fβ in type I and type II error terms permits a lower-bound surrogate using bounded true-positive and false-positive statistics.The surrogate is obtained by substituting the bounds into the score.Source: §6 · pp. 5–6
- A linear-fractional transformation yields an equivalent problem in auxiliary variables that can be solved as a linear program.The resulting program can also be optimized by iterative gradient ascent, as with R@P and AUCPR.Source: §6 · p. 6
- The constrained formulation reduces F1 optimization to a weighted classification problem once ψ and λ are fixed.The paper notes that a different technique had established this weighted-classification formulation.Source: §6 · p. 6
7 Experimental Evaluation
The evaluation compares AUCPR optimization with accuracy-oriented baselines on CIFAR-10, ImageNet, and JFT, including datasets substantially larger than those previously considered. AUCPR improved on all three, with an accuracy trade-off reported on ImageNet.
7 Experimental Evaluation
- The evaluation focused mostly on AUCPR across three challenging problems, two substantially larger than those previously considered in the literature.The CIFAR-10 experiment used 60,000 images and trained models for about eight hours on one GPU.Source: §7 · p. 6, §7.1 · p. 6
7.1 CIFAR-10
- AUCPR increased from 84.6% to 94.2% on CIFAR-10, and the method improved AUCPR across all 10 classes.Results were essentially identical with 5, 10, and 20 anchor points; only K = 10 results are reported.Source: §7.1 · pp. 6–7
7.2 ImageNet
- On ImageNet, AUCPR increased from 82.2% to 83.3% while accuracy decreased by 0.4%.The comparison used the same training time for the baseline and AUCPR-optimized models, with K = 5 anchor points.Source: §7.2 · p. 7
7.3 JFT
- AUCPR rose from 42% to 48% on JFT when the model used the surrogate rather than the accuracy-trained baseline.Both models received the same additional training time; AUCPR optimization started from pretrained parameters because training from scratch takes multiple months.Source: §7.3 · p. 7
8 Summary and Future Directions
The paper presents building-block bounds for scalable optimization of non-decomposable ranking objectives and reports their effectiveness on real-life datasets. The framework also supports more refined objectives, including ROC area over a specified false-positive-rate range.
8 Summary and Future Directions
- Simple building-block bounds provide a unified framework for efficient optimization of a wide range of non-decomposable ranking objectives.The approach was demonstrated on several real-life datasets, including problems dramatically larger than those previously considered.Source: §8 · p. 7
- The method is essentially as efficient as optimizing fully decomposable accuracy loss and can be paired with shallow or deep architectures with negligible performance cost.The paper names SVMs and logistic regression as shallow architectures and CNNs as deep architectures.Source: §8 · p. 7
- The framework also supports refined objectives, such as maximizing ROC area within a prespecified false-positive-rate range.The paper identifies exploring this flexibility for real-world ranking problems as future work.Source: §8 · p. 7