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. The theorem states 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.

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.

— Cover, T.M. , Geometrical and Statistical properties of systems of linear inequalities with applications in pattern recognition., 1965

References

• Haykin, Simon (2009). Neural Networks and Learning Machines Third Edition. 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". IEEE Transactions on Electronic Computers EC-14: 326–334. 

• Mehrotra, K., Mohan, C.K., Ranka, S. (1997) Elements of artificial neural networks, 2nd edition. MIT Press. (Section 3.5) ISBN 0262133288 Google books

This statistics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Machine learning Statistical classification Neural networks Statistics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем сделать НИР Coventya Cover-over subsidies Look at other dictionaries: Cover (algebra) — In abstract algebra, a cover is one instance of some mathematical structure mapping onto another instance, such as a group (trivially) covering a subgroup. This should not be confused with the concept of a cover in topology. When some object X is …   Wikipedia König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into …   Wikipedia Heine–Borel theorem — In the topology of metric spaces the Heine–Borel theorem, named after Eduard Heine and Émile Borel, states:For a subset S of Euclidean space R n , the following two statements are equivalent: * S is closed and bounded *every open cover of S has a …   Wikipedia Infinite monkey theorem in popular culture — The infinite monkey theorem and its associated imagery is considered a popular and proverbial illustration of the mathematics of probability, widely known to the general public because of its transmission through popular culture rather than… …   Wikipedia Cartan–Hadamard theorem — The Cartan–Hadamard theorem is a statement in Riemannian geometry concerning the structure of complete Riemannian manifolds of non positive sectional curvature. The theorem states that the universal cover of such a manifold is diffeomorphic to a… …   Wikipedia Circle packing theorem — Example of the circle packing theorem on K5, the complete graph on five vertices, minus one edge. The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane …   Wikipedia Dilworth's theorem — In mathematics, in the areas of order theory and combinatorics, Dilworth s theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician …   Wikipedia Arzelà–Ascoli theorem — In mathematics, the Arzelà–Ascoli theorem of functional analysis gives necessary and sufficient conditions to decide whether every subsequence of a given sequence of real valued continuous functions defined on a closed and bounded interval has a… …   Wikipedia Noisy-channel coding theorem — In information theory, the noisy channel coding theorem (sometimes Shannon s theorem), establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data (digital information)… …   Wikipedia Path cover — Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).[1] A path cover …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”