LFD Book Forum  

Go Back   LFD Book Forum > Book Feedback - Learning From Data > Chapter 2 - Training versus Testing

Reply
 
Thread Tools Display Modes
  #1  
Old 01-26-2013, 07:51 PM
Suhas Patil Suhas Patil is offline
Senior Member
 
Join Date: Dec 2012
Posts: 57
Default Question on VC dimension

I am trying to understand this concept: "If VC dimension is finite, the final hypothesis will generalize". But somehow not able to relate VC dimension and learning. Can someone help.
Thank you for your attention.
Reply With Quote
  #2  
Old 01-26-2013, 08:11 PM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 595
Default Re: Question on VC dimension

If d_{vc}(\cal H)<\infty, then with enough data, Ein\approx Eout for every hypothesis in your learning model. This is why the final hypothesis will generalize, because it is one of the hypotheses in \cal H. The connection to learning comes when you pick the hypothesis with minimum Ein.

Because Ein\approx Eout, by looking at Ein and picking the function with minimum Ein, that hypothesis you pick will also have minimum Eout, and so you will be able to learn (figure out) the best hypothesis in your model using the data.

Well, that is the first step in learning - can you pick/figure out/learn the best hypothesis available to you? That does not mean that that hypothesis is a good hypothesis, but it is the first step.

The second step is to ask whether this hypothesis that was "learned" is good enough. You will know whether the hypothesis is good or not by looking at its Ein (since it is close to Eout). If you had chosen a good \cal H then the answer to this second step will be yes. If your \cal H is bad then the answer will be no, and you will declare that you failed, but you know you failed.

Quote:
Originally Posted by Suhas Patil View Post
I am trying to understand this concept: "If VC dimension is finite, the final hypothesis will generalize". But somehow not able to relate VC dimension and learning. Can someone help.
Thank you for your attention.
__________________
Have faith in probability
Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


All times are GMT -7. The time now is 05:16 AM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, 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.