Crowdsourcing: Low complexity, Minimax Optimal Algorithms
Crowdsourcing: Low complexity, Minimax Optimal Algorithms
复制标题
众包：低复杂度、极小极大最优算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Richard Combes
中科院分区：
文献类型：
--
作者：
T. Bonald;Richard Combes
我们考虑基于工人提供的噪声标签准确估计工人可靠性的问题，这是众包中的一个基本问题。我们提出了一个新的最小最大估计误差下界，它适用于任何估计过程。我们进一步提出了三角估计（TE），一种估计工人可靠性的算法。TE具有较低的复杂性，当工人实时提供标签时，可以在流设置中实现，并且不依赖于迭代过程。进一步证明了TE是极小极大最优的，并且匹配我们的下界。最后，我们评估了TE和其他最先进算法在合成数据集和真实数据集上的性能。
We consider the problem of accurately estimating the reliability of workers based on noisy labels they provide, which is a fundamental question in crowdsourcing. We propose a novel lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We further prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data sets.