Exercise 2.1

[ilson]

Hi,

For the convex set case, it seems to me that since N points on a circle can always be shattered, there's always at least one data set of size k that can be shattered by . Thus, the break point does not exist for this . So then you can't really verify that for this case - or can you say that it's trivially true since break point k doesn't even exist? Is this the correct interpretation of this exercise?

[magdon]

Yes, when there is no break point, the theorem says that for all N. So the theorem is trivially verified.

Originally Posted by ilson

Hi,

For the convex set case, it seems to me that since N points on a circle can always be shattered, there's always at least one data set of size k that can be shattered by . Thus, the break point does not exist for this . So then you can't really verify that for this case - or can you say that it's trivially true since break point k doesn't even exist? Is this the correct interpretation of this exercise?

[svend]

I don't understand why the breaking point inequality holds for the positive rays or positive intervals .

For instance, it seems to me that no set of 3 real points can be shattered by a positive ray, since at least always the [cross, circle, cross] dichotomy cannot be achieved, no matter how large is, so would be a breaking point and , which is obviously not true for since the real growth function is .

I understand that to be a breaking point, we need that no set of size k can be shattered, am I failing to imagine such set or did I misunderstand some of the definition?

[dubwub]

For N > 7 you need your growth function to be less than 2^N, not 2^3.