  Consider an ensemble of $k$ individual classifiers whose accuracies are
known. Upon receiving a test point, each of the classifiers outputs a predicted
label and a confidence in its prediction for this particular test point. In
this paper, we address the question of whether we can determine the accuracy of
the ensemble. Surprisingly, even when classifiers are combined in the
statistically optimal way in this setting, the accuracy of the resulting
ensemble classifier cannot be computed from the accuracies of the individual
classifiers-as would be the case in the standard setting of confidence weighted
majority voting. We prove tight upper and lower bounds on the ensemble
accuracy. We explicitly construct the individual classifiers that attain the
upper and lower bounds: specialists and generalists. Our theoretical results
have very practical consequences: (1) If we use ensemble methods and have the
choice to construct our individual (independent) classifiers from scratch, then
we should aim for specialist classifiers rather than generalists. (2) Our
bounds can be used to determine how many classifiers are at least required to
achieve a desired ensemble accuracy. Finally, we improve our bounds by
considering the mutual information between the true label and the individual
classifier's output.
