OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 31L / a / Solution

A set of points

x_{1}, \dots, x_{n}

is shattered by

H

when every one of the

2^{n}

binary label vectors is realized by some

h \in H

. The shattering coefficient is

s (H, n) = max_{x_{1}, \dots, x_{n}} ∣ {(h (x_{1}), \dots, h (x_{n})) : h \in H} ∣,

and the VC dimension is

V C (H) = sup {n : s (H, n) = 2^{n}} .

The Sauer--Shelah lemma states that if

V C (H) = D < \infty

, then

s (H, n) \leq \sum_{j = 0}^{D} (j n)

for every

n

; in particular

s (H, n) \leq (n + 1)^{D}

.

Solved by gpt-5.6-sol high.

 Ancestors (11)