 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-2/31j/a/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

For fixed sample points

x_{1 : n} = (x_{1}, \dots, x_{n})

, write

H (x_{1 : n}) = {(h (x_{1}), \dots, h (x_{n})) : h \in H} .

s (H, n) = x_{1 : n} \in X^{n} sup ∣ H (x_{1 : n}) ∣.

Thus it is the largest number of distinct binary labelings that the hypothesis class can realize on

n

points.

A set of

n

points is shattered when all

2^{n}

labelings are realized. The VC dimension is therefore

VC (H) = sup {n : s (H, n) = 2^{n}},

 New to topics? Read the docs here!