liveBook · Manning

Hypothesis space

As explained in Timeless Algorithms, The Foundational Ideas

A hypothesis class is the set of candidate functions or decision boundaries a learning method is permitted to select from.

A hypothesis space, or hypothesis class H, is the complete set of decision boundaries a learning method is permitted to select from. Its capacity matters to theories of generalization: the VC dimension measures how many labeling patterns H can reproduce. section 8.7.2

A set of points is shattered when H can classify it correctly under every possible assignment of two labels. The labels need not express a meaningful pattern; shattering tests the flexibility of the hypothesis space. section 8.7.2

Straight-line classifiers

Three points at the corners of a triangle can be shattered by straight lines. Four points at the corners of a square cannot: alternating labels defeat every straight-line boundary. Thus, straight-line classifiers in two dimensions have VC dimension three. section 8.7.2

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Formalizes capacity through shattering and illustrates the criterion geometrically with straight-line classifiers.
Examples
Uses three triangular points and four square-corner points to demonstrate shattering and its failure.
What you can do after
Evaluate capacity by testing whether a hypothesis class can realize every labeling of a point set.
How it connects
Connects VC dimension and hypothesis classes to structural risk minimization, support vector machines, and generalization.

Also explained in

Compare how 3 books explain hypothesis space →

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.