Solved – Bias and variance estimation with boostrap

biasbootstrapresamplingvariance

The Wikipedia article about Jacknife estimation of the bias and variance of an estimator $\theta$ includes the following formulas:

Variance of $\theta$:

$
\operatorname {Var}(\theta )=\sigma ^{2}={\frac {n-1}{n}}\sum _{{i=1}}^{n}({\bar {\theta }}_{i}-{\bar {\theta }}_{{\mathrm {Jack}}})^{2}$

where ${\bar {\theta }}_{{Jack}}={\frac {1}{n}}\sum _{{i=1}}^{n}({\bar {\theta }}_{i})$ is the jacknife estimator.

Bias-correction of $\theta$:

$
{\bar {\theta }}_{{\mathrm {BiasCorrected}}}=N{\bar {\theta }}-(N-1){\bar {\theta }}_{{Jack}}
$

My question is: What are the corresponding formulas for bootstrap? Are they different?

Best Answer

I think the formulas for Bootstrap are as follows, although I can't seem to find a proper reference:

Let $h = \frac{1}{K} \sum_{k=1}^{K}{\hat{y}_k}$ be the mean predicted outcome from the $K$ bootstrap resamples.

Then:

Bias is $y - h$
Variance is $\frac{1}{K-1}\sum_{k=1}^{K} (y_k - h)^2$

Related Solutions

Solved – Variance of sample mean of bootstrap sample

The correct answer is $\frac{n-1}{n^2}S^2$. The solution is #4 here

Bias-Variance Tradeoff – Understanding Bias-Variance Decomposition and Independence of X and ?

I find the most difficult parts of this subject to be in keeping track of what is is being integrated over (the expectation with respect to what?). Many expositions take this lightly, and the end result can be highly confusing. Here is The Elements of Statistical Learning on this point

Discussions of error rate estimation can be confusing, because we have to make clear which quantities are fixed and which are random

I think you're seeing a bit of that in the wikipedia exposition.

My Preferred Derivation

Here's a detailed break down. Working out the exposition in this way is what finally cleared up the various concepts at play for me. I hope it helps you too.

The first step is to condition on $x$, and take the expectation with respect to $y$. There are no assumptions for this part, $g$ is a general function

$$\begin{align*} ESE(f; x) &= E_Y \left[ \left( y - g(x) \right)^2 \mid x \right] \\ & = E_Y \left[ \left( y - E[y \mid x] + E[y \mid x] - g(x) \right)^2 \mid x \right] \\ & = E_Y \left[ \left( y - E[y \mid x] \right)^2 \mid x \right] + E_Y \left[ \left(E[y \mid x] - g(x) \right)^2 \mid x \right] \\ & \quad + 2 E_Y \left[ \left( y - E[y \mid x] \right) \left( E[y \mid x] - g(x) \right) \mid x \right] \\ \end{align*}$$

The trick here is introducing the $E[ y \mid x ]$ into the middle of the sum. This expectation is over $y$ (the only thing that makes sense in this context), so $E[ y \mid x ]$ is just a function of $x$, same as $g$.

Now we may observe that in

$$ 2 E_Y \left[ \left( y - E[y \mid x] \right) \left( E[y \mid x] - g(x) \right) \mid x \right] $$

the second factor has no dependence on $y$, and the first factor is zero in expectation, so this term dies, and we are left with

$$\begin{align*} ESE(f; x) = E_Y \left[ \left( y - E[y \mid x] \right)^2 \mid x \right] + E_Y \left[ \left(E[y \mid x] - g(x) \right)^2 \mid x \right] \\ \end{align*}$$

The first term is the irreducible error of the classifier. It's your $\sigma^2$ above.

Its worth noting that only the integrand of the first term in this result has any dependence on $y$, so the $E_Y$ may be dropped from the second term.

To get to the bias-variance breakdown, we introduce an expectation over the sampling distribution of $x$. That is, we consider $g$ itself as a random variable; training a learning algorithm takes us from a data set $D$ to a function $g$. Thus, it makes sense to take expectations over this sampling distribution with $g$ as a random variate. I'll write $g(x, D)$ to emphasize this dependence of $g$ on the training dataset $D$. With this notation, the second term in our final equation above becomes

$$ \left[ \left(E[y \mid x] - g(x,D) \right)^2 \mid x \right] $$

Taking the expectation of everything over $D$, and writing $Eg(x)$ for the expectation of $g(x, D)$ with respect to this sampling distribution, we can break this down further

$$\begin{align*} & E_{D} \left[ \left(E[y \mid x] - g(x,D) \right)^2 \mid x \right] \\ & = E_{D} \left[ \left(E[y \mid x] - Eg(x) + Eg(x) - g(x,D) \right)^2 \mid x \right] \\ & = E_{D} \left[ \left(E[y \mid x] - Eg(x) \right)^2 \mid x \right] + E_{D} \left[ \left(Eg(x) - g(x, D) \right)^2 \mid x \right] \\ & \quad + 2 E_{D} \left[ \left(E[y \mid x] - Eg(x) \right) \left( Eg(x) - g(x,D) \right) \mid x \right] \\ \end{align*} $$

The same trick applies. In this breakdown the first factor has no dependence on $D$, and the second is zero in expectation, so the cross term dies. Therefore

$$\begin{align*} E_{D} \left[ \left(E[y \mid x] - g(x,D) \right)^2 \mid x \right] = E_{D} \left[ \left(E[y \mid x] - Eg(x) \right)^2 \mid x \right] + E_{D} \left[ \left(Ef(x) - g(x, D) \right)^2 \mid x \right] \end{align*}$$

The first term here is the bias, and the second is the variance.

Of course, I kept the conditioning on $x$ the entire time, so what we have really arrived at is the pointwise decomposition. To get the usual full decomposition of the total error, all that is needed is to integrate out $x$ as well.

How This Relates to the Wikipedia Breakdown

Wikipedia writes $f(x)$ for my $E[ y \mid x ]$. I think it makes the exposition easier to follow to make this explicit. Wikipedia writes

$$ y = f(x) + \epsilon $$

with the assumption that $E(\epsilon) = 0$. What is really meant is $E(\epsilon \mid x) = 0$. This is implicit in my exposition, I simply use $E[y \mid x]$ throughout.

Note that no independence assumptions are necessary for the bias variance decomposition. What wikipedia says

Thus, since $\epsilon$ and $\hat{f}$ are independent

what they really mean is that $\hat{f}$ can be considered a constant when conditioning on $x$, so it can be taken out front of the expectation.

Best Answer

Related Solutions

Solved – Variance of sample mean of bootstrap sample

Bias-Variance Tradeoff – Understanding Bias-Variance Decomposition and Independence of X and ?

Related Question