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.

尽管收集和存储数据的能力的进步使大量数据集使大量数据集司空见惯，但这些数据集越来越多地包括从不同来源获得的信息，这些信息具有各种数据类型和属性，这些信息和属性会阻碍提取知识和做出决策的能力。该项目着重于从具有任意噪声的异质数据集中推断一组对象的排名，这也称为具有异质信息源的等级聚合。已开发的算法将作为开源软件工具公开提供，并将大大扩展等级聚合到现实世界中问题的适用性，例如数据融合，信息检索，众包，推荐系统以及社交选择和投票。该项目还将提供教育和培训机会，并接触复杂的统计工具，严格的理论分析以及从大型异构数据集中提取知识的经验工作。在该项目中，基于数据的统计模型，将在三个互补的研究推力中开发各种设置的高效且可扩展的等级聚合算法以及性能保证和基本限制。首先，它将基于灵活的潜在概率模型开发等级聚合算法，该模型利用侧面信息并允许序数和数值数据类型。它还将提供有关此类算法性能的信息理论下限。其次，它将为潜在概率模型设计强大的算法，其中未知参数是许多结构化参数的叠加，并且可以通过任意噪声损坏数据的模型。最后，将研究通过交互式强盗算法推断排名的问题。该项目旨在推动等级汇总研究的边界，并有可能在机器学习，非convex优化和信息理论方面提高研究。该奖项反映了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

Rank Aggregation via Heterogeneous Thurstone Preference Models

• DOI: 10.1609/aaai.v34i04.5860
• 发表时间: 2019-12
• 期刊: ArXiv
• 作者: Tao Jin;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