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 the concept of shatter coefficients and VC dimension .

Shatter Coefficients

Let AA be a collection of subsets of RdRd, definition : The nthnth shatter coefficient of AA is defined by

The shatter coefficients are a measure of the richness of the collection AA. SA(n)SA(n) is the largest number of different subsets of a set of nn points that can be generated by intersecting the set with elements of AA.

example : In 1-d, Let A={-∞,t,tϵR}A={-∞,t,tϵR} Possible subsets of {x1,...,xn}{x1,...,xn} generated by intersecting with sets of the form -∞,t-∞,t are {x1,...,xn},{x1,...,xn-1},...,{x1},φ{x1,...,xn},{x1,...,xn-1},...,{x1},φ. Hence Sd(n)=n+1Sd(n)=n+1.

example : In 2-d, Let AA = {{ all rectangles in R2R2}}

Consider a set {x1,x2,x3,x4}{x1,x2,x3,x4} of training points. If we arrange the four points into the corner of a diamond shape. It's easy to see that we can find a rectangle in R2R2 to cover any subsets of the four points as the above picture, i.e. SA(4)=24=16SA(4)=24=16.

Clearly, SA(n)=2n,n=1,2,3SA(n)=2n,n=1,2,3 as well.

However, for n=5,SA(n)<25n=5,SA(n)<25. This is because we can always select four points such that the rectangle, which just contains four of them, contains the other point. Consequently, we cannot find a rectangle classifier which contains the four outer points and does not contain the inner point as shown above.

Note the SA≤2nSA≤2n.

If {{x1,...,xn}⋂A,AϵA}=2n{{x1,...,xn}⋂A,AϵA}=2n then we say that AA shatters x1,...,xnx1,...,xn.

VC Dimension

definition : The VC dimension VAVA of a collection of sets AA is defined as the largest interger nn such that SA(n)=2nSA(n)=2n.

example : A={-∞,t;tϵR},SA=n+1A={-∞,t;tϵR},SA=n+1 hence VA=1VA=1.

example : AA = {{ all rectangles in R2R2}}

SA=2n,n=1,2,3,4SA=2n,n=1,2,3,4 and SA≤2n,n=4SA≤2n,n=4, Hence VA=4VA=4.

The VC dimension provides a useful bound on the growth of the shatter coefficients.

Sauer's Lemma:

Let AA be a collection of set with VC dimension VA<∞VA<∞. Then ∀n,SA(n)≤∑i=0VAni∀n,SA(n)≤∑i=0VAni, also SA(n)≤(n+1)VA,∀nSA(n)≤(n+1)VA,∀n.

VC Dimension and Classifiers

Let FF be a collection of classifiers of the form f:Rd→{0,1}f:Rd→{0,1} Define A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF} In words, this is collection of subsets of X×YX×Y for which on fϵFfϵF maps the features xx to a label opposite of yy.  The size of AA expresses the richness of FF.  The larger AA is the more likely it is that there exists an fϵFfϵF for which R(f)=P(f(X)≠Y)R(f)=P(f(X)≠Y) is close to the Bayes risk R*=P(f*(X)≠Y)R*=P(f*(X)≠Y) where f*f* is the Bayes classifier. The nthnth shatter coefficient of FF is defined as SF(n)=SA(n)SF(n)=SA(n) and the VC dimesion of FF is defined as VF=VAVF=VA.

example : linear (hyperplane) classifiers in RdRd

Consider dd = 2. Let nn be the number of trainning points, It is easy to see that when n=1n=1, Let AA be as above. By using linear classifiers in R2R2, it is easy to see that we can assign 1 to all possible subsets {{x1},φ}{{x1},φ} and 0 to their complements. Hence SF(1)=2SF(1)=2.

When n=2n=2, we can also assign 1 to all possible subsets {{x1,x2},{x1},{x2},φ}{{x1,x2},{x1},{x2},φ} and 0 to their complements, and vice versa. Hence SF(2)=4=22SF(2)=4=22.

When n=3n=3, we can arrange arrange the point x1,x2,x3x1,x2,x3(non-colinear) so that the set of linear classifiers shatters the three points, hence SF(3)=8=23SF(3)=8=23

When n=4n=4, no matter where the points x1,x2,x3,x4x1,x2,x3,x4 and what designated binary values y1,y2,y3,y4y1,y2,y3,y4 are. It's clear that AA does not shatter the four points. To see the claim, first observe that the four points will form a 4-gon (if the four points are co-linear, or if the three points are co-linear then clearly linear classifiers cannot shatter the points). The two points that belong to the same diagonal lines form 2 groups and no linear classifier can assign different values to the 2 groups. Hence SF(4)<16=24SF(4)<16=24 and VF=3VF=3.

We state here without proving it that in general the class of linear classifiers in RdRd has VF=d+1VF=d+1.

The VC Inequality

Let X1,,...,XnX1,,...,Xn be i.i.d. RdRd-valued random variables. Denote the common distribution of Xi,1≤i≤nXi,1≤i≤n by μ(A)=P(X1ϵA)μ(A)=P(X1ϵA) for any subset A⊂RdA⊂Rd. Similarly, define the empirical distribution μn(A)=1n∑1n1{XiϵA}μn(A)=1n∑1n1{XiϵA}.

Thm(VC'71)

For any probablilty measure μμ and collection of subsets AA, and for any ϵ>0ϵ>0.

and

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

Corollary : Let FF be a collection of classifiers of the formf:Rd→{0,1}f:Rd→{0,1} with VC dimension VF<∞VF<∞,  Let R(f)=P(f(X)≠Y)R(f)=P(f(X)≠Y) and R^n(f)=1n∑1n1{f(Xi)≠Yi}R^n(f)=1n∑1n1{f(Xi)≠Yi}, where Xi,Yi,1≤i≤nXi,Yi,1≤i≤n are i.i.d. with joint distributionPXYPXY.

Define

f^n=argminfϵFR^n(f)f^n=argminfϵFR^n(f).

Then

Proof :

Let A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}

Note that

where A={x:f(x)=1}×{0}⋃{x:f(x)=0}×{1}A={x:f(x)=1}×{0}⋃{x:f(x)=0}×{1}

Similarly,

Therefore, according to the VC theorem.

Since VF<∞,SF(n)≤(n+1)VFVF<∞,SF(n)≤(n+1)VF and

Next, note that