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 -