RI: Small: Modern Machine Learning Algorithms for Ranking from Pairwise and Higher-Order Comparisons

RI：小型：用于通过成对和高阶比较进行排名的现代机器学习算法

• 批准号: 1717290
• 负责人: Shivani Agarwal
• 金额: $ 44.55万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717290&HistoricalAwards=false
• 关键词: RI; Small; Modern; Machine; Learning

The problem of ranking a large number of items from comparisons among a few items at a time plays a crucial role in many areas, including recommender systems, crowdsourcing, marketing, and econometrics. In modern settings, as the numbers of items to be ranked increase and corresponding datasets grow in size and complexity, it is critical to re-visit the classical algorithms currently used for these problems and to design new algorithms that can better scale to modern needs under fewer assumptions. This project will design modern machine learning algorithms for such problems, while training PhD students and postdoctoral scientists in the interdisciplinary skills needed to design novel machine learning algorithms for problems involving modern datasets. Other broader impacts of the project will also include organization of workshops and/or tutorials to disseminate the results of the research conducted here, survey articles aimed at conveying the ideas to a broad scientific audience, and activities designed to increase participation of under-represented groups in STEM education opportunities and careers. The problem of ranking from pairwise comparisons has been studied in several fields, including statistics, operations research, social choice, and computer science, and several algorithms have been developed; however, very little has been understood in terms of how these different algorithms relate to each other, under what conditions they succeed (or fail), and how insights from one can be used to improve another. Algorithms for ranking from higher-order comparisons are even less well understood. The project will develop a strong understanding of the conditions under which various pairwise ranking algorithms succeed (or fail), and use insights from this understanding to develop modern machine learning algorithms with strong performance guarantees for ranking from pairwise as well as higher-order comparisons. Specifically, the project will investigate the following three directions: (1) Understanding conditions on pairwise models under which current algorithms succeed or fail.(2) Design of new machine learning algorithms for ranking from pairwise comparisons.(3) Ranking from higher-order comparisons.The project will bring a unified perspective to the study of ranking from pairwise comparisons, which hitherto has been scattered across different disciplines; develop new machine learning algorithms that improve the state of the art for a variety of ranking objectives; and initiate a systematic study of ranking from higher-order comparisons, a nascent area at the intersection of machine learning, statistics and econometrics.

通过一次几个项目的比较对大量项目进行排名的问题在许多领域发挥着至关重要的作用，包括推荐系统、众包、营销和计量经济学。在现代环境中，随着要排序的项目数量的增加以及相应数据集的大小和复杂性的增加，重新审视当前用于这些问题的经典算法并设计能够更好地满足现代需求的新算法至关重要更少的假设。该项目将为此类问题设计现代机器学习算法，同时培训博士生和博士后科学家为涉及现代数据集的问题设计新颖的机器学习算法所需的跨学科技能。该项目的其他更广泛的影响还包括组织研讨会和/或教程来传播这里进行的研究结果，旨在向广大科学受众传达想法的调查文章，以及旨在增加代表性不足群体参与的活动STEM 教育机会和职业。成对比较的排序问题已在多个领域进行了研究，包括统计学、运筹学、社会选择和计算机科学，并开发了多种算法；然而，人们对这些不同算法如何相互关联、它们在什么条件下成功（或失败）以及如何利用一种算法的见解来改进另一种算法的了解知之甚少。通过高阶比较进行排序的算法甚至更不为人所知。该项目将深入了解各种成对排序算法成功（或失败）的条件，并利用这种理解中的见解来开发现代机器学习算法，为成对排序和高阶比较排序提供强大的性能保证。具体来说，该项目将研究以下三个方向：（1）了解当前算法成功或失败的成对模型条件。（2）设计新的机器学习算法，用于通过成对比较进行排序。（3）从高阶排序该项目将为成对比较的排名研究带来统一的视角，迄今为止这种研究分散在不同的学科中；开发新的机器学习算法，提高各种排名目标的技术水平；并启动对高阶比较排名的系统研究，这是机器学习、统计学和计量经济学交叉领域的一个新兴领域。

项目成果

Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions

在存在对抗性腐败的情况下，通过两两比较进行排名聚合

• 发表时间: 2020-01
• 期刊: Proceedings of the 37th International Conference on Machine Learning
• 作者: Agarwal, Arpit;Agarwal, Shivani;Khanna, Sanjeev;Patil, Prathamesh
• 通讯作者: Patil, Prathamesh

Choice bandits

选择强盗

• 发表时间: 2020-01
• 期刊: Advances in neural information processing systems
• 作者: Agarwal, A;Johnson, N;Agarwal, S
• 通讯作者: Agarwal, S

Accelerated Spectral Ranking

加速光谱排名

• 发表时间: 2018-07
• 期刊: Proceedings of Machine Learning Research
• 作者: Agarwal, Arpit;Patil, Prathamesh;Agarwal, Shivani
• 通讯作者: Agarwal, Shivani

Bayes Consistency vs. H-Consistency: The Interplay between Surrogate Loss Functions and the Scoring Function Class

贝叶斯一致性与 H 一致性：代理损失函数和评分函数类之间的相互作用

• 发表时间: 2020-01
• 期刊: Advances in neural information processing systems
• 作者: Zhang, M;Agarwal, S
• 通讯作者: Agarwal, S

Accelerated Spectral Ranking

加速光谱排名

• 发表时间: 2018-01
• 期刊: Proceedings of the 35th International Conference on Machine Learning
• 作者: Agarwal, Arpit;Patil, Prathamesh;Agarwal, Shivani
• 通讯作者: Agarwal, Shivani