The concept underlying the Support Vector Machine (SVM) is to find a "plane" that can separate samples belonging to different categories. Some of the most important concepts in SVM are margin, dual problem, and kernel trick (methods). The concept of margin is where the support vectors originate. The original SVM is defined with a hard margin, while a soft margin can enable SVMs to consider problems with imperfect data: data with noise and mislabeled points. The dual problem is an optimization technique to facilitate the search for solutions to SVM problems. Kernel methods generalize the basic SVM by introducing a kernel function so that a hyperplane can be used to separate different categories of data points without linear boundaries (planes). The kernel trick allows the SVM to consider nonlinear problems by converting the data to a higher dimensional space, in which the problem becomes linear.
This chapter will start a tour to SVM with an introduction to the basic SVM. The idea of SVM will be explained using mathematical functions and graphical illustrations. We will see how to derive the optimization formulation of a machine learning problem using SVM. To facilitate solution, the conversion of this original formulation of the optimization problem into a dual problem will be explained. Based on that, we will show how to generalize the basic SVM for linear problems via kernel functions to obtain nonlinear SVMs. After that, soft margin as a common technique for addressing overfitting issues in SVM applications will be introduced. Like the basic SVM (with soft margin), the introduction to SVM with hard margin will also include formulations of the original optimization problem and dual problem. In the final, extra skills about SVM, including the SMO algorithm and the use of SVM for multi-class classification and regression, will be briefly discussed.
6.2. Basics of SVM: Hard Margin SVM
6.2.1. Basic Formulation
Let us first take a look at typical data in a binary classification problem to see how SVM [55] can be constructed. In a space of samples, as shown in Fig.6.1, the plane separating different categories of data points can be described using the following linear function:
where vec(w)\vec{w} is the normal vector of the plane, which specifies the direction of the plane, bb is the intersect, which determines the distance between the plane and the origin.
In this space, the distance from any point vec(x)\vec{x} to the plane ( vec(w),b)(\vec{w}, b) is
The magnitudes of vec(w)\vec{w} and bb can be adjusted by multiplying them with the same constant so that the two margin lines (or called sides or boundaries) in Fig. 6.1 have the functions of
It is noted that, in SVM, "margin" usually refers to the distance between the separating hyperplane and any of the boundaries of the separation zone or the distance between the two boundaries. However, it is also seen that "margin" is used to refer to the separation zone. To avoid confusion, we reserve the term "margin" for the distance and use "margin area" for the separation zone. The two boundaries of the separation zone, which are also called positive and negative hyperplanes in some literature, are called margin lines or margin boundaries.
Figure 6.1: Conceptual illustration of SVM
These two margin boundaries are the two (dashed) lines that are parallel to the separating hyperplane and passing through the points closest to the hyperplane. The points on these boundaries are the support vectors. Therefore, the data points that are out of the margin area should satisfy the following relations:
where y=+1y=+1 assigns a label of +1 to this point.
The seperating hyperplane, which is a plane in this 2D case, is in the middle of the margin area. Accordingly, the margin, or the width of the margin area, is (2)/(||( vec(w))||)\frac{2}{\|\vec{w}\|}. The two regions on two sides of the margin area mark the two categories. In a binary classification task using the SVM, the two categories are generally labeled as +1 and -1 (for y_(i)y_{i} ). Based on the definitions of the margin and label, we can see that valid points, which are on two sides of the margin area (including points on the margin boundaries), must satisfy the following condition:
where o.\odot is the element-wide product and vec(1)\overrightarrow{1} is the array that has the same size as vec(y)\vec{y} and all the elements as 1 .
If data points belonging to two classes are distributed as shown in Fig. 6.1, then the two categories of points can be separated by an infinite number of planes. In the SVM, the plane associated with the best classification performance is believed to be the plane that can achieve the greatest (widest) margin. Accordingly, the mathematical description of the basic SVM for a binary classification task is
The above optimization problem is a convex quadratic programming problem and can be solved with some optimization packages. However, a more widely accepted way is to convert this problem into a dual problem by multiplying two sides of the equation with the Lagrange multipliers ( alpha_(i) >= 0\alpha_{i} \geqslant 0 ). This will bring two benefits: 1 ) making the optimization problem easier to solve, and 2) facilitating the introduction of kernel functions for tackling nonlinear problems.
The Lagrange function of the above problem can be written as
where vec(alpha)=[alpha_(1),alpha_(2),cdots,alpha_(I)]^(T)\vec{\alpha}=\left[\alpha_{1}, \alpha_{2}, \cdots, \alpha_{I}\right]^{T} are Lagrange multipliers. The optimal (minimal) value of the function locates where the partial derivatives of the equation with respect to vec(w)\vec{w} and b((del l)/(del( vec(w))):}b\left(\frac{\partial l}{\partial \vec{w}}\right. and (del l)/(del b)\frac{\partial l}{\partial b}, respectively) are zero, that is
where vec(1)\overrightarrow{1} is a column array, which has the same size as vec(alpha)\vec{\alpha} and all the elements equaling 1 .
Solving the above dual problem yields vec(alpha)\vec{\alpha}. The optimal vec(w)\vec{w} and bb correspond to the plane that separates the two categories the best in the SVM. According to the Karush-Kuhn-Tucker conditions (KKT), the original and dual problems will have the same optimal values. The following optimal solution to the dual problem can be obtained:
The calculation of b^(**)b^{*} requires the use of support vectors. Let us recall the following equation (for margin boundary) that the support vector needs to satisfy:
where vec(x)^(**)\vec{x}^{*} and y^(**)y^{*} are a support vector (vector/array for a point on the margin boundaries) and its label. The symbol "" is used for such a sample and its label because the point also corresponds to the optimal margin. Due to the same reason, vec(w)\vec{w} and bb also carry the "" sign.
The support vectors are associated with positive Lagrange multipliers. This is because any inequality constraint is defined as g_(i)(x^(**)) >= 0g_{i}\left(x^{*}\right) \geqslant 0. In optimization, we have the complementary slackness condition as part of the KKT conditions. This condition states that g_(i)(x^(**))*alpha_(i)=0g_{i}\left(x^{*}\right) \cdot \alpha_{i}=0. For points that are not support vectors, we have g_(i)(x^(**)) > 0g_{i}\left(x^{*}\right)>0, hence we must have alpha_(i)=0\alpha_{i}=0.
Multiplying two sides of Eq. 6.13 with y^(**)y^{*}, we get
where "sign" is the sign function, which outputs 1 if the input is greater than 0 , output 0 if the input is 0 , and output -1 if the input is lower than 0 .
6.3. Generalization of SVM: Kernel Methods
In reality, many problems are not linearly classifiable. This means that, in a sample space, the points in the two categories cannot be separated by a plane or a hyperplane. In order to classify such samples, we can map the samples from the original space, i.e., vec(x)\vec{x}, into a space with higher dimensions, i.e., phi( vec(x))\phi(\vec{x}). It is possible that a hyperplane can be sought for the data points in the high-dimensional space. The function of the hyperplane in the new space can be formulated as
The solution to the above problem involves the calculation of phi( vec(x)_(i))^(T)*phi( vec(x)_(j))\phi\left(\vec{x}_{i}\right)^{T} \cdot \phi\left(\vec{x}_{j}\right). This is the inner product of the mappings of vec(x)_(i)\vec{x}_{i} and vec(x)_(j)\vec{x}_{j}. Because the mapping leads to a space with a higher dimension, the calculation of the inner product is usually challenging. Therefore, we usually introduce the following kernel function [56]:
It is worthwhile to point out that SVM is relatively sensitive to the selection of kernels in addition to missing data. Like the applications of kernels in other types of machine learning, the selection of kernels in real problems still heavily relies on experience. There is a lack of theories for guiding and explaining the selection of suitable kernels to address specific problems with SVM.
