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 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. :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.