View Single Post
Old 04-19-2012, 01:46 PM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 595
Default Re: Shattering by dichotomies

Def 2.2 defines m(n) using H(x_1,x_2,\ldots,x_N) which is the restriction of H to a data set, i.e the number of different hypotheses that H can implement on this particular data set. A hypothesis when restricted to a finite data set results in a dichotomy, a collection of \pm 1 on the data points; A dichotomy is similar to a hypothesis. H does not shatter a dichotomy. It shatters a data set. So H shatters a data set if when restricted to that data set, H can implement all the 2^N dichotomies.

Def 2.4 is introducing a more subtle concept. Fix a break point k and consider the worst possible hypothesis set with the condition that it must have a break point k. Worst means having the largest m(N). The growth function of this worst hypothesis set is called B(N,k). The k indicates that the hypothesis set must have a break point there; otherwise B(N) is very much like m(N) except it is not for a particular hypothesis set, but rather for the worst possible hypothesis set with the break-point property.

We can analyze B(N,k) (even though it looks harder to analyze since we don't know what this worst hypothesis set is). However, for a particular hypothesis with break point k, we cannot really analyze m(N) without more information on they hypothesis set. But since B(N,k) is for the worst possible hypothesis set, the particular hypothesis set cannot be worse than this and so must have a smaller growth function. That is we indirectly bound m(N) by

m(N)\le B(N,k)

for any hypothesis set that has a break point at k.

Originally Posted by timhndrxn View Post
OK, Definition 2.2 talks about shattering dichotomies based on H. So H shatters dichotomies. So all was OK until Definition 2.4, which talks about shattering dichotomies by other dichotomies.
Have faith in probability
Reply With Quote