Ranking and empirical minimization of U-statistics

By St'ephan Cl'emenccon, Gábor Lugosi, Nicolas Vayatis. 2006

385 citations recorded by the source corpus.

The problem of ranking/ordering instances, instead of simply classifying them, has recently gained much attention in machine learning. In this paper we formulate the ranking problem in a rigorous statistical framework. The goal is to learn a ranking rule for deciding, among two instances, which one is "better," with minimum ranking risk. Since the natural estimates of the risk are of the form of a U-statistic, results of the theory of U-processes are required for investigating the consistency of empirical risk minimizers. We establish in particular a tail inequality for degenerate U-processes, and apply it for showing that fast rates of convergence may be achieved under specific noise assumptions, just like in classification. Convex risk minimization methods are also studied.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Economics and Econometrics, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Economics and Econometrics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Learning to rank for information retrieval (2009, positive): “For another example, in [27], the consistency for pairwise ranking was discussed, but no necessary discussions were provided on how to extend this result to listwise ranking.”
Rademacher Chaos Complexities for Learning the Kernel Problem (2010, methodology): “The nice application of U-processes to the generalization analysis of ranking and scoring problem is recently developed in Clémencon et al. (2008). Our first main result shows that the excess generalization error of MKL algorithms can be bounded by the empirical Rademacher chaos complexity over the ”
A Theoretical Analysis of NDCG Type Ranking Measures (2013, background): “≥ ... ≥ f xf (n) . Let y 1,...,yn (yi ∈ Y) be the degree of relevancy associated with x 1,...,xn. We will denote by Sn = {(x 1,y 1),...,(xn,yn)} the set of data to rank. As in existing literature [18, 13], we assume that (x 1,y 1),...,(xn,yn) are i.i.d. sample drawn from an underlying distribution”
Direct Learning to Rank and Rerank (2018, methodology): “We will extend the deﬁnition of conditional linear rank statistics (Clemenc¸on and Vayatis, 2008; Clemenc¸on et al, 2008) to include various deﬁnitions of rank.”
Distribution-Free, Risk-Controlling Prediction Sets (2021, background): “We consider the problem of uncertainty quantiﬁcation for learning a ranking rule [see, e.g., 57].”
Generalization bounds for learning the kernel (2009, methodology): “The nice application of U-processes to the generalization analysis of the ranking and scoring problem is recently developed in [10].”
Integer optimization methods for machine learning (2012, background): “Special members of this class include: • a ℓ = ℓ: Wilcoxon Rank Sum (WRS) – related to the AUC [see Clemençon et al., 2008, Clemençon and Vayatis, 2008].”
Surrogate regret bounds for bipartite ranking via strongly proper losses (2012, methodology): “…conditional class probabilities [31]; since the class probability function provides the optimal ranking [8], it is intuitively clear (and follows formally from results in [8, 9]) that any algorithm providing a good approximation to the class probability function should also produce a good ranking.”
Predicting accurate probabilities with a ranking loss (2012, background): “(Clémençon et al., 2006) The AUC A (ŝ(·)) of a model ŝ : X → R is”
Chromatic PAC-Bayes Bounds for Non-IID Data (2009, methodology): “These bounds are directly related to the work of Agarwal et al. (2005), Agarwal and Niyogi (2009), Cl´emen¸con et al. (2008) and Freund et al. (2003).”
Convex Calibration Dimension for Multiclass Loss Matrices (2014, background): “We also point out that in a related but diﬀerent context, consistency of ranking has also been studied in the instance ranking setting [7, 6, 15, 1].”
Bipartite Ranking through Minimization of Univariate Loss (2011, background): “Given P (x, y), it can be derived explicitly (Clémençon et al., 2008; Balcan et al., 2008; Ailon & Mohri, 2008): r∗(x, x′) = sgn (η(x)− η(x′)) , (5) where η(x) = P (y = 1 |x), and: sgn (z) = 1 z > 00 z = 0−1 z < 0 is a sign function.”
On the Consistency of Ordinal Regression Methods (2014, result): “The ranking formulation has also been studied in details [5, 6] where it has been shown that existing pairwise approaches were not consistent with respect to the pairwise disagreement.”