2
$\begingroup$

I found the following in The Elements of Statistical Learning.

Suppose we have 1000 training examples $x_i$ generated uniformly on $[-1,1]^p$. Assume that the true relationship between $X$ and $Y$ is $$Y = f(X) = e^{-8||X||^2}$$ without any measurement error. We use the 1-nearest-neighbour rule to predict $y_0$ at the test-point $x_0 = 0$. Denote the training set by $\mathcal T$. We can compute the expected prediction error at $x_0$ for our procedure, averaging over all such examples of size 1000. Since the problem is deterministic, this is the mean squared error (MSE) for estimating $f(0)$:

\begin{align}\text{MSE}(x_0) &= E_\mathcal T[f(x_0)-\hat y_0]^2\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0)]^2 + [E_\mathcal T(\hat y_0)-f(x_0)]^2\\ &= \mbox{Var}_\mathcal T(\hat y_0) + \mbox{Bias}^2(\hat y_0) \end{align}

I don't quite understand what they mean by the problem being deterministic. Also, how exactly do they get from the first line to the second line? I played around with the binomial formula but I can't seem to derive this.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

To answer the second request:

$$ \begin{align} \text{MSE}(x_0) &= E_\mathcal T[f(x_0)-\hat y_0]^2\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0) + E_\mathcal T(\hat y_0)-f(x_0)]^2\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0)]^2 + E_\mathcal T[E_\mathcal T(\hat y_0)-f(x_0)]^2 + 2E_\mathcal T([\hat y_0 - E_\mathcal T(\hat y_0)][E_\mathcal T(\hat y_0)-f(x_0)])\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0)]^2 + [E_\mathcal T(\hat y_0)-f(x_0)]^2\\ &= \mbox{Var}_\mathcal T(\hat y_0) + \mbox{Bias}^2(\hat y_0), \end{align} $$ where fourth equality is true since $E_\mathcal T([\hat y_0 - E_\mathcal T(\hat y_0)]) = E_\mathcal T(\hat y_0) - E_\mathcal T(\hat y_0) = 0$ and $E_\mathcal T[E_\mathcal T(\hat y_0)-f(x_0)]^2 =[E_\mathcal T(\hat y_0)-f(x_0)]^2$, since $f(x_0)$, $E_\mathcal T(\hat y_0) $ are constants.

To answer the first request: They are interested in the case where the random variable $X$ takes $x_0=0$ value with probability $1$, thus the problem is deterministic. Refer ://en.m.wikipedia.org/wiki/Degenerate_distribution for more, degenerate and deterministic terms are interchangeable.

$\endgroup$
6
  • $\begingroup$ I still don't quite get the fourth equality. How do the second and third summand in the third line combine to the second summand in the fourth line? Could you add one more step please? Thank you so much. $\endgroup$
    – akkarin
    Feb 17, 2017 at 18:58
  • 1
    $\begingroup$ @akkarin I have explained how the fourth equality comes about after all the steps are done in the answer itself. Basically the third summand in the third equality becomes $0$ since $E_\mathcal T([\hat y_0 - E_\mathcal T(\hat y_0)]) = E_\mathcal T(\hat y_0) - E_\mathcal T(\hat y_0) = 0.$ Feel free to ask further if something's not clear. $\endgroup$
    – rookie
    Feb 18, 2017 at 6:25
  • $\begingroup$ So which rules do you use to factorise the third summand? Why does it become 0? The expectation is taken of the whole thing rather than just $(\hat y_0 - E_\mathcal T(\hat y_0)$, right? Also, even if the third summand becomes 0, why are the second summands in third and fourth line equivalent? In the third line there is one more expectation taken? $\endgroup$
    – akkarin
    Feb 18, 2017 at 13:12
  • 1
    $\begingroup$ @akkarin Notice $[E_\mathcal T(\hat y_0)-f(x_0)]$ is a constant. In whole of this analysis the only random variable is $\hat y_0$ with statistics given by $\mathcal T$. This answers both of your questions. $\\$And just for an information I have used "Linearity of Expectation" from second to third equality step. $\endgroup$
    – rookie
    Feb 18, 2017 at 14:09
  • $\begingroup$ I see! Of course! Thanks a lot for your patience. :) $\endgroup$
    – akkarin
    Feb 18, 2017 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .