Q3, general question

fgpancorbo · #1 08-13-2012, 08:28 AM

Is this a trick question, or just a direct application of the concepts learned in class, and present in the book? If want to pick the smallest

such that $x \geq VC_{\tilde{d}}$ , this is the same thing as saying pick the smallest

such as $VC_{\tilde{d}} \leq x$ . The example of a polynomial transformation is discussed in detail in the book and the generic formula for the upper bound is provided. Is there anything in this example that begs for a tighter bound that that provided by the formula that appears in page 105 of the book?

I have an even more general question about the VC dimension of these nonlinear transformations. I understand that in the transformed space one needs to apply the dichotomy analysis to come up with the VC dimension and that (since we did it for the general linear case) that is $\tilde{d} + 1$ . Yet there is the caveat that some of the dichotomies that allow for that VC dimension might not be valid points of the transformation. But isn't that the case that the likelihood that the vast majority of points that would allow for such VC dimension will NOT be valid points of the transformation because we are trying to generate $\tilde{d}$ independent points out of

degrees of freedom. Thus, in most cases the VC dimension is likely to be closer to

than to $\tilde{d} + 1$ , unless one gets really lucky.

yaser · #2 08-13-2012, 01:55 PM

Quote:

Originally Posted by fgpancorbo

If want to pick the smallest

such that $x \geq VC_{\tilde{d}}$ , this is the same thing as saying pick the smallest

such as $VC_{\tilde{d}} \leq x$ .

Can you explain this?

Quote:

I have an even more general question about the VC dimension of these nonlinear transformations. I understand that in the transformed space one needs to apply the dichotomy analysis to come up with the VC dimension and that (since we did it for the general linear case) that is $\tilde{d} + 1$ . Yet there is the caveat that some of the dichotomies that allow for that VC dimension might not be valid points of the transformation. But isn't that the case that the likelihood that the vast majority of points that would allow for such VC dimension will NOT be valid points of the transformation because we are trying to generate $\tilde{d}$ independent points out of

degrees of freedom. Thus, in most cases the VC dimension is likely to be closer to

than to $\tilde{d} + 1$ , unless one gets really lucky.

You are right about the difficulty in generating independent points in the transformed space. However, for the purpose of the VC dimension, we only need one such set of points, and the "independence" only pertains to our ability to shatter them even if they are not arbitrarily located in the transformed space.

fgpancorbo · #3 08-13-2012, 02:23 PM

Thanks for the answer on the general question. The bottom line is that one has to be very careful with these transformations.

Quote:

If want to pick the smallest

such that $x \geq VC_{\tilde{d}}$ , this is the same thing as saying pick the smallest

such as $VC_{\tilde{d}} \leq x$ .
Can you explain this?

Maybe I am asking something trivial here but I don't get it, sorry if the question is irrelevant

. And I also think that I made a mistake with my labels of the VC dimensions

. Let's try it again. The question asks "What is the smallest value among the following choices that is $\geq$ the VC dimension of a linear model in the transformed space?". If $5 \geq 3$ , this is the same as saying $3 \leq 5$ , right? Is I read it, the question seems to be asking about the upper bound of $VC_{\tilde{\mathcal{H}}}$ , a topic that is covered, for the class of polynomial transformations, in the book. Are we supposed to apply those concepts here, or, on the other hand, there is something particular to this transformation that begs for a tighter upper bound?

tzs29970 · #4 08-13-2012, 04:52 PM

I got this one wrong...not because of the mathematical challenge, but because of the typographical challenge!

Anyone else with old eyes lose track of the little semicolons down among the little subscripts, and so miscount the number of features in the transformed space? Doh!

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode