Efficient PAC Learning from the Crowd
  In recent years crowdsourcing has become the method of choice for gathering
labeled training data for learning algorithms. Standard approaches to
crowdsourcing view the process of acquiring labeled data separately from the
process of learning a classifier from the gathered data. This can give rise to
computational and statistical challenges. For example, in most cases there are
no known computationally efficient learning algorithms that are robust to the
high level of noise that exists in crowdsourced data, and efforts to eliminate
noise through voting often require a large number of queries per example.
  In this paper, we show how by interleaving the process of labeling and
learning, we can attain computational efficiency with much less overhead in the
labeling cost. In particular, we consider the realizable setting where there
exists a true target function in $\mathcal{F}$ and consider a pool of labelers.
When a noticeable fraction of the labelers are perfect, and the rest behave
arbitrarily, we show that any $\mathcal{F}$ that can be efficiently learned in
the traditional realizable PAC model can be learned in a computationally
efficient manner by querying the crowd, despite high amounts of noise in the
responses. Moreover, we show that this can be done while each labeler only
labels a constant number of examples and the number of labels requested per
example, on average, is a constant. When no perfect labelers exist, a related
task is to find a set of the labelers which are good but not perfect. We show
that we can identify all good labelers, when at least the majority of labelers
are good.
