# Notes - Theories of Deep Learning MT25, Vapnik-Chervonenkis dimension

> Source: https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/notes/ · Updated: 2025-10-19 · Tags: uni, notes

- [Course - Theories of Deep Learning MT25](https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/)
	- [Paper - Error bounds for approximations with deep ReLU networks, Yarotsky (2016)](https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/reading/paper-error-bounds-for-approximations-with-deep-relu-networks-yarotsky-2016/)
	- ["Vapnik-Chervonenkis dimension"](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension) on Wikipedia

### Flashcards
Suppose $f_\theta : \mathcal D \to \{0,1\}$ is a binary classifier parameterised by $\theta$. @Define what it means for $f$ to shatter a set $X \subseteq \mathcal D$.::

For every assignment of labels to those data, there exists a $\theta$ such that $f$ makes no errors when classifying those data.

Recall that a binary classifier $f_\theta : \mathcal D \to \{0,1\}$ parameterised by $\theta$ is said to shatter a set $X \subseteq \mathcal D$ if for every assignment of labels to those data, there exists a $\theta$ such that $f$ makes no errors when classifying those data.

In this context, @define the VC (Vapnik-Chervonenkis) dimension of $f$.::

$$
\text{VCdim}(f) = \max\{|X| : X \subseteq \mathcal D, f \text{ shatters } X\}
$$

The maximum cardinal $D$ such that there is at least some set $X$ of cardinality $D$ such that $f$ can shatter that set.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt