liveBook · Manning

VC dimension

As explained in Timeless Algorithms, The Foundational Ideas

The VC dimension of a hypothesis class is the largest number of points it can shatter, measuring its capacity to realize distinct labelings.

The VC dimension measures the capacity of a hypothesis class: the largest number of points it can shatter. A class shatters a set when, for every possible assignment of two labels, some hypothesis in the class classifies all points correctly. The test measures flexibility, not whether the labels are meaningful or how many observations a classifier can handle. section 8.7.2

Straight-line classifiers in two dimensions

Three points at a triangle’s corners can be shattered: a straight line can separate the labels for every assignment. Four points at a square’s corners cannot: alternating labels cannot be separated by one straight line. Thus, the VC dimension of straight-line classifiers in two dimensions is three. section 8.7.2

In support vector machines, VC dimension gives a formal language for model capacity and connects capacity control to generalization. It complements empirical risk: fitting the observed sample well is not, by itself, the full criterion for choosing a classifier. section 8.7.2 section 8.7.1

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines shattering and works through three- and four-point examples to establish a straight-line classifier’s dimension.
Examples
Uses three triangular points and four square-corner points to illustrate which labelings straight lines can separate.
What you can do after
Understand how shattering tests the flexibility of a hypothesis class and how capacity enters generalization reasoning.
How it connects
Connects support vector machines, structural risk minimization, empirical risk, and model generalization.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.