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 breakpoint 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
.
Quote:
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.
