Growth function

The growth function measures the richness of a set family. It is especially used in the context of statistical learning theory, where it measures the complexity of a hypothesis class.

Definitions

Let $H$ be a set-family (a set of sets) and $C$ a set. Their intersection is defined as the following set-family:

H\cap C:=\{h\cap C|h\in H\}

The growth function measures the size of $H\cap C$ as a function of $|C|$ . Formally:

Growth(H,m):=\max _{C:|C|=m}|H\cap C|

Equivalently, let $H$ be a hypothesis-class (a set of binary functions) and $C$ a set with $m$ elements. The restriction of $H$ to $C$ is the set of binary functions on $C$ that can be derived from $H$ :^[1]^: 45

H_{C}:=\{(h(x_{1}),\ldots ,h(x_{m}))|h\in H,x_{i}\in C\}

The growth function measures the size of $H_{C}$ as a function of $|C|$ :^[1]^: 49

Growth(H,m):=\max _{C:|C|=m}|H_{C}|

References

^ ^a ^b Shalev-Shwartz, Shai; Ben-David, Shai (2014). Understanding Machine Learning – from Theory to Algorithms. Cambridge University Press. ISBN 9781107057135.

[book14-1] Shalev-Shwartz, Shai; Ben-David, Shai (2014). Understanding Machine Learning – from Theory to Algorithms. Cambridge University Press. ISBN 9781107057135.

[1]

Definitions

See also

References