LFD Book Forum example non-overlap hypothesis set H to make union bound equals vc bound
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
02-16-2016, 08:29 PM
 wordchao Junior Member Join Date: Feb 2016 Posts: 2
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? thanks.
#2
02-17-2016, 08:47 PM
 htlin NTU Join Date: Aug 2009 Location: Taipei, Taiwan Posts: 601
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.
__________________
When one teaches, two learn.
#3
02-21-2016, 06:17 PM
 wordchao Junior Member Join Date: Feb 2016 Posts: 2
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.

 Tags hypothesis, on-overlap, union bound

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 08:41 AM.

 Contact Us - LFD Book - Top