View Single Post
Old 04-21-2013, 12:25 PM
Elroch Elroch is offline
Invited Guest
Join Date: Mar 2013
Posts: 143
Default 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 N points where N\geq k is given by the fact that we know some set of k-1 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 2^{k-1} for all N>=k.

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