MSPA-MCS: Learning to Rank

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

During the last few decades, considerable progress has been made in the understanding of binary classification (learning of binary-valued functions) and regression (learning of real-valued functions), both classical problems in machine learning. Although several questions remain to be answered, there is a well-developed theory in place for these problems, and practical successes have been demonstrated in a variety of applications. Recently, a new learning problem, namely that of ranking, has begun to gain attention. In ranking, one learns a real-valued function that assigns scores to objects, but the scores themselves do not matter; instead, what is important is the relative ranking of objects induced by those scores. This problem is distinct from both classification and regression, and cannot be analyzed using existing results for these problems. Consequently, there is a need for a separate theoretical understanding for ranking. This project aims to develop such an understanding. Specifically, the project will investigate three directions: (1) Generalization bounds for ranking; (2) Learnability of ranking functions; and (3) Transductive ranking. Ranking has applications in a vast number of domains: in information retrieval, one wants to rank documents according to relevance to some query or topic; in user-preference modeling, one wants to rank books or movies according to a user''''s likes and dislikes; in computational biology, one wants to rank genes according to their relevance to some disease. Currently, the mathematical properties of ranking are not well understood; save in a few special cases, not much is known about what kinds of ranking functions can be learned, how the performance of a learned ranking function on the training data translates to its expected performance on future data, and so on. By addressing these questions, the project will provide both a better mathematical understanding of ranking, and a strong theoretical foundation for its applications.