LFD Book Forum Relation between feasibility of learning and Hoeffding's Inequality.
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
04-04-2013, 12:14 AM
 jlaurentum Member Join Date: Apr 2013 Location: Venezuela Posts: 41
Relation between feasibility of learning and Hoeffding's Inequality.

Hello.

I understand that learning is picking out a function from a candidate set of functions that most closely resembles the target function. The feasibility of learning would be related to how close this resemblance is.

I understand also that Hoeffding's Inequality is an upper bound to the probability that the in-sample error rate deviates significantly from the real error rate. In the end, this upper bound simply implies that given a large enough sample, estimating the real error rate is feasible.

Is there any misconception in anything here so far?

So my question is: what does the Hoeffding inequality say about the feasibility of learning? Shouldn't it be feasibility of verifying hypothesis?
#2
04-04-2013, 12:51 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Relation between feasibility of learning and Hoeffding's Inequality.

Quote:
 Originally Posted by jlaurentum Hello. I understand that learning is picking out a function from a candidate set of functions that most closely resembles the target function. The feasibility of learning would be related to how close this resemblance is. I understand also that Hoeffding's Inequality is an upper bound to the probability that the in-sample error rate deviates significantly from the real error rate. In the end, this upper bound simply implies that given a large enough sample, estimating the real error rate is feasible. Is there any misconception in anything here so far? So my question is: what does the Hoeffding inequality say about the feasibility of learning? Shouldn't it be feasibility of verifying hypothesis?
Hi,

Your understanding is correct. The contrast between learning and verification that you allude to is precisely why the union bound was used in Lecture 2. The notion of the feasibility of learning will be further discussed next week in Lecture 4, where the question is split into two parts. Stayed tuned!
__________________
Where everyone thinks alike, no one thinks very much
#3
04-04-2013, 10:07 AM
 jlaurentum Member Join Date: Apr 2013 Location: Venezuela Posts: 41
Re: Relation between feasibility of learning and Hoeffding's Inequality.

Thank you very much for your quick response, Professor Yaser. Your course sets the bar for quality in MOOCs very high. You have my respect and gratitude.

At the beginning of minute 32 in the Lecture 2 video, you say "P can be any probability, but the choice of P can affect the value of ...". Is it or ? My intuition tells me it should be , because it is a random variable that varies with the sample, whereas is a fixed but unknown parameter. However, I think I'm hearing "mu" mentioned several times in this context. Can you please clarify this point?
#4
04-04-2013, 01:08 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Relation between feasibility of learning and Hoeffding's Inequality.

Quote:
 Originally Posted by jlaurentum Thank you very much for your quick response, Professor Yaser. Your course sets the bar for quality in MOOCs very high. You have my respect and gratitude. At the beginning of minute 32 in the Lecture 2 video, you say "P can be any probability, but the choice of P can affect the value of ...". Is it or ? My intuition tells me it should be , because it is a random variable that varies with the sample, whereas is a fixed but unknown parameter. However, I think I'm hearing "mu" mentioned several times in this context. Can you please clarify this point?
Thank you.

affects the value of (the probability) since it gives different weights to different input points where there is agreement/disagreement with the target. Consequently, it also affects the value of (the random variable) through its impact on .
__________________
Where everyone thinks alike, no one thinks very much
#5
04-07-2013, 06:00 AM
 kokrah Junior Member Join Date: Apr 2013 Posts: 3
Re: Relation between feasibility of learning and Hoeffding's Inequality.

Thanks for the lectures. I am a stats phd student at MD (new to the ideas of ML). A friend recommended your site.
My understanding of lecture 2 is that you are setting up a general framework to
answer the question of "Is this model feasible?".
In the -tossing 1000 coins 10 times analogy- each of the 1000 coins are the same.
i.e. each of the possible h's in H are thought of as being the same in some sense, at least in the goal of finding a crude bound.
The prob. distribution placed on the input space X affects the bin content and
hence the sample content for any h in the Model, H.

Question: In this 1st step framework: a small (overall) bound of say 0.001 implies a g/model is verified as learnable? i.e. any g/H is learnable is you if have a very large sample size and reasonable M?
Any comments/corrections from anyone is appreciated. Thanks

 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 01:23 PM.

 Contact Us - LFD Book - Top

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.