Ranking and empirical minimization of U-statistics
arXiv (Cornell University)Published 5 March 2006Open access
Stéphan Clémençon, Gábor Lugosi, Nicolas Vayatis
Citations155
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The problem of ranking/ordering instances, instead of simply classifying\nthem, has recently gained much attention in machine learning. In this paper we\nformulate the ranking problem in a rigorous statistical framework. The goal is\nto learn a ranking rule for deciding, among two instances, which one is\n"better," with minimum ranking risk. Since the natural estimates of the risk\nare of the form of a U-statistic, results of the theory of U-processes are\nrequired for investigating the consistency of empirical risk minimizers. We\nestablish in particular a tail inequality for degenerate U-processes, and apply\nit for showing that fast rates of convergence may be achieved under specific\nnoise assumptions, just like in classification. Convex risk minimization\nmethods are also studied.\n
Keywords
Computer Science
Wiley series in probability and statisticsApproximation Theorems of Mathematical Statistics
5,946 Citations1980Robert Serfling
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
4,750 Citations1963Wassily Hoeffding
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
The Annals of Mathematical StatisticsA Class of Statistics with Asymptotically Normal Distribution
1,844 Citations1948Wassily Hoeffding
Bulletin of the American Mathematical SocietyOn the mathematical foundations of learning
1,578 Citations2001Felipe Cucker, Steve Smale
A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference) and relations of the theory of learning to the mainstream of mathematics are emphasized.
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
Journal of the American Statistical AssociationConvexity, Classification, and Risk Bounds
1,019 Citations2006Peter L. Bartlett, Michael I. Jordan +1 more
A general quantitative relationship between the risk as assessed using the 0–1 loss and the riskAs assessed using any nonnegative surrogate loss function is provided, and it is shown that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function.
The Annals of StatisticsStatistical behavior and consistency of classification methods based on convex risk minimization
709 Citations2004Tong Zhang
This study sheds light on the good performance of some recently proposed linear classification methods including boosting and support vector machines and shows their limitations and suggests possible improvements.
The Annals of StatisticsOptimal aggregation of classifiers in statistical learning
577 Citations2004A. B. Tsybakov
The main result of the paper concerns optimal aggregation of classifiers: a classifier that automatically adapts both to the complexity and to the margin, and attains the optimal fast rates, up to a logarithmic factor.
Adapting ranking SVM to document retrieval
570 Citations2006Yunbo Cao, Jun Xu +4 more
Experimental results show that the modifications made in conventional Ranking SVM can outperform the conventional ranking SVM and other existing methods for document retrieval on two datasets and employ two methods to conduct optimization on the loss function: gradient descent and quadratic programming.
Inventiones mathematicaeNew concentration inequalities in product spaces
517 Citations1996Michel Talagrand
The Annals of StatisticsEmpirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers
468 Citations2002Vladimir Koltchinskii, Dmitry Panchenko
New probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifier combinations, based on the methods of the theory of Gaussian and empirical processes are proved.
The Annals of ProbabilitySome Limit Theorems for Empirical Processes
438 Citations1984Evarist Giné, Joel Zinn
ESAIM Probability and StatisticsTheory of Classification: a Survey of Some Recent Advances
416 Citations2005Stéphane Boucheron, Olivier Bousquet +1 more
Applied Physics Letters10.1162/1532443041827916
393 Citations2000
This work describes and analyze an efficient algorithm called RankBoost for combining preferences based on the boosting approach to machine learning, and gives theoretical results describing the algorithm's behavior both on the training data, and on new test data not seen during training.
The Annals of StatisticsLocal Rademacher complexities and oracle inequalities in risk minimization
379 Citations2006Vladimir Koltchinskii
Journal of Combinatorial Theory Series ASphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension
296 Citations1995David Haussler
It is shown that M(k/n,V) >= (cn/(k+d)log(n/k) for some constant c so that any two distinct vectors in W differ on at least k indices.
Analysis and ApplicationsESTIMATING THE APPROXIMATION ERROR IN LEARNING THEORY
265 Citations2003Steve Smale, Ding‐Xuan Zhou
The rate of convergence of the kernel approximation, where ℋ is the range of a compact, symmetric, and strictly positive definite linear operator on a separable Hilbert space B, is studied.
ESAIM Probability and StatisticsOn Talagrand's deviation inequalities for product measures
261 Citations1997Michel Ledoux
Lecture notes in computer scienceSubset Ranking Using Regression
245 Citations2006David Cossock, Tong Zhang
Borders are presented that relate the approximate optimization of DCG to the approximate minimization of certain regression errors and justify the use of convex learning formulations for solving the subset ranking problem.
Applied Physics Letters10.1162/153244302760185252
225 Citations2000
It is shown that the soft margin algorithms with universal kernels are consistent for a large class of classification problems including some kind of noisy tasks provided that the regularization parameter is chosen well.
The Annals of ProbabilityLimit Theorems for $U$-Processes
215 Citations1993Miguel A. Arcones, Evarist Giné
Probability Theory and Related FieldsEmpirical minimization
171 Citations2005Peter L. Bartlett, Shahar Mendelson
Birkhäuser Boston eBooksExponential and Moment Inequalities for U-Statistics
158 Citations2000Evarist Giné, Rafał Latała +1 more
The Annals of StatisticsProcess consistency for AdaBoost
131 Citations2004Wenxin Jiang
It is shown under general regularity conditions that during the process of AdaBoost a consistent prediction is generated, which has the prediction error approximating the optimal Bayes error as the sample size increases.
The Annals of StatisticsPopulation theory for boosting ensembles
89 Citations2004Leo Breiman
It is shown that the simplest kind of trees is complete in D-dimensional L 2 (P) space if the number of terminal nodes T is greater than D and that the AdaBoost algorithm gives an ensemble converging to the Bayes risk.
Birkhäuser Basel eBooksExponential Inequalities, with Constants, for U-statistics of Order Two
83 Citations2003Christian Houdré, Patricia Reynaud-Bouret
The Annals of ProbabilityMoment inequalities for functions of independent random variables
83 Citations2005Stéphane Boucheron, Olivier Bousquet +2 more
Pattern Classification and Learning Theory
79 Citations2002Gábor Lugosi
In pattern recognition, one creates a function g(x): R d → {0, 1} which represents one’s guess of y given x, which is called a classifier and errs on x if g( x) ≠ y.
Lecture notes in computer scienceRanking with a P-Norm Push
57 Citations2006Cynthia Rudin
This work provides a general form of convex objective that gives high-scoring examples more importance near the top of the ranked list, and proves that the minimizer of the objective is unique in a specific sense.
Stochastic Processes and their ApplicationsU-processes indexed by Vapnik-Červonenkis classes of functions with applications to asymptotics and bootstrap of U-statistics with estimated parameters
39 Citations1994Miguel A. Arcones, Evarist Giné
Probability Theory and Related FieldsAn estimate on the supremum of a nice class of stochastic integrals and U-statistics
32 Citations2005Péter Major
The Annals of StatisticsUniversally Consistent Conditional $U$-Statistics
30 Citations1994Winfried Stute
Lecture notes in computer scienceMachine Learning Ranking for Structured Information Retrieval
11 Citations2006Jean-Noël Vittaut, Patrick Gallinari
This work proposes to improve the performance of a baseline Information Retrieval system by using a learning ranking algorithm which operates on scores computed from document elements and from their local structural context.
Using RankBoost to compare retrieval systems
6 Citations2005Huyen-Trang Vu, Patrick Gallinari
A new pooling method for constructing the assessment sets used in the evaluation of retrieval systems based on RankBoost, a machine learning voting algorithm, which leads to smaller pools than classical pooling and thus reduces the manual assessment workload for building test collections.