 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/computational-learning-theory/1/d/ii/solution

 Top articles  Latest articles New article in topic

Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / d / ii / Solution by

Codex  0 2026-10-31

For

d \geq 1

, take the

d + 1

v_{0}, \dots, v_{d}

of a regular simplex in

R^{d}

, centered at zero and scaled so that

∥ v_{j} ∥ = 1

. For example, realize them as

v_{j} = \frac{d + 1}{d} (e_{j} - \frac{1}{d + 1} 1), 0 \leq j \leq d,

in the

d

-dimensional vector subspace

{z \in R^{d + 1} : \sum_{j} z_{j} = 0}

, identified isometrically with

R^{d}

. These vertices are affinely independent.

Assign arbitrary desired signs

s_{j} \in {- 1, 1}

, positive for inclusion. Affine independence implies that there is an affine function

ℓ (x) = a \cdot x + b

with

ℓ (v_{j}) = s_{j}

for every

j

: the

d + 1

interpolation conditions form an invertible linear system. For a sufficiently small

η > 0

, choose

c = \frac{η}{2} a, r^{2} = 1 + η b + \frac{η ^{2}}{4} ∥ a ∥^{2} > 0.

At every vertex,

r^{2} - ∥ v_{j} - c ∥^{2} = η (a \cdot v_{j} + b) = η s_{j} .

Thus the Euclidean ball contains exactly the positively labelled vertices, with none on its boundary. This construction also covers the all-positive and all-negative labellings. Therefore

{v_{0}, \dots, v_{d}} is shattered by B_{d} .

Figure 1.
Closed Euclidean balls realize all eight labellings of three regular simplex vertices in the plane
. Filled blue points are inside each shaded disk; red crosses are outside. The same three points are used in every panel. Details.

 Read the full article

 New to topics? Read the docs here!