Efficient PAC Learning from the Crowd with Pairwise Comparisons
Efficient PAC Learning from the Crowd with Pairwise Comparisons
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Shiwei Zeng;Jie Shen
中科院分区：
文献类型：
--
作者：
Shiwei Zeng;Jie Shen
我们研究阈值函数的众包 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.