Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers
Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Yao Ma;Alexander Olshevsky;Csaba Szepesvari;Venkatesh Saligrama
中科院分区：
文献类型：
--
作者：
Yao Ma;Alexander Olshevsky;Csaba Szepesvari;Venkatesh Saligrama
我们考虑单币david - skene众包模型的工人技能估计。在实践中，技能评估是具有挑战性的，因为由于工人的任意和不受控制的可用性，工人分配是稀疏和不规则的。我们将技能估计表述为秩一相关矩阵补全问题，其中观察到的成分对应于观察到的工人之间的标签相关性。我们表明，当且仅当采样矩阵（观察到的成分）不具有二部连接成分时，相关矩阵可以成功恢复并且技能是可识别的。然后，我们提出了一个投影梯度下降方案，并证明技能估计收敛于这种采样矩阵的理想全局最优。我们的证明是原创的，并且考虑到即使是加权秩一矩阵分解问题在一般情况下也是np困难的事实，结果是令人惊讶的。接下来，我们根据采样矩阵的无符号拉普拉斯函数的谱性质推导出样本复杂度界。我们提出的方案在许多真实世界的数据集上实现了最先进的性能。
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.