  In the domains of dataset construction and crowdsourcing, a notable challenge
is to aggregate labels from a heterogeneous set of labelers, each of whom is
potentially an expert in some subset of tasks (and less reliable in others). To
reduce costs of hiring human labelers or training automated labeling systems,
it is of interest to minimize the number of labelers while ensuring the
reliability of the resulting dataset. We model this as the problem of
performing $K$-class classification using the predictions of smaller
classifiers, each trained on a subset of $[K]$, and derive bounds on the number
of classifiers needed to accurately infer the true class of an unlabeled sample
under both adversarial and stochastic assumptions. By exploiting a connection
to the classical set cover problem, we produce a near-optimal scheme for
designing such configurations of classifiers which recovers the well known
one-vs.-one classification approach as a special case. Experiments with the
MNIST and CIFAR-10 datasets demonstrate the favorable accuracy (compared to a
centralized classifier) of our aggregation scheme applied to classifiers
trained on subsets of the data. These results suggest a new way to
automatically label data or adapt an existing set of local classifiers to
larger-scale multiclass problems.
