Vapnik–Chervonenkis theory

Background on empirical processes

Let ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$ be a measurable space. For any measure ${\displaystyle Q}$ on ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$, and any measurable functions ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$, define

${\displaystyle Qf=\int fdQ}$

Measurability issues will be ignored here, for more technical detail see. Let ${\displaystyle {\mathcal {F}}}$ be a class of measurable functions ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ and define:

${\displaystyle \|Q\|_{\mathcal {F}}=\sup\{\vert Qf\vert \$ :\ f\in {\mathcal {F}}\}.}

Let ${\displaystyle X_{1},\ldots ,X_{n}}$ be independent, identically distributed random elements of ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$. Then define the empirical measure

${\displaystyle \mathbb {P} _{n}=n^{-1}\sum _{i=1}^{n}\delta _{X_{i}},}$

where δ here stands for the Dirac measure. The empirical measure induces a map ${\displaystyle {\mathcal {F}}\to \mathbf {R} }$ given by:

${\displaystyle f\mapsto \mathbb {P} _{n}f={\frac {1}{n}}(f(X_{1})+...+f(X_{n}))}$

Now suppose P is the underlying true distribution of the data, which is unknown. Empirical Processes theory aims at identifying classes ${\displaystyle {\mathcal {F}}}$ for which statements such as the following hold:

• uniform law of large numbers:

  ${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}{\underset {n}{\to }}0,}$

That is, as ${\displaystyle n\to \infty }$,

${\displaystyle \left|{\frac {1}{n}}(f(X_{1})+...+f(X_{n}))-\int fdP\right|\to 0}$

uniformly for all ${\displaystyle f\in {\mathcal {F}}}$.

• uniform central limit theorem:

${\displaystyle \mathbb {G} _{n}={\sqrt {n}}(\mathbb {P} _{n}-P)\rightsquigarrow \mathbb {G} ,\quad {\text{in }}\ell ^{\infty }({\mathcal {F}})}$

In the former case ${\displaystyle {\mathcal {F}}}$ is called Glivenko–Cantelli class, and in the latter case (under the assumption ${\displaystyle \forall x,\sup \nolimits _{f\in {\mathcal {F}}}\vert f(x)-Pf\vert <\infty }$) the class ${\displaystyle {\mathcal {F}}}$ is called Donsker or P-Donsker. A Donsker class is Glivenko–Cantelli in probability by an application of Slutsky's theorem.

These statements are true for a single ${\displaystyle f}$, 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 ${\displaystyle f\in {\mathcal {F}}}$. Intuitively then, the set ${\displaystyle {\mathcal {F}}}$ cannot be too large, and as it turns out that the geometry of ${\displaystyle {\mathcal {F}}}$ plays a very important role.

One way of measuring how big the function set ${\displaystyle {\mathcal {F}}}$ is to use the so-called covering numbers. The covering number

${\displaystyle N(\varepsilon ,{\mathcal {F}},\|\cdot \|)}$

is the minimal number of balls ${\displaystyle \{g:\|g-f\|<\varepsilon \}}$ needed to cover the set ${\displaystyle {\mathcal {F}}}$ (here it is obviously assumed that there is an underlying norm on ${\displaystyle {\mathcal {F}}}$). The entropy is the logarithm of the covering number.

Two sufficient conditions are provided below, under which it can be proved that the set ${\displaystyle {\mathcal {F}}}$ is Glivenko–Cantelli or Donsker.

A class ${\displaystyle {\mathcal {F}}}$ is P-Glivenko–Cantelli if it is P-measurable with envelope F such that ${\displaystyle P^{\ast }F<\infty }$ and satisfies:

${\displaystyle \forall \varepsilon >0\quad \sup \nolimits _{Q}N(\varepsilon \|F\|_{Q},{\mathcal {F}},L_{1}(Q))<\infty .}$

The next condition is a version of Dudley's theorem. If ${\displaystyle {\mathcal {F}}}$ is a class of functions such that

${\displaystyle \int _{0}^{\infty }\sup \nolimits _{Q}{\sqrt {\log N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)}}d\varepsilon <\infty }$

then ${\displaystyle {\mathcal {F}}}$ is P-Donsker for every probability measure P such that ${\displaystyle P^{\ast }F^{2}<\infty }$. In the last integral, the notation means

${\displaystyle \|f\|_{Q,2}=\left(\int |f|^{2}dQ\right)^{\frac {1}{2}}}$.

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:

${\displaystyle f\mapsto (\mathbb {P} _{n}-P)f={\dfrac {1}{n}}\sum _{i=1}^{n}(f(X_{i})-Pf)}$

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

${\displaystyle f\mapsto \mathbb {P} _{n}^{0}f={\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})}$

The symmetrized process is a Rademacher process, conditionally on the data ${\displaystyle X_{i}}$. Therefore, it is a sub-Gaussian process by Hoeffding's inequality.

Lemma (Symmetrization). For every nondecreasing, convex Φ: R → R and class of measurable functions ${\displaystyle {\mathcal {F}}}$,

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} \Phi \left(2\left\|\mathbb {P} _{n}^{0}\right\|_{\mathcal {F}}\right)}$

The proof of the Symmetrization lemma relies on introducing independent copies of the original variables ${\displaystyle X_{i}}$ (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.

A typical way of proving empirical CLTs, first uses symmetrization to pass the empirical process to ${\displaystyle \mathbb {P} _{n}^{0}}$ and then argue conditionally on the data, using the fact that Rademacher processes are simple processes with nice properties.

VC Connection

It turns out that there is a fascinating connection between certain combinatorial properties of the set ${\displaystyle {\mathcal {F}}}$ and the entropy numbers. Uniform covering numbers can be controlled by the notion of Vapnik–Chervonenkis classes of sets – or shortly VC sets.

Consider a collection ${\displaystyle {\mathcal {C}}}$ of subsets of the sample space ${\displaystyle {\mathcal {X}}}$. ${\displaystyle {\mathcal {C}}}$ is said to pick out a certain subset ${\displaystyle W}$ of the finite set ${\displaystyle S=\{x_{1},\ldots ,x_{n}\}\subset {\mathcal {X}}}$ if ${\displaystyle W=S\cap C}$ for some ${\displaystyle C\in {\mathcal {C}}}$. ${\displaystyle {\mathcal {C}}}$ is said to shatter S if it picks out each of its 2ⁿ subsets. The VC-index (similar to VC dimension + 1 for an appropriately chosen classifier set) ${\displaystyle V({\mathcal {C}})}$ of ${\displaystyle {\mathcal {C}}}$ is the smallest n for which no set of size n is shattered by ${\displaystyle {\mathcal {C}}}$.

Sauer's lemma then states that the number ${\displaystyle \Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$ of subsets picked out by a VC-class ${\displaystyle {\mathcal {C}}}$ satisfies:

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})\leq \sum _{j=0}^{V({\mathcal {C}})-1}{n \choose j}\leq \left({\frac {ne}{V({\mathcal {C}})-1}}\right)^{V({\mathcal {C}})-1}}$

Which is a polynomial number ${\displaystyle O(n^{V({\mathcal {C}})-1})}$ of subsets rather than an exponential number. Intuitively this means that a finite VC-index implies that ${\displaystyle {\mathcal {C}}}$ has an apparent simplistic structure.

A similar bound can be shown (with a different constant, same rate) for the so-called VC subgraph classes. For a function ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ the subgraph is a subset of ${\displaystyle {\mathcal {X}}\times \mathbf {R} }$ such that: ${\displaystyle \{(x,t):t<f(x)\}}$. A collection of ${\displaystyle {\mathcal {F}}}$ is called a VC subgraph class if all subgraphs form a VC-class.

Consider a set of indicator functions ${\displaystyle {\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}}$ in ${\displaystyle L_{1}(Q)}$ for discrete empirical type of measure Q (or equivalently for any probability measure Q). It can then be shown that quite remarkably, for ${\displaystyle r\geq 1}$:

${\displaystyle N(\varepsilon ,{\mathcal {I}}_{\mathcal {C}},L_{r}(Q))\leq KV({\mathcal {C}})(4e)^{V({\mathcal {C}})}\varepsilon ^{-r(V({\mathcal {C}})-1)}}$

Further consider the symmetric convex hull of a set ${\displaystyle {\mathcal {F}}}$: ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$ being the collection of functions of the form ${\displaystyle \sum _{i=1}^{m}\alpha _{i}f_{i}}$ with ${\displaystyle \sum _{i=1}^{m}|\alpha _{i}|\leq 1}$. Then if

${\displaystyle N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)\leq C\varepsilon ^{-V}}$

the following is valid for the convex hull of ${\displaystyle {\mathcal {F}}}$:

${\displaystyle \log N\left(\varepsilon \|F\|_{Q,2},\operatorname {sconv} {\mathcal {F}},L_{2}(Q)\right)\leq K\varepsilon ^{-{\frac {2V}{V+2}}}}$

The important consequence of this fact is that

${\displaystyle {\frac {2V}{V+2}}<2,}$

which is just enough so that the entropy integral is going to converge, and therefore the class ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$ is going to be P-Donsker.

Finally an example of a VC-subgraph class is considered. Any finite-dimensional vector space ${\displaystyle {\mathcal {F}}}$ of measurable functions ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ is VC-subgraph of index smaller than or equal to ${\displaystyle \dim({\mathcal {F}})+2}$.

Proof: Take ${\displaystyle n=\dim({\mathcal {F}})+2}$ points ${\displaystyle (x_{1},t_{1}),\ldots ,(x_{n},t_{n})}$. The vectors:

${\displaystyle (f(x_{1}),\ldots ,f(x_{n}))-(t_{1},\ldots ,t_{n})}$

are in a n − 1 dimensional subspace of Rⁿ. Take a ≠ 0, a vector that is orthogonal to this subspace. Therefore:

${\displaystyle \sum _{a_{i}>0}a_{i}(f(x_{i})-t_{i})=\sum _{a_{i}<0}(-a_{i})(f(x_{i})-t_{i}),\quad \forall f\in {\mathcal {F}}}$

Consider the set ${\displaystyle S=\{(x_{i},t_{i}):a_{i}>0\}}$. This set cannot be picked out since if there is some ${\displaystyle f}$ such that ${\displaystyle S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}}$ 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.

Theorem (VC Inequality)

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

${\displaystyle {\begin{aligned}P\left(\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|>\varepsilon \right)&\leq 8S({\mathcal {F}},n)e^{-n\varepsilon ^{2}/32}\\\mathbb {E} \left[\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|\right]&\leq 2{\sqrt {\dfrac {\log S({\mathcal {F}},n)+\log 2}{n}}}\end{aligned}}}$

In words, the VC inequality says that as the sample increases, provided that ${\displaystyle {\mathcal {F}}}$ has a finite VC dimension, the empirical 0/1 risk becomes a good proxy for the expected 0/1 risk. Note that both RHS of the two inequalities will converge to 0, provided that ${\displaystyle S({\mathcal {F}},n)}$ grows polynomially in n.

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

${\displaystyle \left|{\hat {R}}_{n}-R\right|_{\mathcal {F}}}$

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.