Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Qianqian Ma;Alexander Olshevsky
中科院分区：
文献类型：
--
作者：
Qianqian Ma;Alexander Olshevsky
我们考虑了当一些显示的项被未知的并且可以任意大的扰动破坏时，从其显示的项的子集重构秩一矩阵的问题。目前还不知道哪些显示的条目已损坏。提出了一种交替极小化和极值滤波相结合的新算法，并给出了恢复原始一阶矩阵的充要条件。特别地，我们证明了当所揭示的项集由ERDőS-Renyi随机图给出时，我们所提出的算法是最优的。然后将这些结果应用于从众包数据中进行分类的问题，假设虽然大多数工人遵循标准的单硬币David-Skene模型(即，他们以一定的概率输出正确的答案)，但一些工人可以任意偏离该模型。特别是，“对抗性”的工作人员甚至可以做出旨在使算法输出不正确答案的决定。大量的实验结果表明，对于这个问题，我们的算法基于带扰动的秩一矩阵补全，在这种对抗性的场景中，我们的算法比所有其他最先进的方法都要好。
We consider the problem of reconstructing a rank-one matrix from a revealed subset of its entries when some of the revealed entries are corrupted with perturbations that are unknown and can be arbitrarily large. It is not known which revealed entries are corrupted. We propose a new algorithm combining alternating minimization with extreme-value filtering and provide sufficient and necessary conditions to recover the original rank-one matrix. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an Erdős-Renyi random graph. These results are then applied to the problem of classification from crowdsourced data under the assumption that while the majority of the workers are governed by the standard single-coin David-Skene model (i.e., they output the correct answer with a certain probability), some of the workers can deviate arbitrarily from this model. In particular, the "adversarial" workers could even make decisions designed to make the algorithm output an incorrect answer. Extensive experimental results show our algorithm for this problem, based on rank-one matrix completion with perturbations, outperforms all other state-of-the-art methods in such an adversarial scenario.