Ranking and empirical minimization of U-statistics

• 成果类型: Article
• 署名作者: Clemencon, Stephan; Lugosi, Gabor; Vayatis, Nicolas
• 署名单位: IMT - Institut Mines-Telecom; IMT Atlantique; Pompeu Fabra University; Universite Paris Saclay
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/009052607000000910
• 发表日期: 2008
• 页码: 844-874
• 关键词: moment inequalities; LIMIT-THEOREMS; Consistency; error; CLASSIFICATION; bounds

摘要

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.