Support vector machine

A support vector machine (SVM) is a supervised learning technique first discussed by Vladimir Vapnik. An SVM is a maximum-margin hyperplane that lies in some space. Given training examples labeled either "yes" or "no", a maximum-margin hyperplane splits the "yes" and "no" training examples, such that the distance from the closest examples (the margin) to the hyperplane is maximized.

The use of the maximum-margin hyperplane is motivated by statistical learning theory, which provides a probabilistic test error bound which is minimized when the margin is maximized.

If there exists no hyperplane that can split the "yes" and "no" examples, an SVM will choose a hyperplane that splits the examples as cleanly as possible, while still maximizing the distance to the nearest cleanly split examples.

The parameters of the maximum-margin hyperplane are derived by solving a quadratic programming (QP) optimization problem. There exists several specialized algorithms for quickly solving the QP problem that arises from SVMs.

The original SVM was a linear classifier. However, Vapnik suggested using the kernel trick (originally proposed by Aizerman). In the kernel trick, every time a linear algorithm uses a dot product, replace it with a non-linear kernel function. This causes the linear algorithm to operate in a different space. For SVMs, using the kernel trick makes the maximum margin hyperplane be fit in a feature space. The feature space is a non-linear map from the original input space, usually of much higher dimensionality than the original input space. In this way, non-linear SVMs can be created. If the kernel used is a radial basis function, the corresponding feature space is a Hilbert space of infinite dimension. SVMs are well regularized, so the infinite dimension does not spoil the results.

References

• N. Cristianini and J. Shawe-Taylor. AN INTRODUCTION TO SUPPORT VECTOR MACHINES (and other kernel-based learning methods). Cambridge University Press, 2000. ISBN 0-521-78019-5

External links

• http://www.kernel-machines.org/
• K.-R. Müller, S. Mika, G. Rätsch, K. Tsuda, and B. Schölkopf. An introduction to kernel-based learning algorithms. IEEE Neural Networks, 12(2):181-201, May 2001.
• Text Categorization with Support Vector Machines: Learning with Many Relevant Features
• The LIBSVM software package by Chih-Chung Chang and Chih-Jen Lin
• The Formulation of Support Vector Machines