Lan, Yanyan and Liu, Tie-Yan and Ma, Zhiming and Li, Hang
This paper presents a theoretical framework for ranking, and demonstrates how to perform generalization analysis of listwise ranking algorithms using the framework. Many learning-to-rank algorithms have been proposed in recent years. Among them, the listwise approach has shown higher performance when compared to the other approaches. However, the theoretical studies on the listwise approach were not sufficient. In this paper, we propose a theoretical framework for ranking, which can naturally describe various learning-to-rank algorithms, especially listwise ranking algorithms. With this framework, we prove a theorem which gives a query-level generalization bound of a listwise ranking algorithm, on the basis of Rademacher Average of the class of compound functions. The compound functions take listwise loss functions as outer functions and ranking models as inner functions. We then compute the Rademacher Averages for existing listwise algorithms of ListMLE, ListNet, and RankCosine. We also discuss the tightness of the bounds in different situations with regard to the list length and transformation function. To the best of our knowledge, this is the first paper that formally discusses the generalization ability of listwise ranking algorithms.
Discussion