Vapnik–Chervonenkis theory (also known as VC theory) was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

Introduction

VC theory covers at least four parts (as explained in The Nature of Statistical Learning Theory):

Theory of consistency of learning processes

• What are (necessary and sufficient) conditions for consistency of a learning process based on the empirical risk minimization principle?

Nonasymptotic theory of the rate of convergence of learning processes

• How fast is the rate of convergence of the learning process?

Theory of controlling the generalization ability of learning processes

• How can one control the rate of convergence (the generalization ability) of the learning process?

Theory of constructing learning machines

• How can one construct algorithms that can control the generalization ability?

VC Theory is a major subbranch of statistical learning theory. One of its main applications in statistical learning theory is to provide generalization conditions for learning algorithms. From this point of view, VC theory is related to stability, which is an alternative approach for characterizing generalization.

In addition, VC theory and VC dimension are instrumental in the theory of empirical processes, in the case of processes indexed by VC classes. Arguably these are the most important applications of the VC theory, and are employed in proving generalization. Several techniques will be introduced that are widely used in the empirical process and VC theory. The discussion is mainly based on the book Weak Convergence and Empirical Processes: With Applications to Statistics.

Overview of VC theory in empirical processes

Background on empirical processes

be a measurable space, define

Measurability issues will be ignored here, for more technical detail see. and define:

. Then define the empirical measure

where here stands for the Dirac measure given by:

Now suppose for which statements such as the following hold:

• uniform law of large numbers:

• ,

• .

• uniform central limit theorem:

is called Glivenko–Cantelli is called Donsker or -Donsker. A Donsker class is Glivenko–Cantelli in probability by an application of Slutsky's theorem.

, by standard LLN, CLT plays a very important role.

is to use the so-called covering numbers. The covering number

). The entropy is the logarithm of the covering number.

is Glivenko–Cantelli or Donsker.

is -Glivenko–Cantelli if it is -measurable with envelope and satisfies:

The next condition is a version of Dudley's theorem is a class of functions such that

is -Donsker for every probability measure . In the last integral, the notation means

1. .

Symmetrization

The majority of the arguments about how to bound the empirical process rely on symmetrization, maximal and concentration inequalities, and chaining. Symmetrization is usually the first step of the proofs, and since it is used in many machine learning proofs on bounding empirical loss functions (including the proof of the VC inequality which is discussed in the next section). It is presented here:

Consider the empirical process:

Turns out that there is a connection between the empirical and the following symmetrized process:

The symmetrized process is a Rademacher process. Therefore, it is a sub-Gaussian process by Hoeffding's inequality.

Lemma (Symmetrization). For every nondecreasing, convex ,

(sometimes referred to as a ghost sample) and replacing the inner expectation of the LHS by these copies. After an application of Jensen's inequality different signs could be introduced (hence the name symmetrization) without changing the expectation. The proof can be found below because of its instructive nature. The same proof method can be used to prove the Glivenko–Cantelli theorem.

and then argue conditionally on the data, using the fact that Rademacher processes are simple processes with nice properties.

VC Connection

and the entropy numbers. Uniform covering numbers can be controlled by the notion of Vapnik–Chervonenkis classes of sets – or shortly VC sets.

is said to pick out is said to shatter if it picks out each of its subsets. The VC-index (similar to VC dimension is the smallest for which no set of size .

Sauer's lemma satisfies:

has an apparent simplistic structure.

A similar bound can be shown (with a different constant, same rate) for the so-called VC subgraph classes the subgraph is called a VC subgraph class if all subgraphs form a VC-class.

for discrete empirical type of measure (or equivalently for any probability measure :

Further consider the symmetric convex hull. Then if

:

The important consequence of this fact is that

is going to be -Donsker.

.

. The vectors:

are in a dimensional subspace of . Take , a vector that is orthogonal to this subspace. Therefore:

that would imply that the LHS is strictly positive but the RHS is non-positive.

There are generalizations of the notion VC subgraph class, e.g. there is the notion of pseudo-dimension.

VC inequality

A similar setting is considered, which is more common to machine learning be a set of classifiers. Similarly to the previous section, define the shattering coefficient (also known as growth function):

. Therefore, in terms of the previous section the shattering coefficient is precisely

1. .

This equivalence together with Sauer's Lemma is polynomial in for sufficiently large has a finite VC-index.

to be the expected 0/1 loss. However the empirical risk, given by:

can certainly be evaluated. Then one has the following theorem:

Theorem (VC Inequality)

For binary classification and the 0/1 loss function we have the following generalization bounds:

grows polynomially in .

The connection between this framework and the Empirical Process framework is evident. Here one is dealing with a modified empirical process

but not surprisingly the ideas are the same. The proof of (the first part of) the VC inequality relies on symmetrization, and then argues conditionally on the data using concentration inequalities (in particular Hoeffding's inequality). The interested reader can check the book Theorems 12.4 and 12.5.

References

• See references in articles: Richard M. Dudley, empirical processes, Shattered set.

This is a translation by B. Seckler, of the 1968 note.

• Reprinted in

• They obtained results in a draft form in July 1966 and announced in 1968 in their note

• The paper was first published properly in Russian as