Machine Learning. Additional Lecture 1. The Theory of…

What this lecture is about

The classical theory of generalisation — the Vapnik–Chervonenkis bound, capacity, structural risk minimisation, the "Occam's razor" bound — is set out in the first-semester lecture "Generalization Theory". Its main flaw is that the bounds are very loose. There are two reasons: the bound on the uniform deviation ignores the splitting of the family of algorithms, and Boole's inequality ignores the similarity of the algorithms. This lecture is about what happens when both effects are taken into account. First, experiments show how strongly splitting and similarity (connectivity) affect overfitting. Then a combinatorial theory is built: the splitting–connectivity graph of a family of algorithms, the generating and forbidden sets, and an upper bound on the probability of overfitting that takes both effects into account and in a special case turns into the Vapnik–Chervonenkis bound.

Reminder: the probability of overfitting

The first part of the slides for this lecture (pp. 3–20) repeats the problem setting and the classical theory; here we give only what will be needed later.

Definition (The error matrix and the probability of overfitting).

$X^{L} = {x_{1}, \dots, x_{L}}$ is a finite general set of objects; $X^{L} = X^{ℓ} ⊔ X^{k}$ is a split into a training and a test sample;
$A$ is a finite set of algorithms; $I (a, x) = [a errs on x]$ is the binary loss function;
$n (a, X) = \sum_{x \in X} I (a, x)$ is the number of errors, $ν (a, X) = n (a, X) /∣ X ∣$ is the error rate of $a$ on the sample $X$ ;
$μ : X^{ℓ} \mapsto a$ is the learning method;
the overfitting $δ (μ, X^{ℓ}, X^{k}) = ν (μ (X^{ℓ}), X^{k}) - ν (μ (X^{ℓ}), X^{ℓ})$ ;
all splits $X^{L} = X^{ℓ} ⊔ X^{k}$ are equally likely: $P \equiv \frac{1}{C _{L}^{ℓ}} \sum_{X^{ℓ} ⊔ X^{k} = X^{L}}$ .

The probability of overfitting:

R_{ε} (μ, X^{L}) = P [δ (μ, X^{ℓ}, X^{k}) ⩾ ε] .

Complete cross-validation:

CCV (μ, X^{L}) = E ν (μ (X^{ℓ}), X^{k}) .

The error matrix is the $L \times ∣ A ∣$ matrix $(I (a, x_{i}))$ with pairwise distinct columns: each algorithm is represented by its error vector. For a single algorithm with $m$ errors on the general set, the probability of overfitting is computed exactly:

R_{ε} (a, X^{L}) = H_{L}^{ℓ, m} (\frac{ℓ}{L} (m - ε k)), H_{L}^{ℓ, m} (z) = s = 0 \sum ⌊ z ⌋ \frac{C _{m}^{s} C _{L - m}^{ℓ - s}}{C _{L}^{ℓ}},

where $H$ is the hypergeometric distribution function. For a family, the Vapnik–Chervonenkis bound is obtained in two steps — a bound on the uniform deviation and Boole's inequality:

R_{ε} (μ, X^{L}) ⩽ a \in A \sum H_{L}^{ℓ, m (a)} (\frac{ℓ}{L} (m (a) - ε k)) ⩽ ∣ A ∣ \cdot \frac{3}{2} exp (- ε^{2} ℓ) for ℓ = k .

The first step replaces the result of learning by the worst algorithm of the family and ignores the fact that the learning method picks algorithms only from the lower layers of the family by number of errors. This is the splitting effect. The second step adds up the probabilities of events as if they did not overlap, and ignores the fact that for similar algorithms the overfitting events almost coincide. This is the similarity effect, or connectivity effect.

Experiments with overfitting

A monotone chain of algorithms

How can the similarity of algorithms be taken into account, and not only splitting? The simplest model of a family of similar algorithms is a chain.

Definition (A chain of algorithms). A chain is generated by a continuous change of a parameter, for example by a threshold decision rule over a feature $f$ :

A = {a_{d} (x) = [f (x) ⩾ θ_{d}] : d = 0, \dots, D} .

In a chain each next algorithm differs from the previous one on only one object.

Example (A chain of threshold rules: 2 classes, 6 objects, 7 threshold algorithms). The objects $x_{1}, \dots, x_{6}$ are ordered by the value of the feature $f$ ; the classes are ${∙, \circ}$ : $x_{1}, x_{2}, x_{5}$ are of class $∙$ , $x_{3}, x_{4}, x_{6}$ of class $\circ$ . The threshold $θ_{d}$ stands before the object $x_{d + 1}$ ; the rule $a_{d}$ assigns the objects to the right of the threshold to class $\circ$ . The error matrix:

	$a_{0}$	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$a_{5}$	$a_{6}$
$x_{1}$	1	0	0	0	0	0	0
$x_{2}$	1	1	0	0	0	0	0
$x_{3}$	0	0	0	1	1	1	1
$x_{4}$	0	0	0	0	1	1	1
$x_{5}$	1	1	1	1	1	0	0
$x_{6}$	0	0	0	0	0	0	1
$n (a_{d}, X^{L})$	3	2	1	2	3	2	3

Slide

A number line with objects of two classes and thresholds θ0–θ6; below it, a broken line of the number of errors of the threshold rule at each threshold

TikZ

Moving the threshold past one object changes the rule's answer on exactly that object, so neighbouring columns of the error matrix differ in one row, and the number of errors changes by one, in one direction or the other. Threshold rules over one feature, conjunctions of threshold conditions, linear classifiers under a continuous change of the weights — in all these families similar algorithms form such chains and their multidimensional generalisations.

How overfitting depends on the error matrix

Definition (An experiment with four error matrices). The upper bounds of VC theory depend only on the size of the error matrix, $L \times ∣ A ∣$ , and are therefore very loose.

The experiment: compare $R_{ε}$ and CCV for four error matrices:

the best algorithm is the same;
there is or is not splitting — when each next algorithm makes one more error than the previous one;
there is or is not connectivity — when each next algorithm differs from the previous one on only one object.

K. V. Vorontsov. Splitting and similarity phenomena in the sets of classifiers and their effect on the probability of overfitting. PRIA, 2009.

The four matrices are built to differ only in these two properties. With splitting and connectivity: a monotone chain, each next error vector obtained from the previous one by adding one error. Connectivity without splitting: a chain in which the error on one object is moved to another, and the number of errors does not grow. Splitting without connectivity: vectors with a growing number of errors, but random, unlike one another. Neither: random vectors with the same number of errors. The learning method in all cases is empirical risk minimisation; the probability of overfitting and CCV are estimated by the Monte Carlo method over random splits.

Four thumbnails of error matrices (with and without splitting, with and without connectivity) and a plot of the probability of overfitting against the number of algorithms for each of them

Remark (Conclusions from the experiment).

Connectivity slows the growth of the curve $R_{ε} (∣ A ∣)$ .
Splitting lowers the level of the horizontal asymptote.
Huge families with splitting and connectivity may hardly overfit at all.
The VC bound linearly majorises the worst of these curves.

Without either effect the probability of overfitting grows quickly with the number of algorithms and is already close to one at a hundred algorithms. Connectivity without splitting slows this growth: the curve grows almost linearly and slowly. Splitting without connectivity stops the growth: from about fifteen algorithms on, the curve reaches a horizontal asymptote, because algorithms from the upper layers are never chosen. Both effects together give an asymptote of about $0.1$ after only a few algorithms. The Vapnik–Chervonenkis bound grows in proportion to $∣ A ∣$ and does not distinguish these four cases.

The same four error matrices and a plot of the mean error rates in training and on test against the number of algorithms

Remark (Conclusions for CCV).

Without splitting and connectivity even 10 algorithms can overfit badly.
Without taking the splitting and connectivity effects into account, exact bounds on the probability of overfitting cannot be obtained.

The error rate of the best algorithm on the general sample is the same in all four cases, $0.05$ . The gap between the error rates on test and in training is precisely overfitting on average. With splitting and connectivity it is small: the test error rate is about $0.06$ . Without either effect the training error rate falls to $0.01$ , and the test error rate grows almost to $0.1$ : the learning method finds in the family an algorithm that happens to fit the training sample well. Without splitting the gap appears already within the first ten algorithms.

Overfitting of chains with different splitting

A chain can be arranged in different ways: the number of errors along it may grow monotonically from the best algorithm, or it may have several local minima, or stay almost constant for a long time.

Example (Overfitting of chains with different splitting). Experimental conditions: $L = 100$ , $ℓ = 50$ , $m^{*} = 25$ , $∣ N ∣ = 1 0^{4}$ random Monte Carlo splits.

For six chains with different profiles of the error rate along the chain, the mean error rate of ERM in training and on test was computed: a monotone chain from the best algorithm; a V-shaped chain with one minimum in the middle; a chain with three minima; a chain that reaches a noisy plateau; a plateau with one dip; a chain along which the error rate is almost constant.

Sh. Kh. Ishkina. Combinatorial bounds of overfitting for threshold decision rules. 2018 (in Russian).

The weaker the splitting of a chain, the greater the overfitting. For the monotone chain the error rates of ERM in training and on test almost coincide: about $0.25$ and $0.26$ . For the V-shaped chain the gap is larger, for the chain with three equal minima larger still. The chain that overfits most is the one along which the error rate is everywhere close to the minimum: about $0.22$ in training and about $0.29$ on test. Many almost equally good algorithms is exactly what the absence of splitting means: the learning method has many candidates, and one of them will by chance fit the training sample better.

Overfitting when choosing between two algorithms

The simplest case in which both effects are already visible is a family of two algorithms.

Definition (A family of two algorithms). $A = {a_{1}, a_{2}}$ ; suppose that for the algorithms $a_{1}, a_{2}$ the numbers $m_{0}, m_{1}, m_{2}, m_{3}$ are known:

a_{1} a_{2} = (1, \dots, 1, 1, \dots, 1, 0, \dots, 0, 0, \dots, 0); = (m_{0} 1, \dots, 1, m_{1} 0, \dots, 0, m_{2} 1, \dots, 1, m_{3} 0, \dots, 0) .

The similarity of the error vectors is measured by the Hamming distance:

r (a_{1}, a_{2}) = i = 1 \sum L I (a_{1}, x_{i}) - I (a_{2}, x_{i}) = m_{1} + m_{2} .

The splitting is measured by the difference in the number of errors:

d (a_{1}, a_{2}) = n (a_{1}, X^{L}) - n (a_{2}, X^{L}) = ∣ m_{1} - m_{2} ∣.

Experimental conditions: $ℓ = k = 100$ , $m_{0} = 20$ , $ε = 0.05$ , the Monte Carlo method over $∣ N ∣ = 1 0^{4}$ random splits.

The objects fall into four groups: on $m_{0}$ objects both algorithms err, on $m_{1}$ only $a_{1}$ , on $m_{2}$ only $a_{2}$ , on $m_{3}$ neither. The error vectors differ on $m_{1} + m_{2}$ objects, and the numbers of errors by $∣ m_{1} - m_{2} ∣$ .

Plots of the probability of overfitting against the Hamming distance for four values of the difference in the number of errors, the experimental curves and their smoothing

Remark (Conclusions for a pair of algorithms).

Overfitting occurs even when choosing between two algorithms.
The more similar they are, the less the overfitting.
The greater the splitting, the less the overfitting.

If two algorithms coincide almost everywhere ( $r$ is small), choosing between them changes almost nothing, and the probability of overfitting is close to that for a single algorithm. As $r$ grows it grows, and with equal numbers of errors ( $d = 0$ ) it approaches $0.5$ . If, however, one algorithm is noticeably worse than the other ( $d = 40$ ), the learning method almost always chooses the better one, and the probability of overfitting stays half as high for any $r$ .

For two algorithms the probability of overfitting can be computed exactly.

Theorem (On the probability of overfitting). If $A = {a_{1}, a_{2}}$ and the method $μ$ minimises the empirical risk (the number of errors in training), then for any $ε \in [0, 1]$

R_{ε} (μ, X^{L}) = s_{0} = 0 \sum m_{0} s_{1} = 0 \sum m_{1} s_{2} = 0 \sum m_{2} \frac{C _{m_{0}}^{s_{0}} C _{m_{1}}^{s_{1}} C _{m_{2}}^{s_{2}} C _{L - m_{0} - m_{1} - m_{2}}^{ℓ - s_{0} - s_{1} - s_{2}}}{C _{L}^{ℓ}} \times (+ [s_{1} < s_{2}] [s_{0} + s_{1} ⩽ \frac{ℓ}{L} (m_{0} + m_{1} - ε k)] + [s_{1} ⩾ s_{2}] [s_{0} + s_{2} ⩽ \frac{ℓ}{L} (m_{0} + m_{2} - ε k)]) .

Proof. Let $s_{0}$ , $s_{1}$ , $s_{2}$ objects from the first three groups fall into the training sample; the probability of this is the multivariate hypergeometric distribution, the first factor. In training $a_{1}$ makes $s_{0} + s_{1}$ errors and $a_{2}$ makes $s_{0} + s_{2}$ . The empirical risk minimisation method chooses $a_{1}$ if $s_{1} < s_{2}$ , and $a_{2}$ otherwise (in a tie, $a_{2}$ ). The chosen algorithm, with $m$ errors on $X^{L}$ and $s$ errors in training, overfits if $\frac{m - s}{k} - \frac{s}{ℓ} ⩾ ε$ , that is, $s ⩽ \frac{ℓ}{L} (m - ε k)$ , as in the case of a single algorithm.

The combinatorial theory of overfitting

The splitting–connectivity graph

The experiments show that overfitting is determined not by the size of the family but by how its error vectors are arranged: how far they are split by the number of errors and how far they are connected by the similarity relation. This structure is described by a graph.

Definition (The splitting–connectivity graph of a set of algorithms). Define binary relations on the set of algorithms $A$ :

the partial order $a ⩽ b$ : $I (a, x) ⩽ I (b, x)$ for all $x \in X^{L}$ ;
precedence $a ≺ b$ : $a ⩽ b$ and $∥ b - a ∥ = 1$ .

The splitting–connectivity graph $⟨ A, E ⟩$ : $A$ is the set of pairwise distinct error vectors; $E = {(a, b) : a ≺ b}$ .

Properties of the splitting–connectivity graph:

it is a subgraph of the Hasse diagram of the order relation $⩽$ on $A$ ;
each edge $(a, b)$ has an edge object $x_{ab} \in X^{L}$ such that $I (a, x_{ab}) = 0$ , $I (b, x_{ab}) = 1$ ;
the graph is multipartite with layers $A_{m} = {a \in A : n (a, X^{L}) = m}$ , $m = 0, \dots, L$ .

An algorithm $a$ is no worse than $b$ in the sense of the order if $a$ errs only where $b$ errs too. Precedence means that $b$ is obtained from $a$ by adding exactly one error; the object of that error is the edge object $x_{ab}$ . Edges go only between neighbouring layers, from layer $m$ to layer $m + 1$ , so the graph is multipartite. The vertical structure of the graph is the splitting, and the edges are the connectivity: similar algorithms are joined.

Example (A family of linear classifiers). For a sample of ten points on the plane, linear classifiers generate in layer 0 one error vector with no errors, in layer 1 five vectors with one error, in layer 2 eight vectors with two errors, and so on (the error matrix of this sample is given in the first-semester lecture "Generalization Theory"). The splitting–connectivity graph is diamond-shaped: the layers first widen and then, towards vectors with many errors, narrow.

On the left, ten points of two classes on the plane and several separating lines; on the right, the splitting–connectivity graph of the family of linear classifiers with layers from 0 to 10 errors

Example (A monotone chain). A monotone chain of algorithms: $a_{0} ≺ a_{1} ≺ \dots ≺ a_{D}$ .

Example: a one-dimensional threshold classifier $a_{d} (x) = [x > θ_{d}]$ ; 2 classes ${∙, \circ}$ , 6 objects: $x_{4}, x_{5}, x_{6}$ are of class $∙$ , $x_{1}, x_{2}, x_{3}$ of class $\circ$ to the right of them; the thresholds $θ_{0}, \dots, θ_{3}$ move to the right past $x_{1}, x_{2}, x_{3}$ . The error matrix:

	$a_{1}$	$a_{2}$	$a_{3}$
$x_{1}$	1	1	1
$x_{2}$	0	1	1
$x_{3}$	0	0	1
$x_{4}$	0	0	0
$x_{5}$	0	0	0
$x_{6}$	0	0	0

Slide

The graph of a monotone chain: four vertices a0–a3 at levels m from 0 to 3, joined by edges with the edge objects x1, x2, x3

TikZ

Example (A two-dimensional net of classifiers). Example: a two-dimensional linear classifier, 2 classes ${∙, \circ}$ , 6 objects. The lines $a_{ij}$ are obtained by shifting and rotating the separating line: $i$ is the number of errors on the objects of one class ( $x_{2}, x_{4}, x_{6}$ ), $j$ on the objects of the other ( $x_{1}, x_{3}, x_{5}$ ). The error matrix:

	$a_{01}$	$a_{10}$	$a_{02}$	$a_{11}$	$a_{20}$	$a_{03}$	$a_{12}$	$a_{21}$	$a_{30}$
$x_{1}$	1	0	1	1	0	1	1	1	0
$x_{2}$	0	1	0	1	1	0	1	1	1
$x_{3}$	0	0	1	0	0	1	1	0	0
$x_{4}$	0	0	0	0	1	0	0	1	1
$x_{5}$	0	0	0	0	0	1	0	0	0
$x_{6}$	0	0	0	0	0	0	0	0	1

Slide

The graph of a two-dimensional net: ten vertices a00–a30 in four layers, the edges between neighbouring layers labelled by objects

TikZ

A monotone chain is a one-dimensional structure: each algorithm is obtained from the previous one by adding one error. A two-dimensional net arises when the classifier has two degrees of freedom: the separating line can be moved so that it adds errors on the objects of one class, or so that it adds them on the objects of the other. Then two edges leave every vertex except the extreme ones. For linear classifiers in a space of higher dimension the graph is more complicated, but the edges still join similar error vectors, and the layers still split the family by the number of errors.

The generating and forbidden sets

To obtain a bound on the probability of overfitting, we need to understand for which splits the learning method chooses a given algorithm. For this, two characteristics of a vertex of the graph are introduced.

Definition (The generating set and upper connectivity). The upper connectivity $u (a)$ of an algorithm $a$ is the number of all edges leaving the vertex $a$ in the splitting–connectivity graph:

u (a) = ∣ X_{a} ∣, X_{a} = {x_{ab} \in X^{L} a ≺ b};

$X_{a}$ is called the generating set of the algorithm $a$ .

Definition (The forbidden set and inferiority). The inferiority $q (a)$ of an algorithm $a$ is the number of distinct edge objects on all paths leading into $a$ :

q (a) = ∣ X_{a}^{'} ∣, X_{a}^{'} = {x \in X^{L} \exists b \in A : b < a, I (b, x) < I (a, x)};

$X_{a}^{'}$ is called the forbidden set of the algorithm $a$ .

The generating set consists of the objects such that adding an error on any one of them gives a neighbouring, slightly worse algorithm. The forbidden set consists of the objects on which $a$ errs while some better algorithm $b < a$ does not. If even one such object falls into the training sample, $b$ turns out better than $a$ in training, and the empirical risk minimisation method will not choose $a$ . Hence the name: these objects "forbid" the choice of $a$ .

Definition (The splitting and connectivity characteristics of an algorithm).

upper connectivity $u (a) = # {x_{ab} \in X^{L} a ≺ b}$ ;
lower connectivity $d (a) = # {x_{ba} \in X^{L} b ≺ a}$ ;
inferiority $q (a) = # {x \in X^{L} \exists b \in A : b < a, I (b, x) < I (a, x)}$ ;
the number of errors $m (a) = n (a, X^{L})$ .

Proposition. $d (a) ⩽ q (a) ⩽ m (a)$ .

Every object of a lower edge $x_{ba}$ , $b ≺ a$ , belongs to the forbidden set, which gives the first inequality. Every object of the forbidden set is an error of the algorithm $a$ , which gives the second. Upper and lower connectivity and inferiority measure different things: $u (a)$ is how many similar, slightly worse neighbours the algorithm has; $q (a)$ is how much better algorithms "screen" $a$ .

A fragment of a two-dimensional net of algorithms around a vertex a in layer m: two edges upward with the objects x3 and x4 are highlighted in green, two edges downward with the objects x1 and x2 in red

The splitting–connectivity upper bound

Definition (A monotone learning method). An empirical risk minimisation method $μ$ is monotone if

μ (X^{ℓ}) \in A_{K} (X^{ℓ}) = Arg a \in A min K (a, X^{ℓ}),

where $K (a, U)$ is a strictly monotone function of the error vector of $a$ on the sample $U$ : for any $U \subset X^{L}$ and $a, b \in A$ , if $I (a, x) ⩽ I (b, x)$ for all $x \in U$ and the error vectors of $a$ and $b$ on $U$ differ, then $K (a, U) < K (b, U)$ ; and if they coincide on $U$ , then $K (a, U) = K (b, U)$ .

Example. The function $K (a, U) = ν (a, U)$ is strictly monotone.

Theorem (The splitting–connectivity bound). For any monotone method $μ$ , any $X^{L}$ , $A$ and $ε \in (0, 1)$

R_{ε} (μ, X^{L}) ⩽ a \in A \sum \frac{C _{L - u - q}^{ℓ - u}}{C _{L}^{ℓ}} H_{L - u - q}^{ℓ - u, m - q} (\frac{ℓ}{L} (m - ε k)),

where $u = u (a)$ , $q = q (a)$ , $m = m (a)$ .

K. V. Vorontsov, A. A. Ivahnenko, I. M. Reshetnyak. Generalization bound based on the splitting and connectivity graph of the set of classifiers. 2010.

Proof.

From $μ$ build a monotone pessimistic method $μ ˉ$ that maximises the overfitting:

$μ ˉ (X^{ℓ}) = ar g a \in A_{K} (X^{ℓ}) max δ (a, X^{ℓ}, X^{k}) .$

Then $R_{ε} (μ, X^{L}) ⩽ R_{ε} (μ ˉ, X^{L})$ is an upper bound.
If $μ ˉ (X^{ℓ}) = a$ , then $X_{a} \subseteq X^{ℓ}$ because $μ ˉ$ is pessimistic, and $X_{a}^{'} \subseteq X^{k}$ because $μ ˉ$ is monotone.
Therefore

$P [μ ˉ (X^{ℓ}) = a] ⩽ P [S (a, X^{ℓ}) X_{a} \subseteq X^{ℓ} and X_{a}^{'} \subseteq X^{k}] = \frac{C _{L - ∣ X_{a} ∣ - ∣ X_{a}^{'} ∣}^{ℓ - ∣ X_{a} ∣}}{C _{L}^{ℓ}} = \frac{C _{L - u - q}^{ℓ - u}}{C _{L}^{ℓ}} .$
By the law of total probability:

$R_{ε} (μ ˉ, X^{L}) ⩽ a \in A \sum C_{L - u - q}^{ℓ - u} / C_{L}^{ℓ} P [S (a, X^{ℓ})] \cdot H_{L - u - q}^{ℓ - u, m - q} (\frac{ℓ}{L} (m - ε k)) P [δ (a, X^{ℓ}, X^{k}) ⩾ ε S (a, X^{ℓ})] .$

Let us explain steps 2 and 4. Suppose the pessimistic method has chosen $a$ . If some object $x_{ab}$ of the generating set were in the test sample, the neighbouring algorithm $b$ would have as many errors in training as $a$ , that is, it too would be among the best, while erring more on test; the pessimistic method would have chosen $b$ . So all the objects of the generating set are in training. If some object of the forbidden set were in training, there would be an algorithm $b < a$ with a smaller value of $K$ in training, and $a$ would not have been chosen. So all the objects of the forbidden set are in the test sample. The probability that $u$ given objects fall into training and $q$ given objects into test equals the share of such splits: the remaining $ℓ - u$ training objects are chosen from the $L - u - q$ remaining ones. Under this condition the algorithm $a$ makes no error on any object of $X_{a}$ and errs on all $q$ objects of $X_{a}^{'}$ ; among the remaining $L - u - q$ objects it has $m - q$ errors, and overfitting is again described by the hypergeometric function, but on a smaller set.

Remark (Properties of the splitting–connectivity upper bound).

For $∣ A ∣ = 1$ it is the hypergeometric distribution function:

$R_{ε} = H_{L}^{ℓ, m} (\frac{ℓ}{L} (m - ε k)) \to 0 as ℓ, k \to \infty.$
For $q = u = 0$ and $ℓ = k$ it is the Vapnik–Chervonenkis bound:

$R_{ε} ⩽ a \in A \sum H_{L}^{ℓ, m} (\frac{ℓ}{L} (m - ε k)) ⩽ ∣ A ∣ \cdot \frac{3}{2} exp (- ε^{2} ℓ) .$
The contribution of an algorithm $a \in A$ decreases exponentially:
- in $u (a)$ $\Rightarrow$ connected families overfit less;
- in $q (a)$ $\Rightarrow$ only the lower layers contribute to $R_{ε}$ .
The probability of obtaining an algorithm as the result of learning:

$P [μ (X^{ℓ}) = a] ⩽ P_{a} = C_{L - u - q}^{ℓ - u} / C_{L}^{ℓ} .$
The bound is exact (becomes an equality) for multidimensional monotone nets of algorithms.

For $ℓ = k$ the factor $C_{L - u - q}^{ℓ - u} / C_{L}^{ℓ}$ is approximately $2^{- u - q}$ : each object of the generating set falls into training with probability about one half, and each object of the forbidden set into test. So an algorithm with large connectivity or large inferiority contributes almost nothing to the bound. Inferiority grows with the layer number, and the sum is in effect taken over a few lower layers of the graph. This is the quantitative expression of the splitting and similarity effects that the Vapnik–Chervonenkis bound ignores: with $u = q = 0$ , that is, if neither is taken into account, the bound turns into it.

Summary

Without splitting and connectivity, overfitting sets in already at a few dozen algorithms.
Splitting and connectivity greatly reduce overfitting and can compensate for the effect of dimensionality.
In practice families as a rule have them.
A scheme for applying bounds on the probability of overfitting:
1. estimate $η = R_{ε} (μ, X^{L})$ over a few lower layers;
2. by inversion, estimate $ε$ through $η$ ;
3. use the estimate $ν (X^{ℓ}) + ε (η)$ as an external criterion or a regulariser for choosing the model structure.
The looseness of the bounds on $R_{ε}$ can lead to underestimating the complexity of models (oversimplifying them) in this scheme.
It is more practical to use cross-validation estimates.
Tight upper bounds on overfitting are derived in COLT (Computational Learning Theory).

The combinatorial theory explains why complex models in practice overfit much less than the Vapnik–Chervonenkis theory predicts. A huge number of algorithms in a family is not in itself dangerous: what is dangerous is many equally good algorithms unlike one another. Real families — threshold rules, conjunctions, linear classifiers — are split and connected, and their probability of overfitting is determined by a few lower layers of the splitting–connectivity graph. The bounds of this theory can be used for model selection in the same way as the Vapnik–Chervonenkis bound in structural risk minimisation, but they too remain upper bounds. So in practice cross-validation is the more reliable way to choose a model.

Machine Learning. Additional Lecture 1. The Theory of Overfitting

What this lecture is about

Reminder: the probability of overfitting

Experiments with overfitting

A monotone chain of algorithms

How overfitting depends on the error matrix

Overfitting of chains with different splitting

Overfitting when choosing between two algorithms

The combinatorial theory of overfitting

The splitting–connectivity graph

The generating and forbidden sets

The splitting–connectivity upper bound

Summary

Voron-ML-overfitting.pdf

lecture-01-p21.png

lecture-01-p23.png

lecture-01-p24.png

lecture-01-p27.png

lecture-01-p32.png

lecture-01-p33.png

lecture-01-p34.png

lecture-01-p36.png