View Single Post
Old 04-18-2013, 09:21 PM
Michael Reach Michael Reach is offline
Senior Member
Join Date: Apr 2013
Location: Baltimore, Maryland, USA
Posts: 71
Default Re: A little puzzle

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?
Reply With Quote