Social computation: Fundamental limits and efficient algorithms

Ranking, Crowdsourcing

Khetan, Ashish Kumar

关键词: Ranking, Crowdsourcing;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/100996/KHETAN-DISSERTATION-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Social computing systems bring enormous value to society byharnessing the data generated by the members of a community. Though each individual reveals a little information through his online traces, collectively this information gives significant insights on the societal preferences that can be used in designing better systems for the society. Challenging societal problems can be solved using the collective power of a crowd wherein each individual offers only a limited knowledge on a specifically designed online platform. There exists general approaches to design such online platforms, to aggregate the collected data, and to use them for the downstream tasks, but are typically sub-optimal and inefficient. In this work, we investigate several social computing problems and provide efficient algorithms for solving them. This work studies several topics: (a) designing efficient algorithms for aggregating preferences from partially observed traces of online activities, and characterizing the fundamental trade-off between the computational complexity and statistical efficiency; (b) characterizing the fundamental trade-off between the budget and accuracy in aggregated answers in crowdsourcing systems, and designing efficient algorithms for training supervised learning models using the crowdsourced answers; (c) designing efficient algorithms for estimating fundamental spectral properties of a partially observed data such as a movie rating data matrix in recommendation systems, and connections in a large network.