0.17 Vapnik-chervonenkis theory

Review of past lecture

In our past lectures we considered collections of candidate function $\mathcal{F}$ that were either finite or enumerable . We then constructed penalties, usually codelengths, for eachcandidate $c\left(f\right)$ , $f\in \mathcal{F}$ , such that ${\sum }_{f\in \mathcal{F}}{2}^{c\left(f\right)}\le 1$ This allowed us to derive uniform concentration inequalities over the entire set $\mathcal{F}$ using the union bound. However, in many cases the collections $\mathcal{F}$ may be uncountably infinite. A simple example is the collection $\mathcal{F}$ of a single threshold classifier in 1-d having the form

and their complements

Thus, $\mathcal{F}$ contains an uncountable number of classifiers, and we cannot apply the union bound argument in such cases.

Two ways to proceed

Discretize or quantize the collection

Identical empirical errors

Consider the fact that given only n training data, many of the classifiers in such a collection may produce identical empiricalerrors. Also, many $f\in \mathcal{F}$ will produce identical label assignments on the data. We will have at most $2^n$ unique labels.

f is uncountable, its interceptions are countable and bounded by $2^n$ . n intervals with 2 classifier per interval.

The number of distinct labeling assignments that a class $\mathcal{F}$ can produce on a set of n points is denoted

The VC dimension is $logS(\mathcal{F},n)$ . Specifically, $VC\left(\mathcal{F}\right)=k$ , where $k$ is largest integer such that $S(\mathcal{F},k)=2^k$ Ex. $2n=2^n$ , $n=2$ , $VC\left(\mathcal{F}\right)=2$ .

Ex. Consider

Let q be a positive integer and

and,

Moreover, for any $f\in \mathcal{F}$ there exists an $f_1\in {\mathcal{F}}_q$ such that

Now suppose we have n training data and suppose $f^{*}\in \mathcal{F}$ . We know that in general, the minimum empirical risk classifier willconverge to the Bayes classifier at the rate of $n^{-1/2}$ or slower. Therefore, it is unnecessary to drive the approximationerror down faster than $n^{-1/2}$ So, we can restrict our attention of ${\mathcal{F}}_{n^{-1/2}}$ and, provided that the density of x is bound above. We have

Vapnik-Chervonenkis theory is based not on explicitly quantizing the collection of candidate functions, but rather on recognizingthat the richness of $\mathcal{F}$ is limited in a certain sense by the number of training data. Indeed, given n i.i.d. training data,there are at most $2^n$ different binary labelings. Therefore, any collection $\mathcal{F}$ may be divided into $2^n$ subsets of classifiers that are "equilvalent" with respect to the training data. In manycases a collection may not even be capable of producing $2^n$ different labellings.

Example

Consider $X=[0,1]$ .

Suppose we have n training data: $(x_1,...,x_n)\in [0,1]$ . With $x^s$ denotes the location of each training point in [0,1].Associated with each x is a label $y\in \{0,1\}$ . Any classifier in $\mathcal{F}$ will label all points to the left of a number $t\in [0,1]$ as "1" or "0", and points to the right as "0" or "1", respectively.For $t\in [0,x_1)$ , all points are either labelled "0" or "1". For $t\in (x_1,x_2)$ , $x_1$ is labelled "0" or "1" and $x_2...x_n$ are label "1" or "0" and so on. We see that there are exactly $2n$ different labellings; far less than $2^n$ !