Shattering coefficient
ID: shattering-coefficient
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.
New to topics? Read the docs here!