LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Question on VC dimension (http://book.caltech.edu/bookforum/showthread.php?t=3920)

Suhas Patil 01-26-2013 08:51 PM

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.

magdon 01-26-2013 09:11 PM

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 (Post 9016)
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.



All times are GMT -7. The time now is 12: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.