0.18 The vapnik-chervonenkis inequality

The vapnik-chervonenkis inequality

The VC inequality is a powerful generalization of the bounds we obtained for the hyperplane classifier in the previous lecture . The basic idea of the proof is quite similar. Before starting the inequality, we need to introduce theconcept of shatter coefficients and VC dimension.

Shatter coefficients

Let $\mathcal{A}$ be a collection of subsets of ${\mathcal{R}}^d$ , definition: The $n^{th}$ shatter coefficient of $\mathcal{A}$ is defined by

The shatter coefficients are a measure of the richness of the collection $\mathcal{A}$ . ${\mathcal{S}}_{\mathcal{A}}\left(n\right)$ is the largest number of different subsets of a set of $n$ points that can be generated by intersecting the set with elements of $\mathcal{A}$ .

Vc dimension

The VC dimension

$V_{\mathcal{A}}$ of a collection of sets $\mathcal{A}$ is defined as the largest interger $n$ such that $S_{\mathcal{A}}\left(n\right)=2^n$ .

Sauer's lemma:

Let $\mathcal{A}$ be a collection of set with VC dimension $V_{\mathcal{A}}<\infty$ . Then $\forall n,{\mathcal{S}}_{\mathcal{A}}\left(n\right)\le {\sum }_{i=0}^{V_{\mathcal{A}}}\left(\begin{array}{c}n\\ i\end{array}\right)$ , also ${\mathcal{S}}_{\mathcal{A}}\left(n\right)\le {(n+1)}^{V_{\mathcal{A}}},\forall n$ .

Vc dimension and classifiers

Let $\mathcal{F}$ be a collection of classifiers of the form $f:{\mathcal{R}}^d\to \{0,1\}$ Define $\mathcal{A}=\left\{\right\{x:f\left(x\right)=1\}\times \{0\}\bigcup \{x:f\left(x\right)=0\}\times \{1\},fϵ\mathcal{F}\}$ In words, this is collection of subsets of $\mathcal{X}\times \mathcal{Y}$ for which on $fϵ\mathcal{F}$ maps the features $x$ to a label opposite of $y$ .  The size of $\mathcal{A}$ expresses the richness of $\mathcal{F}$ .  The larger $\mathcal{A}$ is the more likely it is that there exists an $fϵ\mathcal{F}$ for which $R\left(f\right)=P\left(f\right(X)\ne Y)$ is close to the Bayes risk $R^{*}=P(f^{*}\left(X\right)\ne Y)$ where $f^{*}$ is the Bayes classifier. The $n^{th}$ shatter coefficient of $\mathcal{F}$ is defined as ${\mathcal{S}}_{\mathcal{F}}\left(n\right)={\mathcal{S}}_{\mathcal{A}}\left(n\right)$ and the VC dimesion of $\mathcal{F}$ is defined as $V_{\mathcal{F}}=V_{\mathcal{A}}$ .

The vc inequality

Let $X_1,,...,X_n$ be i.i.d. ${\mathcal{R}}^d$ -valued random variables. Denote the common distribution of $X_i,1\le i\le n$ by $\mu \left(A\right)=P\left(X_1ϵA\right)$ for any subset $A\subset {\mathcal{R}}^d$ . Similarly, define the empirical distribution ${\mu }_n\left(A\right)=\frac{1}{n}{\sum }_1^n{1}_{\left\{X_iϵA\right\}}$ .

Vc '71

For any probablilty measure $\mu$ and collection of subsets $\mathcal{A}$ , and for any $ϵ>0$ .

and

Before giving a proof to the theorem. We present a Corollary.

Let $\mathcal{F}$ be a collection of classifiers of the form $f:{\mathcal{R}}^d\to \{0,1\}$ with VC dimension $V_{\mathcal{F}}<\infty$ ,  Let $R\left(f\right)=P\left(f\right(X)\ne Y)$ and ${\widehat{R}}_n\left(f\right)=\frac{1}{n}{\sum }_1^n{1}_{\{f\left(X_i\right)\ne Y_i\}}$ , where $X_i,Y_i,1\le i\le n$ are i.i.d. with joint distribution $P_{XY}$ .

Define

${\widehat{f}}_n=\begin{array}{c}argmin\\ fϵ\mathcal{F}\end{array}{\widehat{R}}_n\left(f\right)$ .

Then

Let $\mathcal{A}=\left\{\right\{x:f\left(x\right)=1\}\times \{0\}\bigcup \{x:f\left(x\right)=0\}\times \{1\},fϵ\mathcal{F}\}$

Note that

where $A=\{x:f(x)=1\}\times \left\{0\right\}\bigcup \{x:f(x)=0\}\times \left\{1\right\}$ .

Similarly,

Therefore, according to the VC theorem.

Since $V_{\mathcal{F}}<\infty ,{\mathcal{S}}_{\mathcal{F}}\left(n\right)\le {(n+1)}^{V_{\mathcal{F}}}$ and

Next, note that

Therefore,