LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 5

Reply
 
Thread Tools Display Modes
  #1  
Old 08-13-2012, 08:28 AM
fgpancorbo fgpancorbo is offline
Senior Member
 
Join Date: Jul 2012
Posts: 104
Default Q3, general question

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 x such that x \geq VC_{\tilde{d}}, this is the same thing as saying pick the smallest x 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 d degrees of freedom. Thus, in most cases the VC dimension is likely to be closer to d + 1 than to \tilde{d} + 1, unless one gets really lucky.
Reply With Quote
  #2  
Old 08-13-2012, 01:55 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Q3, general question

Quote:
Originally Posted by fgpancorbo View Post
If want to pick the smallest x such that x \geq VC_{\tilde{d}}, this is the same thing as saying pick the smallest x 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 d degrees of freedom. Thus, in most cases the VC dimension is likely to be closer to d + 1 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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 08-13-2012, 02:23 PM
fgpancorbo fgpancorbo is offline
Senior Member
 
Join Date: Jul 2012
Posts: 104
Default Re: Q3, general question

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 x such that x \geq VC_{\tilde{d}}, this is the same thing as saying pick the smallest x 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?
Reply With Quote
  #4  
Old 08-13-2012, 04:52 PM
tzs29970 tzs29970 is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 52
Default Re: Q3, general question

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!
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 01:46 PM.


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