Problem 5.1b
I get as far as this
P ≥ 1  4mH(N)^2/e^(N/32) but I'm not certain how to go about showing that P ≥ 1  mH(N)/2^N Maybe I have totally the wrong approach: I started with Eout(h) ≤ Ein(h) + sqr (8/N ln(4mH(N)^2/δ)) with P ≥ 1δ So perhaps there's another formula that would work better. I feel like I'm making a silly mistake somewhere but I'm not sure what it could be. 
Re: Problem 5.1b
If the data is generated from a random (arbitrary) target function, then every dichotomy is equally likely. Since you can implement at most m(N) of these dichotomies, the number of dichotomies you cannot implement is at least 2^Nm(N). Each of these dichotomies you cannot implement has probability 1/2^N
Quote:

Re: Problem 5.1b
I just want to say thank you, my problem is solved

All times are GMT 7. The time now is 01:27 PM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2020, 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.