"Machine Learning is a highly interdisciplinary field which builds
upon ideas from cognitive science, computer science, statistics,
optimization among many other disciplines of science and mathematics. In machine learning, classification is a supervised learning
approach used to analyze a given data set and to build a model that
separates data into a desired and distinct number of classes [1].
There are many good classification techniques in the literature
including k-nearest-neighbor classifier [2,3], Bayesian networks
[4,5], artificial neural networks [6–10], decision trees [11,12] and
SVM [13–15]. K-nearest-neighbor methods have the advantage
that they are easy to implement, however, they are usually quite
slow if the input data set is very large. On the other hand, these
are very sensitive to the presence of irrelevant parameters [2,3].
Decision trees have also been widely used in classification problems. These are usually faster than neural networks in the training
phase, however, they do not have flexibility to modeling the
parameters [11,12]. Neuronal networks are one of the most used
techniques [16–20]. Neural networks have been widely used in a
large number of applications as a universal approach. However,
many factors must be taken into account to building a neural network to solve a given problem: the learning algorithm, the architecture, the number of neurons per layer, the number of layers,
the representation of the data and much more. In addition, these
are very sensitive to the presence of noise in the training data
[21,22].
From these techniques, SVM is one of the best known techniques to optimize the expected solution [13,15]. SVM was introduced by Vapnik as a kernel based machine learning model for
classification and regression task. The extraordinary generalization
capability of SVM, along with its optimal solution and its discriminative power, has attracted the attention of data mining, pattern
recognition and machine learning communities in the last years.
SVM has been used as a powerful tool for solving practical binary
classification problems. It has been shown that SVMs are superior
to other supervised learning methods [23–29]. Due to its good theoretical foundations and good generalization capacity, in recent
years, SVMs have become one of the most used classification
methods.
Decision functions are determined directly from the training
data by using SVM in such a way that the existing separation
(margin) between the decision borders is maximized in a highly
https://doi.org/10.1016/j.neucom.2019.10.118
0925-2312/ 2020 Elsevier B.V. All rights reserved.
⇑ Corresponding author.
E-mail addresses: <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> (J. Cervantes), <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>
(F. Garcia-Lamont).
Neurocomputing 408 (2020) 189–215
Contents lists available at ScienceDirect
Neurocomputing
journal homepage: www.elsevier.com/locate/neucom
dimensional space called the feature space. This classification
strategy minimizes the classification errors of the training data
and obtains a better generalization ability, i.e., classification skills
of SVMs and other techniques differ significantly, especially when
the number of input data is small. SVMs are a powerful technique
used in data classification and regression analysis. A notable
advantage of SVMs lies in the fact that they obtain a subset of support vectors during the learning phase, which is often only a small
part of the original data set. This set of support vectors represents a
given classification task and is formed by a small data set.
The rest of this paper is divided as follows: in Section 2 the theoretical basis of SVM are presented; in addition, their characteristics, advantages and disadvantages are described. In Section 3
weaknesses of SVM are introduced and reviewed. In Section 4 a
set of SVM implementations are presented. Section 5 shows some
applications of SVM in real world problems. Finally, Section 6
closes the paper with trends and challenges.
2. Theoretical basis of SVMs
The principal objective in pattern classification is to get a model
which maximizes the performance for the training data. Conventional training methods determine the models in such a way that
each input–output pair is correctly classified within the class to
which it belongs. However, if the classifier is too fit for the training
data, the model begins to memorize training data rather than
learning to generalize, degrading the generalization ability of the
classifier.
The main motivation of SVM is to separate several classes in the
training set with a surface that maximizes the margin between
them. In other words, SVM allows to maximizing the generalization ability of a model. This is the objective of the Structural Risk
Minimization principle (SRM) that allows the minimization of a
bound on the generalization error of a model, instead of minimizing the mean squared error on the set of training data, which is the
philosophy often used by the methods of empirical risk
minimization.
In this Section, we discuss Support Vector Machines, in which
training data are linearly separable in the input space and the case
where training data are not linearly separable.
2.1. Linearly separable case
Training a SVM requires a set of n examples. Each example consists of a pair, an input vector xi and the associated label yi. Assume
that a training set X is given as:
ðx1; y1Þ;ðx2; y2Þ; ... ;ðxn; ynÞ ð1Þ
i:e., X ¼ fxi; yign
i¼1 where xi 2 Rd and yi 2 þð Þ 1; 1 . For reasons of
visualization, we will consider the case of a two-dimensional input,
i.e., x 2 R2. The data are linearly separable and there are many
hyperplanes that can perform the separation. Fig. 1 shows several
decision hyperplanes that perfectly separate the input data set. It
is clear that there are infinite hyperplanes that could perform this
work. However, the generalization ability depends on the location
of the separation hyperplane and the hyperplane with maximum
margin. This hyperplane is called optimal separation hyperplane
[14]. The decision level, i.e., the hyperplane that separates the input
space is defined by the equation wT xi þ b ¼ 0.
The simplest case of SVM is the linearly separable case in the
feature space. We optimize the geometric margin by setting the
functional margin kappai ¼ 1(also called Canonical Hyperplane
[30]), therefore, the linear classifier yi ¼ 1,
w  xþ h i þ b ¼ 1
w  x h i þ b ¼ 1 ð2Þ
These can be combined into a set of inequalities:
yiðh iþ w  xi bÞ P 18i ð3Þ
The geometric margin of xþ y x is
ci ¼ 1
2
w
k k w  xþ
D E  w
k k w  x
  D E
¼ 1
2k k w w  xþ h i  w  x ½  h i
¼ 1
k k w
ð4Þ
where w defines the optimal separation hyperplane and b is the
bias. The distance between the hyperplane and the training data
closest to the hyperplane is called margin. The generalization ability
is maximized if the optimal separation hyperplane is selected as the
separation hyperplane. Optimizing the geometric margin means
minimizing the norm of the vector of weights. When solving the
problem of quadratic programming we try to find the optimal
hyperplane and two parallel hyperplanes (H1 and H2).
The distance between H1 and H2 is maximized and there is no
data between the two hyperplanes. When the distance between
H1and H2 is maximized, some data points can be over H1and some
data points can be over H2.These points of data are called support
vectors [14,30], since they participate directly in defining the separation hyperplane, the other points can be removed or changed
without crossing the planes H1 and H2 and will not modify in
any way the generalization skill of the classifier, i.e., the solution
of an SVM is given only by this small set of support vectors. Any
hyperplane can be represented by w; x and b, where w is a vector
perpendicular to the hyperplane. Fig. 2 shows the geometric representation of the quadratic programming problem showing H (optimal separator) and hyperplanes H1 and H2. In this way, the original
problem of optimization is as follows.
Proposition 1. For the linearly separable case
S ¼ x1; y1 ð Þ xl; yl ½  ð Þ , if ð Þ w; b is the solution
min
w;b
h i w  w ¼ k k w 2
subject to : yið Þ h i w  xi þ b P 1
ð5Þ
then the maximal margin is given by c ¼ 1
k k w .
We change this to the dual problem using the Lagrange formulation. There are two reasons to do this. The first lies in the fact that
the conditions given in the Eq. (5) will be replaced by Lagrange
Fig. 1. Separation hyperplanes.
190 J. Cervantes et al. / Neurocomputing 408 (2020) 189–215
multipliers, which are much easier to handle. The second is the
reformulation of the problem, the training data will only appear
in the form of dot product between vectors. This is a fundamental
property that will allow to generalize the procedure in the nonlinear case. In this way, the Lagrangian is given by:
Lðw; b; aÞ  1
2 h i w  w Xl
i¼1
ai½yi
ðh i w  xi þ b  1 ð6Þ
where ai are the Lagrange’s multipliers.
The dual is found in two steps: first, taking the derivative with
respect to w and b
@Lðw; b; aÞ
@w ¼ w Xl
i¼1
aiyixi ¼ 0 ! w ¼ Xl
i¼1
aiyixi ð7Þ
@Lðw; b; aÞ
@b ¼ Xl
i¼1
aiyi ¼ 0 ! Xl
i¼1
aiyi ¼ 0 ð8Þ
and second, substituting Eqs. (7) and (8) in the original Lagrangian
(6)
Lðw; b; aÞ ¼ 1
2 h i w  w Xl
i¼1
ai½yi
ðh i w  xi þ bÞ  1
¼ 1
2
Xl
i¼1
aiyixi
Xl
i¼1
aiyixi
* + Xl
i;j¼1
aiajyiyjð xj  xi
  þ bÞ Xl
i¼1
ai
¼ 1
2
Xl
i;j¼1
aiyiajyj xi  xj
  Xl
i;j¼1
aiyiajyj xj  xi
  Xl
i¼1
aiyib þXl
i¼1
ai
¼  1
2
Xl
i;j¼1
aiyiajyj xi  xj
  þXl
i¼1
ai
ð9Þ
The data points with ai > 0 are called ‘‘support vectors” and
these vectors define the hyperplanes H1; H2. At all other training
data ai ¼ 0. Support vectors are the critical elements of the training
data and these are the closest to the decision hyperplane.
Remark 1. SVMs obtain a hyperplane by training the initial data
set, which perfectly separates these data and is defined by a small
set of support vectors. If all other points (non-support vectors)
were eliminated (or moved around without crossing H1or H2) and
the training was repeated, the same hyperplane defined by the
same set of support vectors would be found. Therefore, the original
problem of optimization is as follows.
Proposition 2. To the linearly separable case
S ¼ ½ðx1; y1Þðxl; yl
Þ, if a
i is the solution to the quadratic optimization problem
max ai
 1
2
Xl
i;j¼1
aiyiajyj xi  xj
  þXl
i¼1
ai
s:t: :
Xl
i¼1
aiyi ¼ 0
ð10Þ
Then k k w 2 defines the minimum w ¼ Pl
i¼1a
i yixi and the geometric
margin c ¼ 1
w k k is maximized.
2.2. Karush-Kuhn-Tucker conditions
Karush-Kuhn-Tucker conditions (KKT) [31,32] play a very
important role in the theory of optimization, because they give
the conditions to obtain an optimal solution to a general optimization problem.
Theorem 1. Given an optimization problem with convex domain
X # Rn,
minimize fðwÞ; w 2 X
s:t: giðwÞ 6 0; i ¼ 1; ... ; k;
hiðwÞ ¼ 0; i ¼ 1; ... ; m;
ð11Þ
with f 2 C1 convex, the necessary and sufficient conditions for a
normal point w to be optimal are the existence of a; b such that
@Lðw;a;bÞ
@w ¼ 0
@Lðw;a;bÞ
@b ¼ 0
a
i gi
ðwÞ ¼ 0; i ¼ 1; ... ; k;
giðwÞ 6 0; i ¼ 1; ... ; k;
a
i P 0; i ¼ 1; ... ; k:
ð12Þ
From KKT conditions if the training set is linearly separable, it is
verified that
w k k2 ¼ w  w h i¼ðX
i2sv
a
i Þ
1
2 ð13Þ
Therefore, the maximum distance of a hyperplane is:
1
w k k ¼ X
i2sv
a
i
 !1
2"
Summarize the explanation of SVM in the paper above, try use your own words, do not directly copy from the paragraphs above.