We consider worker skill estimation for the single-coin Dawid-Skene
crowdsourcing model. In practice, skill-estimation is challenging because
worker assignments are sparse and irregular due to the arbitrary and
uncontrolled availability of workers. We formulate skill estimation as a
rank-one correlation-matrix completion problem, where the observed components
correspond to observed label correlations between workers. We show that the
correlation matrix can be successfully recovered and skills are identifiable if
and only if the sampling matrix (observed components) does not have a bipartite
connected component. We then propose a projected gradient descent scheme and
show that skill estimates converge to the desired global optima for such
sampling matrices. Our proof is original and the results are surprising in
light of the fact that even the weighted rank-one matrix factorization problem
is NP-hard in general. Next, we derive sample complexity bounds in terms of
spectral properties of the signless Laplacian of the sampling matrix. Our
proposed scheme achieves state-of-art performance on a number of real-world
datasets.

本文提出了一种新的方法，将工人技能评估问题转化为一种秩为 1 的相关矩阵完成问题，并且展示出当采样矩阵不具有二分图连通部分时，相关矩阵可以成功恢复和技能可识别，此外，作者还推导出了基于采样矩阵符号 Laplacian 的样本复杂度界限，并且该方案在许多实际数据集上实现了最先进的性能。