<p>I believe a common name for what you describe as <span class="math-container">$\mathcal{N}(\mathcal{F},2n)$</span> is the &quot;growth function&quot;.</p>
<p>For a concept class <span class="math-container">$\mathcal{F} = \{ h : X \to \{0,1\} \}$</span> and <span class="math-container">$S = (x_1,\dots,x_n) \subseteq X^n$</span> we define
<span class="math-container">$$ \mathcal{F} \Big|_S = \{(h(x_1,\dots,h(x_n)) ~|~ h \in \mathcal{F}\}.$$</span>
Then, the &quot;growth function&quot; for <span class="math-container">$\mathcal{F}$</span> is:
<span class="math-container">$$ \mathcal{N}(\mathcal{F},n) = \max_{S \subseteq X^n, |S| = m} | \mathcal{F}\Big|_S|$$</span>
with <span class="math-container">$|\cdot|$</span> representing the cardinality.</p>
<p>In particular, a result very similar to the first item you describe can be found in <a href="https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/" rel="nofollow noreferrer">these lecture notes</a> where the growth function is called <span class="math-container">$\Pi_\mathcal{F}(m)$</span> as opposed to <span class="math-container">$\mathcal{N}$</span>. The results you mention appear in a few places, notably starting with the definition of the growth function (appearing in <a href="https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec8_100115.pdf" rel="nofollow noreferrer">Lecture 8</a>) and continuing through <a href="https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec14_102915.pdf" rel="nofollow noreferrer">Lecture 14</a>.</p>
<p>As mentioned in Stella's answer, this is all closely related to the Vapnik-Chervonenkis dimension. The relation is via the <a href="https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma" rel="nofollow noreferrer">Sauer-Shelah lemma</a> that controls the size of the growth function provided the VC dimension is known. Consider the Sauer-Shelah lemma written as in Theorem 9.6 of <a href="https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec9_100615.pdf" rel="nofollow noreferrer">Lecture 9</a>. This says if the VC dimension of our concept class <span class="math-container">$\mathcal{F}$</span> is <span class="math-container">$d$</span> then
<span class="math-container">$$
\mathcal{N}(\mathcal{F},n) = O(n^d).
$$</span>
Combine this with the &quot;Big Theorem&quot; (Theorem 14.3) of <a href="https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec14_102915.pdf" rel="nofollow noreferrer">Lecture 14</a> which states (roughly)
<span class="math-container">$$
\mathbb{P}\left[ R(h_\mathbf{w}) - R_{\text{empirical}}(h_\mathbf{w}) \leq \sqrt{\dfrac{8d\log(n)}{n}} + \sqrt{\dfrac{2 \log(1/\delta)}{n}}\right] \geq 1-\delta
$$</span>
and notice that we can &quot;move the <span class="math-container">$d$</span>&quot; inside the <span class="math-container">$\log$</span> of the <span class="math-container">$8d\log(n)$</span> term and then using the Sauer-Shelah lemma compare <span class="math-container">$n^d$</span> with the growth function obtaining something very close to the form you desire.</p>

CC BY-SA 4.0
2021-07-30T07:54:46.143Z
2021-07-30T21:44:21.617Z
2021-07-30T21:44:21.617Z
Lockjaw
<p>The shattering coefficient is a way of describing how well <span class="math-container">$\mathcal{F}$</span> can classify points into binary categories. It does this by counting the maximum number of behaviors that can be correctly classified by functions in the family on <span class="math-container">$n$</span> points.</p>
<p>Take some set <span class="math-container">$D$</span> of <span class="math-container">$n$</span> points and look at the <span class="math-container">$2^n$</span> total ways to assign them binary labels. Some of these will be classifiable by functions in <span class="math-container">$\mathcal{F}$</span>, but often times some will not. To compute the shattering coefficient, <span class="math-container">$\mathcal{N}(\mathcal{F}, n)$</span>, count the number of labeling assignments that an element of <span class="math-container">$\mathcal{F}$</span> can correctly classify and then take the max of this value across all sets <span class="math-container">$D$</span> in your data space of cardinality <span class="math-container">$n$</span>. For example, a 2D linear classifier can classify all <span class="math-container">$2^3$</span> labelings of a set of <span class="math-container">$3$</span> points correctly, so <span class="math-container">$\mathcal{N}(\mathcal{F}, 3) = 8$</span>. However, for any set of <span class="math-container">$4$</span> points (ignoring the degenerate cases for simplicity) we can draw a convex quadrilateral. When we label opposite corners of this quadrilateral the same, we find that no linear function can correctly classify all four points. There are two ways to do this and these are the only two assignments of labels that a linear classifier can't classify, so <span class="math-container">$\mathcal{N}(\mathcal{F}, 4) = 14$</span>.</p>
<p>A related function is the Vapnik–Chervonenkis (VC) dimension. The VC dimension is the largest value of <span class="math-container">$n$</span> such that <span class="math-container">$\mathcal{N}(\mathcal{F}, n)=2^n$</span>. In the case of a 2D linear classifier, it is 3.</p>
<p>Your inequality looks a lot like ones found in Vapnik (2000), <em>The nature of statistical learning theory</em>. I would recommend checking that book out for a lead on the specific inequality.</p>

CC BY-SA 4.0
2021-07-28T21:48:59.997Z
2021-07-31T03:23:27.050Z
2021-07-31T03:23:27.050Z
Stella Biderman
<p>I am told that that a bound on the generalization error of the following form exists in terms of something called the ``shattering coefficient&quot; - but I am not able to reference this quantity in the usual learning theory resources like, <a href="http://dept.stat.lsa.umich.edu/%7Etewaria/teaching/LearningTheory-Spring2008/" rel="nofollow noreferrer">http://dept.stat.lsa.umich.edu/~tewaria/teaching/LearningTheory-Spring2008/</a></p>
<p>Suppose we are given a function class <span class="math-container">${\cal F}$</span> and <span class="math-container">$n$</span> data points then apparently one can define a ``shattering coefficient&quot; <span class="math-container">${\cal N}({\cal F},2n)$</span> s.t we have the following probabilistic inequalities over sampling the data,</p>
<ul>
<li>If <span class="math-container">$R$</span> is a risk function and <span class="math-container">$f_{\bf w}$</span> is the ``worst classifier&quot; (not sure how exactly is it being defined!) we have,</li>
</ul>
<p><span class="math-container">$$ \mathbb{P} \left [ R(f_{\bf w}) \leq R_{\rm empirical}(f_{\bf w}) + \sqrt{\frac{4}{n} \left (  \log \frac{2 \cdot {\cal N}({\cal F},2n)}{\delta} \right )}   \right ] \geq 1 - \delta $$</span></p>
<ul>
<li><span class="math-container">$$\mathbb{P} \left [ \sup_{f \in {\cal F}}  \vert R(f) - R_{\rm empirical}(f) \vert &gt; \epsilon \right ] \leq 2 {\cal N}({\cal F},2n) e^{-n \epsilon^2}$$</span></li>
</ul>
<p>It would be great to get some references for this quantity and the proofs of the above equations!</p>
<hr />
<p>It might be that these require <span class="math-container">$\cal F$</span> to be a binary valued function. I am not sure.</p>

CC BY-SA 4.0
2021-07-20T01:45:14.337Z
Have you looked at, e.g., https://link.springer.com/referenceworkentry/10.1007%2F978-0-387-30164-8_328
Clement C.
<machine-learning><lg.learning><st.statistics><pac-learning>
An (unusual?) risk bound
gradstudent
# An (unusual?) risk bound

(Asked by: username_0 on 2021-07-19)

I am told that that a bound on the generalization error of the following form exists in terms of something called the ``shattering coefficient" - but I am not able to reference this quantity in the usual learning theory resources like, [http://dept.stat.lsa.umich.edu/~tewaria/teaching/LearningTheory-Spring2008/](http://dept.stat.lsa.umich.edu/%7Etewaria/teaching/LearningTheory-Spring2008/)

Suppose we are given a function class ${\cal F}$ and $n$ data points then apparently one can define a ``shattering coefficient" ${\cal N}({\cal F},2n)$ s.t we have the following probabilistic inequalities over sampling the data,

* If $R$ is a risk function and $f\_{\bf w}$ is the ``worst classifier" (not sure how exactly is it being defined!) we have,

$$ \mathbb{P} \left [ R(f\_{\bf w}) \leq R\_{\rm empirical}(f\_{\bf w}) + \sqrt{\frac{4}{n} \left ( \log \frac{2 \cdot {\cal N}({\cal F},2n)}{\delta} \right )} \right ] \geq 1 - \delta $$

* $$\mathbb{P} \left [ \sup\_{f \in {\cal F}} \vert R(f) - R\_{\rm empirical}(f) \vert > \epsilon \right ] \leq 2 {\cal N}({\cal F},2n) e^{-n \epsilon^2}$$

It would be great to get some references for this quantity and the proofs of the above equations!

---

It might be that these require $\cal F$ to be a binary valued function. I am not sure.

**Tags:** machine-learning, lg.learning, st.statistics, pac-learning
> **Comments:**
> **username_1**: Have you looked at, e.g., https://link.springer.com/referenceworkentry/10.1007%2F978-0-387-30164-8_328  

---

## 2 answers

### Answer by username_2 on 2021-07-30. Score: 2

I believe a common name for what you describe as $\mathcal{N}(\mathcal{F},2n)$ is the "growth function".

For a concept class $\mathcal{F} = \{ h : X \to \{0,1\} \}$ and $S = (x\_1,\dots,x\_n) \subseteq X^n$ we define
$$ \mathcal{F} \Big|\_S = \{(h(x\_1,\dots,h(x\_n)) ~|~ h \in \mathcal{F}\}.$$
Then, the "growth function" for $\mathcal{F}$ is:
$$ \mathcal{N}(\mathcal{F},n) = \max\_{S \subseteq X^n, |S| = m} | \mathcal{F}\Big|\_S|$$
with $|\cdot|$ representing the cardinality.

In particular, a result very similar to the first item you describe can be found in [these lecture notes](https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/) where the growth function is called $\Pi\_\mathcal{F}(m)$ as opposed to $\mathcal{N}$. The results you mention appear in a few places, notably starting with the definition of the growth function (appearing in [Lecture 8](https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec8_100115.pdf)) and continuing through [Lecture 14](https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec14_102915.pdf).

As mentioned in Stella's answer, this is all closely related to the Vapnik-Chervonenkis dimension. The relation is via the [Sauer-Shelah lemma](https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma) that controls the size of the growth function provided the VC dimension is known. Consider the Sauer-Shelah lemma written as in Theorem 9.6 of [Lecture 9](https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec9_100615.pdf). This says if the VC dimension of our concept class $\mathcal{F}$ is $d$ then
$$
\mathcal{N}(\mathcal{F},n) = O(n^d).
$$
Combine this with the "Big Theorem" (Theorem 14.3) of [Lecture 14](https://web.eecs.umich.edu/%7Ejabernet/eecs598course/fall2015/web/notes/lec14_102915.pdf) which states (roughly)
$$
\mathbb{P}\left[ R(h\_\mathbf{w}) - R\_{\text{empirical}}(h\_\mathbf{w}) \leq \sqrt{\dfrac{8d\log(n)}{n}} + \sqrt{\dfrac{2 \log(1/\delta)}{n}}\right] \geq 1-\delta
$$
and notice that we can "move the $d$" inside the $\log$ of the $8d\log(n)$ term and then using the Sauer-Shelah lemma compare $n^d$ with the growth function obtaining something very close to the form you desire.


---

### Answer by username_3 on 2021-07-28. Score: 0

The shattering coefficient is a way of describing how well $\mathcal{F}$ can classify points into binary categories. It does this by counting the maximum number of behaviors that can be correctly classified by functions in the family on $n$ points.

Take some set $D$ of $n$ points and look at the $2^n$ total ways to assign them binary labels. Some of these will be classifiable by functions in $\mathcal{F}$, but often times some will not. To compute the shattering coefficient, $\mathcal{N}(\mathcal{F}, n)$, count the number of labeling assignments that an element of $\mathcal{F}$ can correctly classify and then take the max of this value across all sets $D$ in your data space of cardinality $n$. For example, a 2D linear classifier can classify all $2^3$ labelings of a set of $3$ points correctly, so $\mathcal{N}(\mathcal{F}, 3) = 8$. However, for any set of $4$ points (ignoring the degenerate cases for simplicity) we can draw a convex quadrilateral. When we label opposite corners of this quadrilateral the same, we find that no linear function can correctly classify all four points. There are two ways to do this and these are the only two assignments of labels that a linear classifier can't classify, so $\mathcal{N}(\mathcal{F}, 4) = 14$.

A related function is the Vapnik–Chervonenkis (VC) dimension. The VC dimension is the largest value of $n$ such that $\mathcal{N}(\mathcal{F}, n)=2^n$. In the case of a 2D linear classifier, it is 3.

Your inequality looks a lot like ones found in Vapnik (2000), *The nature of statistical learning theory*. I would recommend checking that book out for a lead on the specific inequality.


---

