Skip to content Skip to navigation

Connexions

You are here: Home » Content » The Vapnik-Chervonenkis Inequality

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.

Recently Viewed

This feature requires Javascript to be enabled.
Reuse / Edit
x

Module:

Add to a lens
x

Add module to:

Add to Favorites
x

Add module to:

 

The Vapnik-Chervonenkis Inequality

Module by: Robert Nowak. E-mail the author

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

S A ( n ) = m a x x 1 , ... , x n ϵ R d { { x 1 , ... , x n } ⋂ A , A ϵ A } . S A ( n ) = m a x x 1 , ... , x n ϵ R d { { x 1 , ... , x n } ⋂ A , A ϵ A } .
(1)

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 1

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 2

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 1: 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 3

linear (hyperplane) classifiers in RdRd

Consider dd = 2. Let nn be the number of training 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}.

Theorem 1: VC '71

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

P s u p A ϵ A μ n ( A ) - μ ( A ) > ϵ ≤ 8 S A ( n ) e - n ϵ 2 / 32 P s u p A ϵ A μ n ( A ) - μ ( A ) > ϵ ≤ 8 S A ( n ) e - n ϵ 2 / 32
(2)

and

E s u p A ϵ A μ n ( A ) - μ ( A ) ≤ 2 log 2 S A ( n ) n E s u p A ϵ A μ n ( A ) - μ ( A ) ≤ 2 log 2 S A ( n ) n
(3)

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

Corollary 1

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

E [ R ( f ^ n ) ] - i n f f ϵ F R ( f ) ≤ 4 V F log n + 1 + log 2 n . E [ R ( f ^ n ) ] - i n f f ϵ F R ( f ) ≤ 4 V F log n + 1 + log 2 n .
(4)

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

P ( f ( X ) ≠ Y ) = P ( ( X , Y ) ϵ A ) : = μ ( A ) P ( f ( X ) ≠ Y ) = P ( ( X , Y ) ϵ A ) : = μ ( A )
(5)

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

Similarly,

1 n ∑ 1 n 1 { f ( X i ) ≠ Y i } = 1 n ∑ 1 n 1 { ( X i , Y i ) ϵ A } : = μ ( A ) . 1 n ∑ 1 n 1 { f ( X i ) ≠ Y i } = 1 n ∑ 1 n 1 { ( X i , Y i ) ϵ A } : = μ ( A ) .
(6)

Therefore, according to the VC theorem.

E s u p f ϵ F R ^ n ( f ) - R ( f ) = E s u p A ϵ A μ n ( A ) - μ ( A ) ≤ 2 log 2 S A ( n ) n = 2 log 2 S F ( n ) n E s u p f ϵ F R ^ n ( f ) - R ( f ) = E s u p A ϵ A μ n ( A ) - μ ( A ) ≤ 2 log 2 S A ( n ) n = 2 log 2 S F ( n ) n
(7)

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

E s u p f ϵ F R ^ n ( f ) - R ( f ) ≤ 2 V F log ( n + 1 ) + log 2 n . E s u p f ϵ F R ^ n ( f ) - R ( f ) ≤ 2 V F log ( n + 1 ) + log 2 n .
(8)

Next, note that

R f ^ n - i n f f ϵ F R ( f ) = R f ^ n - R ^ n f ^ n + R ^ n f ^ n - i n f f ϵ F R ( f ) = R f ^ n - R ^ n f ^ n + s u p f ϵ F R ^ n ( f ^ n ) - R ( f ) ≤ R f ^ n - R ^ n f ^ n + s u p f ϵ F R ^ n ( f ) - R ( f ) ≤ 2 s u p f ϵ F R ^ n ( f ) - R ( f ) . R f ^ n - i n f f ϵ F R ( f ) = R f ^ n - R ^ n f ^ n + R ^ n f ^ n - i n f f ϵ F R ( f ) = R f ^ n - R ^ n f ^ n + s u p f ϵ F R ^ n ( f ^ n ) - R ( f ) ≤ R f ^ n - R ^ n f ^ n + s u p f ϵ F R ^ n ( f ) - R ( f ) ≤ 2 s u p f ϵ F R ^ n ( f ) - R ( f ) .
(9)

Therefore,

E R f ^ n - i n f f ϵ F R ( f ) ≤ 2 E s u p f ϵ F R ^ n ( f ) - R ( f ) ≤ 4 V F log ( n + 1 ) + log 2 n . E R f ^ n - i n f f ϵ F R ( f ) ≤ 2 E s u p f ϵ F R ^ n ( f ) - R ( f ) ≤ 4 V F log ( n + 1 ) + log 2 n .
(10)

Content actions

Download module as:

PDF | More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Reuse / Edit:

Reuse or edit module (?)

Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.