
#1




example nonoverlap 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? thanks. 
#2




Re: example nonoverlap hypothesis set H to make union bound equals vc bound
One possibility is when which makes always and hence the event of the difference would be of zero probability and the union bound is trivially true. But I guess that's not what you are looking for.
__________________
When one teaches, two learn. 
#3




Re: example nonoverlap 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 
Tags 
hypothesis, onoverlap, union bound 
Thread Tools  
Display Modes  

