Confidence interval for classification error: binomial assumption vs. bootsrap resampling I am developing a classifier using a set of N patterns, where N~1000. I am using K-fold cross-validation (with K=5) and computing the probability of classification error p (typical value is p=0.03).  I am also computing estimates of the 95% confidence interval; I do this by assuming the classifier output is binomial distributed (see Brown, Cai, & DasGupta, Anirban, “Interval Estimation for a Binomial Proportion”, Statistical Science, 16, 2, 2001, pp. 101-133).  
Now to my question.  I have also heard mention of using bootstrapping to measure confidence intervals.  I don't have a feel for why you would need to use a resampling method; can we not assume the number of errors to be binomial distributed?  Does the cross-validation screw this up?  Is resampling only necessary if N and p are such that directly estimating the confidence interval becomes difficult/impossible?  
This seems like a question that would come up any time the performance of a classifier is being analyzed.
 A: The proportion classified correctly is an improper scoring rule (i.e., it is optimized by a bogus model) and is a discontinuous function of the data.  Therefore the methods used to estimate its statistical properties need to be more carefully chosen.  For bootstrapping, the particular variant of the bootstrap you choose will matter, whereas for proper and semi-proper scoring rules (e.g., ROC area = c-index) the bootstrap variant matters very little.
Here is an R example showing one problem with proportion classified correctly.  The cutoff chosen for a predicted Y=1 is 0.5.
require(rms)
n <- 400
## Function to compute ROC area (C-index), proportion classified correctly
## and LR chi-square
ac <- function(f, y, cutoff=0.5) {
  if(!length(f)) c(0.5, 0, mean(y)) else {
    s <- f$stats
    c(cindex=s['C'], lr=s['Model L.R.'],
      prop=mean((predict(f, type='fitted') > cutoff)==y))
  }

}
h <- function(cutoff=0.5) {  
  age <- rnorm(n, 50, 12)
  sex <- factor(sample(c('m','f'), n, replace=TRUE))
  L <- (age-50)*.04 + .75*(sex=='m')
  y <- ifelse(runif(n) < plogis(L), 1, 0)
  if(is.na(cutoff)) cutoff <- mean(y)
  w <- rbind(ac(NULL, y, cutoff), ac(lrm(y ~ age), y, cutoff),
             ac(lrm(y ~ sex), y, cutoff),
             ac(lrm(y ~ age + sex), y, cutoff))
  dimnames(w) <- list(c('none','age','sex','age+sex'),
                      c('C-index','LR Chi-square','Proportion Correct'))
  print(round(w,3))
  invisible(data.frame(age, sex, y))
}


set.seed(26)
h()

        C-index LR Chi-square Proportion Correct
none      0.500         0.000              0.572
age       0.592        10.520              0.622
sex       0.589        12.373              0.588
age+sex   0.639        22.848              0.600

You can see that with no predictors you get 0.57 correct by predicting every outcome to be Y=1 (this is the observed proportion of Y=1).  The sex variable adds highly significant information to the model as judged by the gold standard likelihood ratio $\chi^2$ statistic, but adding sex to age actually decreases the proportion classified correctly, implying that the sex variable contains negative information.
