Rigorous statement of expectations for the bias-variance trade-off

Quoted from Forex.com.bd-Editorial External answer — Cross Validated Stack Exchange Author: Gabriel Romon Source score (net votes, not local likes): 2 Original post: https://stats.stackexchange.com/a/664944 License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/ Adaptation: HTML converted to plain text; contact email addresses removed. First, we clarify the framework and notation. The number of observations is $n$ , we have training data $\mathcal D_n = ((X_1,Y_1),\ldots,(X_n,Y_n))$ and test data $(X,Y)$ . We assume that $X\perp\!\!\!\!\!\!\perp \mathcal D_n$ . We do not make the usual i.i.d. assumption on $(X,Y)$ and the $(X_i,Y_i)$ , so as not to exclude the fixed-design setting covered at the end of this post. By applying a learning algorithm to $\mathcal D_n$ we obtain a predictor $\hat f$ , which is therefore random since it depends on the training data, which is random by assumption. The prediction of $\hat f$ at any $x\in \mathcal X$ will be denoted by $\hat f(x; \mathcal D_n)$ , in order to highlight the dependence on $\mathcal D_n$ . The expected prediction error of $\hat f$ at $x_0$ is the following conditional expectation (see Chung's book or Shiryaev's book for a reference on this measure-theoretic concept) $$E\Big[\big(Y-\hat f(X; \mathcal D_n)\big)^2\Big|X = x_0\Big] = E\Big[\big(Y-\hat f(x_0; \mathcal D_n)\big)^2\Big|X = x_0\Big].$$ Looking at the RHS, only the randomness in $Y$ and $\mathcal D_n$ is involved in the expectation. At this point, we specify the distribution of $(X,Y)$ by assuming that $Y= f(X)+\epsilon$ , with $\epsilon \perp\!\!\!\!\!\!\perp (X,\mathcal D_n)$ , $E[\epsilon] = 0$ and $V[\epsilon] = \sigma^2$ . Under this assumption, the conditional expectation rewrites as $$\begin{align} E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n) + \epsilon\big)^2\Big|X = x_0\Big] = &\phantom{+}E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2 \Big|X = x_0\Big] \\&+ E\Big[\epsilon^2 \Big|X = x_0\Big] \\&+E\Big[\epsilon\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big) \Big|X = x_0\Big] \end{align}$$ $\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2$ is a function of $\mathcal D_n$ only, and thus independent of $X$ . Consequently, the first summand rewrites as $E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2 \Big]$ . Since $\epsilon \perp\!\!\!\!\!\!\perp X$ , the second summand is $E[\epsilon^2]=\sigma^2$ . $\epsilon\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)$ is a function of $\epsilon$ and $\mathcal D_n$ , and thus independent of $X$ . Consequently, the third summand rewrites as $E\Big[\epsilon\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big) \Big] = E[\epsilon] E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big) \Big] = 0$ . Hence $$\begin{align} &\phantom{+}E\Big[\big(Y-\hat f(X; \mathcal D_n)\big)^2\Big|X = x_0\Big] \\&= E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2 \Big] + \sigma^2 \\&= \big(E[\hat f(x_0; \mathcal D_n)] - f(x_0)\big)^2 + E\Big[\big(\hat f(x_0; \mathcal D_n) - E[\hat f(x_0; \mathcal D_n)]\big)^2 \Big] + \sigma^2 \\&= \big(E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)] - f(x_0)\big)^2 + E_{\mathcal D_n}\Big[\big(\hat f(x_0; \mathcal D_n) - E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]\big)^2 \Big] + \sigma^2, \end{align}$$ where the last line emphasizes the exact source of randomness in each of the expectation. More generally, we can formulate a bias-variance decomposition without an additive error model specification of $(X,Y)$ . If we define the Bayes predictor $f^*:x\mapsto E[Y|X=x]$ , then a similar computation shows that $$\begin{align}&\phantom{+}E\Big[\big(Y-\hat f(X; \mathcal D_n)\big)^2\Big|X = x_0\Big] \\&= \underbrace{\big(E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)] - f^*(x_0)\big)^2}_{\text{squared bias}} + \underbrace{E_{\mathcal D_n}\Big[\big(\hat f(x_0; \mathcal D_n) - E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]\big)^2 \Big]}_{\text{variance}} + \underbrace{E[\big(Y-f^*(X)\big)^2|X=x_0]}_{\text{irreducible error}}. \end{align} $$ In some paragraphs, Hastie et al. add a fixed design assumption, i.e, that $(X_1,\ldots,X_n)$ is a degenerate random vector that is always equal to $(x_1,\ldots,x_n)\in \mathcal X^n$ . This assumption is irrelevant in the derivation of the bias-variance decomposition. It is relevant however when looking for a closed form for the bias and variance terms. For instance, consider the setting of k-NN regression, where it is further assumed that for each $i$ , $Y_i=f(x_i) + \epsilon_i$ , with $E[\epsilon_i] = 0$ , $V[\epsilon_i] = \sigma^2$ and pairwise independence of the $\epsilon_i$ . The fixed-design assumption allows for a simple expression of the predicted value: $$\hat f(x_0,\mathcal D_n) = \frac 1k \sum_{\ell=1}^k Y_{(\ell)},$$ where the indices $(1),\ldots, (k)$ are such that $x_{(1)},\ldots,x_{(k)}$ are the k-nearest neighbors of $x_0$ . The quantity $E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]$ is then simply $\frac 1k \sum_{\ell=1}^k E[Y_{(\ell)}] = \frac 1k \sum_{\ell=1}^k f(x_{(\ell)})$ and the variance term is $$E_{\mathcal D_n}\Big[\big(\hat f(x_0; \mathcal D_n) - E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]\big)^2 \Big] = V\left[\frac 1k \sum_{\ell=1}^k Y_{(\ell)}\right] = \frac{\sigma^2}k.$$

Cancel quote