TY - GEN

T1 - Learnability of bipartite ranking functions

AU - Agarwal, Shivani

AU - Roth, Dan

PY - 2005/1/1

Y1 - 2005/1/1

N2 - 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 learnability 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 learnability of a class of ranking functions ℱ: we show that ℱ 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 learnability: we define a new combinatorial parameter for a class of ranking functions ℱ that we term the rank dimension of ℱ, and show that ℱ is learnable only if its rank dimension is finite. Finally, we investigate questions of the computational complexity of learning ranking functions.

AB - 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 learnability 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 learnability of a class of ranking functions ℱ: we show that ℱ 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 learnability: we define a new combinatorial parameter for a class of ranking functions ℱ that we term the rank dimension of ℱ, and show that ℱ is learnable only if its rank dimension is finite. Finally, we investigate questions of the computational complexity of learning ranking functions.

UR - http://www.scopus.com/inward/record.url?scp=26944498632&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26944498632&partnerID=8YFLogxK

U2 - 10.1007/11503415_2

DO - 10.1007/11503415_2

M3 - Conference contribution

AN - SCOPUS:26944498632

SN - 3540265562

SN - 9783540265566

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 16

EP - 31

BT - Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings

PB - Springer-Verlag Berlin Heidelberg

T2 - 18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory

Y2 - 27 June 2005 through 30 June 2005

ER -