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.