Lecture 34 · Regression: how good is the ML estimator?

Goodness of the Maximum Likelihood Estimator

Because the labels are random, $\hat w_{\text{ML}}$ is random too: a different draw of noise gives a different estimate. Measure its quality by the average squared distance to the true $w$. The answer, $\sigma^2\,\operatorname{tr}\big((XX^\top)^{-1}\big)$, depends on the noise and on the features, and the feature part is something we might be able to improve.

Source: this lecture on YouTube (≈12 min). Previous: L33 · Next: L35.

1 · Recap

Model: $y\mid x=w^\top x+\epsilon$, $\epsilon\sim\mathcal N(0,\sigma^2)$, so $y\mid x\sim\mathcal N(w^\top x,\sigma^2)$. Maximum likelihood gave

$$\hat w_{\text{ML}}=(XX^\top)^{+}Xy,$$

the same $w^\star$ as least squares (L33). Now: how good a guess for the true $w$ is it?

2 · The estimator is a random variable

$\hat w_{\text{ML}}$ is the solution of an optimisation problem that involves the data, and the labels $y_i=w^\top x_i+\epsilon_i$ are random. So $\hat w_{\text{ML}}$ is a function of random quantities, hence random. (Nothing is assumed about how $x$ is generated; the features are treated as given.)
On an unlucky day the noise values $\epsilon_i$ are large, the labels carry little information about $w$, and the estimate is poor. So we can't judge the estimator from a single dataset.
Instead we ask how it performs on average, over all the datasets the noise could have produced.

3 · Measuring goodness: mean squared error

Both $\hat w_{\text{ML}}$ and $w$ live in $\mathbb R^d$, so measure their squared Euclidean distance, and average over the randomness in $y$:

$$\text{MSE}(\hat w_{\text{ML}})=\mathbb E\Big[\,\lVert\hat w_{\text{ML}}-w\rVert^2\,\Big].$$

Thought experiment: generate a dataset (same $x_i$, fresh noise), compute $\hat w_{\text{ML}}$, record $\lVert\hat w_{\text{ML}}-w\rVert^2$. Repeat many times and average. That average converges to the expectation above. The demo below does exactly this.

4 · The answer

The lecture states the result without derivation (it's a short algebraic exercise, done in the note below):

$$\boxed{\;\mathbb E\Big[\lVert\hat w_{\text{ML}}-w\rVert^2\Big]=\sigma^2\;\operatorname{tr}\!\Big(\big(XX^\top\big)^{-1}\Big)\;}$$

(use the pseudo-inverse if $XX^\top$ isn't invertible; for simplicity assume it is.) It is a product of two terms:

Term	What it is	Effect
$\sigma^2$	variance of the label noise	More noise, worse estimate. Makes sense: noise hides $w^\top x$.
$\operatorname{tr}\big((XX^\top)^{-1}\big)$	depends only on the features; $XX^\top$ is like a covariance matrix	How the features relate to each other also decides the quality of the estimate.

5 · What we can and can't control

$\sigma^2$ belongs to the data-generating process. The noise is added before the data reaches us, so we have to live with it. The features $X$, though, are in our hands. So if a better estimator (lower mean squared error) exists at all, it has to come from doing something about the $\operatorname{tr}\big((XX^\top)^{-1}\big)$ part. That's the question for L35.

Two features, true $w=(1,\,-0.5)$. The features are drawn once (fixed); each dot is $\hat w_{\text{ML}}$ from one of 400 datasets with fresh label noise. Correlation makes the two features nearly redundant.

noise σ = feature correlation ρ = n =

ŵ_ML from one datasettrue waverage of the ŵ's

–

average ‖ŵ − w‖² (400 runs)

–

σ² · tr((XXᵀ)⁻¹)

–

eigenvalues of XXᵀ

The derivation, going beyond the video. Stack the noise into $\epsilon\in\mathbb R^n$, so $y=X^\top w+\epsilon$. Then $$\hat w_{\text{ML}}=(XX^\top)^{-1}X(X^\top w+\epsilon)=w+(XX^\top)^{-1}X\epsilon .$$ Since $\mathbb E[\epsilon]=0$, $\mathbb E[\hat w_{\text{ML}}]=w$: the estimator is unbiased (the green dot sits on the orange one). Its error is $(XX^\top)^{-1}X\epsilon$, and with $\mathbb E[\epsilon\epsilon^\top]=\sigma^2 I$, $$\mathbb E\lVert\hat w_{\text{ML}}-w\rVert^2=\mathbb E\big[\epsilon^\top X^\top(XX^\top)^{-2}X\epsilon\big]=\sigma^2\operatorname{tr}\big(X^\top(XX^\top)^{-2}X\big)=\sigma^2\operatorname{tr}\big((XX^\top)^{-1}\big),$$ using $\mathbb E[\epsilon^\top M\epsilon]=\sigma^2\operatorname{tr}(M)$ and the cyclic property of the trace.

Key takeaways

The labels are random, so $\hat w_{\text{ML}}$ is random. Judge it on average over datasets, not on one.
Goodness = mean squared error $\mathbb E\lVert\hat w_{\text{ML}}-w\rVert^2=\sigma^2\operatorname{tr}\big((XX^\top)^{-1}\big)$.
Two factors: noise variance $\sigma^2$ (out of our control) and a feature term (possibly improvable).
Any better estimator must attack the $\operatorname{tr}\big((XX^\top)^{-1}\big)$ term (L35).