What is the VC-dimension of intervals in
? The target
function is specified by an interval, and labels any example
positive iff it lies inside that interval.
VC-dim = 2. A set of two points can be shattered, since there's
only a single block of positive examples that could lie within the
interval. But no set of 3 points can be shattered, because it can
not be labeled in alternating +,-,+