Set-family definition edit

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 edit

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}|}$ 

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 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}$ .

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}}$ .

Trivial upper bound edit

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 edit

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 edit

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 edit

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 edit

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 edit

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}$ .

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, if 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.