THE ERROR-REJECT TRADEOFF
Lars Kai Hansen
CONNECT, Electronics Institute B349
The Technical University of Denmark
DK-2800 Lyngby, Denmark,
lkhansen@ei.dtu.dk
Christian Liisberg
Applied Bio Cybernetics
Overdrevsvej
DK-3390 Hundested, Denmark
abcyabc@pop.denet.dk
Peter Salamon
Dept. of Mathematical Sciences
San Diego State University
San Diego CA 92182 USA,
salamon@math.sdsu.edu
Abstract:
We investigate the error versus reject tradeoff for classifiers.
Our analysis is motivated by the remarkable similarity in error-reject
tradeoff curves for widely differing algorithms classifying handwritten
characters. We present the data in a new scaled version that makes this
universal character particularly evident.
Based on Chow's theory of the error-reject tradeoff and its underlying
Bayesian analysis we argue that such universality is in fact to be
expected for general classification problems. Furthermore, we extend
Chow's theory to classifiers working from finite samples on a broad,
albeit limited, class of problems.
The problems we consider are _effectively binary_, i.e., classification
problems for which almost all inputs involve a choice between the right
classification and at most one predominant alternative.
We show that for such problems at most half of the initially rejected
inputs would have been erroneously classified. We show further that
such problems arise naturally as small perturbations of the PAC model
for large training sets. The perturbed model leads us to conclude that
the dominant source of error comes from pairwise overlapping categories.
For infinite training sets, the overlap is due to noise and/or poor
preprocessing. For finite training sets there is an additional
contribution from the inevitable displacement of the decision boundaries
due to finiteness of the sample. In either case, a rejection mechanism which
rejects inputs in a shell surrounding the decision boundaries leads to
a universal form for the error-reject tradeoff. Finally we analyze a
specific reject mechanism based on the extent of consensus among an
ensemble of classifiers. For the ensemble reject mechanism we find
an analytic expression for the error-reject tradeoff based on a maximum
entropy estimate of the problem difficulty distribution.
Keywords: error-reject tradeoff, handwritten digits,
ensembles, neural networks.