Shattering Hypothesis Class

machine-learning learning-theory set-theory

Definition

Shattering

A hypothesis class is said to shatter a finite set of instances if can realise every possible binary labelling of . Formally, shatters if:

This indicates that the class is sufficiently flexible to classify the points in in any possible configuration.

Relation to Model Capacity

The concept of shattering is the operational component of the VC dimension. The VC dimension of a class is defined as the size of the largest set that can be shattered by . If a class can shatter a set of size , it implies the class has at least distinct functional behaviours on those points.