Generalization Bounds for k-Partite Ranking

We study generalization properties of ranking algorithms in the setting of the k-partite ranking problem. In the k-partite ranking problem, one is given examples of instances labeled with one of k ordered ‘ratings’, and the goal is to learn from these examples a real-valued ranking function that ranks instances in accordance with their ratings. This form of ranking problem arises naturally in a variety of applications and, formally, constitutes a generalization of the bipartite ranking problem that has recently been studied. We start by defining notions of ranking error suitable for measuring the quality of a ranking function in the k-partite setting. We then give distribution-free probabilistic bounds on the expected error of a ranking function learned by a k-partite ranking algorithm