VC Dimensions of Thresholds and Intervals

Why Order Determines VC Dimension

On the real line, threshold and interval classifiers are simple to describe: a threshold changes its label at one cut point, while an interval labels a consecutive stretch of points as positive. Their VC dimensions are small, but the reason is structural. The order of sample points restricts which label patterns these classes can produce, regardless of how the cut points are chosen.

We will first study thresholds that label one side of a cut as positive, then intervals, and finally clarify what changes when a threshold may point in either direction. In each case, the calculation has two parts: exhibit a finite set on which every labeling is possible, then identify a larger set with at least one impossible labeling.

Definitions and Conventions

Definition: A binary classifier on a domain \(\mathcal X\) is identified with the set of points it labels positive. For a class \(\mathcal C\) of such sets, a finite set \(S\subseteq\mathcal X\) is shattered by \(\mathcal C\) if every subset of \(S\) can be written as \(C\cap S\) for some \(C\in\mathcal C\). Equivalently, every assignment of positive and negative labels to the points in \(S\) is realized by a member of the class. The VC dimension of \(\mathcal C\) is the largest cardinality of a finite set it shatters, or infinity if it shatters sets of arbitrarily large finite size.

Unless stated otherwise, the domain is \(\mathbb R\), and the positive class of a one-sided threshold is the closed left ray \[ (-\infty,t]=\{x\in\mathbb R:x\le t\},\qquad t\in\mathbb R. \] Using a strict inequality instead gives the same VC dimension. For intervals, take all closed bounded intervals \([a,b]\) with \(a\le b\). Allowing other endpoint conventions does not change the results below.

Worked Example: One Point Is Shattered by a Threshold

Consider the one-point set \(S=\{2\}\) and the class of left thresholds \((-\infty,t]\). There are two possible labelings. To label the point positive, choose \(t=2\), since \(2\le 2\). To label it negative, choose \(t=1\), since \(2\not\le 1\). Thus \(S\) is shattered. This establishes that the VC dimension of this class is at least one; an upper bound still needs to rule out shattering two points.

One-Sided Thresholds Have VC Dimension One

Theorem: The class \(\mathcal T_L=\{(-\infty,t]:t\in\mathbb R\}\) of one-sided left thresholds has VC dimension \(1\).

The one-point example already proves the lower bound. For the upper bound, take any two distinct points and write them in increasing order as \(x_1<x_2\). A left threshold cannot label \(x_1\) positive and \(x_2\) negative: if \(x_1\le t\), then \(x_2\) need not be below \(t\), so we must check the direction carefully. In fact, this labeling is possible: choosing \(t=x_1\) includes \(x_1\) and excludes \(x_2\). The impossible labeling is the reverse one, with \(x_1\) negative and \(x_2\) positive.

Indeed, if \(x_2\le t\), then \(x_1<x_2\le t\), so \(x_1\le t\) as well. Therefore no left threshold realizes labels \((0,1)\) on the ordered pair. Every two-point set fails to be shattered, so no set of size two or larger can be shattered: if a larger set were shattered, each of its two-point subsets would also be shattered. Together with the shattered singleton, this proves the theorem. \(\square\)

Worked Example: Checking All Patterns on Two Ordered Points

Let \(S=\{1,4\}\), with \(1<4\). A left threshold can realize the following patterns, listed in the order \((1,4)\):

\((0,0)\): choose \(t=0\), so neither point is at most \(t\).
\((1,0)\): choose \(t=1\), so \(1\le t\) but \(4\not\le t\).
\((1,1)\): choose \(t=4\), so both points are at most \(t\).

The remaining pattern, \((0,1)\), cannot occur. If \(4\le t\), then \(1<4\le t\), which forces \(1\le t\). Hence only three of the four labelings are available and the pair is not shattered. This concrete check illustrates the general upper-bound argument.

Intervals Have VC Dimension Two

Theorem: The class \(\mathcal I=\{[a,b]:a,b\in\mathbb R,\ a\le b\}\) of closed bounded intervals has VC dimension \(2\).

To prove the lower bound, take any two distinct real numbers \(x_1<x_2\). The empty labeling can be realized by a singleton interval at a point outside the pair. The labeling with both points positive is realized by \([x_1,x_2]\). The labeling with only \(x_1\) positive is realized by \([x_1,x_1]\), and the labeling with only \(x_2\) positive by \([x_2,x_2]\). Thus every two-point set is shattered.

For the upper bound, consider any three distinct points ordered as \(x_1<x_2<x_3\). The labeling \((1,0,1)\) is impossible for an interval. Any interval containing both \(x_1\) and \(x_3\) must also contain every point between them, in particular \(x_2\). Therefore this three-point set is not shattered. If a larger set were shattered, any three-point subset would also be shattered, which we have just ruled out. The lower and upper bounds give VC dimension exactly two. \(\square\)

Worked Example: Realizing Every Labeling of Two Points With an Interval

Take \(S=\{2,5\}\). The four label patterns, in the order \((2,5)\), have explicit realizations:

\((0,0)\): use the interval \([0,0]\), which contains neither sample point.
\((1,0)\): use \([2,2]\).
\((0,1)\): use \([5,5]\).
\((1,1)\): use \([2,5]\).

Each interval is a member of the class and its intersection with \(S\) gives exactly the indicated positive points. Thus the pair is shattered, not merely classified in some of the possible ways.

Worked Example: The Missing Pattern on Three Points

Let \(S=\{1,3,6\}\), in increasing order. Try to realize the labeling \((1,0,1)\). An interval containing \(1\) and \(6\) has a left endpoint no greater than \(1\) and a right endpoint no less than \(6\). Since \(1<3<6\), these endpoint inequalities imply that \(3\) lies in the interval too. The resulting labels must therefore include the middle point, so they cannot equal \((1,0,1)\). This single impossible pattern is enough to show that the three-point set is not shattered.

When “Threshold” Allows Either Direction

The phrase “threshold classifier” is sometimes used for a class that allows either orientation of the cut: positive points may lie to the left or to the right. This is a larger class than \(\mathcal T_L\), so it has a different VC dimension. Define \[ \mathcal T_{\pm}=\{(-\infty,t]:t\in\mathbb R\}\cup\{[t,\infty):t\in\mathbb R\}. \] This class has VC dimension \(2\).

For two points \(x_1<x_2\), the left thresholds realize \((0,0),(1,0),(1,1)\), as shown above. A right threshold realizes the remaining pattern \((0,1)\): take \([x_2,\infty)\). Thus every two-point set is shattered. On three ordered points, however, the pattern \((0,1,0)\) cannot be realized. A left ray containing the middle point also contains the left point; a right ray containing the middle point also contains the right point. No member of \(\mathcal T_{\pm}\) labels only the middle point positive. Hence no three-point set is shattered, proving the stated dimension.

Worked Example: Why Orientation Changes the Threshold Dimension

On \(S=\{1,4\}\), the one-sided left-threshold class cannot realize \((0,1)\), so it does not shatter \(S\). If the class also includes right thresholds, choose the positive set \([4,\infty)\); its labels on \((1,4)\) are exactly \((0,1)\). The other patterns are available from left thresholds: use \(t=0\) for \((0,0)\), \(t=1\) for \((1,0)\), and \(t=4\) for \((1,1)\). The two orientations together shatter the pair. The three-point middle-only pattern remains impossible, so the enlarged class has dimension two rather than one.

Common Pitfall and Why the Distinction Matters

A common error is to say that all “threshold classifiers on the line” have VC dimension one without specifying whether the positive ray may point in either direction. The claim is correct for a fixed orientation, such as \((-\infty,t]\), but false for the union of left and right rays: that union shatters two points and has dimension two. Always state the hypothesis class before reporting its VC dimension.

A second error is to infer an upper bound from a single convenient sample. To establish that a class has dimension at most \(d\), one must rule out shattering every set of size \(d+1\). Here the order structure makes that possible: every pair of distinct real numbers has the same ordered obstruction for one-sided thresholds, and every triple has the interval obstruction. The argument applies to arbitrary sample locations, not just the numerical examples above.

These small calculations are useful because they turn a geometric description into a precise complexity measure. Once the class is fixed, the VC dimension records how many arbitrary labelings it can fit on a finite sample. The distinction between one-sided thresholds, two orientations, and intervals is therefore not just terminology; it changes the number of label patterns the class can represent.

Key takeaway: On \(\mathbb R\), one-sided thresholds have VC dimension \(1\), thresholds with either orientation have VC dimension \(2\), and intervals have VC dimension \(2\). Each result follows from a shattered set at the claimed dimension and an explicit impossible labeling at the next size.

Check Your Understanding

Use the order of the sample points to justify each answer.

For left thresholds \((-\infty,t]\), which labeling on \(x_1<x_2\) is impossible, and what inequality proves it?
Give an interval that realizes the labeling \((0,1)\) on the points \(2<5\).
Why does the pattern \((1,0,1)\) rule out shattering three ordered points by intervals?
What is the VC dimension of the union of left and right rays, and which two-point pattern requires the right-ray orientation?
Explain why showing one particular three-point set is not shattered would not, by itself, prove that intervals have VC dimension at most two.