Growth Function

From GM-RKB
(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 [math] s \subset \Omega [/math] , [math] \Omega [/math] being any space, often a sample space, and [math] x_1,x_2,\dots,x_n \in \Omega [/math] being any set of n points, we define

      the nth shattering coefficient of C as : [math] 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 \} [/math] where [math] \operatorname{card} [/math] denotes the cardinality of the set. [math] S_C(n) [/math] 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 [math] S_C(n) [/math] :

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


2018a

2018b

2018c

2017a

2017b

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 [math]\mathcal{H} \subseteq \{0, 1\}^{\mathcal{X}} [/math]. For [math]x_1, x_2, \cdots , x_n \in \mathcal{X}[/math] denote

      [math] N_{\mathcal{H}}(x_1, \cdots , x_n) := |\{(h(x_1), \cdots , h(x_n)) : h \in \mathcal{H}\}|[/math]

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

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

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

      [math] N_{\mathcal{H}}(x_1, \cdots , x_n) = 2^n[/math]

      and we say that [math]\mathcal{H}[/math] shatters [math]x_1, \cdots , x_n[/math].

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

2013

1971