View Single Post
Old 04-18-2013, 08:41 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: A little puzzle

Originally Posted by Michael Reach View Post
This problem makes me wonder if the VC dimension formula for the growth function isn't (sometimes?) far too restrictive. It's true that the growth function here is 2^N, and therefore our problem is maybe un-learnable. But is that really true? Because we could find one wacko example with numbers 2^50 digits long, does that mean that our hypotheses are really much too general? Actually, this set of hypotheses is awfully restricted, and you (probably) can't hardly do anything with them for almost all sets of x1,...xn. Maybe we should have a modified version of the VC formula, where the bound works for almost all sets of xn. Is it still true that the growth will be polynomial, almost always?
Indeed, the VC dimension addresses a worst-case scenario. The advantage is that it is applicable regardless of what the input probability distribution turns out to be, so 'learnable' means guaranteed to be learnable. The disadvantage is that it may be unduly pessimistic in many practical cases. There is a modified version of this analysis based on expected values. It is more involved technically, and can be found in Vapnik's book.
Where everyone thinks alike, no one thinks very much
Reply With Quote