Report: The Error-Reject Tradeoff

[Lars Kai Hansen]

FTP-host:  eivind.ei.dth.dk [129.142.65.123] 
FTP-file:  /dist/hansen_reject.ps.Z

[30 pages; 400kb uncompressed]
                                  
The following technical report is available by anonymous ftp from the
Electronics Institute ftp-server. Hardcopies are not available.

-------------------------------------------------------------------------------
  
                             
                    "THE ERROR-REJECT TRADEOFF" 
                     


Lars Kai Hansen          Christian Liisberg           Peter Salamon
CONNECT,                 Applied Bio Cybernetics      Dept. of Math. Sciences
Electronics Inst. B349   DK-3390 Hundested,           San Diego State University
Tech. Univ. Denmark      Denmark                      San Diego CA 92182 USA,
DK-2800 Lyngby, 
Denmark                   


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.   
                  
------------------------------------------------------------------------------------
                                        
-  Lars Kai Hansen   lkhansen at ei.dtu.dk