VC dimension and uniform laws for zero–one loss
\[ % Generalization error \def\err{\textrm{Error}} \]
Goals
- Give an example of the integrable Lipschitz conditions
- Show that zero–one loss does not satisfy the integrable Lipschitz conditions
- Define the Vapnik-Chervonenkis (VC) dimension
- State (but do not prove) a ULLN in terms of the VC dimension
Reading
These notes can be supplemented with Hastie et al. (2009) Chapter 7.9. The final bound is based on Wainwright (2019) Chapter 4.3, which is more advanced by provides a more complete treatment. Finally, if you want to go further, there are nice video tutorials in lectures 7 and 8 of this online course.
Zero–one loss functions
Unfortunately, zero–one losses are not typically IL, since they depend non–smoothly on the classification function \(f\). For a simple example, take \(x\in \mathbb{R}^{}\), \(y\in \{0,1\}\) (so it’s a classification problem), and \(\mathscr{L}(\hat{y}, y) = \mathrm{I}\left(\hat{y}\ne y\right)\). Consider the simple threshold classifier
\[ f(x; \theta) = \mathrm{I}\left(x\ge \theta\right). \]
Then consider classification error at \(\theta = x\pm \varepsilon\) for small \(\varepsilon\) and \(y= 1\). We have:
\[ \mathscr{L}(f(x; x+ \varepsilon), 1) - \mathscr{L}(f(x; x- \varepsilon), 1) = 1 \quad\textrm{but}\quad \left\Vert x+ \varepsilon - (x- \varepsilon)\right\Vert = 2 \varepsilon. \]
Since \(\mathscr{L}(f(x; \theta), 1)\) is discontinuous in \(\theta\) at \(x\), the function cannot be IL. A different technique is needed to control generalization error for zero–one loss.
VC dimension
\[ \def\xvec{\mathcal{X}} \]
A key tool in controlling generalization error for functions taking values in \(\{0,1\}\) is Vapnik–Chervonenkis (VC) dimension. The VC dimension is a measure of complexity of set of functions, so we might write \(VC(\mathcal{F})\) for the VC dimension of the function class \(\mathcal{F}\), where each member \(f\in \mathcal{F}\) maps some domain \(x\) to binary values \(\{0, 1\}\). (The VC dimension can be defined for more general functions by reducing them to binary–valued functions; see Van der Vaart (2000) Chapter 19, for example.)
For a given set of \(N\) points, \(\xvec_N = (x_1, \ldots, x_N)\), a function \(f\) returns a binary vector \(f(\xvec) := (f(x_1), \ldots, f(x_N))\). As \(f\) ranges over \(\mathcal{F}\), \(f(\xvec)\) ranges over possible values of the \(2^N\) possible binary vectors.
For example, take our threshold classifier from above. If \(N=2\) and \(\xvec = (3, 4)\), then as \(\theta\) ranges from \(-\infty\) to \(\infty\), \(f(\xvec)\) goes from \((1,1)\) to \((0, 1)\) (as \(\theta\) passes \(3\)) to \((0, 0)\) (as \(\theta\) passes \(4\)). The value \((1, 0)\) is impossible to produce with any \(f\in \mathcal{F}\) and this \(\xvec\), since \(3 < 4\), and so \(4\) is classified as \(1\) whenever \(3\) is.
As we saw, for a given \(\xvec\), the number of distinct values of \(f(\xvec)\) may be more or less than the total number of possibly values \(2^N\). If \(f(\xvec)\) is able to take all possible \(2^N\) values as \(f\) ranges over \(\mathcal{F}\), then \(f\) is said to “shatter” \(\xvec\). Intuitively, \(\xvec\) gets harder to shatter as it contains more and more points. For example, the threshold function above can shatter a single point, but cannot shatter two points. Also intuitively, more expressive function classes can shatter larger and larger sets of points.
For a given function class \(\mathcal{F}\) of functions taking values in \(\{0,1\}\), let \(VC(\mathcal{F})\) be the largest number \(N\) such that there exists a vector \(\xvec\) of length \(N\) that can be shattered by \(\mathcal{F}\). Equivalently, if \(M\) is smallest number such that no \(\xvec\) can be shattered by \(\mathcal{F}\), then \(VC(\mathcal{F}) = M - 1\).
Note that the VC dimension doesn’t mean you can shatter all sets of size \(VC(\mathcal{F})\). In fact, this is obviously impossible, since a set consisting of \(N\) copies of the same value cannot be shattered, no matter how complex \(\mathcal{F}\) is. The VC dimension requires only that you can find some set \(\xvec\) of size \(VC(\mathcal{F})\) that is shattered, but no such set \(VC(\mathcal{F}) + 1\).
We have already shown that the VC dimension of the boundary classifier is \(1\).
ULLNs from VC dimension.
The passage from VC dimension to ULLNs is somewhat complex, and beyond the scope of this (undergraduate) course. An end–to–end treatment can be found in Wainwright (2019) chapter four, from which we simply state the result with some intuition. Alternatively, see Section 6.5.2 of Shalev-Shwartz and Ben-David (2014).
Finite function class ULLN reminder
Recall from our proof of ULLNs for finite function classes that if \(|\mathcal{F}| = K < \infty\), and if there is an \(N^*\) such that \[ N > N^* \Rightarrow p\left( \left|\frac{1}{N} \sum_{n=1}^Nf(z_n) - \mathbb{E}_{\vphantom{}}\left[f(z)\right]\right| > \epsilon \right) < \delta \textrm{ for each }f \in \mathcal{F}, \tag{1}\] then by a union bound, \[ N > N^* \Rightarrow p\left( \sup_{f\in \mathcal{F}} \left|\frac{1}{N} \sum_{n=1}^Nf(z_n) - \mathbb{E}_{\vphantom{}}\left[f(z)\right]\right| > \epsilon \right) \le K \delta. \] The first tool that we will state but not prove is Hoeffding’s inequality (Wainwright (2019) Proposition 2.5) for binary random variables. Specifically, if \(f\) takes values in \(\{0,1\}\) (as is the case for zero-one loss), then Equation 1 is satisfied with \[ \delta = 2 \exp\left( -2 N \epsilon^2 \right) \textrm{ (when $f$ is binary-valued)}. \] Note that this result is stronger than our asymptotic results, in the sense that it is a finite–sample exact bound, rather than an (otherwise uncontrolled) guarantee as \(N \rightarrow \infty\). Finite–sample bounds are much easier to obtain when the function \(f(x)\) is bounded as a function of \(x\), as is the case for zero–one loss, but which is not typically the case for regression loss.
The key useful fact about the Hoeffding bound is that the number of functions in our class, \(K\), can grow with \(N\), as long as it grows more slowly than \(1 / \delta\).
The second tool that we will state but not prove is the Sauer-Shelah lemma (Wainwright (2019) Proposition 4.18). This states that, if a class has VC dimension \(\nu\), then the number of binary vectors that can be produced from \(N\) points is not only less than \(2^N\), but must be less than \((N + 1)^\nu\): \[ f(\xvec) \textrm{ takes at most }(N+1)^{\nu}\textrm{ distinct values when the VC dimension }\nu < \infty. \] This lemma states that, although a function class with finite VC dimension may be infinite (think of separating hyperplanes, for example), it can produce only a polynomially growing number of distinct classifications on any particular dataset of size \(N\). This is almost like having an effectively finite function class, of polynomial size, for a given dataset, though of course the particular binary vectors achievable will vary from one dataset to the next. The proof of a ULLN for classes with finite VC dimension uses a clever “symmetrization trick” to make this intuition precise.
The formal result follows. Let \(VC(\mathcal{F}) = \nu\), and \(f\in \mathcal{F}\) take values in \(\{0,1\}\). Then, by Wainwright (2019): \[ p\left( \sup_{f\in \mathcal{F}} \left| \frac{1}{N} \sum_{n=1}^Nf(z_n) - \mathbb{E}_{\vphantom{}}\left[f(z)\right] \right| > C \sqrt{\frac{\nu \log (N+1)}{N}} + t \right) \le \exp\left(-N t^2 / 2 \right), \textrm{ for a universal constant }C. \] (Note that \(C=8\) in the textbook but its precise value doesn’t matter here.) Specifically, this is a consequence of the following results from Wainwright (2019):
- Proposition 4.18 and Definition 4.13 (VC dimension implies polynomial discrimination)
- Lemma 4.14 and equation 4.24 (polynomial discrimination controls Rademacher complexity)
- Theorem 4.10 (Rademacher complexity controls the ULLN)
Rearranging the above result slightly to match the finite function class bound, we get \[ p\left( \sup_{f\in \mathcal{F}} \left| \frac{1}{N} \sum_{n=1}^Nf(z_n) - \mathbb{E}_{\vphantom{}}\left[f(z)\right] \right| > \varepsilon \right) \le (N+1)^{\nu / 2} \exp\left( -N \varepsilon^2 / 2 \right). \] since \[ \begin{aligned} \varepsilon ={}& C \sqrt{\frac{\nu \log (N+1)}{N}} + t \Rightarrow\\ t^2 ={}& \left( \varepsilon^2 - C \sqrt{\frac{\nu \log (N+1)}{N}} \right)^2 \ge \varepsilon^2 - C^2 \frac{\nu \log (N+1)}{N} \Rightarrow \\ \exp\left(-N t^2 / 2 \right) \le {}& \exp\left( -N \varepsilon^2 / 2 + C^2 \frac{\nu}{2} \log (N+1) \right) \\={}& (N+1)^{\nu C^2} \exp\left( -N \varepsilon^2 / 2 \right). \end{aligned} \] This is similar to finite class bound, but with the number of distinct binary vectors \((N+1)^{\nu}\) playing the role of the number of classes \(K\), up to some constant terms that occur because of the symmetrization argument.
From classifiers to loss
You will show in your homework that if a classifier has finite VC dimension then its zero–one loss function also has finite VC dimension, and vice-versa.