Expected prediction error - derivation

Question

I am struggling to understand the derivation of the expected prediction error per below (ESL), especially on the derivation of 2.11 and 2.12 (conditioning, the step towards point-wise minimum). Any pointers or links much appreciated.

Below I am reporting the excerpt from ESL pg. 18. The first two equations are, in order, equation 2.11 and 2.12.

---

Let $X \in \mathbb{R}^p$ denote a real valued random input vector, and $Y \in \mathbb{R}$ a real valued random output variable, with joint distribution $\text{Pr}(X,Y)$. We seek a function $f(X)$ for predicting $Y$ given values of the input $X$. This theory requires a loss function $L(Y,f(X))$ for penalizing errors in prediction, and by far the most common and convenient is squared error loss: $L(Y,f(X))=(Y-f(X))^2$. This leads us to a criterion for choosing $f$,

$$ \begin{split} \text{EPE}(f) &= \text{E}(Y - f(X))^2\\ & = \int [y - f(x)]^2 \text{Pr}(dx, dy) \end{split} $$

the expected (squared) prediction error. By conditioning on $X$, we can write EPE as

$$ \text{EPE}(f) = \text{E}_X \text{E}_{Y|X}([Y-f(X)]^2|X) $$

and we see that it suffices to minimize EPE point-wise:

$$ f(x) = \text{argmin}_c \text{E}_{Y|X}([Y-c]^2|X) $$

The solution is

$$ f(x) = \text{E}(Y|X=x) $$

the conditional expectation, also known as the regression function.

Answer 1

\begin{align*} EPE(f) &= \int [y - f(x)]^2 Pr(dx, dy) \\ &= \int [y - f(x)]^2p(x,y)dxdy \\ &= \int_x \int_y [y - f(x)]^2p(x,y)dxdy \\ &= \int_x \int_y [y - f(x)]^2p(x)p(y|x)dxdy \\ &= \int_x\left( \int_y [y - f(x)]^2p(y|x)dy \right)p(x)dx \\ &= \int_x \left( E_{Y|X}([Y - f(X)]^2|X = x) \right) p(x)dx\\ &= E_{X}E_{Y|X}([Y - f(X)]^2| X = x) \end{align*}

Answer 2

The equation (2.11) is a consequence of the following little equality. For any two random variables $Z_1$ and $Z_2$, and any function $g$

$$ E_{Z_1, Z_2} (g(Z_1, Z_2)) = E_{Z_2}(E_{Z_1 \mid Z_2}(g(Z_1, Z_2) \mid Z_2)) $$

The notation $E_{Z_1, Z_2}$ is the expectation over the joint distribution. The notation $E_{Z_1 \mid Z_2}$ essentially says "integrate over the conditional distribution of $Z_1$ as if $Z_2$ was fixed".

It's easy to verify this in the case that $Z_1$ and $Z_2$ are discrete random variables by just unwinding the definitions involved

$$ \begin{align} E_{Z_2} & (E_{Z_1 \mid Z_2}(g(Z_1, Z_2) \mid Z_2)) \\ &= E_{Z_2} \left( \sum_{z_1} g(z_1, Z_2) Pr(Z_1 = z_1 \mid Z_2 ) \right) \\ &= \sum_{z_2} \left( \sum_{z_1} g(z_1, z_2) Pr(Z_1 = z_1 \mid Z_2 = z_2 ) \right) Pr(Z_2 = z_2) \\ &= \sum_{z_1, z_2} g(z_1, z_2) Pr(Z_1 = z_1 \mid Z_2 = z_2) Pr(Z_2 = z_2) \\ &= \sum_{z_1, z_2} g(z_1, z_2) Pr(Z_1 = z_1, Z_2 = z_2 ) \\ &= E_{Z_1, Z_2} (g(Z_1, Z_2)) \end{align} $$

The continuous case can either be viewed informally as a limit of this argument, or formally verified once all the measure theoretic do-dads are in place.

To unwind the application, take $Z_1 = Y$, $Z_2 = X$, and $g(x, y) = (y - f(x))^2$. Everything lines up exactly.

The assertion (2.12) asks us to consider minimizing

$$ E_X E_{Y \mid X} (Y - f(X))^2 $$

where we are free to choose $f$ as we wish. Again, focusing on the discrete case, and dropping halfway into the unwinding above, we see that we are minimizing

$$ \sum_{x} \left( \sum_{y} (y - f(x))^2 Pr(Y = y \mid X = x) \right) Pr(X = x) $$

Everything inside the big parenthesis is non-negative, and you can minimize a sum of non-negative quantities by minimizing the summands individually. In context, this means that we can choose $f$ to minimize

$$\sum_{y} (y - f(x))^2 Pr(Y = y \mid X = x)$$

individually for each discrete value of $x$. This is exactly the content of what ESL is claiming, only with fancier notation.

Answer 3

I find some parts in this book express in a way that is difficult to understand, especially for those who do not have a strong background in statistics.

I will try to make it simple and hope that you can get rid of confusion.

Claim 1 (Smoothing) $E(X) = E(E(X|Y)),\forall X,Y$

Proof: Notice that E(Y) is a constant but E(Y|X) is a random variable depending on X. \begin{align} E(E(X|Y)) &= \displaystyle\int E(X|Y=y) f_Y(y) dy \\ &= \int \int x f_{X|Y} (x|y) dx f_Y(y) dy \\ &= \int \int x f_{X|Y} (x|y) f_Y(y) dx dy \\ &= \int \int x f_{XY} (x,y) dx dy \\ &= \int x \left(\int f_{XY} (x,y) dy \right) dx \\ &= \int x f_X(x) dx = E(X) \end{align}

Claim 2: $E(Y - f(X))^2 \geq E(Y - E(Y|X))^2, \forall f$

Proof: \begin{align} E((Y - f(X))^2 | X) &= E( ([Y - E(Y|X)] + [E(Y|X) - f(X)])^2|X) \\ &= E((Y-E(Y|X))^2 |X) + E((E(Y|X) - f(X))^2|X) + \\ &\qquad 2 E((Y - E(Y|X))(E(Y|X) - f(X))|X) \\ &=E((Y-E(Y|X))^2 |X) + E((E(Y|X) - f(X))^2|X) + \\ &\qquad 2 (E(Y|X) - f(X)) E(Y - E(Y|X))|X) \\[5pt] &( \text{ since } E(Y|X) - f(X) \text{ is constant given } X) \\[5pt] &= E((Y-E(Y|X))^2 |X) + E((E(Y|X) - f(X))^2|X) \text{ ( use Claim 1 }) \\ &\geq E((Y-E(Y|X))^2 |X) \end{align}

Taking expectation both sides of the above equation give Claim 2 (Q.E.D)

Therefore, the optimal f is $f(X) = E(Y|X)$

Answer 4

I found the explanation in the textbook and the other answers here (and Confusion in regression function derivation and Confused by Derivation of Regression Function) inadequate, so I decided to add my own version. I know many readers of the book and this website will not have a background in measure theory but for me it makes everything clearer. Some of the difficulties the authors have - to my mind - comes from avoiding rigorous treatment of the probability parts of their arguments:

Let $X : \bigl(\Omega,\mathcal{F},\mathbb{P}\bigr) \to \bigl(\mathbf{R}^p,\mathcal{B}(\mathbf{R}^p)\bigr)$ and $Y : \bigl(\Omega,\mathcal{F},\mathbb{P}\bigr) \to \bigl(\mathbf{R},\mathcal{B}(\mathbf{R})\bigr)$ be random variables (there's no need for them not to be on the same underlying probability space, so we may as well do it like this). Define the expected prediction error as $$ EPE(f) = \mathbb{E}\Bigl[ \bigl(Y-f(X)\bigr)^2\Bigr]. $$

---

Aside: Recall that given some other random variable $Z : \bigl(\Omega,\mathcal{F},\mathbb{P}\bigr) \to \bigl(\mathbf{R},\mathcal{B}(\mathbf{R})\bigr)$, we have that $\mathbb{E}(Z |X ) : \bigl(\Omega,\mathcal{F},\mathbb{P}\bigr) \to \bigl(\mathbf{R},\mathcal{B}(\mathbf{R})\bigr)$ is a random variable of the form $\omega \mapsto G(X(\omega))$ f. When we write $\mathbb{E}(Z|X=x)$, we are evaluating the random variable $\mathbb{E}(Z |X )$ at some $\omega \in \Omega$ for which $X(\omega) = x$. And recall that the definition of the conditional expectation means that $$ \mathbb{E}(Z) = \mathbb{E}\biggl( \mathbb{E}(Z |X ) \biggr). $$ Also: From a rigorous perspective, there isn't really such a thing as $\mathbb{E}_X$ or $\mathbb{E}_{Y|X}$; this is just confusing: If everything is on the same probability space then "$\mathbb{E}$" means "integrate over the probability space'' and nothing else, every time.

---

So \begin{align} EPE(f) &= \mathbb{E}\Bigl[ \bigl(Y-f(X)\bigr)^2\Bigr]\\ & = \mathbb{E}\biggl(\mathbb{E}\Bigl[ \bigl(Y-f(X)\bigr)^2\big| X \Bigr]\biggr)\\ &= \int_{\Omega} \mathbb{E}\Bigl[ \bigl(Y-f(X)\bigr)^2\big| X\Bigr] d\mathbb{P}(\omega) \end{align} By taking $Z = \bigl(Y-f(X)\bigr)^2$ in our aside above, we can see that the integrand here is of the form $G(X(\omega))$, i.e. we can write this as $\int_{\Omega} G(X(\omega)) d\mathbb{P}(\omega)$ and - using the definition of the the law $\mu_X$ of $X$ - this is equal to $\int_{\mathbf{R}^p} G(x) d\mu_X(x)$. This certainly makes it clear that to choose an $f$ which minimizes the EPE you should minimize the integrand pointwise as a function of $x$. So let's try to do that: By linearity and 'taking out what is known' (i.e. the fact that $f(X)$ is $\sigma(X)$-measurable): \begin{align*} \mathbb{E}\Bigl[ \bigl(Y-f(X)\bigr)^2\big| X\Bigr] &= \mathbb{E}\bigl[ Y^2 | X\bigr] - 2\mathbb{E}\bigl[ Y f(X) | X\bigr] + \mathbb{E}\bigl[ f(X)^2 | X\bigr] \\ &= \mathbb{E}\bigl[ Y^2 | X\bigr] - 2f(X)\mathbb{E}\bigl[ Y | X\bigr] + f(X)^2 \\ &= \mathbb{E}\bigl[ Y^2 | X\bigr] - \mathbb{E}\bigl[ Y | X\bigr]^2 + \biggl(f(X) - \mathbb{E}\bigl[ Y | X\bigr] \biggr)^2 \end{align*} Then when we evaluate both sides at some $\omega \in \Omega$ for which $X(\omega) = x$, we get $$ \mathbb{E}\Bigl[ \bigl(Y-f(X)\bigr)^2\big| X=x\Bigr] = \mathbb{E}\bigl[ Y^2 | X=x\bigr] - \mathbb{E}\bigl[ Y | X=x\bigr]^2 + \biggl(f(x) - \mathbb{E}\bigl[ Y | X=x\bigr] \biggr)^2, $$ and we can see that the choice of $f(x)$ which minimizes this expression is $f(x) = \mathbb{E}\bigl[ Y | X=x\bigr]$, the so-called 'regression function'

Answer 5

I will try to explain this as per my understanding. The main idea of the section 2.4 Statistical Decision Theory is to provide a framework for developing models(e.g. least-squares regression, k-NN).

As a first step(it is what author of this topic is asking about) in that section we consider regression function.

Idea of the step: to show that we can use conditional expectation as a linear regression function. So

$$f(x) = mx+b = \text{E}(Y|X=x)$$

where $m$ - slope, $b$ - intercept ($X$ is vector in the example of the book but I hope it doesn't confuse.)

I understand this mapping next way. Linear regression is a process to find a line closest to every point on scatter-plot. So to predict $y$ we can use expected value(or mean) of $y$ for given $x$ instead of $mx+b$.

How to prove that we are right with above assumption?
1. We need a loss function(squared error): $$L(Y, f(X))=(Y-f(X))^2$$    Therefore the expected squared prediction error for our regression function will be: $$EPE(f) = E(L[Y, f(x)]) = E([Y-f(X)]^2) \text{ - this is how we're getting 2.9}$$

2. Then how to derive 2.11 from 2.10 and 2.10 from 2.9. Generally we need to follow one of properties for conditional expectation

$$E(E[X|Y]) = E[X|Y = y] P(Y = y) \text{ - by law of unconscious statistician}$$    and $$E[X|Y = y] P(Y = y) = E[X] \text{ - by partition theorem from above we get this.}$$

   We can do the next steps:

   2.9 to 2.10:

   $EPE(f)= E([Y-f(X)]^2) = \int[y−f(x)]^2Pr(dx,dy)$ - this is by definition of expectation($E(X)=∫xf(x)dx$ for continuous case) probably except for $Pr(dx, dy)$
   There are 3 parts:
   $\int$ - because we're using continuous random variables
   $[y−f(x)]^2$ - this is our x from definition
   $Pr(dx, dy)$ - just notation for $p(x,y)dxdy$ where $p(x,y)$ is probability

   2.10 to 2.11: $$\int [y−f(x)]^2Pr(dx,dy) \text{ - 2.10 formula}$$ $$=\int[y−f(x)]^2\mathbf{p(x,y)dxdy} \text{ - from the above}$$ $$=\mathbf{\int_{x}\int_{y}}[y−f(x)]^2p(x,y)dxdy \text{ - just more precise integrals}$$ $$=\int_{x}\int_{y}[y−f(x)]^2\mathbf{p(x)p(y|x)}dxdy \text{ - by multiplication rule we got this}$$ $$=\int_{x}\mathbf{(\int_{y}[y−f(x)]^2p(y|x)dy)}p(x)dx \text{ - just regrouped members}$$ $$=\int_{x}\mathbf{(E_{Y|X}([Y−f(X)]^2|X=x))}p(x)dx \text{ - by definition of conditional expectation}$$

$$=E_{X}[E_{Y|X}([Y−f(X)]^2|X=x)] \text{ - by law of unconscious statistician we get this}$$

   So $E_{X}E_{Y|X}([Y−f(X)]^2|X=x)$ is generally $E(E[Y|X])$.

3. So far we've worked on $EPE(f)$ and proved that $E([Y-f(X)]^2)$ can be represented like this $E_{X}E_{Y|X}([Y−f(X)]2|X=x)$

   Then authors say that it suffices to minimize $EPE$ pointwise for $f(x)$. $$f(x) = argmin_{c} E_{Y|X}([Y − c]^2|X) = x$$    I thought of simple notations for regression to realize what authors mean. Specifically we can minimize squared error of regression line with partial derivatives.
   a. we can represent this $$SE_{line} = (y_{0}-(mx_{0}+b))^2+(y_{1}-(mx_{1}+b))^2 +...+(y_{n}-(mx_{n}+b))^2$$    like this $$SE_{line} = n\overline{y^2}-2mn\overline{yx}-2bn\overline{y}+m^2n\overline{x^2}+2mbn\overline{x}+nb^2$$    It is the same actually.
   b. Then we can find partial derivatives of the above with respect of $m$(slope) and $b$(intersect) to find minima for those variables.

   c. So we can use $m$ and $b$ in $mx+b$ to get predicted $y$ with minimum error.

   The same idea is in the book. We want to find some $c$ to get minimum for $$E_{Y|X}([Y − c]^2|X = x)\text{ (2.12)}$$

   So the best prediction of $Y$ at any point $X$ is the conditional mean(mean of $Y$'s for $X$) when the best is measured by average squared error.

   Hope it helps.