Learnability of bipartite ranking functions

The problem of ranking, in which the goal is to learn a real-valued ranking function that induces a ranking or ordering over an instance space, has recently gained attention in machine learning. We define a model of leamability for ranking functions in a particular setting of the ranking problem known as the bipartite ranking problem, and derive a number of results in this model. Our first main result provides a sufficient condition for the leamability of a class of ranking functions F: we show that F is learnable if its bipartite rank-shatter coefficients, which measure the richness of a ranking function class in the same way as do the standard VC-dimension related shatter coefficients (growth function) for classes of classification functions, do not grow too quickly. Our second main result gives a necessary condition for leamability: we define a new combinatorial parameter for a class of ranking functions F that we term the rank dimension of F, and show that F is learnable only if its rank dimension is finite. Finally, we investigate questions of the computational complexity of learning ranking functions.