# What is the .632+ rule in bootstrapping?

Here @gung makes reference to the .632+ rule. A quick Google search doesn't yield an easy to understand answer as to what this rule means and for what purpose it is used. Would someone please elucidate the .632+ rule?

I will get to the 0.632 estimator, but it'll be a somewhat long development:

Suppose we want to predict $Y$ with $X$ using the function $f$, where $f$ may depend on some parameters that are estimated using the data $(\mathbf{Y}, \mathbf{X})$, e.g. $f(\mathbf{X}) = \mathbf{X}\mathbf{\beta}$

A naïve estimate of prediction error is $$\overline{err} = \dfrac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))$$ where $L$ is some loss function, e.g. squared error loss. This is often called training error. Efron et al. calls it apparent error rate or resubstitution rate. It's not very good since we use our data $(x_i,y_i)$ to fit $f$. This results in $\overline{err}$ being downward biased. You want to know how well your model $f$ does in predicting new values.

Often we use cross-validation as a simple way to estimate the expected extra-sample prediction error (how well does our model do on data not in our training set?). $$Err = \text{E}\left[ L(Y, f(X))\right]$$

A popular way to do this is to do $K$-fold cross-validation. Split your data into $K$ groups (e.g. 10). For each group $k$, fit your model on the remaining $K-1$ groups and test it on the $k$th group. Our cross-validated extra-sample prediction error is just the average $$Err_{CV} = \dfrac{1}{N}\sum_{i=1}^N L(y_i, f_{-\kappa(i)}(x_i))$$ where $\kappa$ is some index function that indicates the partition to which observation $i$ is allocated and $f_{-\kappa(i)}(x_i)$ is the predicted value of $x_i$ using data not in the $\kappa(i)$th set.

This estimator is approximately unbiased for the true prediction error when $K=N$ and has larger variance and is more computationally expensive for larger $K$. So once again we see the bias–variance trade-off at play.

Instead of cross-validation we could use the bootstrap to estimate the extra-sample prediction error. Bootstrap resampling can be used to estimate the sampling distribution of any statistic. If our training data is $\mathbf{X} = (x_1,\ldots,x_N)$, then we can think of taking $B$ bootstrap samples (with replacement) from this set $\mathbf{Z}_1,\ldots,\mathbf{Z}_B$ where each $\mathbf{Z}_i$ is a set of $N$ samples. Now we can use our bootstrap samples to estimate extra-sample prediction error: $$Err_{boot} = \dfrac{1}{B}\sum_{b=1}^B\dfrac{1}{N}\sum_{i=1}^N L(y_i, f_b(x_i))$$ where $f_b(x_i)$ is the predicted value at $x_i$ from the model fit to the $b$th bootstrap dataset. Unfortunately, this is not a particularly good estimator because bootstrap samples used to produce $f_b(x_i)$ may have contained $x_i$. The leave-one-out bootstrap estimator offers an improvement by mimicking cross-validation and is defined as: $$Err_{boot(1)} = \dfrac{1}{N}\sum_{i=1}^N\dfrac{1}{|C^{-i}|}\sum_{b\in C^{-i}}L(y_i,f_b(x_i))$$ where $C^{-i}$ is the set of indices for the bootstrap samples that do not contain observation $i$, and $|C^{-i}|$ is the number of such samples. $Err_{boot(1)}$ solves the overfitting problem, but is still biased (this one is upward biased). The bias is due to non-distinct observations in the bootstrap samples that result from sampling with replacement. The average number of distinct observations in each sample is about $0.632N$ (see this answer for an explanation of why Why on average does each bootstrap sample contain roughly two thirds of observations?). To solve the bias problem, Efron and Tibshirani proposed the 0.632 estimator: $$Err_{.632} = 0.368\overline{err} + 0.632Err_{boot(1)}$$ where $$\overline{err} = \dfrac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))$$ is the naïve estimate of prediction error often called training error. The idea is to average a downward biased estimate and an upward biased estimate.

However, if we have a highly overfit prediction function (i.e. $\overline{err}=0$) then even the .632 estimator will be downward biased. The .632+ estimator is designed to be a less-biased compromise between $\overline{err}$ and $Err_{boot(1)}$. $$Err_{.632+} = (1 - w) \overline{err} + w Err_{boot(1)}$$ with $$w = \dfrac{0.632}{1 - 0.368R} \quad\text{and}\quad R = \dfrac{Err_{boot(1)} - \overline{err}}{\gamma - \overline{err}}$$ where $\gamma$ is the no-information error rate, estimated by evaluating the prediction model on all possible combinations of targets $y_i$ and predictors $x_i$.

$$\gamma = \dfrac{1}{N^2}\sum_{i=1}^N\sum_{j=1}^N L(y_i, f(x_j))$$.

Here $R$ measures the relative overfitting rate. If there is no overfitting (R=0, when the $Err_{boot(1)} = \overline{err}$) this is equal to the .632 estimator.

• Those are good questions, @rpierce, but they move somewhat away from this thread's central topic. It would be better, CV organization-wise, to have them in a new thread, so that it's easier for people to find & utilize that information subsequently. – gung - Reinstate Monica May 7 '14 at 14:24
• Question 1: stats.stackexchange.com/questions/96764/… – russellpierce May 7 '14 at 14:40
• – russellpierce May 7 '14 at 14:44
• @rpierce I'm sorry if I made my question a little difficult to follow. $\overline{err} = \dfrac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))$ is comparing the fit of your model to the data used to fit it. So for squared error loss that would just be $\dfrac{1}{n}\sum_{i=1}^n (y_i-\hat{y}_i)^2$ – bdeonovic May 7 '14 at 15:17
• @rpierce, yes! I was being a little general because I was recyling a lot of this material from some class notes. – bdeonovic May 7 '14 at 15:19

You will find more information in section 3 of this1 paper. But to summarize, if you call $S$ a sample of $n$ numbers from $\{1:n\}$ drawn randomly and with replacement, $S$ contains on average approximately $(1-e^{-1})\,n \approx 0.63212056\, n$ unique elements.

The reasoning is as follows. We populate $S=\{s_1,\ldots,s_n\}$ by sampling $i=1,\ldots,n$ times (randomly and with replacement) from $\{1:n\}$. Consider a particular index $m\in\{1:n\}$.

Then:

$$P(s_i=m)=1/n$$

and

$$P(s_i\neq m)=1-1/n$$

and this is true $\forall 1\leq i \leq n$ (intuitively, since we sample with replacement, the probabilities do not depend on $i$)

thus

$$P(m\in S)=1-P(m\notin S)=1-P(\cap_{i=1}^n s_i\neq m)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=1-\prod_{i=1}^n P(s_i\neq m)=1-(1-1/n)^n\approx 1-e^{-1}$$

You can also carry this little simulation to check empirically the quality of the approximation (which depends on $n$):

n <- 100
fx01 <- function(ll,n){
a1 <- sample(1:n, n, replace=TRUE)
length(unique(a1))/n
}
b1 <- c(lapply(1:1000,fx01,n=100), recursive=TRUE)
mean(b1)


1. Bradley Efron and Robert Tibshirani (1997). Improvements on Cross-Validation: The .632+ Bootstrap Method. Journal of the American Statistical Association, Vol. 92, No. 438, pp. 548--560.

• here is a doc for you in reference -- stat.washington.edu/courses/stat527/s14/readings/… – user45127 May 7 '14 at 15:27
• (+1) Very good. I would only make the notation a little more standard. Data: $(x_1,\dots,x_n)$. IID random variables $S_1,\dots,S_n$ with $P(S_i=k)=\frac{1}{n}\;I_{\{1,\dots,n\}}(k)$. Result: $P(\cup_{i=1}^n\{S_i=k\})=1-P(\cap_{i=1}^n\{S_i\neq k\})=1-\prod_{i=1}^n P\{S_i\neq k\}=1-(1-1/n)^n\to1-1/e\approx 63.21\%$. – Zen May 7 '14 at 16:43
• @rpierce: Right. The "obvious" bit that the answer currently fails to mention is that $1-e^{-1}\approx0.63212056$. – Ilmari Karonen May 7 '14 at 18:58
• This answer is also great, in fact, the accepted answer plus this answer actually provide the full answer to my question - but between the two I feel like Benjamin's is closer to what I was looking for in an answer. That being said - I really wish it were possible to accept both. – russellpierce May 7 '14 at 19:25
• @rpierce: To quote Celine Dion, "Tale as old as time / song as old as rhyme / Beauty and the beast." :P – Nick Stauner May 7 '14 at 20:00

In my experience, primarily based on simulations, the 0.632 and 0.632+ bootstrap variants were needed only because of severe problems caused by the use of an improper accuracy scoring rule, namely the proportion "classified" correctly. When you use proper (e.g., deviance-based or Brier score) or semi-proper (e.g., $c$-index = AUROC) scoring rules, the standard Efron-Gong optimism bootstrap works just fine.

• I don't think I understand most of the things you said here Frank. Would you be willing to clarify? It sounds like you have something unique and important to contribute. – russellpierce May 8 '14 at 18:59
• Glad to expand if you can state a specific question. – Frank Harrell May 8 '14 at 19:58
• These scoring rules were ... judging the quality of the bootstrap result? Could you provide a link that describes the proportion "classified" correctly scoring rule, I'm having trouble imagining what kind of beast that might be. Of the top results for "Efron-Gong optimism" on Google the vast majority seem to be posts by you... how is that different from if I say "bootstrap" without the qualifiers? Which Effron and Gong article should I look to? There seem to be several. – russellpierce May 8 '14 at 21:17
• See the original paper about 0.632 which uses and defines the proportion classified correctly (Efron & Tibshirani JASA 92:548; 1997). The optimism bootstrap is a variant of the bootstrap for estimating bias. It is described in Gong: JASA 85:20; 1990. – Frank Harrell May 8 '14 at 22:38

Those answers are very useful. I couldn't find a way to demonstrate it with maths so I wrote some Python code which works quite well though:

    from numpy import mean
from numpy.random import choice

N = 3000

variables = range(N)

num_loop = 1000
# Proportion of remaining variables
p_var = []

for i in range(num_loop):
set_var = set(choice(variables, N))
p=len(set_var)/float(N)
if i%50==0:
print "value for ", i, " iteration ", "p = ",p
p_var.append(p)

print "Estimator of the proportion of remaining variables, ", mean(p_var)


I was struggling with this concept of 632+. The given answers here clear up some things for me but I find it all rather technical. For those of you that are at my level I'll try to explain it:

The 632+ bootstrap trains en test models with a bootstraps of your dataset and then calculates scores, for example accuracy, for those models. To check how much the predicted values of your model differs from what should be expected, some magical math with e and other stuff is done to adjust your results to what might be expected in the real population.

If you want to implement it in Python without knowing whats going on this is great resource with explaination and a great library: bootstrap_point632_score - mlxtend (rasbt.github.io)

That method generates a list with scores for each trained model which you can use to evaluate your model.