Exercise 2.6

[wolszhang]

I am pretty confused with the Ein and Eout. According to my understanding, Etest 's error bar is calculated by Hoeffding Bounds with hypothesis set size = 1. But if i want to use Ein to estimate Eout, I either need the growth function or dvc and none of these two is given. i would assume that Etest would have a smaller error bar. But i cannot prove it.
Also, for part(b), the only reason i come up with is that the hypothesis that we would be testing would not be as good as it is with a bigger N. And if Etest is big, we are screwed.
Any help would be appreciated. Thanks

[wqymcgill]

Hi,

For part(a), I simply assume dvc=0 and get an error bar of about 0.316. Etest's error bar is only about 0.096. So Ein will always be higher thatn Etest no matter what dvc is.

For part(b), I don't know why either.. Hope anyone helps.

[bonfire09]

I'm stuck on this problem too. I was thinking we just use the generalization error for both.

Do we just calculate E_out<=E_test+sqrt(1/200 ln (2/0.5)) and
E_out<=E_in+sqrt(1/400 ln(2/0.5)) ?

[SpencerNorris]

I'm wondering what bounds we should use for E_test and E_in. It states that E_test obeys the simple Hoeffding bound; does this mean that we should use the generalization error outlined on p.40, eq. 2.1? Or can we use the VC Bound on E_test as well as E_in?

[anirban.das]

2.6.a I think that the training error bound (as well as the testing error bound) is given by equation (2.1), because in this particular case the hypothesis set is finite already.

2.6.b Also, here I suppose more examples in testing data set will do nothing much as it is already a good apprx. to the E_out, but this will decrease the available training samples and we would get a stupid final hypothesis.

Any thoughts?

[k_sze]

I don't think the growth function or VC dimension are involved at all? The exercise tells us the exact size of the hypothesis set (the learning model), which is 1000, right?

[seoma]

thanks for your post
کاراپ