Semi-verified PAC Learning from the Crowd
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Tag-Evol: Achieving Efficient Instruction Evolving via Tag Injection
Towards Actionable Pedagogical Feedback: A Multi-Perspective Analysis of Mathematics Teaching and Tutoring Dialogue
Lean Formalization of Generalization Error Bound by Rademacher Complexity
Scaling Rich Style-Prompted Text-to-Speech Datasets
Tag-Pag: A Dedicated Tool for Systematic Web Page Annotations
TAG: A Decentralized Framework for Multi-Agent Hierarchical Reinforcement Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.