Ranking and Empirical Minimization of U-statistics

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