Efficient PAC Learning from the Crowd with Pairwise Comparisons
This work addresses the challenge of efficient learning from noisy crowdsourced data, which is incremental as it builds on prior methods by introducing a novel query type.
The paper tackles the problem of crowdsourced PAC learning of threshold functions with adversarial annotators by using pairwise comparison queries, resulting in an exponential reduction in label complexity while maintaining query complexity and runtime.
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.