Closed-Form Gaussian Spread Estimation for Small and Large Support Vector Classification

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 1 Closed-Form Gaussian Spread Estimation for Small and Large Support Vector Classification Diego Isla-Cernadas, Manuel Fernández-Delgado , Eva Cernadas , Manisha S. Sirsat , Haitham Maarouf , and Senén Barro Abstract— The support vector machine (SVM) with Gaussian kernel often achieves state-of-the-art performance in classification problems, but requires the tuning of the kernel spread. Most optimization methods for spread tuning require training, being slow and not suited for large-scale datasets. We formulate an analytic expression to calculate, directly from data without iterative search, the spread minimizing the difference between Gaussian and ideal kernel matrices. The proposed direct gamma tuning (DGT) equals the performance of and is one to two orders of magnitude faster than the state-of-the art approaches on 30 small datasets. Combined with random sampling of training patterns, it also runs on large classification problems. Our method is very efficient in experiments with 20 large datasets up to 31 million of patterns, it is faster and performs significantly better than linear SVM, and it is also faster than iterative minimization. Code is available upon paper acceptance from this link: http://persoal.citius.usc.es/ manuel.fernandez.delgado/papers/dgt/index.html and from CodeOcean: https://codeocean.com/capsule/4271163/tree/v1. Index Terms— Classification, efficient computing, large-scale datasets, model selection, radial basis kernel, support vector machine (SVM). I. INTRODUCTION THE support vector machine (SVM) is a popular classifier that can use several kinds of kernels, being the radial basis function (RBF) very used because of its good behavior in terms of performance [1]. A major configuration issue for the SVM is the tuning of its hyperparameters: regularization or penalty (λ) and spread (σ) of the RBF kernel, which has a specially strong influence on performance. Its tuning has been largely studied in the literature and it will be the focus of this article. Often, σis selected by searching the value that maximizes the SVM performance from a collection of values (grid-search (GS) approach), thus requiring to train and test the SVM for each σvalue. This also happens with random search [2], although the number of values tested is Manuscript received 14 February 2023; revised 3 October 2023 and 12 December 2023; accepted 12 March 2024. This work was supported in part by the Consellería de Educación, Universidade e Formación Profesional under Grant ED431G-2019/04 and in part by the European Regional Development Fund (ERDF), through the Centro Singular de Investigación en Tecnoloxías Intelixentes da Universidade de Santiago de Compostela (CiTIUS) as a Research Center of the Galician University System. (Corresponding author: Manuel Fernández-Delgado.) Diego Isla-Cernadas, Manuel Fernández-Delgado, Eva Cernadas, Haitham Maarouf, and Senén Barro are with the Centro Singular de Investigación en Tecnoloxías Intelixentes da USC (CiTIUS), University of Santiago de Compostela, 15782 Santiago de Compostela, Spain (e-mail: [email protected]). Manisha S. Sirsat is with the Department of Data Management and Risk Analysis, InnovPlantProtect, 7350-478 Elvás, Portugal. Digital Object Identifier 10.1109/TNNLS.2024.3377370 reduced with possible performance loss. Alternative model selection criteria for the SVM were compared in [3] on physiological data, including distance between two classes and expected square distance ratio. Other in-sample statistical approaches were also proposed for model selection and error estimation [4]. Among optimization methods, genetic algorithms (GAs) were used in [5] updating the strategy parameters and the values of λand σwith the covariance data matrix to maximize the average test accuracy of several SVMs. The method was applied only on small datasets up to 768 patterns and 13 features because SVM training and covariance matrix calculation were slow. Both the hyperparameters were also selected using particle swarm optimization (PSO) in the modeling of Iju deposit mineralization and alteration zones [6], and using dynamic PSO [7] on 14 datasets up to 7000 training patterns, outperforming GS, standard, and chained PSO. Penalty and spread were also selected using differential evolution [8] to maximize the accuracy on four datasets up to 11 692 patterns. Multiobjective adaptive differential evolution [9] was proposed to minimize the number of support vectors and maximize the generalization capacity in SVM model selection with RBF, polynomial, and Hermite kernels, being validated on 11 datasets up to 4435 patterns. The Bat algorithm [10], inspired in swarm intelligence, outperformed GA and PSO on nine small datasets up to 958 patterns, minimizing the classification error and avoiding the fall into local minima. Tharwat and Gabel [11] combined the social ski driver algorithm and synthetic minority oversampling technique (SMOTE) to select λand σmaximizing sensitivity. The method outperformed GS and PSO over eight small unbalanced datasets up to 336 patterns and 11 features. Glasmachers and Igel [12] developed a model selection method for 1-norm soft-margin SVM using gradient ascent on a likelihood function of λand σbased on logistic regression, being validated on 28 datasets up to 5000 patterns. The spread was also selected [13] by maximizing the margin in the feature space, while regularization is calculated analytically using the jackknife estimate of perturbations in the eigenvalues of the kernel matrix. The experiments included 24 datasets up to 7400 patterns. Model selection for multiclass SVM was studied [14] using spherical and elliptical RBF kernels and two criteria that redefine the SVM radius-margin bound in terms of class separability. The method was validated on 13 datasets up to 6435 patterns, where it spent 232 s using spatial GRBF kernel (dag) and criterion II. © 2024 The Authors. This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 2 IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS Several approaches calculate the spread directly from data. Xu et al. [15] formulated a direct formula to set σusing local and global distances, thus requiring to sort the distances between training patterns randomly selected. The method was validated on 13 datasets up to 7400 patterns. Varewick and Martens [16] calculated σusing a simple analytical formula of the input dimensionality and the class dispersion, without any SVM train or test, evaluating its method on 17 datasets up to 8124 patterns. Several alternative ways to calculate σbased on local features, such as soft k-nearest- neighbor, nearest enemy, and redundant fast clustering estimations [17], were compared with tenfold GS on six datasets up to 7400 patterns. Liu and Xu [18] selected σmaximizing (resp. minimizing) simultaneously between-class (resp. within-class) separability, measured by the cosine similarity in the kernel space. The method used eight small datasets up to 400 patterns. Afterward, Liu et al. [19] proposed an analytical formula valid when the within-class mean distance is below the between-class mean distance, using 17 classification datasets up to 141 691 patterns spending 43.4 s. The random RBF kernel SVM [20] used a modified RBF kernel with random-generated parameters that maximized the SVM accuracy on 18 datasets up to 32 561 patterns. Menezes et al. [21] selected σby maximizing a dissimilarity function between two classes based on an RBF-based kernel density estimation (KDE). This method was efficient and outperformed GS on a collection of 18 small datasets up to 3210 patterns. In a previous work [22], we proposed the ideal kernel tuning (IKT), where σminimizes the difference between RBF and ideal kernel matrices. On 37 datasets up to 1 million of patterns, IKT achieved lower time (up to 384 s) and memory requirements, with performance similar to GS, KDE, GA, Bayesian search, and PSO. Starting from this idea, this article derives an efficient closed-form expression for the inverse γof spread that minimizes the previous difference, extending it to datasets much larger than the ones in previous approaches. Sections II and III describe the proposed methods and experimental results, respectively, while Section IV reports the conclusions of the current study. II. MATERIALS AND METHODS The ideal kernel Jfor a classification problem [22] is a function defined as J(x,y)=1 when xand yshare the class label, and J(x,y)=0 otherwise. Let {xn}N n=1be the set of training patterns, cnbe the class label of xn, with cn∈ {1,...,C}, and Cbe the number of classes. The ideal kernel matrix J, that is squared of order N, has elements {Jnm}N nm=1defined as Jnm =J(xn,xm)=1 when cn=cm and Jnm =J(xn,xm)=0 otherwise. To achieve a good performance in classification problems, a kernel should be so similar as possible to the ideal kernel. Specifically, an RBF kernel K(x,y, σ) =exp−|x−y|2 2σ2(1) is expected to provide the best performance when σminimizes the difference between the RBF and ideal kernels, which can be evaluated as the mean square difference D(σ) between their respective matrices D(σ) =1 M N−1 X n=1 N X m=n+1 [Knm(σ ) −Jnm]2.(2) Here, Knm(σ ) =K(xn,xm, σ ) and the sum is over m>n because Knn =1 and Knm =Kmn, being M=N(N−1)/2 the number of terms in the sum. Our strategy in previous works [22],[23] was to calculate D(σ) for several σvalues and to select σminimizing D(σ). In the following, we develop a method to estimate σdirectly from the training set {xn,cn}N n=1. We define γ=1 2σ2,dnm = −|xn−xm|2,Knm(γ ) =eγdnm .(3) Thus, γis the inverse of double squared kernel spread σ, while dnm is minus the squared distance between xnand xm. The values {dnm }N nm=1compose the N×N-order distance matrix D. The difference D(γ ) is D(γ ) =1 MX nm (eγdnm −Jnm)2.(4) Deriving D(γ ), using that K′ nm(γ ) =eγdnm dnm and equaling to zero, we achieve d D dγ=2 MX nm (eγdnm −Jnm)eγdnm dnm =0.(5) This equation does not allow to calculate an analytic solution for γ, but an estimation might be achieved by supposing that all the distances dnm are equal to their expected or mean value, denoted by d dnm =d=1 MX pq dpq (6) where the sum over p,qhas the same limits as previously with n,m. Using this hypothesis, (5) becomes X nm (eγd−Jnm )eγdd=0→eγdX nm 1=X nm Jnm (7) where we divided by eγdd. Note that Pnm 1=M. Besides, Pnm Jnm is the number of pairs of patterns (n,m)where cn=cm. For k=1,...,C, the class kwith Nktraining patterns has Nk(Nk−1)/2 pairs, so that X nm Jnm =1 2 C X k=1 (N2 k−Nk)(8) and (7) becomes Meγd=1 2 C X k=1 (N2 k−Nk). (9) Substituting dfrom (6), the estimated value of γis γ= −ln"1 2M C X k=1 (N2 k−Nk)# 1 M N−1 X n=1 N X m=n+1 |xn−xm|2 .(10) This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. ISLA-CERNADAS et al.: CLOSED-FORM GAUSSIAN SPREAD ESTIMATION 3 Fig. 1. Values of D,D2, and kappa varying γfrom 2−20 to 220, with the true and estimated γvalues minimizing Dand D2(square and circle, respectively) in dataset voting. Theorem 1: The function D(γ ) in (4) has a minimum at the value of γcalculated by (10) under hypothesis in (6). Proof: The function D(γ ) has a minimum for γin (10) if D′′(γ ) > 0. This second derivative is d2D dγ2=2 MX nm (2dnme2γdnm −dnm Jnm eγdnm )dnm.(11) Using that dnm =dand γ=(ln p)/d, so that eγd=pand e2γd=p2, we achieve d2D dγ2=2 MX nm (2p2d2−pJnm d2) =2 M 2p2Md2−pd2X nm Jnm !=2p2d2>0 (12) where we used that Pnm 1=Mand Pnm Jnm =Mp.□ Note that class populations Nkin (10) require the class labels that define the classification problem, being therefore necessary to calculate the optimal γ. Using ddefined by (6) instead of dnm transforms D(γ ) in (4) to D2(γ ) =1 MX nm eγd−Jnm 2=e2γd+p1−2eγd(13) where p=(1/M)Pnm Jnm . It follows that D′ 2(γ ) =0 and D2(γ ) =p(1−p)for γ=(ln p)/das in (10). Note that D(0)=1−pand D(∞)=p. Fig. 1shows in this case for dataset voting that D(γ ) and D2(γ ) are very similar and their minima are very near. Thus, although the distances {dnm} are not equal to their mean d, the deviation is somehow compensated and the value of γthat minimizes D(γ ) can be calculated as if {dnm}were equal to their mean. Besides, both the minima are located at the maximum of performance on the validation set, measured by the Cohen kappa statistic, so that minimizing Dor D2also maximizes performance. The proposed method to estimate γhas been named direct gamma tuning (DGT). Algorithm 1describes DGT for small datasets (DGS), that trains the SVM using the γcalculated using (10) by procedure gamma (algorithm 2) on the whole training set {xn,cn}N n=1. Algorithm 1 DGT, Small Datasets. 1Algorithm: S=DGS({xn,cn}N n=1,λ) Data: {xn,cn}N n=1: training patterns and class labels cn∈ {1,...,C};λ: regularization parameter. Result: S: trained SVM. 2γ←gamma({xn,cn}N n=1)#procedure gamma in alg. 2 3S←SVMTrain({xn,cn}N n=1,λ,γ) Algorithm 2 Calculation of γ. 1Algorithm: γ=gamma({wh,bh}H h=1) Data: {wh,bh}H h=1: training patterns and class labels bh∈ {1,...,C}. Result: γ: inverse of double squared kernel spread σ. 2M←H(H−1) 2;d←−1 M H−1 X h=1 H X m=h+1 |wh−wm|2 3   Nk← H X h=1,bh=k 1   C k=1 ;p←1 2M C X k=1 (N2 k−Nk) 4γ=1 dlnp M When the number Nof training patterns is high, the calculation of distances {dnm}N−1,N n=1,m=n−1becomes expensive. Besides, the SVM cannot be trained on the whole dataset. The approach proposed in [23] by the fast support vector classifier (FSVC) for large datasets is to use a reduced set of 100 prototypes of each class instead of the whole training set. This low number of prototypes is because the method requires to calculate the distances between these prototypes and the training patterns, which is slow when many prototypes are used. This article is focused on the standard SVM instead of FSVC, and the SVM performance might be very poor using so few training patterns. In addition, a large number of prototypes would slow down the distance computation, so we propose to replace prototypes by training patterns randomly selected, i.e., to perform a random sampling on the training set, for the distance calculation. This sampling must be performed by keeping the relative class populations in the original set. The number L<Nof patterns to be selected for SVM training is very important: low values might reduce performance, and high values slow down the training and may lead to memory failures. Larger datasets require larger training sets, so Lmust be increasing with Nas, e.g., L=αN with α < 1. To avoid errors in SVM training for high N, an upper bounded L0is required for L. The values of αand L0should be carefully set to achieve a good tradeoff between performance and speed. The upper panel of Fig. 2reports kappa versus time when Lraises from 1000 to N(from left to right in each line) for several large datasets used in the experimental work (Section III-B). The time raises with L because the training is slower. Kappa raises slowly in some datasets (magic,letter,adult, and shuttle) and faster in others with larger datasets (chess,wisdm, and ijcnn1). This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 4 IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS Fig. 2. Upper panel: kappa versus time (log. scale) of several large datasets varying Lfrom 1000 to Nfrom left to right. Lower panel: kappa versus L/N (log. scale) for the same datasets. The lower panel of Fig. 2shows plots of kappa versus L/N. In datasets where kappa raises slowly and in ijcnn1,L/N about 0.5 or even lower already provides a good performance. In the second group of datasets, larger L/Nvalues are required to achieve performance near the highest available (for L/N→1). Therefore, to achieve a tradeoff between performance and speed, we propose to use α=0.5, although in some datasets (e.g., chess and wisdm) the performance may be suboptimal. To set the upper bound L0for L, the capability of SVM to train with large datasets must be considered. Datasets with hundreds or thousands of inputs can be discarded for RBF SVM, which does not outperform and is slower than linear SVM. With less than 200 inputs, the SVM is able to train with 10 000–20 000 training patterns, so we propose to set L0=20 000 patterns. Finally, Lis calculated as L=min(L0,⌊αN⌋), α =0.5,L0=20,000.(14) Equation (10) requires the distance matrix D, which is of size L. The computation of D, of complexity O(L2), might be too slow, so that a smaller size U<Lwas used instead. To evaluate the influence of Uon performance and speed, Fig. 3shows kappa versus time for the datasets in Fig. 2 varying Ufrom 500 to 5000 with step 500 from left to right points in each line. The time raises with U, but kappa remains fairly insensitive, so γcan be accurately estimated using a smaller distance matrix. Specifically, we propose to Fig. 3. Kappa versus time in several large datasets varying U from 500 to 5000 with step 500 from left to right. Algorithm 3 DGT, Large Datasets. 1Algorithm: S=DGL({xn,cn}N n=1,λ) Data: {xn,cn}N n=1: training patterns and class labels cn∈ {1,...,C};λ: regularization parameter. Result: S: trained SVM. 2L0←20,000; α←0.5; L←min(L0,⌊αN⌋) 3U←1,000; r← ⌊L/U⌋ 4#R(A,L)←random sampling of Litems from A 5{zl,ql}L l=1←R({xn,cn}N n=1,L) 6γ←gamma({zl,ql}L l=1,r)#procedure gamma, alg. 2 7S←SVMTrain({zl,ql}L l=1,λ,γ) use U=1000 patterns. Algorithm 3describes the whole DGT procedure for large datasets (DGL), which: selects a random sample Rof size Lof the whole training set, keeping the relative class populations; calls procedure gamma (algorithm 2) passing only Uof these Lpatterns in line 6, where lruns from 1 to Lwith step r= ⌊L/U⌋; and trains SVM on the L training patterns. III. RESULTS AND DISCUSSION The proposed methods DGS and DGL were used to calculate γand train the SVM. The experiments were performed in a desktop computer with 8 Intel©Core1i7-9700K processors at 3.60 GHz, equipped with 64-GB RAM under operative system Linux Kubuntu 20.04. The methodology was four fold cross-validation (CV), using two folds to train the SVM, one for validation (in hyperparameter tuning) and the remaining fold for test. The classification performance was measured using the kappa statistic. The SVM implementation was LibSVM [24], accessed from its Octave binding.2The datasets were selected from the UCI [25] and Kaggle3repositories. A. Small Datasets A first group of experiments were run over a collection of 30 datasets of small size (Table I), with less 1Trademarked. 2http://www.octave.org (May, 2022). 3https://www.kaggle.com This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. ISLA-CERNADAS et al.: CLOSED-FORM GAUSSIAN SPREAD ESTIMATION 5 TABLE I LIST OF SMALL DATASETS (Q<15 000) WITH THEIR NUMBERS OF TOTAL (Q)AND TRAINING (N) PATTERNS, INPUTS (I), AND CLASSES (C) than 15 000 patterns. The γof SVM was estimated: 1) using DGS; 2) using GS, with values in the set 0= {2i}20 i=−20; and 3) selecting the value in 0that minimizes D(γ ) in (4), named D-minimization for small datasets (DMS), equivalent to IKT [22]. The regularization λwas always tuned in the set {2i}15 i=−7to maximize kappa on the validation set. The hypothesis in (6) is evaluated in Table II by comparing γ,D(γ ), and kappa on the validation set achieved by DGS and DMS. For most datasets, DGS achieves γvery near to the right value selected by DMS (column 3), with an average difference (last row, column 4) of 0.037. The difference in D(γ ) between DGS and DMS (column 7) is also very low, 0.012 on average. The kappa values of DGS and DMS in columns 8 and 9 are also very similar in all the datasets, with an average difference of 0.8%, so the difference in γbetween DGS and DMS does not reduce very much the SVM validation performance. Table III reports the kappa and times (in s excluding λ tuning) spent by DGS, GS, and DMS on test sets. The kappa of DGS is very similar to GS and DMS in all the cases, achieving the best result in seven of them. In the last line, the average kappa of DGS (79.7%) is only 0.6 and 1 point below GS and DMS (80.3% and 80.7%, respectively). Columns 5 and 6 report the average time (T1, in s) per fold spent by DGS or TABLE II VALUES OF γAND D(γ ), ABSOLUTE DIFFERENCES,AND KAPPA VALUES ON THE VALIDATION SETS ACHIEVED BY DGS AND DMS ON THE SMALL DATASETS DMS to calculate γ. The values of DMS are one to three orders of magnitude higher than DGS. Column 6 of the last line reports the average of T1(DMS)/T1(DGS), being the latter one order of magnitude (16.3 times) faster than the former. This is expectable because DGS calculates γusing (10). Although this requires to calculate the distances between the Ntraining patterns, they must also be calculated for DMS, which additionally requires to repeat the calculation of D(γ ) for the 41 values of γin the set 0. This ratio raises very fast with the dataset size, with values above 20 in the 11 last datasets. The time T2(columns 7 and 8 in Table III) is the average total execution time per fold for DGS and GS. The last line of column 8 reports that DGS is one order of magnitude (10.9 times on average) faster than GS, reaching ratios T2(GS)/T2(DGS) about 20–40 in the last datasets. B. Large Datasets Experiments were also conducted on a collection of 20 large datasets (more than 15 000 training patterns, Table IV) up to 31 million of patterns and 122 inputs. Our method DGL was compared to the ones below. This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 6 IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS TABLE III KAPPA (IN %) AND TIMES T1,T2(IN s, SEE TEXT FOR DETAILS) OF SVM USING DGS, GS, AND DMS ON THE TEST SETS FOR SMALL DATASETS. BEST KAPPA VALUES ARE IN BOLD 1) Minimization of D(γ ) for large datasets, named DML, with γ∈0, equivalent to IKT with random sampling of Ltraining patterns, see (14) with α=0.5 and L0 =20 000, and a reduced distance matrix of size U= 1000. 2) Linear kernel SVM (LSVM), implemented by the Liblinear library [26], because RBF kernel SVM cannot be executed on such large datasets. The regularization parameter λwas not tuned, given the dataset size, but set to 100, a value widely used in the literature. All the experiments used the same seed for the random number generator to guarantee the reproducibility of the results. To evaluate whether the initialization of the random number generator during the training set sampling influences performance of DGL, Table Vreports the mean and standard deviations of the kappa achieved by DGL on the first seven large datasets using 20 different random seeds. The deviations are very low compared with the mean kappa values. This means that performance is very similar in all the cases, and that influence of randomness on performance is not significant. Table VI reports kappa and times T1and T2of DGL, DML, and LSVM, and time T3required only by the disk reading, TABLE IV LIST OF LARGE DATASETS (Q>15 000 PATTERNS) SORTED BY Q·I TABLE V MEAN AND STANDARD DEVIATION OF KAPPA (IN %) ACHIEVED BY DGL OVER 20 DIFFERENT RANDOM SEEDS ON SOME LARGE DATASETS TABLE VI KAPPA (IN %), TIMES T1AND T2(IN s) OF DGL, LSVM, AND DML, AND DATASET READ TIME T3IN THE LARGE DATASETS on the large datasets. In 12 of 20 datasets, DGL achieves the best kappa, being globally higher than DML and much higher than LSVM, which runs out-of-memory in three cases. This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. ISLA-CERNADAS et al.: CLOSED-FORM GAUSSIAN SPREAD ESTIMATION 7 Fig. 4. Time spent by DGL and DML to find γfor large datasets. On average, the kappa of DGL (62.6%) is 27 and 3 points higher than LSVM and DML, respectively. Thus, direct calculation of γ(10) combined to random sampling seems to be effective performing the RBF tuning for the SVM on large datasets. According to a Wilcoxon rank-sum test, the difference between DGL and LSVM is statistically significant (p=0.0032), while the difference between DGL and DML is not statistically significant (p=0.7). Considering the time T1spent to calculate γ(columns 5 and 6), DGL is much faster (907 times, almost three orders) than DML. The difference between their times raises with the dataset size, from one to even three to four orders, so direct calculation of γin DGL really allows a large time saving compared with DML. Considering the total execution time T2 (columns 7 and 8), DGL is faster than LSVM in 10 of 17 datasets where LSVM does not fail, and on average DGL is 3.3 times faster than LSVM, despite that LSVM uses linear kernel and is designed for large datasets. Note also that in the largest datasets, the ratio T2(LSVM)/T2(DGL) is much higher than 3.3, e.g., 22.4 in baiot. The time T3required by file reading is near T2for DGL in some datasets, e.g., in record, kddcup,baiot, and kitsune, so the execution of DGL is very fast and most of the time is spent just in data reading. Fig. 4shows plots of the time spent by DGL and DML to calculate and search, respectively, γon the large datasets. DML is much slower than DGL because it requires to calculate D(γ ) for the 41 values in the collection {2i}20 −20. Besides, the difference between their times raises from left to right starting in one order of magnitude up to three to four orders for the largest datasets, so DGL allows a large time saving compared with DML. Fig. 5shows plots of the times spent in the large datasets by the four stages of DGL: random sampling of training patterns, γtuning using (10), training, and test of the SVM. The sampling, train, and test times raise with the dataset size from left to right, although the train times oscillating strongly due to SVM training may be faster or slower depending on the complexity of the training set. However, the tuning time is very stable and remains constant with the dataset size, being much slower than the times of the other stages. Fig. 5. Time spent by DGL in each stage. C. Comparison With Existing Approaches Compared with the methods evaluated in [22], the average performance of DGS or DGL over the datasets also used in the current work (78.3%) is similar to IKT (78.6%), KDE (78.1%), genetic (79.7%), PSO (78.4%), and Bayesian (80%). IKT spends 384 s in its largest training set (ijcnn1, Table III in [22]), while DGL spends only 7.7 s (T2in Table VI). DGL is faster than IKT due to: 1) the closed-form expression in (10), faster than iterative minimization and not limited to a predefined collection of γvalues; and 2) use of random sampling instead of class prototypes in IKT. Thus, DGL comes up to training sets of 8 million of patterns (kitsune), being a step ahead to extend the standard SVM for large-scale datasets. The FSVC [23] achieves kappa of 27.9% and 59.8% spending 6015 and 599 s in datasets kitsune and hepmass, respectively, while DGL achieves 77.4% and 66.8% spending 2793 and 1078 s, so DGL outperforms FSVC and is faster in the first case. The indefinite core vector machine [27] achieves kappa4of 28.5%, 59.2%, and 73% with times 115.26, 170.36, and 88.0 s in datasets magic,nursery, and grid, respectively, while DGL achieves 70%, 100%, and 98% with times 1.4, 8.21, and 2.59 s in the same datasets, so DGL outperforms ICVM and is much faster. Table VII shows comparison of the test error and execution time T2(or T1when asterisk is present), of DGS (or DGL with †), and several related approaches referenced in Section Ion common datasets. Note that the experimental methodology can be different to the current one, which may lead to differences in performance. In general, DGS achieves a test error similar to the competing approaches, outperforming them in 13 of 26 datasets. Besides, DGS is much faster, and the differences reach often several orders of magnitude. In dataset ion, the Bat algorithm [10] spends 645.3 s while DGS spends 0.02 s, a large difference even considering the difference in computing power since 2017. In adult, dynamic PSO [7] achieved 15.55% error using tenfold CV spending 5287 s, while DGL achieves 20.44% using fourfold CV in 74.9 s. The DGS also compares well to 4https://www.techfak.uni-bielefeld.de/∼fschleif/software.xhtml This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 8 IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS TABLE VII TEST ERROR (IN %) AND TIME T2(∗MEANS T1)OF DGS (†MEANS DGL) AND OTHER APPROACHES IN THE LITERATURE nearest enemy [17], calculating γabout ten times faster with similar error. Differential evolution [8] is almost three orders slower than DGS (155.35 versus 0.199 s), and the random RBF SVM [20] gets more error than DGS being two orders slower. Overall, DGS and DGL are between one and three orders faster than the existing approaches with performances similar to or higher than the state-of-the-art, confirming the value of DGT. IV. CONCLUSION We propose a method to calculate the inverse γof the double squared RBF kernel spread σfor the SVM directly from training data in classification problems. The DGT for small (DGS) or large (DGL) datasets uses a closed-form expression that only requires the average distance between training patterns. This expression is an approximated analytical solution for the minimization of the mean squared difference D(γ ) between the RBF and ideal kernel matrices. It avoids to repeat the calculation of D(γ ) for different γ values, as in our previous approach IKT [22], being two orders of magnitude faster with similar performance. In a collection of 30 small size datasets, the SVM with γtuned by DGS is very efficient, one order of magnitude faster than GS and D-minimization (DMS), equivalent to IKT, and achieves kappa (79.5% on average) virtually equal to DMS and GS (80.4% and 80.1%, respectively). In large datasets, both the calculation of the distances between patterns required by the γestimation and SVM training become slow, so DGL performs a random sampling of the training set both for distance calculation and SVM training. The experiments prove that a small distance matrix, with a low number of randomly sampled training patterns, is enough for an accurate estimation of γ. The performance of DGL (62.6%) on 20 large-scale datasets up to 31 million of patterns clearly outperforms the linear kernel SVM (35.8%), which fails in the largest datasets, with statistical significance. Besides, DGL also outperforms D-minimization (DML), equivalent to IKT with random sampling, which achieves kappa of 59.6%. On average, DGL is 907 times (two to three orders) faster than DML and even three times faster than LSVM, which is specially suited for large datasets. These results prove that the proposed analytical formula for γalways achieves the optimal value and, combined with random sampling of the training set, allows to extend the SVM with RBF kernel to arbitrary large classification problems. Future work includes to generalize the proposed method to other nonlinear kernels, such as polynomial or sigmoid, with one or even two tunable parameters. REFERENCES [1] M. M. Fernández-Delgado, E. Cernadas, S. Barro, and D. Amorim, “Do we need hundreds of classifiers to solve real world classification problems?” J. Mach. Learn. Res., vol. 15, pp. 3133–3181, Jan. 2014. [2] J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization,” J. Mach. Learn. Res., vol. 13, pp. 281–305, Feb. 2012. [3] M. Choi and J. J. Jeong, “Comparison of selection criteria for model selection of support vector machine on physiological data with intersubject variance,” Appl. Sci., vol. 12, no. 3, p. 1749, Feb. 2022. [4] D. Anguita, A. Ghio, L. Oneto, and S. Ridella, “In-sample and out- of-sample model selection and error estimation for support vector machines,” IEEE Trans. Neural Netw. Learn. Syst., vol. 23, no. 9, pp. 1390–1406, Sep. 2012. [5] F. Friedrichs and C. Igel, “Evolutionary tuning of multiple SVM parameters,” Neurocomputing, vol. 64, pp. 107–117, Mar. 2005. [6] M. Abbaszadeh, S. Soltani-Mohammadi, and A. N. Ahmed, “Optimization of support vector machine parameters in modeling of Iju deposit mineralization and alteration zones using particle swarm optimization algorithm and grid search method,” Comput. Geosci., vol. 165, Aug. 2022, Art. no. 105140. [7] M. N. Kapp, R. Sabourin, and P. Maupin, “A dynamic model selection strategy for support vector machine classifiers,” Appl. Soft Comput., vol. 12, no. 8, pp. 2550–2565, Aug. 2012. [8] J. Zhang, A. Niu, K. Li, and G. Irwing, “Model selection in SVMs using differential evolution,” in Proc. World Congr. Int. Fed. Automat. Control, 2011, pp. 14717–14722. [9] C. E. D. S. Santos, R. C. Sampaio, L. D. S. Coelho, G. A. Bestard, and C. H. Llanos, “Multi-objective adaptive differential evolution for SVM/SVR hyperparameters selection,” Pattern Recognit., vol. 110, Feb. 2021, Art. no. 107649. [10] A. Tharwat, A. E. Hassanien, and B. E. Elnaghi, “A BA-based algorithm for parameter optimization of support vector machine,” Pattern Recognit. Lett., vol. 93, pp. 13–22, Jul. 2017. [11] A. Tharwat and T. Gabel, “Parameters optimization of support vector machines for imbalanced data using social ski driver algorithm,” Neural Comput. Appl., vol. 32, no. 11, pp. 6925–6938, Jun. 2020. [12] T. Glasmachers and C. Igel, “Maximum likelihood model selection for 1-norm soft margin SVMs with multiple parameters,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 32, no. 8, pp. 1522–1528, Aug. 2010. [13] C.-C. Chang and S.-H. Chou, “Tuning of the hyperparameters for L2-loss SVMs with the RBF kernel by the maximum-margin principle and the jackknife technique,” Pattern Recognit., vol. 48, no. 12, pp. 3983–3992, Dec. 2015. [14] L. Wang, P. Xue, and K. L. Chan, “Two criteria for model selection in multiclass support vector machines,” IEEE Trans. Syst., Man, Cybern., B, Cybern., vol. 38, no. 6, pp. 1432–1448, Dec. 2008. [15] Z. Xu, M. Dai, and D. Meng, “Fast and efficient strategies for model selection of Gaussian support vector machine,” IEEE Trans. Syst., Man, Cybern., B, Cybern., vol. 39, no. 5, pp. 1292–1307, Oct. 2009. This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. ISLA-CERNADAS et al.: CLOSED-FORM GAUSSIAN SPREAD ESTIMATION 9 [16] M. Varewyck and J.-P. Martens, “A practical approach to model selection for support vector machines with a Gaussian kernel,” IEEE Trans. Syst., Man, Cybern., B, Cybern., vol. 41, no. 2, pp. 330–340, Apr. 2011. [17] M. Lázaro-Gredilla, V. Gómez-Verdejo, and E. Parrado-Hernández, “Low-cost model selection for SVMs using local features,” Eng. Appl. Artif. Intell., vol. 25, no. 6, pp. 1203–1211, Sep. 2012. [18] Z. Liu and H. Xu, “Kernel parameter selection for support vector machine classification,” J. Algorithms Comput. Technol., vol. 8, no. 2, pp. 163–177, Jun. 2014. [19] Z. Liu, M. Zuo, X. Zhao, and H. Xu, “An analytical approach to fast parameter selection of Gaussian RBF kernel for support vector machine,” J. Inf. Sci. Eng., vol. 31, no. 2, pp. 691–710, 2015. [20] X. Ding, J. Liu, F. Yang, and J. Cao, “Random radial basis function kernel-based support vector machine,” J. Franklin Inst., vol. 358, no. 18, pp. 10121–10140, Dec. 2021. [21] M. V. F. Menezes, L. C. B. Torres, and A. P. Braga, “Width optimization of RBF kernels for binary classification of support vector machines: A density estimation-based approach,” Pattern Recognit. Lett., vol. 128, pp. 1–7, Dec. 2019. [22] Z. Akram-Ali-Hammouri, M. Fernández-Delgado, A. Albtoush, E. Cernadas, and S. Barro, “Ideal kernel tuning: Fast and scalable selection of the radial basis kernel spread for support vector classification,” Neurocomputing, vol. 489, pp. 1–8, Jun. 2022. [23] Z. Akram-Ali-Hammouri, M. Fernández-Delgado, E. Cernadas, and S. Barro, “Fast support vector classification for large-scale problems,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 10, pp. 6184–6195, Oct. 2022. [24] C.-C. Chang and C.-J. Lin, “LIBSVM: A library for support vector machines,” ACM Trans. Intell. Syst. Technol., vol. 2, no. 3, pp. 1–27, Apr. 2011. [25] D. Dua and C. Graff. (2017). UCI Machine Learning Repository. [Online]. Available: http://archive.ics.uci.edu/ml [26] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin, “LIBLINEAR: A library for large linear classification,” J. Mach. Learn. Res., vol. 9, pp. 1871–1874, Jun. 2008. [27] F.-M. Schleif and P. Tino, “Indefinite core vector machine,” Pattern Recognit., vol. 71, pp. 187–195, Nov. 2017. Diego Isla-Cernadas was born in A Coruña, Spain, in 1981. He received the B.S. degree from the Polithecnic University of Valencia, Valencia, Spain, in 2011, and the M.S. degree in automatic and electronic engineering from the Polithecnic University of Madrid, Madrid, Spain, in 2018. He is currently pursuing the Ph.D. degree in machine learning, neural networks, and classification with the Centro Singular de Investigación en Tecnoloxías Intelixentes da USC (CiTIUS), Santiago de Compostela, Spain. Manuel Fernández-Delgado received the B.S. degree in physics and the Ph.D. degree in computer science from the University of Santiago de Compostela (USC), Santiago, Spain, in 1994 and 1999, respectively. He is a Lecturer of computer science and researcher at Centro Singular de Investigación en Tecnoloxías Intelixentes da USC (CiTIUS), Santiago de Compostela, Spain, with a focus on neural computation, machine learning, and pattern recognition of the CiTIUS. Eva Cernadas was born in A Coruña, Spain, in 1969. She received the B.S. and Ph.D. degrees in physics from the University of Santiago de Compostela (USC), Santiago, Spain, in 1992 and 1997, respectively. She is a Lecturer of computer science and researcher at Centro Singular de Investigación en Tecnoloxías Intelixentes da USC (CiTIUS), Santiago de Compostela, Spain, with a focus on computer vision and machine learning, specially in food technology, medical, and biological domains. Manisha S. Sirsat received the Ph.D. degree in computer science from the University of Santiago de Compostela (USC), Santiago, Spain, in 2017. She is a Senior Researcher of machine learning at the InnovPlantProtect, Elvás, Portugal. Her main research area includes implementing artificial intelligence for solving agriculture problems, and thus she has applied classification and regression methods to a wide variety of applications in agriculture. Haitham Maarouf received the Ph.D. degree (Hons.) in computer science from the University of Santiago de Compostela (USC), Santiago, Spain, in 2018. He is a Post-Doctoral Researcher at Centro Singular de Investigación en Tecnoloxías Intelixentes da USC (CITIUS), Santiago de Compostela, Spain, and a Researcher and System Analyst at Plexus Tech, Santiago de Compostela. His research interests include artificial intelligence, data science, machine learning, knowledge representation, biomedical ontologies, and terminologies. Senén Barro was born in As Pontes de García Rodríguez, Spain, in 1962. He received the B.S. and Ph.D. degrees in physics from the University of Santiago de Compostela (USC), Santiago, Spain, in 1985 and 1988, respectively. He is a Full Professor of Computer Science at USC in 1995. From 2002 to 2010, he was the Rector at USC. He is currently the Scientific Director of the Centro Singular de Investigación en Tecnoloxías Intelixentes da USC (CiTIUS), Santiago de Compostela, Spain. He has authored seven books and more than 300 scientific papers in these fields. This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.