# Growth Function

(Redirected from Shattering Coefficient)
Jump to: navigation, search

A Growth Function is a Statistical Learning function that measures the richness of a Set Family.

## References

### 2019a

1. 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.

### 2019b

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Shattered_set#Shatter_coefficient Retrieved:2019-12-6.
• To quantify the richness of a collection C of sets, we use the concept of shattering coefficients (also known as the growth function). For a collection C of sets $s \subset \Omega$ , $\Omega$ being any space, often a sample space, and $x_1,x_2,\dots,x_n \in \Omega$ being any set of n points, we define

the nth shattering coefficient of C as : $S_C(n) = \max_{\forall x_1,x_2,\dots,x_n \in \Omega } \operatorname{card} \{\,\{\,x_1,x_2,\dots,x_n\}\cap s, s\in C \}$ where $\operatorname{card}$ denotes the cardinality of the set. $S_C(n)$ is the largest number of subsets of any set A of n points that can be formed by intersecting A with the sets in collection C.

Here are some facts about $S_C(n)$ :

1. $S_C(n)\leq 2^n$ for all n because $\{s\cap A|s\in C\}\subseteq P(A)$ for any $A\subseteq \Omega$ .
2. If $S_C(n)=2^n$, that means there is a set of cardinality n, which can be shattered by C.
3. If $S_C(N)\lt 2^N$ for some $N\gt 1$ then $S_C(n)\lt 2^n$ for all $n\geq N$ .
• The third property means that if C cannot shatter any set of cardinality N then it can not shatter sets of larger cardinalities.

### 2014

• (Scott et al., 2014) ⇒ Clayton Scott (Lecturer), Srinagesh Sharma, Scott Reed, and Petter Nilsson (2014)."Vapnik-Chevronenkis Theory". In: EECS 598: Statistical Learning Theory, Winter 2014.
• QUOTE: Let $\mathcal{H} \subseteq \{0, 1\}^{\mathcal{X}}$. For $x_1, x_2, \cdots , x_n \in \mathcal{X}$ denote

$N_{\mathcal{H}}(x_1, \cdots , x_n) := |\{(h(x_1), \cdots , h(x_n)) : h \in \mathcal{H}\}|$

Clearly $N_{\mathcal{H}}(x_1, \cdots, x_n) \leq 2^n$. The nth shatter coefficient is defined as

$S_{\mathcal{H}}(n) =: \displaystyle \underset{x_1,\cdots,x_n \in \mathcal{X}} max N_{\mathcal{H}}(x_1, \cdots , x_n)$

If $S_{\mathcal{H}}(n) = 2n$, then $\exists\; x_1, \cdots , x_n$ such that

$N_{\mathcal{H}}(x_1, \cdots , x_n) = 2^n$

and we say that $\mathcal{H}$ shatters $x_1, \cdots , x_n$.

Note. The shatter coefficient is sometimes called the growth function in the literature.