2016/10/05 by Ravi Kiran Raman, Lav R. Varshney, Raman, Ravi Kiran +1
Computer Science · Decision Sciences · #Auction Theory and Applications #FOS: Computer and information sciences #Human-Computer Interaction (cs.HC) #Information Theory (cs.IT) #Machine Learning (stat.ML) #Mobile Crowdsensing and Crowdsourcing #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1610.02276
openalex publication_date 2016/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider unsupervised clustering of objects drawn from a discrete set, through the use of human intelligence available in crowdsourcing platforms. This paper defines and studies the problem of universal clustering using responses of crowd workers, without knowledge of worker reliability or task difficulty. We model stochastic worker response distributions by incorporating traits of memory for similar objects and traits of distance among differing objects. We are particularly interested in two limiting worker types---temporary workers who retain no memory of responses and long-term workers with memory. We first define clustering algorithms for these limiting cases and then integrate them into an algorithm for the unified worker model. We prove asymptotic consistency of the algorithms and establish sufficient conditions on the sample complexity of the algorithm. Converse arguments establish necessary conditions on sample complexity, proving that the defined algorithms are asymptotically order-optimal in cost.