论文标题
通过强大的排名矩阵完成的对抗性众包
Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
论文作者
论文摘要
当某些揭示的条目被未知的扰动损坏并且可以任意大的扰动时，我们考虑从其条目的一个揭示子集中重建排名一的矩阵的问题。尚不清楚哪些揭示条目被损坏。我们提出了一种新算法，将交替最小化与极值过滤结合在一起，并提供足够的必要条件以恢复原始的排名矩阵。特别是，我们表明，当eRdős-rényi随机图给出一组显示的条目时，我们提出的算法是最佳的。然后将这些结果应用于众包数据的分类问题，假设大多数工人受标准的单克胶戴维 - 基因模型的控制（即，他们以一定的可能性输出正确的答案），但一些工人可以任意偏离该模型。特别是，“对抗性”的工人甚至可以做出旨在使算法输出不正确的答案的决定。广泛的实验结果表明，基于对扰动的排名矩阵完成，我们的算法优于这种对抗性情况下的所有其他最新方法。
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-Rényi 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.
