论文标题
通过成对比较向人群学习有效的PAC
Efficient PAC Learning from the Crowd with Pairwise Comparisons
论文作者
论文摘要
我们研究了众包PAC学习阈值功能，其中标签是从一个注释池中收集的一些标签，其中一些人可能会在对手方面行事。这仍然是一个具有挑战性的问题，直到最近，Awasthi等人建立了计算和查询有效的PAC学习算法。 （2017）。在本文中，我们表明，通过利用更容易获得的成对比较查询，可以指数降低标签复杂性，同时保留整体查询复杂性和运行时。我们的主要算法贡献是配备了比较的标签方案，它可以忠实地恢复一小部分实例的真实标签，并且具有标签有效的过滤过程，该过程与小标记集合可以可靠地推断出大实例集的真实标签。
We study crowdsourced PAC learning of threshold functions, where the labels are gathered from a pool of annotators some of whom may behave adversarially. This is yet a challenging problem and until recently has computationally and query efficient PAC learning algorithm been established by Awasthi et al. (2017). In this paper, we show that by leveraging the more easily acquired pairwise comparison queries, it is possible to exponentially reduce the label complexity while retaining the overall query complexity and runtime. Our main algorithmic contributions are a comparison-equipped labeling scheme that can faithfully recover the true labels of a small set of instances, and a label-efficient filtering process that in conjunction with the small labeled set can reliably infer the true labels of a large instance set.
