MSPA-MCS: Learning to Rank

在过去的几十年里，在理解二元分类（二值函数的学习）和回归（实值函数的学习）方面取得了相当大的进展，这两个都是机器学习中的经典问题。虽然还有几个问题有待回答，但对于这些问题，已经有了一个完善的理论，并且在各种应用中已经证明了实际的成功。最近，一个新的学习问题，即排名问题，开始引起人们的关注。在排序中，人们学习了一个实值函数，该函数为对象分配分数，但分数本身并不重要；相反，重要的是由这些分数引起的物体的相对排名。这个问题不同于分类和回归，不能使用这些问题的现有结果进行分析。因此，有必要对排名进行单独的理论理解。本项目旨在发展这样一种认识。具体而言，该项目将研究三个方向：(1)排序的概化界限；(2)排序函数的可学习性；(3)转导排序。排名在许多领域都有应用：在信息检索中，人们希望根据与某些查询或主题的相关性对文档进行排名；在用户偏好建模中，人们希望根据用户的好恶对书籍或电影进行排名；在计算生物学中，人们希望根据基因与某种疾病的相关性对它们进行排序。目前，排名的数学性质还没有被很好地理解；除了在少数特殊情况下，对于可以学习哪种排序函数、学习到的排序函数在训练数据上的性能如何转化为其在未来数据上的预期性能等问题，我们知之甚少。通过解决这些问题，该项目将为排名提供更好的数学理解，并为其应用提供强大的理论基础。

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.