The growth function, also called the shatter coefficient or the shattering number, measures the richness of a set family or class of function. It is especially used in the context of statistical learning theory, where it is used to study properties of statistical learning methods. 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
be a set family (a set of sets) and
a set. Their intersection is defined as the following set-family:
![{\displaystyle H\cap C:=\{h\cap C\mid h\in H\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dad00f8eb7d6a38bf2f93884dfb319f1ffe8ad41)
The intersection-size (also called the index) of
with respect to
is
. If a set
has
elements then the index is at most
. If the index is exactly 2m then the set
is said to be shattered by
, because
contains all the subsets of
, i.e.:
![{\displaystyle |H\cap C|=2^{|C|},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/776808d8b2698a9c884d31ca86cfd74e76c6521a)
The growth function measures the size of
as a function of
. Formally:
![{\displaystyle \operatorname {Growth} (H,m):=\max _{C:|C|=m}|H\cap C|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5111b7a4c7b7aba20fabade3fa9e66c59320d335)
Hypothesis-class definition
Equivalently, let
be a hypothesis-class (a set of binary functions) and
a set with
elements. The restriction of
to
is the set of binary functions on
that can be derived from
:[3]: 45
![{\displaystyle H_{C}:=\{(h(x_{1}),\ldots ,h(x_{m}))\mid h\in H,x_{i}\in C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/798f81d0151c42f60ecadbaaa13bb94187b2ccb2)
The growth function measures the size of
as a function of
:[3]: 49
![{\displaystyle \operatorname {Growth} (H,m):=\max _{C:|C|=m}|H_{C}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a9ca71f484f7e7007465dd7d7089f73b8ca4d3b)
Examples
1. The domain is the real line
. The set-family
contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form
for some
. For any set
of
real numbers, the intersection
contains
sets: the empty set, the set containing the largest element of
, the set containing the two largest elements of
, and so on. Therefore:
.[1]: Ex.1 The same is true whether
contains open half-lines, closed half-lines, or both.
2. The domain is the segment
. The set-family
contains all the open sets. For any finite set
of
real numbers, the intersection
contains all possible subsets of
. There are
such subsets, so
. [1]: Ex.2
3. The domain is the Euclidean space
. The set-family
contains all the half-spaces of the form:
, where
is a fixed vector. Then
, 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
. The set-family
contains all the real intervals, i.e., all sets of the form
for some
. For any set
of
real numbers, the intersection
contains all runs of between 0 and
consecutive elements of
. The number of such runs is
, so
.
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
of size
, and for some number
,
- - then, there exists a subset
of size
such that
.
This implies the following property of the Growth function.[1]: Th.1 For every family
there are two cases:
- The exponential case:
identically. - The polynomial case:
is majorized by
, where
is the smallest integer for which
.
Other properties
Trivial upper bound
For any finite
:
![{\displaystyle \operatorname {Growth} (H,m)\leq |H|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aaed9da7e216e95e6204d4a7b875183fa1c7463e)
since for every
, the number of elements in
is at most
. Therefore, the growth function is mainly interesting when
is infinite.
Exponential upper bound
For any nonempty
:
![{\displaystyle \operatorname {Growth} (H,m)\leq 2^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/143545060a1e0a79c3b650f32ab7308f2bc563bd)
I.e, the growth function has an exponential upper-bound.
We say that a set-family
shatters a set
if their intersection contains all possible subsets of
, i.e.
. If
shatters
of size
, then
, which is the upper bound.
Cartesian intersection
Define the Cartesian intersection of two set-families as:
.
Then:[2]: 57
![{\displaystyle \operatorname {Growth} (H_{1}\bigotimes H_{2},m)\leq \operatorname {Growth} (H_{1},m)\cdot \operatorname {Growth} (H_{2},m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c14ac3497ba7a7cecbddffa1501ba0dbeecdd01)
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92429a6b00ea26c38f3bb023369f3fe218e8759f)
VC dimension
The VC dimension of
is defined according to these two cases:
- In the polynomial case,
= the largest integer
for which
. - In the exponential case
.
So
if-and-only-if
.
The growth function can be regarded as a refinement of the concept of VC dimension. The VC dimension only tells us whether
is equal to or smaller than
, while the growth function tells us exactly how
changes as a function of
.
Another connection between the growth function and the VC dimension is given by the Sauer–Shelah lemma:[3]: 49
- If
, then: - for all
: ![{\displaystyle \operatorname {Growth} (H,m)\leq \sum _{i=0}^{d}{m \choose i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90fd0e956da65fd9d3a000fa011418741780ea71)
In particular,
- for all
: ![{\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}=O(m^{d})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/494d9c9c3a3c3ff3693eb5f452727140bddda8e8)
- so when the VC dimension is finite, the growth function grows polynomially with
.
This upper bound is tight, i.e., for all
there exists
with VC dimension
such that:[2]: 56
![{\displaystyle \operatorname {Growth} (H,m)=\sum _{i=0}^{d}{m \choose i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eabe741342ed60bc68710629bb38048117bcc8a4)
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 ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da8a51f53f78d6b140e81abf08f833e9d111da89)
The intersection-size has the following property. For every set-family
:
![{\displaystyle |H\cap (C_{1}\cup C_{2})|\leq |H\cap C_{1}|\cdot |H\cap C_{2}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c23f659483f8a74bf268f6dbbc7ab5d277a1393f)
Hence:
![{\displaystyle \operatorname {Entropy} (H,m_{1}+m_{2})\leq \operatorname {Entropy} (H,m_{1})+\operatorname {Entropy} (H,m_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6559563e35188f371c518611c595c850b89102ed)
Moreover, the sequence
converges to a constant
when
.
Moreover, the random-variable
is concentrated near
.
Applications in probability theory
Let
be a set on which a probability measure
is defined. Let
be family of subsets of
(= a family of events).
Suppose we choose a set
that contains
elements of
, where each element is chosen at random according to the probability measure
, independently of the others (i.e., with replacements). For each event
, we compare the following two quantities:
- Its relative frequency in
, i.e.,
; - Its probability
.
We are interested in the difference,
. 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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3983b94757436c5b6f4577d7603f1cb598f0a32)
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ff48ad6fbed3077caf1a95949bc592a03a4a178)
In words: the probability that for all events in
, the relative-frequency is near the probability, is lower-bounded by an expression that depends on the growth-function of
.
A corollary of this is that, if the growth function is polynomial in
(i.e., there exists some
such that
), then the above probability approaches 1 as
. I.e, the family
enjoys uniform convergence in probability.
References
- ^ a b c d e f g h 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.
- ^ a b c d Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Foundations of Machine Learning. US, Massachusetts: MIT Press. ISBN 9780262018258., especially Section 3.2
- ^ a b c d Shalev-Shwartz, Shai; Ben-David, Shai (2014). Understanding Machine Learning – from Theory to Algorithms. Cambridge University Press. ISBN 9781107057135.