LFD Book Forum Why multiply right side of Hoeffding Inequality by number of hypothesis?
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
03-30-2014, 12:17 AM
 dvs79 Member Join Date: Jul 2012 Location: Moscow, Russia Posts: 24
Why multiply right side of Hoeffding Inequality by number of hypothesis?

I don't quite understand reasoning here.
I understand that probability of event from many attempts is increasing (the more coins we toss the higher probability to have at least one tails). And we can loosely estimate such probability as P(A or B) <P(A)+P(B), ignoring term -P(A and B) for simplicity.
But why should we apply this estimation to our goal function g(x) if we chose it as the only result of our learning? We don't ask ourselves "What's the probability of bad event (exceeding tolerance to generalization) among ALL our tested hypothesis?". We interested in "What's the probability of the bad event for a certain hypothesis, we somehow chose?" I mean, yes, probability to toss at least 1 tails with 10 coins is very close to 1, but nonetheless, probability to toss tails for each single coin out of those ten is still 0.5, right?
So why to lift the threshold of probability of bad event for our final hypothesis, multiplying right part of inequality by M?
#2
03-30-2014, 10:13 AM
 dvs79 Member Join Date: Jul 2012 Location: Moscow, Russia Posts: 24
Re: Why multiply right side of Hoeffding Inequality by number of hypothesis?

Oh, I think I got it.
The link in reasoning that I missed is that probability of bad event in each hypothesis MAY AFFECT our final choice. But we don't know how, so we consider the range between the best and the worst possible cases.

The best case - bad events happening in tested hypothesis don't affect our choice of the final one at all, so for probability of bad event in g(x) we can still use Hoeffding without factor M.

The worst case - when we have such sample, and such hypothesis set, and such learning algorithm that bad event in some hypothesis makes us to select the very same hypothesis as a final one. In this unlucky situation probability of bad event in final hypothesis will be probability of "at least one hypothesis in a set has bad event".

Am I right?
#3
04-02-2014, 01:54 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Why multiply right side of Hoeffding Inequality by number of hypothesis?

You are right!
__________________
Where everyone thinks alike, no one thinks very much

 Thread Tools Display Modes Hybrid 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 06:50 PM.

 Contact Us - LFD Book - Top