Support Vector Machines

Support vector machines (SVM) are a system of machine learning (or classification) algorithm that constructs a classifier to assign a group label to each case on the basis of its attributes. The algorithm requires that there be two variables for each case in the data. The first is the group variable to be classified and predicted (such as disease status or treatment), and the second is the variable of attributes, which is usually multidimensional numerical data (such as amount of daily cigarette consumption or abundance of particular enzymes in the blood). Normally a classifier is learned from the method based on a set of training cases. The classifier is then applied to an independent test set to evaluate the classification accuracy.

SVM was first developed by Vladimir Vapnik in the 1990s. In the simplest situation, binary (e.g., “disease” vs. “normal”), separable, and linear classification is considered. The method seeks a hyperplane that separates the two groups of data with the maximum margin, where the margin is defined as the distance between the hyperplane and the closest example in the data. The idea came originally from the Vapnik Chervonenkis theory, which shows that the generalized classification error is minimized when the margin is maximized.

Why the name support vector machines? The answer is that the solution of the classification hyperplane for SVM depends only on the support vectors that are the closest cases to the hyperplane. All the remaining cases, farther away, do not contribute to the formulation of the classification hyperplane. The optimization problem is solved through quadratic programming techniques, and algorithms are available for fast implementation of SVM.

SVM is widely applied in virtually any classification application, including writing recognition, face recognition, disease detection, and other biological problems. Two important extensions in the development of SVM made it popular and feasible [Page 979]in practical applications: kernel methods and soft margin. Kernel methods are used to extend the concept of linear SVM to construct a nonlinear classifier. The idea is to map the current space to a higher-dimensional space, with the nonlinear classifier in the current space transformed to a linear one in the new, high-dimensional space. The distance structure (dot product) is simply replaced by a kernel function, and the optimization is performed similarly. Common choices of kernel functions include polynomial, radial basis, and sigmoid. Soft margin is used when the two groups of cases are not separable by any possible hyperplane. Penalties are given to “misclassified” cases in the target function, and the penalized “soft margin” is similarly optimized.