0.17 Vapnik-chervonenkis theory  (Page 2/2)

The number of different labellings that a class $\mathcal{F}$ can produce on a set of n training data is a measure of the "effective size"of $\mathcal{F}$ . The Vapnik-Chervonenkis (VC) dimension of $\mathcal{F}$ is proportional to the log of the effective size. Let $V(\mathcal{F},n)$ denote the VC dimension of $\mathcal{F}$ , typically a constant, independent of n. The VC inequality states that for all $f\in \mathcal{F}$

This type of uniform concentration inequality can be used in a similar fashion to our use of Hoeffding's inequality plus unionbound.

Hyperplane classifiers

We will go into the details of VC Theory next lecture , and the remainder of this lecture will introduce the key ideas with anexample Consider the following setup. Let $X={[0,1]}^d$ , $Y=\{0,1\}$ Let

with $w_0$ and $w$ $\in R^{d+1}$ This is the collection of all hyperplane classifiers. $\mathcal{F}$ is infinite and uncountable.

Suppose that we have n training data

There are at most $2\left(\genfrac{}{}{0pt}{}{n}{d}\right)$ unique classifiers in $\mathcal{F}$ with respect to these data. To see this, consider d arbitrary datapoints $x_1,...,x_{i_d}$ , and let $w^{T}x+w_0>0$ be a hyperplane containing these points. To be specific, take thehyperplane with

this hyperplane coincides with two possible classification rules:

Each d-tuple of training data produces two distinct classifiers, assuming the data are not co-linear. Thus, there are at most $2*\left(\genfrac{}{}{0pt}{}{n}{d}\right)$ unique classifiers in $\mathcal{F}$ with respect to the training data. (All other $f\in \mathcal{F}$ produce the same labels and empirical risk as one of the classifiers.) Let's enumerate theunique hyperplane classifiers $f_1,...,f_{2*\left(\genfrac{}{}{0pt}{}{n}{d}\right)}$ , and let

and let

and define

If multiple $f\in \mathcal{F}$ achieve $R^{*}$ , pick $f^{*}$ to be one of them in an arbitrary fixed number.

Assume that $P_x$ has a density, but that the distribution of $(x,y)$ is other arbitrary. If $n\ge d$ and $2d/n\le ϵ\le 1$ then

The proof is a specialization of the basic ingredients of VC Theory to the case at hand. Here we follow the proof in DGL'96. First we note that,

and since ${\widehat{R}}_n\left({\widehat{f}}_n\right)\le {\widehat{R}}_n\left(f\right)+d/n$ for any $f\in \mathcal{F}$

Therefore, by the union bound:

We can bound the second term of the above bound using Chernoff's/Hoeffding's inequality:

Next, let's bound one of the terms in the summation. For example, take

Note that by symmetry all $2\left(\genfrac{}{}{0pt}{}{n}{d}\right)$ terms will have identical bounds. Since the bounds are independent of $P_{x}y$ .

Assume that $f_1$ is determined by the first d data points $x_{1}4,...,x_d$ . By the smoothing property of expectations we can write,

From here, we will bound the conditional probability inside the expectation. Let $(X_1^{"},Y_1^{"}),...,(X_d^{"},Y_d^{"})$ be d additional random samples that are independent and identicallydistributed as the data $(X_1,Y_1),...,(X_d,Y_d)$ . ${\left\{X_i^{"},,,Y_i^{"}\right\}}_{i=1}^d$ are often called the "ghost sample" since they are not actually observed. They are a fictious sample leads to asimple bound on the conditional probability. Define if $i\le d$

or if $i>d$

That is, ${\left\{X_i^{{}^{\text{'}}},,,Y_i^{{}^{\text{'}}}\right\}}_{i=1}^d$ agrees with our observed data on i>d, but the first d samples are replaced with the ghost sample. Then,

where,

Note that $n\widehat{(}{R)}_n^{{}^{\text{'}}}\left(f_1\right)$ is binomially distributed with mean $R\left(f_1\right)$ and it is independent of $x_1,...,x_d$ Therefore,

In conclusion,

Lastly, Corollary If $n\ge d$ , then