Re: Ch. 1.3.1 vs. Ch. 1.3.2
I suspect this will be clear!
You have indicated that a coin toss is a trial and you have had 97 of them. The only hypotheses for the toss of a coin are "heads" and "tails". If you have been dead right on 97 trials, you have a double headed coin (or a doubletailed one). This will give you confidence for the next 3 trials. Your example reminded me that Hoeffding requires independent, identically distributed examples. 
Re: Ch. 1.3.1 vs. Ch. 1.3.2
The truth table in section 1.3.1 is emphasizing that if you had your choice of those 8 functions, then each is as good as the other. On any test point, half will be correct, and half wrong.
To link with the coin, you must narrow down from all 8 functions to just one of them, say (this function is picked before you look at the data). Now when you look at the data (five points), you get agreement on all 5 points. Assuming that each set of 5 data points is equally likely to have been picked, the agreement or disagreement is like tossing the coin (with a small modification that repeated data points should have been allowed to have independence). It is still the case that if any of those previous 8 functions could be the true target function, then on a test point is equally likely to be correct as wrong. However, the point being made by the Hoeffding bound is that you must have been extremely unlucky to get those particular points on which you agreed with the target, when in fact you disagreed with the target elsewhere. Or, equivalently, on a normal day you would have made some mistakes on your data, so the fact that you didn't means that either you are having a very abnormal day or your is good. Quote:

All times are GMT 7. The time now is 07:27 PM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2021, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.