LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 1 - The Learning Problem (http://book.caltech.edu/bookforum/forumdisplay.php?f=108)
-   -   Hoeffding inequality for multiple classifiers (http://book.caltech.edu/bookforum/showthread.php?t=4021)

 cls2k 02-22-2013 01:51 PM

Hoeffding inequality for multiple classifiers

I'm having some trouble understanding the case of applying Hoeffding to the case of multiple classifier (Bins). Shouldn't the final picked hypothesis g* still be bound by Hoeffding's inequality since its just like any other hypothesis in the set? How does the process of picking the hypothesis based on the data affect the Hoeffding's bound? What if I pick the worst hypothesis instead of the best one? shouldn't hoeffding's bound apply to that too?

While I understand the mathematics behind the union bound, it seems unintuitive that the bond on g* should be a union of all the bonds of h() in the set since the final g* does not have anything to do with the other unpicked hypothesis.

I do understand the coin example. since the chance of getting 10 heads in a row for one coin is very low but its actually high if you repeat the experiment 1000 times. However I'm unsure as to how this relates to the learning scenario. Getting 10 heads on a sample would be equivelant to getting an Ein of 0. But its mentioned again and again that this is a "bad" event. How does this have anything to do with the Hoeffding bound?

Any insight into this will be greatly appreciated.

 yaser 02-22-2013 04:36 PM

Re: Hoeffding inequality for multiple classifiers

Quote:
 Originally Posted by cls2k (Post 9477) I'm having some trouble understanding the case of applying Hoeffding to the case of multiple classifier (Bins). Shouldn't the final picked hypothesis g* still be bound by Hoeffding's inequality since its just like any other hypothesis in the set? How does the process of picking the hypothesis based on the data affect the Hoeffding's bound? What if I pick the worst hypothesis instead of the best one? shouldn't hoeffding's bound apply to that too?
The assumptions used to prove Hoeffding necessitate that not depend on the sample, which is violated when is the hypothesis since it was chosen according to the sample. Without this assumption, the proof doesn't go through.

Quote:
 While I understand the mathematics behind the union bound, it seems unintuitive that the bond on g* should be a union of all the bonds of h() in the set since the final g* does not have anything to do with the other unpicked hypothesis.
It is just a bound that can be asserted without making assumptions about what depends on what, so it is valid even if more careful analysis in a particular case yields a tighter bound.

Quote:
 I do understand the coin example. since the chance of getting 10 heads in a row for one coin is very low but its actually high if you repeat the experiment 1000 times. However I'm unsure as to how this relates to the learning scenario. Getting 10 heads on a sample would be equivelant to getting an Ein of 0. But its mentioned again and again that this is a "bad" event. How does this have anything to do with the Hoeffding bound?
Equate getting a head with making an error, and that explains the 'bad event' part. The relation to learning is that the sample suggests the coin is not fair when in fact it is, which means generalization is poor.

 All times are GMT -7. The time now is 06:19 AM.

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. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.