IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

A Study of the Bipartite Ranking Problem in Machine Learning

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF A Study of the ... em in Machine Learning.pdf (861KB) (no description provided) PDF
Title: A Study of the Bipartite Ranking Problem in Machine Learning
Author(s): Agarwal, Shivani
Subject(s): machine learning
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. A particular setting of interest is the bipartite ranking problem, in which instances come from two categories, positive and negative; the learner is given examples of instances labeled as positive or negative, and the goal is to learn from these examples a ranking function that ranks future positive instances higher than negative ones. This thesis makes four important contributions to the understanding of the bipartite ranking problem. First, we derive large deviation and uniform convergence bounds for the bipartite ranking error, a quantity used to measure the quality of a bipartite ranking function. The large deviation bound serves to bound the expected error of a ranking function in terms of its empirical error on an independent test sample; the uniform convergence bound serves to bound the expected error of a learned ranking function in terms of its empirical error on the training sample from which it is learned. The uniform convergence bound is expressed in terms of a new set of combinatorial parameters that we term the bipartite rank-shatter coefficients. Second, we define a model of learnability for bipartite ranking functions, and derive a number of results in this model. In particular, we derive both upper and lower bounds on the sample complexity of learning ranking functions in this model. The upper bound is expressed in terms of the bipartite rank-shatter coefficients. The lower bound is expressed in terms of another new combinatorial parameter that we term the rank dimension. Third, we derive generalization bounds for bipartite ranking algorithms based on the notion of algorithmic stability. Unlike bounds based on uniform convergence, these bounds can be applied also to algorithms that search function classes of unbounded complexity. In particular, we are able to apply our results to obtain generalization bounds for kernel-based ranking algorithms, to which bounds based on uniform convergence are often not applicable. Finally, we demonstrate a practical application of bipartite ranking to a problem in bioinformatics, namely the problem of identifying genes related to a given disease based on microarray data. Our studies on leukemia and colon cancer data sets show very promising results, including the identification of some exciting candidate genes as potential targets for drug development.
Issue Date: 2005-05
Genre: Technical Report
Type: Text
Other Identifier(s): UIUCDCS-R-2005-2529
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-17

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 741
  • Downloads this Month: 10
  • Downloads Today: 0


My Account


Access Key