Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 22 down vote accepted

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

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]$$ where $L$ is some loss function, e.g. squared error loss.

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 $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. 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.

share|improve this answer
    
Okay... I'm a little over my head in the notation so I'm going to have to ask some potentially uninformed questions. 1) When K=N is that the equivalent of a studentized estimator (i.e. the statistic is recalculated holding one observation out each time?). 2) What is the difference between the procedure for leave-one-out bootstrapping and jackknifing? 3) I'm somewhat notation/equation illiterate... is $\bar{err}$ a K-fold estimate? Is it a particular K-fold? Or is it just any old K-fold? 4) Is there any reason, other than computational time, to prefer this approach over a K=N K-fold? –  rpierce May 7 at 13:53
1  
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 May 7 at 14:24
1  
Question 1: stats.stackexchange.com/questions/96764/… –  rpierce May 7 at 14:40
1  
1  
@rpierce, yes! I was being a little general because I was recyling a lot of this material from some class notes. –  Benjamin May 7 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.

share|improve this answer
    
Am I correct in thinking that your answer addresses where the .632 constant came from and @Benjamin's addresses the practical use for that constant? –  rpierce May 7 at 13:54
1  
here is a doc for you in reference -- stat.washington.edu/courses/stat527/s14/readings/… –  ichangkim May 7 at 15:27
1  
(+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 at 16:43
1  
@rpierce: Right. The "obvious" bit that the answer currently fails to mention is that $1-e^{-1}\approx0.63212056$. –  Ilmari Karonen May 7 at 18:58
1  
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. –  rpierce May 7 at 19:25

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.

share|improve this answer
    
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. –  rpierce May 8 at 18:59
    
Glad to expand if you can state a specific question. –  Frank Harrell May 8 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. –  rpierce May 8 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 at 22:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.