Cover's theorem

Cover's theorem is a statement in computational learning theory and is one of the primary theoretical motivations for the use of non-linear kernel methods in machine learning applications. It is so termed after the information theorist Thomas M. Cover who stated it in 1965, referring to it as counting function theorem.

Theorem

Let the number of homogeneously linearly separable sets of ${\displaystyle N}$ points in ${\displaystyle d}$ dimensions be defined as a counting function ${\displaystyle C(N,d)}$ of the number of points ${\displaystyle N}$ and the dimensionality ${\displaystyle d}$. The theorem states that ${\displaystyle C(N,d)=2\sum _{k=0}^{d-1}{\binom {N-1}{k}}}$.

It requires, as a necessary and sufficient condition, that the points are in general position. Simply put, this means that the points should be as linearly independent (non-aligned) as possible. This condition is satisfied "with probability 1" or almost surely for random point sets, while it may easily be violated for real data, since these are often structured along smaller-dimensionality manifolds within the data space.

The function ${\displaystyle C(N,d)}$ follows two different regimes depending on the relationship between ${\displaystyle N}$ and ${\displaystyle d}$.

• For ${\displaystyle N\leq d+1}$, the function is exponential in ${\displaystyle N}$. This essentially means that any set of labelled points in general position and in number no larger than the dimensionality + 1 is linearly separable; in jargon, it is said that a linear classifier shatters any point set with ${\displaystyle N\leq d+1}$. This limiting quantity is also known as the Vapnik-Chervonenkis dimension of the linear classifier.

• For ${\displaystyle N>d+1}$, the counting function starts growing less than exponentially. This means that, given a sample of fixed size ${\displaystyle N}$, for larger dimensionality ${\displaystyle d}$ it is more probable that a random set of labelled points is linearly separable. Conversely, with fixed dimensionality, for larger sample sizes the number of linearly separable sets of random points will be smaller, or in other words the probability to find a linearly separable sample will decrease with ${\displaystyle N}$.

A consequence of the theorem is that given a set of training data that is not linearly separable, one can with high probability transform it into a training set that is linearly separable by projecting it into a higher-dimensional space via some non-linear transformation, or:

A complex pattern-classification problem, cast in a high-dimensional space nonlinearly, is more likely to be linearly separable than in a low-dimensional space, provided that the space is not densely populated.

Proof

By induction with the recursive relation$${\displaystyle C(N+1,d)=C(N,d)+C(N,d-1).}$$To show that, with fixed ${\displaystyle N}$, increasing ${\displaystyle d}$ may turn a set of points from non-separable to separable, a deterministic mapping may be used: suppose there are ${\displaystyle N}$ points. Lift them onto the vertices of the simplex in the ${\displaystyle N-1}$ dimensional real space. Since every partition of the samples into two sets is separable by a linear separator, the property follows.

The left image shows 100 points in the two dimensional real space, labelled according to whether they are inside or outside the circular area. These labelled points are not linearly separable, but lifting them to the three dimensional space with the kernel trick, the points becomes linearly separable. Note that in this case and in many other cases it will not be necessary to lift the points to the 99 dimensional space as assumed in the explanation.

Other theorems

The 1965 paper contains multiple theorems.

Theorem 6: Let ${\textstyle X\cup \{y\}=\left\{x_{1},x_{2},\cdots ,x_{N},y\right\}}$ be in ${\textstyle \phi }$-general position in ${\textstyle d}$-space, where ${\textstyle \phi =\left(\phi _{1},\phi _{2},\cdots ,\phi _{d}\right)}$. Then ${\textstyle y}$ is ambiguous with respect to ${\textstyle C(N,d-1)}$ dichotomies of ${\textstyle X}$ relative to the class of all ${\textstyle \phi }$-surfaces.

Corollary: If each of the ${\textstyle \phi }$-separable dichotomies of ${\textstyle X}$ has equal probability, then the probability ${\textstyle A(N,d)}$ that ${\textstyle y}$ is ambiguous with respect to a random ${\textstyle \phi }$-separable dichotomy of ${\textstyle X}$ is ${\displaystyle {\frac {C(N,d-1)}{C(N,d)}}}$.

If ${\displaystyle N/d\to \beta }$, then at the limit of ${\displaystyle N\to \infty }$, this probability converges to ${\displaystyle \lim _{N}A(N,d)={\begin{cases}1,&0\leq \beta \leq 2\\{\frac {1}{\beta -1}},&\beta \geq 2\end{cases}}}$.

This can be interpreted as a bound on the memory capacity of a single perceptron unit. The ${\displaystyle d}$ is the number of input weights into the perceptron. The formula states that at the limit of large ${\displaystyle d}$, the perceptron would almost certainly be able to memorize up to ${\displaystyle 2d}$ binary labels, but almost certainly fail to memorize any more than that. ( MacKay 2003 , p. 490)

See also

• Support vector machine
• Kernel method

References

• Haykin, Simon (2009). Neural Networks and Learning Machines (Third ed.). Upper Saddle River, New Jersey: Pearson Education Inc. pp. 232–236. ISBN   978-0-13-147139-9.
• Cover, T.M. (1965). "Geometrical and Statistical properties of systems of linear inequalities with applications in pattern recognition" (PDF). IEEE Transactions on Electronic Computers. EC-14 (3): 326–334. doi:10.1109/pgec.1965.264137. S2CID   18251470. Archived from the original (PDF) on 2019-12-20.
• Mehrotra, K.; Mohan, C. K.; Ranka, S. (1997). Elements of artificial neural networks (2nd ed.). MIT Press. ISBN   0-262-13328-8. (Section 3.5)
• MacKay, David J. C. (2003). "40. Capacity of a Single Neuron". Information theory, inference, and learning algorithms. Cambridge: Cambridge University Press. ISBN   978-0-521-64298-9.