View Single Post
#4
04-21-2013, 12:25 PM
 Elroch Invited Guest Join Date: Mar 2013 Posts: 143
Re: slide #4 lecture 6 'Recursive Bound on B(N,k)'

I should perhaps explain the thinking behind my last post on the general bounds on the variation of growth functions (so someone can check it ). The minimum number of dichotomies on a set of points where is given by the fact that we know some set of points is shattered, and we can extend such a shattering in a minimal way to the whole set of points in a way that excludes all other points. This makes the growth function constant for all .

I believe all the possible values of the growth function between this minimum and the bound B(N, k) can occur for some carefully chosen hypothesis set, but haven't actually proved it. Is this so?