Semi-Verified PAC Learning from the Crowd
Semi-Verified PAC Learning from the Crowd
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Shiwei Zeng;Jie Shen
中科院分区：
文献类型：
--
作者：
Shiwei Zeng;Jie Shen
我们研究阈值函数的众包 PAC 学习问题。这是一个具有挑战性的问题，直到最近才在假设相当一部分工作人员是完美的情况下建立了查询高效的算法。在这项工作中，我们研究了一个更具挑战性的案例，其中大多数人可能表现出敌对性，而其余的人则表现得像马萨特噪声——完美性假设的重要概括。我们在 Charikar 等人的{半验证模型}下证明了这一点。 （2017），我们可以（有限）访问始终返回正确注释的可信预言机，PAC 可以通过可管理数量的标签查询来学习底层假设类。此外，我们表明，通过更容易获得的比较查询可以大大降低标签成本。与半验证或列表可解码学习的最新发展正交，这些学习主要依赖于数据分布假设，我们的 PAC 保证通过探索人群的智慧而成立。
We study the problem of crowdsourced PAC learning of threshold functions. This is a challenging problem and only recently have query-efficient algorithms been established under the assumption that a noticeable fraction of the workers are perfect. In this work, we investigate a more challenging case where the majority may behave adversarially and the rest behave as the Massart noise - a significant generalization of the perfectness assumption. We show that under the {semi-verified model} of Charikar et al. (2017), where we have (limited) access to a trusted oracle who always returns correct annotations, it is possible to PAC learn the underlying hypothesis class with a manageable amount of label queries. Moreover, we show that the labeling cost can be drastically mitigated via the more easily obtained comparison queries. Orthogonal to recent developments in semi-verified or list-decodable learning that crucially rely on data distributional assumptions, our PAC guarantee holds by exploring the wisdom of the crowd.