Growth function

The growth function, also called the shatter coefficient or the shattering number, 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. The term 'growth function' was coined by Vapnik and Chervonenkis in their 1968 paper, where they also proved many of its properties.[1] It is a basic concept in machine learning.[2] [3]

Definitions

Set-family definition

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

${\displaystyle H\cap C:=\{h\cap C\mid h\in H\}}$

The intersection-size (also called the index) of ${\displaystyle H}$ with respect to ${\displaystyle C}$ is ${\displaystyle |H\cap C|}$. If a set ${\displaystyle C_{m}}$ has ${\displaystyle m}$ elements then the index is at most ${\displaystyle 2^{m}}$. If the index is exactly 2^m then the set ${\displaystyle C}$ is said to be shattered by ${\displaystyle H}$, because ${\displaystyle H\cap C}$ contains all the subsets of ${\displaystyle C}$, i.e.:

${\displaystyle |H\cap C|=2^{|C|},}$

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

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

Hypothesis-class definition

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

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

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

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

Examples

1. The domain is the real line ${\displaystyle \mathbb {R} }$. The set-family ${\displaystyle H}$ contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form ${\displaystyle \{x>x_{0}\mid x\in \mathbb {R} \}}$ for some ${\displaystyle x_{0}\in \mathbb {R} }$. For any set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains ${\displaystyle m+1}$ sets: the empty set, the set containing the largest element of ${\displaystyle C}$, the set containing the two largest elements of ${\displaystyle C}$, and so on. Therefore: ${\displaystyle \operatorname {Growth} (H,m)=m+1}$.[1]^:Ex.1 The same is true whether ${\displaystyle H}$ contains open half-lines, closed half-lines, or both.

2. The domain is the segment ${\displaystyle [0,1]}$. The set-family ${\displaystyle H}$ contains all the open sets. For any finite set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains all possible subsets of ${\displaystyle C}$. There are ${\displaystyle 2^{m}}$ such subsets, so ${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$. [1]^:Ex.2

3. The domain is the Euclidean space ${\displaystyle \mathbb {R} ^{n}}$. The set-family ${\displaystyle H}$ contains all the half-spaces of the form: ${\displaystyle x\cdot \phi \geq 1}$, where ${\displaystyle \phi }$ is a fixed vector. Then ${\displaystyle \operatorname {Growth} (H,m)=\operatorname {Comp} (n,m)}$, where Comp is the number of number of components in a partitioning of an n-dimensional space by m hyperplanes.[1]^:Ex.3

4. The domain is the real line ${\displaystyle \mathbb {R} }$. The set-family ${\displaystyle H}$ contains all the real intervals, i.e., all sets of the form ${\displaystyle \{x\in [x_{0},x_{1}]|x\in \mathbb {R} \}}$ for some ${\displaystyle x_{0},x_{1}\in \mathbb {R} }$. For any set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains all runs of between 0 and ${\displaystyle m}$ consecutive elements of ${\displaystyle C}$. The number of such runs is ${\displaystyle {m+1 \choose 2}+1}$, so ${\displaystyle \operatorname {Growth} (H,m)={m+1 \choose 2}+1}$.

Polynomial or exponential

The main property that makes the growth function interesting is that it can be either polynomial or exponential - nothing in-between.

The following is a property of the intersection-size:[1]^:Lem.1

• If, for some set ${\displaystyle C_{m}}$ of size ${\displaystyle m}$, and for some number ${\displaystyle n\leq m}$, ${\displaystyle |H\cap C_{m}|\geq \operatorname {Comp} (n,m)}$ -
• then, there exists a subset ${\displaystyle C_{n}\subseteq C_{m}}$ of size ${\displaystyle n}$ such that ${\displaystyle |H\cap C_{n}|=2^{n}}$.

This implies the following property of the Growth function.[1]^:Th.1 For every family ${\displaystyle H}$ there are two cases:

• The exponential case: ${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$ identically.
• The polynomial case: ${\displaystyle \operatorname {Growth} (H,m)}$ is majorized by ${\displaystyle \operatorname {Comp} (n,m)\leq m^{n}+1}$, where ${\displaystyle n}$ is the smallest integer for which ${\displaystyle \operatorname {Growth} (H,n)<2^{n}}$.

Other properties

Trivial upper bound

For any finite ${\displaystyle H}$:

${\displaystyle \operatorname {Growth} (H,m)\leq |H|}$

since for every ${\displaystyle C}$, the number of elements in ${\displaystyle H\cap C}$ is at most ${\displaystyle |H|}$. Therefore, the growth function is mainly interesting when ${\displaystyle H}$ is infinite.

Exponential upper bound

For any nonempty ${\displaystyle H}$:

${\displaystyle \operatorname {Growth} (H,m)\leq 2^{m}}$

I.e, the growth function has an exponential upper-bound.

We say that a set-family ${\displaystyle H}$ shatters a set ${\displaystyle C}$ if their intersection contains all possible subsets of ${\displaystyle C}$, i.e. ${\displaystyle H\cap C=2^{C}}$. If ${\displaystyle H}$ shatters ${\displaystyle C}$ of size ${\displaystyle m}$, then ${\displaystyle \operatorname {Growth} (H,C)=2^{m}}$, which is the upper bound.

Cartesian intersection

Define the Cartesian intersection of two set-families as:

${\displaystyle H_{1}\bigotimes H_{2}:=\{h_{1}\cap h_{2}\mid h_{1}\in H_{1},h_{2}\in H_{2}\}}$.

Then:[2]^:57

${\displaystyle \operatorname {Growth} (H_{1}\bigotimes H_{2},m)\leq \operatorname {Growth} (H_{1},m)\cdot \operatorname {Growth} (H_{2},m)}$

Union

For every two set-families:[2]^:58

${\displaystyle \operatorname {Growth} (H_{1}\cup H_{2},m)\leq \operatorname {Growth} (H_{1},m)+\operatorname {Growth} (H_{2},m)}$

VC dimension

The VC dimension of ${\displaystyle H}$ is defined according to these two cases:

• In the polynomial case, ${\displaystyle \operatorname {VCDim} (H)=n-1}$ = the largest integer ${\displaystyle d}$ for which ${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$.
• In the exponential case ${\displaystyle \operatorname {VCDim} (H)=\infty }$.

So ${\displaystyle \operatorname {VCDim} (H)\geq d}$ if-and-only-if ${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$.

The growth function can be regarded as a refinement of the concept of VC dimension. The VC dimension only tells us whether ${\displaystyle \operatorname {Growth} (H,d)}$ is equal to or smaller than ${\displaystyle 2^{d}}$, while the growth function tells us exactly how ${\displaystyle \operatorname {Growth} (H,m)}$ changes as a function of ${\displaystyle m}$.

Another connection between the growth function and the VC dimension is given by the Sauer–Shelah lemma:[3]^:49

If ${\displaystyle \operatorname {VCDim} (H)=d}$, then:

for all ${\displaystyle m}$: ${\displaystyle \operatorname {Growth} (H,m)\leq \sum _{i=0}^{d}{m \choose i}}$

In particular,

for all ${\displaystyle m>d+1}$: ${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}=O(m^{d})}$

so when the VC dimension is finite, the growth function grows polynomially with ${\displaystyle m}$.

This upper bound is tight, i.e, for all ${\displaystyle m>d}$ there exists ${\displaystyle H}$ with VC dimension ${\displaystyle d}$ such that:[2]^:56

${\displaystyle \operatorname {Growth} (H,m)=\sum _{i=0}^{d}{m \choose i}}$

Entropy

While the growth-function is related to the maximum intersection-size, the entropy is related to the average intersection size:[1]^:272–273

${\displaystyle \operatorname {Entropy} (H,m)=E_{|C_{m}|=m}{\big [}\log _{2}(|H\cap C_{m}|){\big ]}}$

The intersection-size has the following property. For every set-family ${\displaystyle H}$:

${\displaystyle |H\cap (C_{1}\cup C_{2})|\leq |H\cap C_{1}|\cdot |H\cap C_{2}|}$

Hence:

${\displaystyle \operatorname {Entropy} (H,m_{1}+m_{2})\leq \operatorname {Entropy} (H,m_{1})+\operatorname {Entropy} (H,m_{2})}$

Moreover, the sequence ${\displaystyle \operatorname {Entropy} (H,m)/m}$ converges to a constant ${\displaystyle c\in [0,1]}$ when ${\displaystyle m\to \infty }$.

Moreover, the random-variable ${\displaystyle \log _{2}{|H\cap C_{m}|/m}}$ is concentrated near ${\displaystyle c}$.

Applications in probability theory

Let ${\displaystyle \Omega }$ be a set on which a probability measure ${\displaystyle \Pr }$ is defined. Let ${\displaystyle H}$ be family of subsets of ${\displaystyle \Omega }$ (= a family of events).

Suppose we choose a set ${\displaystyle C_{m}}$ that contains ${\displaystyle m}$ elements of ${\displaystyle \Omega }$, where each element is chosen at random according to the probability measure ${\displaystyle P}$, independently of the others (i.e, with replacements). For each event ${\displaystyle h\in H}$, we compare the following two quantities:

• Its relative frequency in ${\displaystyle C_{m}}$, i.e, ${\displaystyle |h\cap C_{m}|/m}$;
• Its probability ${\displaystyle \Pr[h]}$.

We are interested in the difference, ${\displaystyle D(h,C_{m}):={\big |}|h\cap C_{m}|/m-\Pr[h]{\big |}}$. This difference satisfies the following upper bound:

${\displaystyle \Pr \left[\forall h\in H:D(h,C_{m})\leq {\sqrt {8(\ln \operatorname {Growth} (H,2m)+\ln(4/\delta )) \over m}}\right]~~~~>~~~~1-\delta }$

which is equivalent to:[1]^:Th.2

${\displaystyle \Pr {\big [}\forall h\in H:D(h,C_{m})\leq \varepsilon {\big ]}~~~~>~~~~1-4\cdot \operatorname {Growth} (H,2m)\cdot \exp(-\varepsilon ^{2}\cdot m/8)}$

In words: the probability that for all events in ${\displaystyle H}$, the relative-frequency is near the probability, is lower-bounded by an expression that depends on the growth-function of ${\displaystyle H}$.

A corollary of this is that, iff the growth function is polynomial in ${\displaystyle m}$ (i.e, there exists some ${\displaystyle n}$ such that ${\displaystyle \operatorname {Growth} (H,m)\leq m^{n}+1}$), then the above probability approaches 1 as ${\displaystyle m\to \infty }$. I.e, the family ${\displaystyle H}$ enjoys uniform convergence in probability.

References

1. Vapnik, V. N.; Chervonenkis, A. Ya. (1971). "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Theory of Probability & Its Applications. 16 (2): 264. doi:10.1137/1116025. This is an English translation, by B. Seckler, of the Russian paper: "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Dokl. Akad. Nauk. 181 (4): 781. 1968. The translation was reproduced as: Vapnik, V. N.; Chervonenkis, A. Ya. (2015). "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Measures of Complexity. p. 11. doi:10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
2. Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Foundations of Machine Learning. USA, Massachusetts: MIT Press. ISBN 9780262018258., especially Section 3.2
3. Shalev-Shwartz, Shai; Ben-David, Shai (2014). Understanding Machine Learning – from Theory to Algorithms. Cambridge University Press. ISBN 9781107057135.