Growth function

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\mid h\in H\}

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

:$$$$

|H\cap C|=2^

C

,

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

:$$$$

\operatorname{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$:{{rp|45}}

:$$$$

H_{C} := \{(h(x_1),\ldots,h(x_m))\mid h\in H, x_i\in C\}

The growth function measures the size of $H\_C$ as a function of $|C|$:{{rp|49}}

:$$$$

\operatorname{Growth}(H,m) := \max_{C: |C|=m} |H_C|

1. The domain is the real line $\backslash mathbb\{R\}$.

The set-family $H$ contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form $\backslash \{x\; >\; x\_0\; \backslash mid\; x\backslash in\; \backslash mathbb\{R\}\backslash \}$ for some $x\_0\backslash in\; \backslash mathbb\{R\}$.

For any set $C$ of $m$ real numbers, the intersection $H\backslash cap\; C$ contains $m+1$ sets: the empty set, the set containing the largest element of $C$, the set containing the two largest elements of $C$, and so on. Therefore: $\backslash operatorname\{Growth\}(H,m)=m+1$.{{rp|Ex.1}} The same is true whether $H$ contains open half-lines, closed half-lines, or both.

2. The domain is the segment $[0,1]$.

The set-family $H$ contains all the open sets.

For any finite set $C$ of $m$ real numbers, the intersection $H\backslash cap\; C$ contains all possible subsets of $C$. There are $2^m$ such subsets, so $\backslash operatorname\{Growth\}(H,m)=2^m$.

{{rp|Ex.2}}

3. The domain is the Euclidean space $\backslash mathbb\{R\}^n$.

The set-family $H$ contains all the half-spaces of the form: $x\backslash cdot\; \backslash phi\; \backslash geq\; 1$, where $\backslash phi$ is a fixed vector.

Then $\backslash operatorname\{Growth\}(H,m)=\backslash operatorname\{Comp\}(n,m)$,

where Comp is the number of components in a partitioning of an n-dimensional space by m hyperplanes.{{rp|Ex.3}}

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

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:{{rp|Lem.1}}

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

This implies the following property of the Growth function.{{rp|Th.1}}

For every family $H$ there are two cases:

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

For any finite $H$:

:$\backslash operatorname\{Growth\}(H,m)\; \backslash leq\; |H|$

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

For any nonempty $H$:

:$\backslash operatorname\{Growth\}(H,m)\; \backslash leq\; 2^m$

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

We say that a set-family $H$ shatters a set $C$ if their intersection contains all possible subsets of $C$, i.e. $H\backslash cap\; C\; =\; 2^C$.

If $H$ shatters $C$ of size $m$, then $\backslash operatorname\{Growth\}(H,C)=2^\{m\}$, which is the upper bound.

Define the Cartesian intersection of two set-families as:

::$H\_1\backslash bigotimes\; H\_2\; :=\; \backslash \{h\_1\backslash cap\; h\_2\; \backslash mid\; h\_1\backslash in\; H\_1,\; h\_2\backslash in\; H\_2\backslash \}$.

Then:{{rp|57}}

::$\backslash operatorname\{Growth\}(H\_1\backslash bigotimes\; H\_2,\; m)\; \backslash leq\; \backslash operatorname\{Growth\}(H\_1,\; m)\backslash cdot\; \backslash operatorname\{Growth\}(H\_2,\; m)$

For every two set-families:{{rp|58}}

::$\backslash operatorname\{Growth\}(H\_1\backslash cup\; H\_2,\; m)\; \backslash leq\; \backslash operatorname\{Growth\}(H\_1,\; m)\; +\; \backslash operatorname\{Growth\}(H\_2,\; m)$

The VC dimension of $H$ is defined according to these two cases:

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

So $\backslash operatorname\{VCDim\}(H)\backslash geq\; d$ if-and-only-if $\backslash 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 $\backslash operatorname\{Growth\}(H,d)$ is equal to or smaller than $2^d$, while the growth function tells us exactly how $\backslash operatorname\{Growth\}(H,m)$ changes as a function of $m$.

Another connection between the growth function and the VC dimension is given by the Sauer–Shelah lemma:{{rp|49}}

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

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

In particular,

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

:so when the VC dimension is finite, the growth function grows polynomially with $m$.

This upper bound is tight, i.e., for all $m>d$ there exists $H$ with VC dimension $d$ such that:{{rp|56}}

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

While the growth-function is related to the maximum intersection-size,

the entropy is related to the average intersection size:{{rp|272–273}}

::$\backslash operatorname\{Entropy\}(H,\; m)\; =\; E\_\{|C\_m|=m\}\backslash big[\backslash log\_2(|H\backslash cap\; C\_m|)\backslash big]$

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

::$$

|H\cap (C_1 \cup C_2)|

\leq

|H\cap C_1|\cdot |H \cap C_2|

Hence:

::$$

\operatorname{Entropy}(H, m_1+m_2)

\leq

\operatorname{Entropy}(H, m_1) + \operatorname{Entropy}(H, m_2)

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

Moreover, the random-variable $\backslash log\_2\{|H\backslash cap\; C\_m|/m\}$ is concentrated near $c$.

Let $\backslash Omega$ be a set on which a probability measure $\backslash Pr$ is defined.

Let $H$ be family of subsets of $\backslash Omega$ (= a family of events).

Suppose we choose a set $C\_m$ that contains $m$ elements of $\backslash Omega$,

where each element is chosen at random according to the probability measure $P$, independently of the others (i.e., with replacements). For each event $h\backslash in\; H$, we compare the following two quantities:

• Its relative frequency in $C\_m$, i.e., $|h\backslash cap\; C\_m|/m$;
• Its probability $\backslash Pr[h]$.

We are interested in the difference, $D(h,C\_m)\; :=\; \backslash big||h\backslash cap\; C\_m|/m\; -\; \backslash Pr[h]\backslash big|$. This difference satisfies the following upper bound:

::$$$$

\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:{{rp|Th.2}}

::$$$$

\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 $H$, the relative-frequency is near the probability, is lower-bounded by an expression that depends on the growth-function of $H$.

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

{{reflist}}

Category:Measures of complexity

Category:Statistical classification

Category:Computational learning theory

Category:Families of sets