Shattering by dichotomies

[timhndrxn]

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.

[magdon]

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


Def 2.4 is introducing a more subtle concept. Fix a break point and consider the worst possible hypothesis set with the condition that it must have a break point . Worst means having the largest . The growth function of this worst hypothesis set is called . The indicates that the hypothesis set must have a break point there; otherwise is very much like 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 (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 , we cannot really analyze without more information on they hypothesis set. But since 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 by



for any hypothesis set that has a break point at .

Originally Posted by timhndrxn

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.

[jcatanz]

Thanks for this helpful explanation!

[timhndrxn]

Magdon, the explanation helps. Thank you. --Tim