I am currently trying to go through the "Understanding Machine Learning: From Theory to Algorithms" book. The book is heavy on the maths and I get a bit confused by the notation sometimes but I am making slow progress.

There is a section on overfitting and the authors illustrate it with this example.

Attached is the section. Apologies for sticking the PDF but this would otherwise take me a long time to type and explain.

enter image description here

Now I understand that equation 2.3 is saying that during the training, our prediction rule $h_S(x)$ will predict the training label of the sample we are investigating and the prediction will be 0 everywhere else. So, during our testing if we encounter a sample that we have seen during the training we will output the correct label/prediction otherwise we will just output 0.

Now, it says the true error for this predictor is actually $\frac{1}{2}$. I am not sure why that would be. The instances are distributed uniformly and assuming the training sample does not cover the whole population then how can we draw this conclusion that the true error will be the ratio of the areas of the two squares? The true error is defined as the probability of making an incorrect prediction. Surely that should somehow relate to how densely by test dataset is sampled over the population space? For example, suppose my inner square is very densely sampled in the training set. In that case, I should have close to perfect prediction in the real world.

What have I misunderstood here?


Any sample set we create from probability distribution $D$ will be countable because we can label the first sample we get as 1, the second as 2 and so on. However, there are uncountably infinite distinct points that may be sampled from probability distribution $D$. Thus, even with an arbitrarily large training set of any ratio of labels, the loss of $h_S$ on the entire uncountably infinite population makes the loss on the countable training set infinitesimal and so still yields 1/2 because a sample with label 0 is just as likely as a sample with label 1.

  • $\begingroup$ Thanks for that explanation. So, it is due to the size of the infinities involved. I can tell this book will take me a decade to finish! Thanks again! $\endgroup$ – Luca Aug 1 '17 at 21:46
  • 1
    $\begingroup$ Yes, that is exactly it. You're welcome! $\endgroup$ – Evan Phibbs Aug 1 '17 at 21:46

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.