# Computing a bootstrap confidence interval for the prediction error with the percentile and the BCa method

I have two related questions regarding the computation of a non-parametric bootstrap confidence interval for the prediction error.

Setting: I have a sample S from a data population P and a learner L, and I want to compute a 95% confidence interval for the 0.632 bootstrap estimator $\hat{\theta}_{.632bs}$ of the prediction error $\theta$ of the classifier C learned by learner L on sample S.

Q1 My first question is whether the following procedure, to compute the confidence interval with the percentile method, is correct. Specifically, the sampling of a test set $S_{test}$ in step 2 to evaluate my classifier on. I have read that, for every observation, you have to keep track of predictions from bootstrap samples not containing that observation. This seems to come down to the same thing according to me? I compute the confidence interval with the percentile method as follows:

1. I compute the resubstitution error $\theta_{resub}$ of the classifier C learned by L on S
2. I compute N (e.g. = 1000) bootstrap estimates $\hat{\theta}_i^*$ of the prediction error on S as follows:

For i = 1 : 1000 do:

• Sample from S with replacement until I have a new sample $S_{train}$ the same size as S
• From all the instances that were not sampled in step 1, I sample again with replacement until I have a sample $S_{test}$ with the same size as S
• I learn a classifier on $S_{train}$ and evaluate it on $S_{test}$. The classifier performance on $S_{test}$ is my bootstrap estimate $\hat{\theta}_i^*$.
3. For each sample i of the N bootstrap samples I compute the estimate $\hat{\theta}^*_{i,.632bs}$ as $\hat{\theta}^*_{i,.632bs} = 0.368 \cdot \theta_{resub} + 0.632 \cdot \hat{\theta}_i^*$

4. I sort the 1000 bootstrap estimates
5. I select the 25th bootstrap estimate as the lower bound of the confidence interval and the 975th estimate as the upper bound of the confidence interval.

Q2 My second question is how to compute the confidence interval for the 0.632 bootstrap estimator for the prediction error with the bias corrected accelerated (BCa) method. Namely, I find that I have a problem here: I need an estimate of a term $b$ for the bias correction, and for term $a$, the acceleration term (http://www.tau.ac.il/~saharon/Boot/10.1.1.133.8405.pdf p1153-1154).

• To compute $b$, I need an estimate of the prediction error $\hat{\theta}$ from the complete sample S. I am not sure how to do this. I see several possibilities: The average of $\hat{\theta}^*_{i,.632bs}$ over all $i$, the resubstitution error, a hold-out error, perform cross-validation on S...?
• I have the same problem for computing $a$. Here, I need jackknife estimates that use all of the data from S except one instance $x_i$ ($S \setminus x_i$). What exactly do I compute here? Is this computation the same as computing the leave-one-out cross-validation estimator for the prediction error?

I have tried finding the answers in the literature, but I have difficulty understanding the papers I found, so I hope somebody can help me here. Thank you!

• Did you ever manage to solve this problem? I'm having the same issue right now. – gibberfish Mar 20 '15 at 22:56

The 0.632 bootstrap estimator $$\hat{\theta}_{.632bs}$$ is a point estimator for a prediction error, which simply is a binomial proportion. You are thus seeking a confidence interval for a binomial proportion. As this parameter is known to strictly follow a binomial distribution, there is no point in sampling it, as confidence intervals with known and exacly computable coverage probilities are readily available.
To be on the safe side, especially when the prediction error is close to one, you can use the "exact" Clopper-Pearson interval, which is guaranteed to have a coverage probability $$P_{cov}\geq 0.95$$. For an approximate confidence interval, Brown at al. recommend the Wilson interval in