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
Let be a measurable space. For any measure on , and any measurable functions , define
Measurability issues will be ignored here, for more technical detail see. Let be a class of measurable functions and define:
Let be independent, identically distributed random elements of . Then define the empirical measure
where here stands for the Dirac measure. The empirical measure induces a map given by:
Now suppose is the underlying true distribution of the data, which is unknown. Empirical Processes theory aims at identifying classes for which statements such as the following hold:
uniform law of large numbers:
That is, as ,
uniformly for all .
uniform central limit theorem:
In the former case is called Glivenko–Cantelli class, and in the latter case (under the assumption ) the class is called Donsker or -Donsker. A Donsker class is Glivenko–Cantelli in probability by an application of Slutsky's theorem .
These statements are true for a single , by standard LLN, CLT arguments under regularity conditions, and the difficulty in the Empirical Processes comes in because joint statements are being made for all . Intuitively then, the set cannot be too large, and as it turns out that the geometry of plays a very important role.
One way of measuring how big the function set is to use the so-called covering numbers. The covering number
is the minimal number of balls needed to cover the set (here it is obviously assumed that there is an underlying norm on ). The entropy is the logarithm of the covering number.
Two sufficient conditions are provided below, under which it can be proved that the set is Glivenko–Cantelli or Donsker.
A class is -Glivenko–Cantelli if it is -measurable with envelope such that and satisfies:
The next condition is a version of the celebrated Dudley's theorem. If is a class of functions such that
then is -Donsker for every probability measure such that . In the last integral, the notation means
.
Symmetrization
The majority of the arguments of 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, conditionally on the data . Therefore, it is a sub-Gaussian process by Hoeffding's inequality.
Lemma (Symmetrization). For every nondecreasing, convex and class of measurable functions ,