Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 30J / c

Table of contents
- Solution c

Solution

If

x_{1 : n}

is shattered by

⋃_{k = 1}^{r} F_{k}

, then all

2^{n}

label vectors belong to the union of the label-vector sets generated by the individual classes. The shattering coefficient of a union and the Sauer-Shelah lemma therefore give

2^{n} \leq \sum_{k = 1}^{r} s (F_{k}, n) \leq r \sum_{j = 0}^{v} (j n) \leq r (n + 1)^{v} .

Taking base-two logarithms yields

n \leq lo g_{2} r + v lo g_{2} (n + 1) .

For

r > 1

, apply the stated elementary bound with

α = lo g_{2} r

and

β = v \geq 3

:

n \leq 4 v lo g_{2} (2 v) + 2 lo g_{2} r .

If

r = 1

, the assertion follows directly from

n \leq v

. Taking the largest shattered sample size proves

VC (k = 1 ⋃ r F_{k}) \leq 4 v lo g_{2} (2 v) + 2 lo g_{2} r .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version