An (unusual?) risk bound

Question

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/

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.

Answer 1

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 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) and continuing through Lecture 14.

As mentioned in Stella's answer, this is all closely related to the Vapnik-Chervonenkis dimension. The relation is via the Sauer-Shelah 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. 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 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 2

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.