Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / a / iv

Table of contents
- Solution iv

Solution

The Sauer-Shelah lemma says that a hypothesis class of finite VC dimension

d

satisfies

Π_{H} (m) \leq j = 0 \sum m i n (d, m) (j m) .

In particular, for

m \geq d \geq 1

,

Π_{H} (m) \leq (\frac{e m}{d})^{d} .

Here the binomial coefficients count small subsets. One way to obtain the last inequality is to set

t = d / m \leq 1

: since

t^{j} \geq t^{d}

for

j \leq d

,

t^{d} \sum_{j = 0}^{d} (j m) \leq \sum_{j = 0}^{d} (j m) t^{j} \leq (1 + t)^{m} \leq e^{m t} = e^{d} .

Thus finite VC dimension replaces the unrestricted exponential number of labellings by a polynomial bound in the sample size.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

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