Learnability of bipartite ranking functions

Shivani Agarwal, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationLearning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages16-31
Number of pages16
ISBN (Print)3540265562, 9783540265566
DOIs
StatePublished - Jan 1 2005
Event18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory - Bertinoro, Italy
Duration: Jun 27 2005Jun 30 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3559 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory
CountryItaly
CityBertinoro
Period6/27/056/30/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Learnability of bipartite ranking functions'. Together they form a unique fingerprint.

Cite this