CIF: Small: Collaborative Research: Rank Aggregation with Heterogeneous Information Sources: Efficient Algorithms and Fundamental Limits

CIF：小型：协作研究：异构信息源的排名聚合：高效算法和基本限制

• 批准号: 1911168
• 负责人: Quanquan Gu
• 金额: $ 25万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1911168&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Rank

While advances in the ability to collect and store data have made large data sets commonplace, these data sets increasingly consist of information obtained from different sources with various data types and properties that impede the ability to extract knowledge and make decisions. This project focuses on inferring the ranking of a set of objects from heterogeneous datasets with arbitrary noise, which is also known as rank aggregation with heterogeneous information sources. The developed algorithms will be made publicly available as open source software tools, and will significantly expand the applicability of rank aggregation to real-world problems, such as data fusion, information retrieval, crowd-sourcing, recommendation systems, as well as social choice and voting. This project will also provide educational and training opportunities and exposure to sophisticated statistical tools, rigorous theoretical analysis, and the empirical work of extracting knowledge from large heterogeneous data sets. In this project, based on statistical models of data, efficient and scalable rank aggregation algorithms for various settings will be developed along with performance guarantees and fundamental limits, in three complementary research thrusts. First, it will develop rank aggregation algorithms based on flexible latent probabilistic models that exploit side information and allow both ordinal and numerical data types. It will also provide information-theoretic lower bounds on the performance of such algorithms. Second, it will design robust algorithms for latent probabilistic models in which the unknown parameters are a superposition of many structured parameters, and models in which data can be corrupted by arbitrary noise. Finally, the problem of inferring a ranking through interactive bandit algorithms will be studied. This project aims to push the frontier of rank aggregation research, and can potentially advance research in machine learning, nonconvex optimization and information theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

虽然收集和存储数据的能力的进步使大型数据集变得司空见惯，但这些数据集越来越多地包含从不同来源获得的信息，这些信息具有各种数据类型和属性，阻碍了提取知识和决策的能力。该项目致力于从具有任意噪声的异质数据集中推断一组对象的排名，这也被称为具有异质信息源的排名聚合。开发的算法将作为开源软件工具公开提供，并将显著扩大排名聚合在现实世界问题中的适用性，如数据融合、信息检索、众包、推荐系统以及社会选择和投票。该项目还将提供教育和培训机会，接触复杂的统计工具、严格的理论分析以及从大型不同数据集中提取知识的经验工作。在这个项目中，基于数据的统计模型，将在三个互补的研究推进中开发各种设置的高效和可扩展的等级聚集算法，以及性能保证和基本限制。首先，它将开发基于灵活的潜在概率模型的排名聚合算法，该模型利用辅助信息，并允许顺序和数字数据类型。它还将为此类算法的性能提供信息论下限。其次，它将为未知参数是许多结构化参数叠加的潜在概率模型以及数据可能被任意噪声破坏的模型设计稳健的算法。最后，将研究通过交互式强盗算法来推断排名的问题。该项目旨在推动排名聚合研究的前沿，并有可能促进机器学习、非凸优化和信息论的研究。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits

• DOI: 10.48550/arxiv.2310.00968
• 发表时间: 2023-10
• 期刊: ArXiv
• 作者: Qiwei Di;Tao Jin;Yue Wu;Heyang Zhao;Farzad Farnoud;Quanquan Gu

Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

• 发表时间: 2021-02
• 作者: Yue Wu;Dongruo Zhou;Quanquan Gu

Active Ranking without Strong Stochastic Transitivity

• 发表时间: 2022
• 作者: Hao Lou;Tao Jin;Yue Wu;Pan Xu;Quanquan Gu;Farzad Farnoud

Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons

来自噪声成对比较的异构排名聚合的自适应采样

• 发表时间: 2022
• 期刊: International Conference on Artificial Intelligence and Statistics
• 作者: Wu, Yue;Jin, Tao;Lou, Hao;Xu, Pan;Farnoud, Farzad;Gu, Quanquan
• 通讯作者: Gu, Quanquan

Rank Aggregation via Heterogeneous Thurstone Preference Models

• DOI: 10.1609/aaai.v34i04.5860
• 发表时间: 2019-12
• 期刊: ArXiv
• 作者: Tao Jin;Pan Xu;Quanquan Gu;Farzad Farnoud