CAREER: Social Computation: Fundamental Limits and Efficient Algorithms

职业：社会计算：基本限制和高效算法

• 批准号: 1927712
• 负责人: Sewoong Oh
• 金额: $ 39.41万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-01-01 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1927712&HistoricalAwards=false
• 关键词: CAREER; Social; Computation; Fundamental; Limits

Social computing systems bring enormous value to society by harnessing the data generated by members of a community. While each individual alone can offer only limited knowledge, time, and effort, a crowd together can solve challenging societal problems. General approaches to aggregate such data from crowds exists, but are typically suboptimal and inefficient. This project applies information-theoretic techniques to explore the fundamental sample/computation/accuracy trade-offs in social computing. The success of the proposed research will make progress towards a society that efficiently learns from the activities of its members for greater societal good. The proposed research is strongly integrated with an education plan that aims to develop a new graduate course on algorithmic foundations of social computing and innovative adaptive learning platforms that integrates the technology of social computing into the domain of education. The project will investigate several topics: (1) characterizing the fundamental trade-offs between the available budget and the accuracy of the answers in crowd-sourcing platforms, by applying information-theoretic tools and methods; (2) designing efficient algorithms achieving this fundamental trade-off using techniques from spectral graph theory and coding theory, as well as by applying a family of novel rank-breaking approaches to reduce complexity; and (3) characterizing the three-way fundamental trade-offs between computational complexity, sample size, and accuracy in aggregating preferences from partially observed traces of online and mobile activities.

社会计算系统通过利用社区成员产生的数据为社会带来了巨大的价值。尽管每个人都只能提供有限的知识，时间和精力，但人群在一起可以解决具有挑战性的社会问题。存在从人群中汇总此类数据的一般方法，但通常是次优和效率低下的。该项目应用信息理论技术来探索社交计算中的基本样本/计算/准确性权衡。拟议的研究的成功将使一个社会有效地从其成员的活动中学习以获得更大的社会利益。拟议的研究与一项教育计划完全融合，该计划旨在开发一个新的研究生课程，以社会计算的算法基础和创新的自适应学习平台，将社会计算技术整合到教育领域。该项目将调查几个主题：（1）通过应用信息理论工具和方法来表征可用预算与人群平台中答案准确性之间的基本权衡； （2）设计有效的算法，使用光谱图理论和编码理论的技术以及采用一种新型的破坏性方法来降低复杂性来实现这一基本权衡； （3）表征计算复杂性，样本量和准确性之间的三向基本权衡，从部分观察到的在线和移动活动中汇总偏好。