# Cross Validation and Confidence Interval of the True Error

I'm interested in the relation between Cross Validation and the True Error Estimation of a Classifier (Chapter 5 - Machine Learning - Mitchell).

Suppose we have 150 examples, I decide to use a 100 repeated 5-fold Cross Validation to understand the behavior of my classifier. At this point I have $100 \times 5$ results and I can use the mean and std dev of the error rates to estimate the variance of the model performance.

$$\text{mean(Error Rate)} \pm z \times \text{std(Error Rate)}$$

I could estimate Confidence Interval of the True Error (that I would obtain on the unseen data) using the the average Error rate:

$$\text{mean(Error Rate)} \pm z \times \sqrt{ \frac{mean(errorRate) \times (1 - mean(errorRate) )}{ N}}$$

Two questions:

1. Is this approach correct?
2. Is correct to set $N=150$ in the second equation or I should use the average number of Test Data used as Test Set in each fold of CV ($N = 30$)?
• Have a look here stats.stackexchange.com/questions/61783/… and here jmlr.org/papers/volume5/grandvalet04a/grandvalet04a.pdf - this is no easy topic and is subject to much debate - but if you bootstrap sample a large enough data set and your algorithm is stable you can hope to estimate some sort of true confidence interval Sep 3, 2018 at 16:14
• This is a perfectly reasonable question w/ a good answer. I'm voting to leave open. Sep 5, 2018 at 14:08

## Background

Consider the following definitions:

• A training set $D = {z_1,...,z_n}$ with $Z_i \in Z$ independently sampled from an unknown distribution $P$.
• An algorithm $A$ which maps a data set to a function $A : \mathcal{Z} \rightarrow \mathcal{F}$
• A loss function $L$. e.g. a quadratic loss: $L(f,x,y)) = (f(x) - y)^2$ or a missclassification ${0,1}$ loss $L(f,x,y)) = 1_{f(x) \neq y}$
• Let $f = A(D)$ be the function returned by algorithm $A$ on the training set $D$

We can define two measures of importance:

1. Prediction error: expected loss on future test examples $$PE(D) = E[L(f,z)]$$ Where the expectation is taken with respect to $z$ sampled from $P$

2. Expected performance error: a more general measure which is the expected loss on training sets of size $n$ sampled from $P$ $$EPE(n) = E[L(A(D),z)]$$ Where the expectation is taken with respect to $D$ sampled from $P$ and $z$ is independently sampled from $P$ also

## Cross validation estimator

In practice the data set $D$ is chunked into $K$ disjoint subsets of the same size with $m = n / K$. Let us write $T_k$ for the $k$-th such block and $D_k$ for the training set obtained by removing the elements in $T_k$ from $D$, then

The cross validation estimator is defined as the average of the errors on test block $T_k$ obtained when training the algorithm on $D_k$ $$CV(D) = \frac{1}{K} \sum_{k=1}^K \frac{1}{m} \sum_{z_i \in T_k} L(A(D_k), z_i)$$

Once you have this Cross Validation Estimator $CV(D)$ you can construct bootstrap confidence intervals around it in the same way as you would for any other estimator. Bootstrap your dataset, compute the estimator, repeat many times...

The difficulty lies in understanding what you are actually computing, and how close it is from the truth... Here are a few questions: - Is the mean of the $CV$ an estimator of the $PE$ or the $EPE$ ? - What about the variance of $CV$ ? Does it inform us about the uncertainty of the PE or EPE ? - Under what conditions is the difference $|CV(D) - PE(D)|$ bounded ? - And lastly how does bootstrapping effect all of the above ?

This is an active topic of research and there are different views, conclusions, proofs to be taken into account. The paper linked below is a good place to start if you want to go into more depth.

• Thanks for this answer, do you have a reference for using bootstrap on top of cross-validation? It makes sense to me, and I saw it in some papers, but I would like to have something to cite Sep 28, 2020 at 11:51

I think you should use the following as CL:

CL = mean(Error Rate) ± 𝑧×std(Error Rate)/10

10 comes from sqrt(100). Error Rate is the average Error Rate from each CV round, so it is averaged over every 5-fold CV. So Error Rate has 100 elements.

Alternatively you can use bootstrapping of Error Rate. Let's say you create 60 bootstrapped samples from Error Rate, for each of the 60 bootstrapped samples, you'd calculate the mean. So you get 60 Error_Bootstrap values. Now use

CL = mean(Error_Bootstrap) ± 𝑧×std(Error_Bootstrap)

Notice how we don't need to divide by sqrt(size) in bootstrapped calculation. Hope this helps.