In an ml-class, they introduced overfitting with an example:

Say, we have

  • $x$ picked from $Uniform(0,1)$
  • $v$ random noise, picked indepidently of $x$ from $Uniform(-0.3,0.3)$ and $\mathbb{E}[v] = 0$
  • $y = +1$ , if $x+v \geq \frac{1}{2}$, otherwise $y = -1$

If we take a sample from this distribution, we may learn a hypothesis, such that the 0-1-loss on the sample would be zero. This hypothesis would consist of a series of intervals so that a point which falls in one of the intervals, would be classified with $+1$, otherwise as $-1$

However, an optimal hypothesis (one with minimal generalzation error) would be the one, which classifies $x$ as +1, if $x < \frac{1}{2}$, else as -1.

Intuitively I understand, that the $\frac{1}{2}$-hypothesis is optimal because we expect noise to be 0.

I wonder how to prove that mathematically, in particular, would the $\frac{1}{2}$-hypothesis stay optimal, if $v$ would be sampled from some other distribution with mean 0?

Any hints will be appreciated.


Your Answer

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

Browse other questions tagged or ask your own question.