CAREER: Social Computation: Fundamental Limits and Efficient Algorithms

社会计算系统通过利用社区成员产生的数据为社会带来巨大的价值。虽然每个人只能提供有限的知识、时间和努力，但一群人在一起可以解决具有挑战性的社会问题。从人群中汇总此类数据的一般方法是存在的，但通常是次优和低效的。本项目应用信息理论技术来探索社会计算中基本的样本/计算/精度权衡。拟议研究的成功将推动社会的进步，使社会能够有效地从其成员的活动中学习，以实现更大的社会利益。拟议的研究与一项教育计划紧密结合，该计划旨在开发一门关于社会计算算法基础的新研究生课程，以及将社会计算技术集成到教育领域的创新自适应学习平台。该项目将研究几个主题：(1)通过应用信息理论工具和方法，描述可用预算与众包平台中答案准确性之间的基本权衡；(2)利用谱图理论和编码理论的技术，设计有效的算法来实现这一基本的权衡，并应用一系列新颖的秩分解方法来降低复杂性；(3)描述从部分观察到的在线和移动活动的痕迹中汇总偏好的计算复杂性、样本量和准确性之间的三方面基本权衡。

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.