Question on VC dimension

[Suhas Patil]

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]

If , then with enough data, for every hypothesis in your learning model. This is why the final hypothesis will generalize, because it is one of the hypotheses in . The connection to learning comes when you pick the hypothesis with minimum Ein.

Because , 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 then the answer to this second step will be yes. If your is bad then the answer will be no, and you will declare that you failed, but you know you failed.

Originally Posted by Suhas Patil

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.