5
$\begingroup$

From Theodoridis' Machine Learning, exercise 3.26.

Consider, once more, the same regression as that of Problem 3.8, but with $\boldsymbol\Sigma_{\boldsymbol\eta} = \mathbf{I}_N$.

For context, this is the regression model $$y_n = \boldsymbol\theta^{T}\mathbf{x}_n + \eta_n\text{, } \qquad n = 1, 2, \dots, N$$ where $\boldsymbol\eta \sim \mathcal{N}(\mathbf{0}, \boldsymbol\Sigma_{\boldsymbol\eta})$ and the $\mathbf{x}_n$ are considered fixed.

Compute the MSE of the predictions $\mathbb{E}[(y-\hat{y})^2]$, where $y$ is the true response and $\hat{y}$ is the predicted value, given a test point $\mathbf{x}$ and using the LS estimator $$\hat{\boldsymbol\theta}=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y}\text{.}$$ The LS estimator has been obtained via a set of $N$ measurements, collected in the (fixed) input matrix $\mathbf{X}$ and $\mathbf{y}$ [....] The expectation $\mathbb{E}[\cdot]$ is taken with respect to $y$, the training data $\mathcal{D}$, and the test points $\mathbf{x}$. Observe the dependence of the MSE on the dimensionality of the space.

Hint: Consider, first, the MSE, given the value of a test point $\mathbf{x}$, and then take the average over all the test points.

My attempt:

Theodoridis shows on p. 81 that the generalization error $\mathbb{E}_{y\mid\mathbf{x}}\mathbb{E}_{\mathcal{D}}\left[\left(y-f(\mathbf{x};\mathcal{D})\right)^2\right]$ at $\mathbf{x}$ is $$\mathrm{MSE}(\mathbf{x}) = \sigma^2_{\eta}+\mathbb{E}_{\mathcal{D}}\left[\left(f(\mathbf{x};\mathcal{D})-\mathbb{E}_{\mathcal{D}}f(\mathbf{x};\mathcal{D})\right)^2\right]+\left(\mathbb{E}_{\mathcal{D}}f(\mathbf{x};\mathcal{D})-\mathbb{E}[y\mid\mathbf{x}]\right)^2$$ Setting $$\hat{y}=f(\mathbf{x};\mathcal{D})=\mathbf{x}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y}$$ we obtain $$\mathbb{E}_{\mathcal{D}}\hat{y}=\mathbf{x}^{T}\mathbb{E}_{\mathcal{D}}\left[(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y}\right]=\mathbf{x}^{T}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{X}\boldsymbol\theta=\mathbf{x}^{T}\boldsymbol\theta$$ so $$\left(f(\mathbf{x};\mathcal{D})-\mathbb{E}_{\mathcal{D}}f(\mathbf{x};\mathcal{D})\right)^2 = \left\{\mathbf{x}^{T}\left[(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{X}\mathbf{y}-\boldsymbol\theta\right]\right\}^2$$ This looks disgusting (and not easily simplified), so I'm guessing I'm doing something wrong. We also have $\sigma^2_\eta = 1$ by assumption.

Edit: This appears to be solved in the 12th printing (Jan 2017) of Elements of Statistical Learning by Hastie et al. (see here), equation (2.47) on p. 37, but they seem to have skipped showing the details (not to mention, I find the notation confusing).

$\endgroup$
4
+100
$\begingroup$

Here are two facts that we can utilize: if $A$ is a constant matrix, then $$\operatorname{E}[AX]=A\operatorname{E}[X],\qquad\operatorname{Var}(AX)=A\operatorname{Var}(X)A'.$$

For convenience let's denote $\hat{y}=f(\mathbf{x};\mathcal{D})$. Notice that $\operatorname{E}_{\mathcal{D}}\left[\left(\hat{y}-\operatorname{E}[\hat{y}]\right)^2\right]$ is just a fancy way of writing $\operatorname{Var}_{\mathcal{D}}(\hat{y})=\operatorname{Var}_{\mathcal{D}}(x'(X'X)^{-1}X'y)$. Thus, $$\operatorname{E}_{\mathcal{D}}\left[\left(\hat{y}-\operatorname{E}[\hat{y}]\right)^2\right]=x'(X'X)^{-1}X'\operatorname{Var}_{\mathcal{D}}(y)X(X'X)^{-1}x=x'(X'X)^{-1}x.$$ On the other hand, you already know that $\operatorname{E}_{\mathcal{D}}[\hat{y}]=x'\theta$, since $\operatorname{E}[\eta]=0$, the bias part $$\operatorname{E}_{\mathcal{D}}[\hat{y}]-\operatorname{E}[y\mid x]=0$$ as well. Therefore, the MSE over one test point $x$ is $$\operatorname{MSE}(x)=1+x'(X'X)^{-1}x.$$

To average over the test set, note that $$x'(X'X)^{-1}x=\operatorname{tr}(x'(X'X)^{-1}x)=\operatorname{tr}((X'X)^{-1}xx').$$ So $$\operatorname{E}_x[x'(X'X)^{-1}x]=\operatorname{tr}((X'X)^{-1}\operatorname{E}_x(xx')).$$

$\endgroup$
  • $\begingroup$ Thank you! One last question for you... the exercise says to, after $\mathrm{MSE}(\mathbf{x})$ is computed, "take the average over all test points." So this would amount to finding $\mathbb{E}_{\mathbf{x}}\mathrm{MSE}(\mathbf{x})$. However, $\mathbf{x}^{\prime}(\mathbf{X}^{\prime}\mathbf{X})^{-1}\mathbf{x}$ is not a linear transformation of $\mathbf{x}$ (in fact, it's a quadratic form). What is Theodoridis intending here? $\endgroup$ – Clarinetist Jan 9 '18 at 14:48
  • $\begingroup$ @Clarinetist: just edited my answer, the average can be simplified a little by the trace-expectation trick, maybe that's what the author intended. $\endgroup$ – Francis Jan 9 '18 at 15:03
  • 1
    $\begingroup$ Thank you, I definitely wouldn't have known to do that! So in other words... what appears is happening is that the expected MSE will only become larger (the trace is the sum of scaled squared terms) as the length of $\mathbf{x}$ increases. Very interesting stuff. $\endgroup$ – Clarinetist Jan 9 '18 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.