Exercise 3.4

tomaci_necmi · #1 05-30-2014, 06:21 AM

I asked the question at math stack exchange,

http://math.stackexchange.com/questi...to-a-dataset-d

Can anyone explain me how it works ?

tomaci_necmi · #2 05-30-2014, 06:22 AM

In my textbook, there is a statement mentioned on the topic of linear regression/machine learning, and a question, which is simply quoted as,

Consider a noisy target, $y = (w^{*})^T \textbf{x} + \epsilon$ , for generating the data, where $\epsilon$ is a noise term with zero mean and $\sigma^2$ variance, independently generated for every example $(\textbf{x},y)$ . The expected error of the best possible linear fit to this target is thus $\sigma^2$ .

For the data $D = \{ (\textbf{x}_1,y_1), ..., (\textbf{x}_N,y_N) \}$ , denote the noise in

as $\epsilon_n$ , and let $\mathbf{\epsilon} = [\epsilon_1, \epsilon_2, ...\epsilon_N]^T$ ; assume that

is invertible. By following the steps below, ***show that the expected in-sample error of linear regression with respect to

is given by***,

$\mathbb{E}_D[E_{in}( \textbf{w}_{lin} )] = \sigma^2 (1 - \frac{d+1}{N})$

Below is my methodology,

Book says that,

In-sample error vector, $\hat{\textbf{y}} - \textbf{y}$ , can be expressed as $(H-I)\epsilon$ , which is simply, hat matrix, $H= X(X^TX)^{-1}X^T$ , times, error vector, $\epsilon$ .

So, I calculated in-sample error, $E_{in}( \textbf{w}_{lin} )$ , as,

$E_{in}( \textbf{w}_{lin} ) = \frac{1}{N}(\hat{\textbf{y}} - \textbf{y})^T (\hat{\textbf{y}} - \textbf{y}) = \frac{1}{N} (\epsilon^T (H-I)^T (H-I) \epsilon)$

Since it is given by the book that,

, and also

is symetric,

I got the following simplified expression,

$E_{in}( \textbf{w}_{lin} ) =\frac{1}{N} (\epsilon^T (H-I)^T (H-I) \epsilon) = \frac{1}{N} \epsilon^T (I-H) \epsilon = \frac{1}{N} \epsilon^T \epsilon - \frac{1}{N} \epsilon^T H \epsilon$

Here, I see that,

$\mathbb{E}_D[\frac{1}{N} \epsilon^T \epsilon] = \frac {N \sigma^2}{N}$

And, also, the sum formed by $- \frac{1}{N} \epsilon^T H \epsilon$ , gives the following sum,

$- \frac{1}{N} \epsilon^T H \epsilon = - \frac{1}{N} \{ \sum_{i=1}^{N} H_{ii} \epsilon_i^2 + \sum_{i,j \ \in \ \{1..N\} \ and \ i \neq j}^{} \ H_{ij} \ \epsilon_i \ \epsilon_j \}$

I undestand that,

$- \frac{1}{N} \mathbb{E}_D[\sum_{i=1}^{N} H_{ii} \epsilon_i^2] = - trace(H) \ \sigma^2 = - (d+1) \ \sigma^2$

However, I don't understand why,

$- \frac{1}{N} \mathbb{E}_D[\sum_{i,j \ \in \ \{1..N\} \ and \ i \neq j}^{} \ H_{ij} \ \epsilon_i \ \epsilon_j ] = 0 \ \ \ \ \ \ \ \ \ \ \ \ (eq \ 1)$

should be equal to zero in order to satisfy the equation,

$\mathbb{E}_D[E_{in}( \textbf{w}_{lin} )] = \sigma^2 (1 - \frac{d+1}{N})$

***Can any one mind to explain me why

leads to a zero result ?***

tomaci_necmi · #3 05-30-2014, 06:49 AM

Well all fits now, just my mind played a game to me.

off course $\mathbb{E}[\epsilon_i] = 0$

yaser · #4 05-30-2014, 12:46 PM

Thank you for the question and the answer.

yongxien · #5 08-03-2015, 02:33 AM

Why the last statement is 0? I don't quite understand. Does the mean being zero imply E(e_i) and E(e_j) = 0? I find it weird if that is the case. Because that will mean E(e_i) = 0 but E(e_i^2) = \sigma^2. I understand E(e_i^2) = \sigma^2 from statistics but not the first part.

If it is not the case, then what is the reason for the last statement to be 0?

htlin · #6 08-03-2015, 04:22 PM

In the problem statement, I think "zero mean of the noise" is a given condition?

johnwang · #7 10-13-2017, 10:50 AM

I still don't understand why "eq1" leads to zero. I know that e_i and e_j are zero mean independent variables. However, H_ij is dependent on both e_i and e_j,, so I don't know how to prove that the sum of H_ij*e_i*e_j has an expected value of zero.

Quote:

Originally Posted by tomaci_necmi

In my textbook, there is a statement mentioned on the topic of linear regression/machine learning, and a question, which is simply quoted as,

Consider a noisy target, $y = (w^{*})^T \textbf{x} + \epsilon$ , for generating the data, where $\epsilon$ is a noise term with zero mean and $\sigma^2$ variance, independently generated for every example $(\textbf{x},y)$ . The expected error of the best possible linear fit to this target is thus $\sigma^2$ .

For the data $D = \{ (\textbf{x}_1,y_1), ..., (\textbf{x}_N,y_N) \}$ , denote the noise in

as $\epsilon_n$ , and let $\mathbf{\epsilon} = [\epsilon_1, \epsilon_2, ...\epsilon_N]^T$ ; assume that

is invertible. By following the steps below, ***show that the expected in-sample error of linear regression with respect to

is given by***,

$\mathbb{E}_D[E_{in}( \textbf{w}_{lin} )] = \sigma^2 (1 - \frac{d+1}{N})$

Below is my methodology,

Book says that,

In-sample error vector, $\hat{\textbf{y}} - \textbf{y}$ , can be expressed as $(H-I)\epsilon$ , which is simply, hat matrix, $H= X(X^TX)^{-1}X^T$ , times, error vector, $\epsilon$ .

So, I calculated in-sample error, $E_{in}( \textbf{w}_{lin} )$ , as,

$E_{in}( \textbf{w}_{lin} ) = \frac{1}{N}(\hat{\textbf{y}} - \textbf{y})^T (\hat{\textbf{y}} - \textbf{y}) = \frac{1}{N} (\epsilon^T (H-I)^T (H-I) \epsilon)$

Since it is given by the book that,

, and also

is symetric,

I got the following simplified expression,

$E_{in}( \textbf{w}_{lin} ) =\frac{1}{N} (\epsilon^T (H-I)^T (H-I) \epsilon) = \frac{1}{N} \epsilon^T (I-H) \epsilon = \frac{1}{N} \epsilon^T \epsilon - \frac{1}{N} \epsilon^T H \epsilon$

Here, I see that,

$\mathbb{E}_D[\frac{1}{N} \epsilon^T \epsilon] = \frac {N \sigma^2}{N}$

And, also, the sum formed by $- \frac{1}{N} \epsilon^T H \epsilon$ , gives the following sum,

$- \frac{1}{N} \epsilon^T H \epsilon = - \frac{1}{N} \{ \sum_{i=1}^{N} H_{ii} \epsilon_i^2 + \sum_{i,j \ \in \ \{1..N\} \ and \ i \neq j}^{} \ H_{ij} \ \epsilon_i \ \epsilon_j \}$

I undestand that,

$- \frac{1}{N} \mathbb{E}_D[\sum_{i=1}^{N} H_{ii} \epsilon_i^2] = - trace(H) \ \sigma^2 = - (d+1) \ \sigma^2$

However, I don't understand why,

$- \frac{1}{N} \mathbb{E}_D[\sum_{i,j \ \in \ \{1..N\} \ and \ i \neq j}^{} \ H_{ij} \ \epsilon_i \ \epsilon_j ] = 0 \ \ \ \ \ \ \ \ \ \ \ \ (eq \ 1)$

should be equal to zero in order to satisfy the equation,

$\mathbb{E}_D[E_{in}( \textbf{w}_{lin} )] = \sigma^2 (1 - \frac{d+1}{N})$

***Can any one mind to explain me why

leads to a zero result ?***

johnwang · #8 10-13-2017, 10:55 AM

Is it because the noise is generated independently for each datapoint?

LFD master · #9 10-10-2018, 05:20 PM

I was wondering if the following is a correct answer for part c:

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode