What is the .632+ rule in bootstrapping?

Question

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?

Answer 1

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.

Answer 2

You will find more information in section 3 of this¹ 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.

Answer 3

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.

Answer 4

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)

Answer 5

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.