0.19 Applications of vc bound

Linear classifiers

Suppose $\mathcal{F}$ = {linear classifiers in ${\mathbf{R}}^d$ }, then we have

Generalized linear classifiers

Normally, we have a feature vector $X\in {\mathbf{R}}^d$ . A hyperplane in ${\mathbf{R}}^d$ provides a linear classifier in ${\mathbf{R}}^d$ . Nonlinear classifiers can be obtained by a straightforward generalization.

Let ${\phi }_1,\cdots ,{\phi }_{d^{{}^{\text{'}}}}$ , $d^{{}^{\text{'}}}\ge d$ be a collection of functions mapping ${\mathbf{R}}^d\to \mathbf{R}$ . These functions, applied to a feature $X\in {\mathbf{R}}^d$ , produce a generalized set of features, $\phi ={({\phi }_1\left(X\right),{\phi }_2\left(X\right),\cdots ,{\phi }_{d^{\text{'}}}\left(X\right))}^{\text{'}}$ . For example, if $X={(x_1,x_2)}^{\text{'}}$ , then we could consider $d^{\text{'}}=S$ and $\phi ={(x_1,x_2,x_1{x}_2,x_1^2,x_2^2)}^{\text{'}}\in {\mathbf{R}}^5$ . We can then construct a linear classifier in the higher dimensional generalized feature space ${\mathbf{R}}^{d^{\text{'}}}$ .

The VC bounds immediately extend to this case, and we have for $\mathcal{F}$ ' = { generalized linear classifiers based on maps $\phi :{\mathbf{R}}^d\to {\mathbf{R}}^{d^{\text{'}}}$ },

Half-space classifiers

Steele '75, dudley '78

Let $\mathcal{G}$ be a finite-dimensional vector space of real-valued functions on ${\mathbf{R}}^d$ . The class of sets $\mathcal{A}=\left\{\right\{x:g\left(x\right)\ge 0\}:g\in \mathcal{G}\}$ has VC dimension $\ge$ dim( $\mathcal{G}$ ).

It is sufficient to show that no set of $n=dim\left(\mathcal{G}\right)+1$ points can be shattered by $\mathcal{A}$ . Take any $n$ points and for each $g\in \mathcal{G}$ , define the vector $V_g=(g\left(x_1\right),\cdots ,g\left(x_n\right))$ .

The set $\{V_g:g\in \mathcal{G}\}$ is a linear subspace of ${\mathbf{R}}^n$ of dimension $\le$ dim ( $\mathcal{G}$ ) = $n-1$ . Therefore, there exists a non-zero vector $\alpha =({\alpha }_1,\cdots ,{\alpha }_n)\in {\mathbf{R}}^n$ such that ${\sum }_{i=1}^n{\alpha }_{i}g\left(x_i\right)=0$ . We can assume that at least one of these ${\alpha }_i^S$ is negative (if all are positive, just negate the sum). We can then re-arrange thisexpression as ${\sum }_{i:{\alpha }_i\ge 0}{\alpha }_{i}g\left(x_i\right)={\sum }_{i:{\alpha }_i<0}-{\alpha }_{i}g\left(x_i\right)$ .

Now suppose that there exists a $g\in \mathcal{G}$ such that the set $\{x:g(x)\ge 0\}$ selects precisely the $x_i^S$ on the left-hand side above. Then all terms on the left are non-negative and allthe terms on the right are non-positive. Since $\alpha$ is non-zero, this is a contradiction. Therefore, $x_1,\cdots ,x_n$ cannot be shattered by sets in $\{x:g(x)\ge 0\}$ , $g\in \mathcal{G}$ .  6.375pt0.0pt6.375pt

Tree classifiers

Let

Let $T\in {\mathcal{T}}_k$ . Each cell of $T$ results from splitting a rectangular region into two smaller rectangles parallel to one ofthe coordinate axes.

Vc bound for tree classifiers

Structural risk minimization (srm)

SRM is simply complexity regularization using VC type bounds in place of Chernoff's bound or other concentration inequalities.

The basic idea is to consider a sequence of sets of classifiers ${\mathcal{F}}_1,{\mathcal{F}}_2,...,$ of increasing VC dimensions $V_{{\mathcal{F}}_1}\le V_{{\mathcal{F}}_2}\le ...$ . Then for each $k=1,2,...$ we find the minimum empirical risk classifier

and then select the final classifier according to

and ${\widehat{f}}_n\equiv {\widehat{f}}_n^{\left(\widehat{k}\right)}$ is the final choice.

The basic rational is that we know

where $C^{\text{'}}$ is a constant.

The end result is that

analogous to our pervious complexity regularization results, except thatcodelengths are replaced by VC dimensions.

In order to prove the result we use the VC probability concentration bound and assume that $△={\sum }_{k\ge 1}{V}_{{\mathcal{F}}_k}<\infty$ . This enables a union bounding argument and leads to a risk bound of the form given above.

Key point of vc theory

Complexity of classes depends on richness (shattering capability) relative to a set of $n$ arbitrary points. This allows us to effectively “quantize" collections of functions in a slightlydata-dependent manner.

Application to trees

Let

Then

satisfies

compare with

from Lecture 11 .