Efficient PAC Learning from the Crowd
Efficient PAC Learning from the Crowd
复制标题
DOI：
--
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Pranjal Awasthi;Avrim Blum;Nika Haghtalab;Y. Mansour
中科院分区：
文献类型：
--
作者：
Pranjal Awasthi;Avrim Blum;Nika Haghtalab;Y. Mansour
近年来，众包已成为为学习算法收集标记训练数据的首选方法。众包的标准方法将获取标记数据的过程与从收集的数据中学习分类器的过程分开。这可能会带来计算和统计方面的挑战。例如，在大多数情况下，没有已知的计算效率高的学习算法对众包数据中存在的高水平噪声具有鲁棒性，并且通过投票消除噪声的努力通常需要每个示例进行大量查询。在本文中，我们展示了如何通过交错标记和学习的过程，我们可以以更少的标记成本来获得计算效率。特别是，我们考虑可实现的设置，存在一个真正的目标函数在F和考虑一个池的标签。当一个明显的分数的标签是完美的，其余的行为任意，我们表明，任何F，可以有效地学习在传统的可实现的PAC模型可以学习在一个计算效率的方式通过查询人群，尽管大量的噪音的反应。此外，我们表明，这是可以做到的，而每个标签只标记一个恒定数量的例子和标签的数量要求每个例子，平均而言，是一个常数。当不存在完美的标签器时，一个相关的任务是找到一组好的但不完美的标签器。我们表明，我们可以识别所有好的标签，当至少大多数的标签是好的。
In recent years crowdsourcing has become the method of choice for gathering labeled training data for learning algorithms. Standard approaches to crowdsourcing view the process of acquiring labeled data separately from the process of learning a classifier from the gathered data. This can give rise to computational and statistical challenges. For example, in most cases there are no known computationally efficient learning algorithms that are robust to the high level of noise that exists in crowdsourced data, and efforts to eliminate noise through voting often require a large number of queries per example. In this paper, we show how by interleaving the process of labeling and learning, we can attain computational efficiency with much less overhead in the labeling cost. In particular, we consider the realizable setting where there exists a true target function in F and consider a pool of labelers. When a noticeable fraction of the labelers are perfect, and the rest behave arbitrarily, we show that any F that can be efficiently learned in the traditional realizable PAC model can be learned in a computationally efficient manner by querying the crowd, despite high amounts of noise in the responses. Moreover, we show that this can be done while each labeler only labels a constant number of examples and the number of labels requested per example, on average, is a constant. When no perfect labelers exist, a related task is to find a set of the labelers which are good but not perfect. We show that we can identify all good labelers, when at least the majority of labelers are good.