LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   General Discussion of Machine Learning (http://book.caltech.edu/bookforum/forumdisplay.php?f=105)
-   -   example non-overlap hypothesis set H to make union bound equals vc bound (http://book.caltech.edu/bookforum/showthread.php?t=4659)

wordchao 02-16-2016 07:29 PM

example non-overlap hypothesis set H to make union bound equals vc bound
 
consider the union bound, when H consists of only h1 and h2,
Pr[|Ein(g)-Eout(g)|>e]
<=Pr[|Ein(h1)-Eout(h1)|>e or |Ein(h2)-Eout(h2)|>e] (eq.1)
<=Pr[|Ein(h1)-Eout(h1)|>e] + Pr[|Ein(h2)-Eout(h2)|>e] (eq.2)
=2exp(-2Ne^2) (eq.3)

i wonder which kind of h1 and h2 can more "accurately" satisfy the union bound, maybe this means union bound equals vc bound.
in other words, can i find h1 and h2 to let (eq.1)=(eq.2)?

Pr[|Ein(h1)-Eout(h1)|>e or |Ein(h2)-Eout(h2)|>e]
=Pr[|Ein(h1)-Eout(h1)|>e and |Ein(h2)-Eout(h2)|>e] (eq.a)
+Pr[|Ein(h1)-Eout(h1)|>e and |Ein(h2)-Eout(h2)|<=e] (eq.b)
+Pr[|Ein(h1)-Eout(h1)|<=e and |Ein(h2)-Eout(h2)|>e] (eq.c)

if (eq.2)=(eq.1), then,
sup(eq.a)=0
sup(eq.b)=sup(eq.c)=1/2(eq.3)=exp(-2Ne^2)

but i cannot find the example h1&h2, which means h1 and h2 has no overlap when considering the union bound.
can u help? :):D thanks.

htlin 02-17-2016 07:47 PM

Re: example non-overlap hypothesis set H to make union bound equals vc bound
 
One possibility is when h_1 = f which makes E_{in}(h_1) = E_{out}(h_1) = 0 always and hence the event of the difference > \epsilon would be of zero probability and the union bound is trivially true. But I guess that's not what you are looking for. :clueless:

wordchao 02-21-2016 05:17 PM

Re: example non-overlap hypothesis set H to make union bound equals vc bound
 
Hi, htlin. I'm sorry for check the reply late.

Thanks for your proposition and it is a good institution.
I want to find a more general way to build examples but I have not done it.
I tried a small lab,
when the loss function of h1 and h2 are same/or complementary, A=B;
when increase the difference btw loss functions of h1 and h2, the overlap btw A&B increase also.


keep in touch if u would like, i am new in Mearchine learning.
https://www.facebook.com/wordchao


All times are GMT -7. The time now is 12:26 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. 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.