2
$\begingroup$

Setting:

Let $S$ be a set of $m$ samples from a set $Z$ and $w^{*}$ be an arbitrary vector. (Samples Are I.I.D and we are operating in a binary classification setting)

Then $\mathbb{E}_{S \sim D^{m}}\left[L_{S}\left(w^{*}\right)\right]=L_{D}\left(w^{*}\right)$

Where: $L_{S}\left(w^{*}\right) \equiv \frac{1}{m} \sum_{i=1}^{m} l\left(w^{*}, z_{i}\right)$ and $z_{i} \in S, L_{D}\left(w^{*}\right) \equiv \mathbb{E}_{z \sim D}\left[l\left(w^{*}, z\right)\right], D$ is a distribution on $Z,$ and $l(\ldots)$ is a loss function.

When proving that the empirical risk is an unbiased estimate of the risk we usually argue that.

$\begin{aligned} \mathbb{E}_{S} L_{n}(h) &=\mathbb{E}_{S} \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\left[h\left(X_{i}\right) \neq Y_{i}\right] \\ &=\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{S} \mathbf{1}\left[h\left(X_{i}\right) \neq Y_{i}\right] \\ &=\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{(X, Y)} \mathbf{1}[h(X) \neq Y] \\ &=\frac{1}{n} \sum_{i=1}^{n} L(h) \\ &=L(h) \end{aligned}$

or something along these lines. (Thorough proofs can be seen at)

1) Binary Classification : Prove that $\mathbb{E}_{\mathcal{D}_n}\left[R_e(h)\right] = R(h)$

2) Why is the risk equal to the empirical risk when taking the expectation over the samples?

After this, we can pose a Claim that there exists a distribution $P$ and a learner, such that for all $n$ we have $$ L_{n}\left(h_{n}\right)=0 \text { and } L\left(h_{n}\right)=1 $$

Meaning that we can create a model that overfits on the Training Data $S$.

As: $E\left[L\left(f^{*}\left(S\right)\right)-\hat{L}\left(f^{*}\left(S\right), S\right)\right] \geq 0$.

Meaning that the training error actually IS a biased estimate of the risk. On a high level, we are told that this happens because $h_n$ depends on the data and that at any given sample size, there exist functions, for which true and empirical risk are arbitrarily far apart.

Question:

Now I want to know how does $h_n$ being dependent on the data $S$ breaks the proof that the empirical risk is an unbiased estimate of the risk. Is the IID assumption broken or what exactly happens mathematically.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.