For a hypothesis class , the shattering coefficient counts the largest number of binary labelings that the class can realize on sample points:There are at most possible labelings. A set of distinct sample points is shattered exactly when all labelings occur on it.
For example, the threshold hypothesis class on the real line realizes labelings on distinct ordered points: the position where the labels change from to has choices. Thus . The Sauer-Shelah lemma generalizes this polynomial-growth phenomenon to classes of finite VC dimension.
For binary hypothesis classes,because the label vectors realized by the union form the union of the two sets of realized label vectors.
The VC dimension is the largest number of points on which a binary hypothesis class realizes every possible labeling.
The positive-radius closed Euclidean balls in have VC dimension for . Vertices of a regular simplex are shattered: interpolate any desired signs by an affine function , then perturb a sphere through the vertices to the score . For the upper bound, take an affine dependence among points and orient it so that . Labelling the positive coefficients inside and the negative coefficients outside would force , while the affine dependence makes this sum equal . The weaker upper bound from unrestricted lifted affine linear classifiers loses their fixed quadratic coefficient.
If a binary hypothesis class has finite VC dimension , then its shattering coefficient satisfiesThe binomial coefficients bound how many different label patterns the class can realize. For fixed , their sum grows polynomially in , although the number of unrestricted binary patterns is .
Here is an inductive counting proof on a fixed sample. Partition the realized patterns according to their last label, and let be the corresponding sets of patterns on the first points. Put and . The original number of patterns is .
The class has VC dimension at most . The class has VC dimension at most : if shattered earlier points, both last labels would extend every pattern there, so the original class would have a shattered set of points. Applying mathematical induction and Pascal's identity gives the displayed sum. The base cases are , with at most one empty pattern, and , with at most one realized pattern.
If no -set were shattered, the Sauer-Shelah lemma would bound the number of traces by . This strict middle-layer gap contradicts the displayed lower bound. Therefore a family with such traces at every even size has unbounded finite VC dimension.
The elementary estimate converts finite VC dimension into a polynomial bound on the number of sample labelings.
The class of lower orthants in has VC dimension at most . Among any points, choose a coordinate maximizer for each of the coordinates. A remaining point cannot be excluded while all those maximizers are included.
Indicators of real intervals have VC dimension two: two ordered points can be labeled arbitrarily, while an interval containing the two outer points of a triple must contain the middle point.
For a target positive set consisting of two disjoint intervals of total probability , choosing its heavier component has misclassification risk at most . Choosing the spanning interval has misclassification risk at most . The smaller bound is at most . The constant is sharp: on three ordered atoms with equal masses and labels , every single interval makes a mistake on at least one atom. Together with the VC uniform convergence theorem, this gives weak PAC learning using an interval hypothesis class.
Intervals together with their label complements shatter three ordered points, but cannot realize an alternating labeling on four, so their VC dimension is three.
Articles by others on the same topic
There are currently no matching articles.