"3. Weaknesses of SVM
Despite the generalization capacity and many advantages of the
SVM, they have some very marked weaknesses, among which are:
the selection of parameters, algorithmic complexity that affects the
training time of the classifier in large data sets, development of
optimal classifiers for multi-class problems and the performance
of SVMs in unbalanced data sets.
3.1. Algorithmic complexity
Maybe the principal disadvantage of SVM is due to its excessive
computational cost in large data sets, because the training kernel
matrix grows in quadratic form with the size of the data set, which
provokes that training of SVM on large data sets is a very slow process. Support Vector Machines (SVM) have demonstrated highly
competitive performance in many real-world applications. However, despite its good theoretical foundations and generalization
performance, SVM is not suitable for large data set classification.
Training an SVM is usually posed as a quadratic programming
(QP) problem to find a separation hyperplane which implicates a
matrix of density n  n , where the n is the number of points in
the data set. This needs huge quantities of computational time
and memory for large data sets, so the training complexity of
SVM is highly dependent on the size of a data set [61,62].
According to the strategy used, the training methods for SVM
can be categorized into data selection, decomposition, geometric,
parallel implementations and heuristics. Their core ideas and the
most representative algorithms are presented in this section.
Data selection methods for SVM intent to decrease the size of
data sets by removing the instances that do not contribute to the
definition of the optimal separating hyperplane. The latter depends
completely on instances which are located closest to the separation
boundary [63], and correspond to those whose Lagrange multipliers are greater than zero in the Karush–Kuhn–Tucker conditions
J. Cervantes et al. / Neurocomputing 408 (2020) 189–215 195
(60). These instances are called support vectors (SVs). Generally,
the number of SVs is a small portion compared with the size of
training sets.
ai ¼ 0 ) yiðh i x; xi þ bÞ P 1; ni ¼ 0
0 < ai < C ) yiðh i x; xi þ bÞ ¼ 1; ni ¼ 0
alphai ¼ C ) yi
ðh i x; xi þ bÞ 6 1; ni P 0
ð60Þ
Simple random sampling (SRS) is probably the most basic strategy to reduce the size of training sets. It consists in choosing a
number of instances and then training a SVM with them. The
works presented in [64–66] show that uniform random sampling
is the optimal robust selection scheme in terms of several statistical criteria. However, although SRS is computationally cheap, the
standard deviation of classification accuracy is large in most cases
[66].
A more sophisticated form of this type of sampling consists in
assigning to each instance a probability to be chosen. Once a number of instances is randomly selected, a SVM is trained with them.
After this, the probabilities are updated, increasing those whose
instances have been miss-classified [67–69]. This process is
repeated several times.
Some data selection methods have been developed by computing the distance between the instances and the optimal hyperplane. Several metrics for measuring distance have been used in
previous works: These measures include the Euclidean [70], Mahalanobis [71] and Hausdorff [72,73] distances. Most of the current
distance-based methods are inspired on two observations: (1)
the instances closest to those ones with opposite label have high
chances to be SVs [72] and (2) instances far from hyperplane do
not contribute to the definition of the decision boundary [74]. A
problem with naive implementations that require to compute all
distances between objects is that this task has a temporal and a
spatial complexity of Oðn2Þ.
The Condensed Nearest Neighbor (CNN) [75] chooses instances
near to class frontiers, reducing the size of training sets. However,
CNN is not noise tolerant. Reduced Nearest Neighbor (RNN) [76],
Selective Nearest Neighbor (SNN) [77] and Minimal Consistent
Set (MCS) are methods based on CNN, and therefore, they have also
problems with noisy data sets. RNN, SNN and MCS are more costly
than CNN.
Neighborhood properties of SVs have also been exploited to
reduce size of training sets. Wang and Kwong [78] used neighborhood entropy, while in [79] only the patterns in the overlap region
around the decision boundary are selected. The method presented
in [80] follows this trend but use fuzzy C-mean clustering to select
samples on the boundaries of class distribution, whereas [72] uses
hyper spheres. Clustering has been proved to be an effective
method to collaborate with SVM on classifying large data sets.
For example, hierarchical clustering [81,82], k-means [83] and parallel clustering [84]. Clustering-based methods can reduce the
computations burden of SVM, however, the clustering algorithms
themselves are still complicated for large data set. Rocchio bundling is a statistics-based data reduction method [85]. The Bayesian
committee machine is also reported to be used to train SVM on
large data sets, where the large data set is divided into m subsets
of the same size, and m models are derived from the individual sets
[86]. But, it has higher error rate than normal SVM and the sparse
property does not hold.
The basis for decomposition methods lies in the fact that the
training time can be reduced if only the active constraints of the
QP problem are taken into account [87]. A similar idea to active
set methods for optimization is applied in decomposition methods.
In the active set approach, two sets are used: the working set and
the set of fixed variables. The optimization is made only on the
working set. For the case of SVM, the working set is usually composed of instances that violate the Karush–Kuhn–Tucker conditions. Apart of the proved convergence [88], a clear advantage of
decomposition is that memory requirement is linear in the number
of training examples; but on the other hand, because only a fraction of variables is being considered in each iteration, it is time
consuming [89,90] if elements in the active set are not carefully
selected. One of the first decomposition methods was Chunking
[74]. It consists in repetitively obtaining the maximum margin
hyperplane from an amount of instances (called the chunk) and
then forming a new chunk with the SVs from the previous solution
and some new instances. Probably the most famous decomposing
algorithm is the SMO [15]. Sequential minimal optimization
(SMO) is a fast method to train SVM [91,84]. Training SVM requires
the solution of the QP optimization problem. SMO breaks this large
QP problem into a series of smallest possible QP problems. It considers the smallest size working set: only two training samples,
and it is faster than the projected conjugate gradient (PCG) chunking algorithm. Dong et al. [61] introduced a parallel optimization
step where block diagonal matrices are used to approximate the
original kernel matrix so that SVM classification can be split into
hundreds of sub-problems. A recursive and computational superior
mechanism referred as adaptive recursive partitioning was proposed in [92], where the data are recursively subdivided into smaller subsets. Genetic programming is able to deal with large data
sets that do not fit in main memory [93]. Neural networks technique can also be applied for SVM to simplify the training process
[94]. LibSVM [95] is an algorithm based on SMO with the improvement of a more advanced mechanism of selection of the working
set by using the second order information method previously
shown in [96]. The SVMlight [97] is another important state-ofthe-art decomposition method.
Variants of SVM speed up the training time of SVM at expense
of loosing accuracy [89]. These methods work by changing the
original QP problem formulation. Most of the variants methods
conclude with a system of linear equations solved efficiently if
the number of features is moderate, i.e., around 100. A representative method in this category is the least square SVM (LS-SVM) [98]
which changes the original QP problem by using a linear system of
equations that can be solved explicitly or by using a conjugate gradient method. Other important methods are the PSVM (Proximal
SVM) [99] and reduced SVM (RSVM) [100].
Parallel implementation of the QP problem is difficult because
there is a strong dependence between data [101]. Most parallel
methods for training SVM divide the training set into independent
subsets to train SVM in different processors, as in [101–103]. In
[61], the kernel matrix of SVM is approximated by block diagonal
matrices so that the original optimization problem can be decomposed into hundreds of sub problems, which are easy to solve in a
parallel fashion. Other parallel implementations can be found in
[104–108].
Geometric methods for SVM are based on that computing the
optimal separating hyperplane is equivalent to find the closest pair
of points belonging to convex hulls [63,109,110]. Recent advances
on geometric methods can be found in [111–115].
Among all heuristic methods, the alpha seeding [116] consists
of providing initial estimates of the ai values for the starting of
the QP problem. Alpha seeding seems to be a practical method to
improve training time of SVM. Recently, an improvement of this
method has been proposed in [117].
According to the reviewed literature, there are currently just
few methods that combine decision tree (DT) for instance selection
in a similar way to the presented in this research. In [118], the patterns by ordered projections (POP) algorithm was presented. It
uses projections of instances on the axis of attributes to find the
minimal number of elements to represent hyper-rectangles which
196 J. Cervantes et al. / Neurocomputing 408 (2020) 189–215
contain instances of the same class (entropy zero). A disadvantage
of POP is that the reduction of the size of data sets is very low
[119].
In [120], a method that approximates the decision boundary of
SVM using a DT to speed up SVM in its testing phase was proposed.
In [120], an SVM is used in some leaves of a DT. The idea is to
reduce the number of test data points that require SVM’s decision.
Recently, in [121,26], the combination of a DT and SVM was
proposed. The underlying idea is to train an SVM first, and then
use the predictions of the model obtained to modify the class of
examples in the training set. A DT is afterward trained using the
modified set. The SVM is used as a pre-processor for improving
the performance of DT, when dealing with the problem of
imbalance.
3.2. Development of optimal classifiers for multi-class problems
Support Vector Machines were originally designed to solve binary classification problems [122]. The problem of multiclassification for SVM, does not present an easy solution. In order
to apply SVM to multi-classification problems, it is necessary to
change the problem to multiple binary classification problem.
There are two basic types of algorithms to solve the multiclass
classification based in SVM.
1. ‘‘one versus one” method (OVO). This method constructs kðk1Þ
2
hyperplanes for k-class problem, where each one is trained with
just two-class data sets. Thus given n training data
ðx1; y1Þ; ... ;ðxn; ynÞ, where xi 2 Rd
; i ¼ 1; ... ; n and
yi 2 f g 1; ... ; k is the class of xi, the i
th SVM solves the problem:
min
wij;bij;nij
1
2 ðwijÞ
T
wij þ C
Xl
j¼1
nij
t
ðwijÞ
T
/ðxtÞ þ bij P 1  nij
t ; ifo
yt ¼ i
ðwi
Þ
T
/ðxjÞ þ bi
6 1 þ nij
t ; ifo
yt ¼ j
nij
t P 0; j ¼ 1; ... ; n
ð61Þ
At the prediction phase, a voting scheme is applied to get the class
of x. The KðK1Þ=2 classifiers are applied to an unseen sample x. If the
k
th classifier says that x belongs to the i class, then one vote for the i
class is added by one and the label of x is predicted in the class that
got the highest number of votes. The principal disadvantage of OVO
is that some times the ambiguities in some regions of its input
space can provoke that two regions receive the same number of
votes.
2. ‘‘one versus all” method (OVA). This algorithm constructs k
hyperplanes for k-class problem. The i-th hyperplane is trained
with the samples between the i-th class and the rest data. Thus
given n training data ðx1; y1Þ; ... ;ðxn; ynÞ, where
xi 2 Rd
; i ¼ 1; ... ; n and yi 2 f g 1; ... ; k is the class of xi, the i
th
SVM solves the problem:
min
wp;bp;np
1
2 ðwpÞ
T
wp þ C
Xl
j¼1
np
i
ðwpÞ
T
/ðxiÞ þ bp P 1  np
i ; ifo
yi ¼ p
ðwpÞ
T
/ðxiÞ þ bp 6 1 þ np
i ; ifo
yi – p
np
i P 0; i ¼ 1; ... ; n
ð62Þ
where xi are mapped to high dimensional space by means of /,
where /is a Kernel that satisfies the Mercer’s condition [14], and C
is a penalty parameter. The k decision functions are given by
ðw1Þ
T
/ðxÞ þ b1
ðw2Þ
T
/ðxÞ þ b2
.
.
.
ðwkÞ
T
/ðxÞ þ bk
ð63Þ
Given a sample x to classify, the label of the class that has the largest value of the decision function is chosen as:
class of x ¼ arg max i¼1;2;...;k
ððwpÞ
T
/ðxÞ þ bp
Þ ð64Þ
where wi and bi depict the hyperplane of the ith SVM.
Currently, most of methods use one-against-all or one-againstrest approaches to facing multi-class problems with SVM. However, there are numerous researchers who have faced the problem
and have developed algorithms to try to solve the problem [123–
131].
3.3. Performance of SVMs in imbalanced datasets
In imbalanced data sets, the correct classification of minority
class objects is a challenging problem. Normal classification methods, such as support vector machines, do not work well for these
skewed data sets because is difficult to get the optimal separation
hyperplane for an SVM trained with imbalanced data.
The imbalance in data sets affects considerably the performance
of most classifiers. In general, the model extracted from this type of
data sets is biased towards the minority class. As a result, the accuracy on the minority classes is hampered. The imbalance in data
sets is a recurrent problem in many domains, some examples
are: fraud detection problems [132], classification of protein
sequences [133–135], medical diagnosis of rare and dangerous diseases [136], intrusion detection and text classification [137,138],
discrimination between earthquakes and nuclear explosions
[139]. Support Vector Machines were introduced by Vapnik [13]
as a kernel based machine learning model for classification and
regression tasks. The generalization capabilities and discriminative
power of SVM have attracted the attention of practitioners and
theorists in last years. SVM has strong theoretical foundations,
and, in general, it presents high classification accuracy in realworld applications. However, recent experiments [140–142] show
that the performance of SVM is severely affected when it is applied
on imbalanced data sets. This is more evident when the ratio
between the majority and the minority class is large. The first disadvantage of SVM on imbalanced data sets is due to the margin
obtained is biased towards the minority class.
There are several solutions of SVM classification for imbalanced
data [143]. The techniques used to minimize the negative effect of
imbalanced data sets on classifiers can be categorized as external
and internal. The first techniques balance the data sets before
training a classifier [144,145,142]. The second techniques modify
the model or architecture of classification methods [146–148].
Principal external techniques are under sampling and over sampling. In general, under sampling consists in selecting, randomly,
a small number of objects from majority class [146]. Over sampling
techniques generate artificial examples of the minority class. Other
methods use evolutionary algorithms to balance the data sets
[143,149,150]. However, to add artificial data points to the minority class is a promising technique to tackle the problem of imbalance. Chawla et al. [140] proposed Synthetic Minority Over
sampling Technique (SMOTE), which generates artificial objects
to be included as members of the minority class. The minority class
is over-sampled by taking each minority class sample and introducing synthetic examples along the line segments joining any or
all of the k minority class nearest neighbors. It does not cause
J. Cervantes et al. / Neurocomputing 408 (2020) 189–215 197
any information loss and could potentially find hidden minority
regions. The disadvantage of this method is that it creates noise
for the classifiers which could result in a loss of performance
because SMOTE makes the assumption that the instance between
a positive class instance and its nearest neighbors is also positive
[151].
Classification for imbalanced data sets has been studied by
machine learning community since the last decade [142]. There
are many methods that are applied to imbalanced data sets in
order to improve the performance of classifiers [135]. Generally,
these methods are divided into two categories: external methods
and internal methods. External methods involve a pre processing
of training data sets in order to make them balanced. Internal
methods deal with modifications of the learning algorithms in
order to reduce their sensitiveness to class imbalance. In other
words, external methods attempt to balance the data sets by considering the number of examples for each class, whereas internal
methods consider the costs associated with misclassification and
include these costs in the model. The most popular external methods are under-sampling, over-sampling and SMOTE. The under
sampling and over sampling method [146] balances the data sets
by randomly selecting small number of objects from majority class,
and doubling the objects in the minority class. The main drawback
is that some important points, such as support vectors, may be
neglected by the random algorithm. [141] pointed out that the
under sampling strategy is not a good choice for SVM, and that
the over sampling cannot improve the final accuracy. The synthetic
minority over sampling technique [140] generates artificial data in
the minority class by multiplying a random number in each original object. [152] showed that SMOTE is better than under sampling
and over sampling. Several proposals inspired in SMOTE have been
proposed, see, for example, [153–155]. In [146] an SVM with different costs and SMOTE is used. That method introduces a scheme to
penalize classification errors. The majority class is assigned a high
cost and the minority class is assigned a low cost. This combination
makes denser the distribution of the minority class, and pushes the
separating hyperplane to the minority class. In [135], a penalization criterion is used to produce a similar effect on the separating
hyper plane. In [142], a kernelized version of SMOTE is proposed.
Other kernel-modification methods have been proposed in
[142,156,157]. Other proposals can be found in [158,159].
Although sampling methods and cost-sensitive learning methods seem to dominate the current research efforts in imbalanced
learning, Genetic Algorithm (GA)-based approaches have also been
pursued by the community. These algorithms use GAs in order to
balanced data sets. [149] used a GA for under-sampling the majority class, the algorithm tackles the difficulties of SVM learning on
large data sets, because the method significantly reduce the size
of the training set without loss of performance. Batuwita and
Palade [160] applied Fuzzy SVM (FSVM) to improve the performance on imbalanced data sets to handle the problem of outliers
and noise by assigning different fuzzy-membership values based
on their importance. In [161], the authors proposed a efficient
resampling method selecting the most informative data examples
located closer to the class boundary region by using the separating
hyperplane found by training an SVM model on the original imbalanced data set, and then use only those examples in resampling. An
excellent survey about classification on imbalanced data sets can
be found in [162]. In [143], a GA is used to balance skewed data
sets. That method produces better results than simple random
sampling. Bazi and Melgani [163] used PSO algorithm in order to
improve the performance of SVM. That method was applied for
the classification of electrocardiogram signals and parameters estimation. In [159], the authors propose a classification system in
order to detect the most important rules, and the rules which perturb the performance of classifier. That system uses hierarchical
fuzzy rules and a GA. Garcia et al. [150] implemented an algorithm
which performs an optimized selection of examples from data sets.
The learning algorithm is based on the nested generalized exemplar method and GA to generate and select the best suitable data
to enhance the classification performance over imbalanced
domains. GA is used to guide the search process. Although generating new instances in the minority class can improve the performance in SVM classification [144], this process could introduce
noise to the data set, and to select randomly instances that helps
to improve the performance in this area is almost impossible without using a genetic algorithm because the search space is huge"
Summarize the disadvantages of SVM in the paper above, try use your own words, do not directly copy from the paragraphs above.