Comparative performance analysis of epsilon-insensitive and pruningbased algorithms for sparse least

Abstract

Keywords: Least Squares Support Vector Regression; Pruning; Epsilon Insensitiveness; Robustness; Sparseness

Introduction

Support Vector Machines (SVMs), a machine learning method, were initially introduced by Vapnik in 1995 [1]. They were quickly recognized as an effective tool in classification and regression tasks and have since found widespread application in various real-world scenarios [2-7]. Within

the realm of regression, support vector machines are called Support Vector Regression (SVR) [8, 9]. SVR uses the ε-insensitive l1 loss function, which disregards noise while trying to suppress the influence of outliers, providing better generalization ability compared to least squares regression. Similar to the ridge regression, which minimizes a regularized l2 loss, SVR is adept at constructing models with enhanced

*Corresponding author. *E-mail address: omerkaral@aybu.edu.tr This paper was recommended for publication in revised form by Regional Editor Md. Sabir Hossain Published by Yıldız Technical University Press, İstanbul, Turkey Copyright 2021, Yıldız Technical University. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

generalization abilities. This is attained by minimizing both regularized and ε-insensitive empirical error. The optimal parameters for an SVR model are typically determined by minimizing the convex quadratic cost function formulated in the dual space. This involves utilizing Lagrange multipliers and a kernel to achieve the optimal solution. While minimizing convex quadratic costs is efficient, dual representations for classical SVR encounter significant time consumption due to the substantial number of optimization variables, especially when dealing with large datasets. To address this, a more computationally efficient alternative, known as the Least Squares Support Vector Regression (LSSVR), has been presented [10]. The formulation of LSSVR resembles ridge regression, using a regularized l2 loss, where experimental errors are treated as linear constraints [11]. Typically, LSSVR is formulated as a quadratic minimization problem subject to a linear equality constraint on Lagrange multipliers in the dual space. A significant advantage of LSSVR over SVR is the possibility of having the ability to represent the primary cost constraint as a penalty term in the dual formulation representation using a single Lagrange multiplier, as opposed to the pair of Lagrange multipliers required for training samples in SVR. This formulation results in LSSVR requiring only half the Lagrange multipliers required for classical SVR compared to classical SVR, leading to a remarkable reduction in calculation time. In the LSSVR approach, the loss function used is the regularized squared (l2) loss; The error terms are symbolized as the equality constraints, resulting in the formulation of a linear system of equations. Though this feature offers computational advantages, the sparsity property inherent in traditional SVR, induced through ε-insensitivity, is vanished in LSSVR, where each input instance is treated as a support vector. Moreover, due to the squared loss used, LSSVR lacks robustness to outliers compared to SVR. To deal with the lack of sparseness for LSSVR, current methods can be classified in two approaches: iterative and direct methods. In iterative methods, training samples are progressively eliminated either forward or backward, one by one, in each iteration. For instance, Suykens et al. introduced the Pruned LSSVR (PLSSVR) model, which initially runs the standard LSSVR model and sort the resulting support vectors from largest to smallest. Then, it gradually prunes the support vectors beginning from the smallest value in the spectrum [12]. Additionally, they proposed a weighted version to enhance robustness against outliers [13]. Kruif and Vries proposed an alternative pruning algorithm where the training sample yielding the smallest error after its ignorance in the previous iteration is removed [14]. Kuh and De Wilde [15] extended the Kruif and Vries’s pruning algorithm which is applied to a non-regularized loss to the regularized loss. Hoegaerts et al. [16] presented two pruning algorithms: one is based on deleting the sample with the smallest correlation with the output and the other on removing the sample with the least similarity to

the best fitting span. Zeng and Chen [17] introduced the SMO-based pruning scheme, which eliminates samples that contribute the least change in the dual objective function, rather than being merely on errors. Zhao and Sun [18] presented a technique called recursive reduced LSSVR (RRLSSVR), where data contributing more to the objective function are selected as support vectors while considering all constraints yielded by all training samples. Subsequently, the improved version of RRLSSVR (IRRLSSVR) was introduced to get much sparser solution than RLLSSVR in [19]. Later, refined versions of them [20] were proposed to improve their performance. Si et al. [21] introduced the reconstructed LSSVR algorithm (RCLSSVR), applied in mill load prediction, which utilizes reconstructed support vectors. It selects reconstructed data based on density clustering information in the training dataset and to improve sparseness and robustness simultaneously. Sun et al. [22] proposed a localized generalization error model based on the training mean square error and sensitivity measure to prune support vectors in the LS-SVM. In direct methods, the algorithm begins with a full dense solution and then eliminates training samples based on objective criteria. For instance, Espinoza et al. [23] introduced a fixed-size least squares least squares support vector machine (FS-LSSVM) method, utilizing Nystrm approximation with a predefined set of prototype vectors (PVs) to provide a solution in the primal space. Based on the similar idea, Mall and Suykens [24] proposed two L0-norm-reduced models: the sparsified primal FS-LSSVM for the input space and sparsified subsampled dual LSSVM for the dual space. Yang et al. [25] introduced a one-step compressive pruning strategy to construct a sparse LSSVM. Zhou [26] introduced a low-rank representation technique using pivoted Cholesky decomposition for the kernel matrix to sparsify the LSSVM. Later, this method was extended to a robust LSSVM using a non-convex truncated loss function [27]. Xia [28] used the Kernel Matching Tracking technique, which exploits the number of support vectors as the regularization parameter to achieve sparsity in the LS-SVM solution. Ma et al. [29] designed an indicator to assess the global representation of data points based on density and distribution of them in the feature space. Next, they presented a fast sparse LS-SVM method by choosing support vectors with a non-recursive strategy using global representation. Recently, a new sparse LSSVR model (ε-LSSVR) with ε-insensitivity at quadratic loss has been introduced in [30]. ε-LSSVR ignores errors within a given ε band, as in SVM, and its sparsity is controlled only by the ε parameter. Inspired by [30], this paper theoretically derives ε-LSSVR from the LSSVR model in detail, which results in fewer support vectors that provide sparsity in dual space without necessitating computationally expensive algorithms. However, the quadratic loss function of ε-LSSVR may comprise robustness in the presence of outliers. To address this limitation and improve robustness, a weighted version, ε-WLSSVR, will be presented in Section 2.2, for the specific case of this study.

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

The pruning approach iteratively removes the constraints of non-support vectors backwards to build a sparse LSSVR model. This may result in better convergence and higher stability for inhomogeneous and unbalanced datasets. Conversely, the ε-insensitive strategy forces certain support vectors to move to zero, allowing direct control over the selection of non-zero support vectors, which directly influences solution sparsity and computation time. In this study, the performances of iterative based PLSSVR, WPLSSVR algorithms and ε-LSSVR and ε-WLSSVR methods that provide direct sparsity are analyzed for the first time in terms of generalization ability, sparsity, and computation time on both synthetic and 8 different real-world data. The main contributions of this paper are summarized as follows: i. Directly defining the sparseness of LSSVR in the input space by using ε-insensitivity within the quadratic loss function and providing a theoretical solution. ii. Addressing the robustness matter inherent in the quadratic loss function of ε-LSSVR by introducing its weighted version, ε-WLSSVR. iii. Analyzing the performances of PLSSVR, WPLSSVR, ε-LSSVR, and ε-WLSSVR methods for the first time in terms of sparsity, generalization ability, and computation time across both synthetic and 8 different realworld datasets. The remainder of the paper is structured as follows: Section 2 presents a review of the basic concepts of LSSVR followed by a full portrait of the four methods of

interest. Section 3 examines and compares pruning-based, and ε-insensitivity based approaches in both synthetic and real-world datasets. Finally, Section 4 presents result descriptions and potential feature guidelines. Least Squares Support Vector Regression , where xs. represents Given a training set the sth input data vector, ys denotes the target output data points for the input xs, and L is the number of training data points, LSSVR is formulated in primal space as follows [10]: (1)

(2) Where, C is a user defined regularization constant that controls the balance between empirical error (for large C) and generalization ability (for small C), w is the unknown model parameter, es representing the deviation of the actual output from the predicted output for each training example, φ(.) is a nonlinear basis function, and b is the unknown threshold parameter. LSSVR optimization problem (1) in primal space is transformed into the following unconstrained optimization problem in dual space by applying the Lagrange multipliers method.

Figure 1. a) Loss function of LSSVR b) ε-insensitivity in loss function of LSSVR c) Derivative of LSSVR loss function d) Derivative of LSSVR loss function with ε-insensitivity.

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

Where: · αs represents the Lagrange multipliers. · K(xs, xr) represents kernel functions characterized as the inner product of two input samples φ(xs) and φ(xr) in the high dimensional space i.e. . The predicted range of learned LSSVR for the test sample x, can be expressed as follows:

The conditions required for the optimal solution of the Lagrangian formulation model (9) are as follows: (10)

(4) (12) ε-insensitive Least Squares Support Vector Regression ε-LSSVR, the ε-insensitive variant of LSSVR, is introduced in detail in this section. According to Equation (4), every training data point xs contributes to the solution representation of model except training data points with αs =

0. Therefore, the significance of a training data point xs is

determined by its support value αs. The values of αs, which are Lagrange multipliers, rarely equal zero in most practical scenarios, leading to numerous support vectors in the LSSVR solution representation. The optimization problem required to derive ε-LSSVR from LSSVR is formulated as follows [30]:

(13) To derive a cost function based on the Lagrange multipliers αs it is necessary to solve for es in terms of αs in equation (12). There are 3 distinct regions, each of which establishes a relationship between αs and es in an affine manner:

Since es > ε implies as > 0, -ε ≤ es ≤ ε implies as = 0, and es < -ε implies as < 0 equation (12) can be written as (14)

is a continuously differenIt’s important to note that tiable function. Figure 1 illustrates the LSSVR loss function and its derivative in comparison, as well as the ε-insensitivity in loss function of LSSVR and its derivative. The canonical representation of the first derivative of the ε-LSSVR loss function is as follows:

Substituting equations (10) and (14) into equation (9) and using equation (11) to eliminate variables es and w, the optimization formulation of ε-LSSVR becomes:

(8) The formulation model in terms of Lagrange multipliers becomes:

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

The, the last term, in equation (15), , is . Similarly, third term, refers to the ε-inequal to . sensitive squared loss function and is equal to Under these conditions, equation (15) can be rearranged as follows to compactly represent the dual minimization for ε-LSSVR. (17)

By employing optimality conditions (first derivative with respect to the optimization variables) and removing and w*variables to solve the optimization problem in (21), the ε-WLSSVR optimization problem can be expressed in dual space as follows:

(18) (22) The only difference observed when comparing equation (3) with equation (17), is that the last term, because

of equation (17), does not seen in LSSVR model (8). In other words, when ε = 0, classical LSSVR is obtained as a particular scenario of ε-LSSVR. The ε-LSSVR optimization problem can be solved using any convex algorithm that doesn’t necessitate taking derivatives of the variables in the optimization formulation. Finally, the b parameter can be calculated using equation (13). ε-insensitive Weighted Least Squares Support Vector Regression To increase robustness against outliers, it is a common practice in the literature to employ weighting techniques for training data points [13]. However, while ε-LSSVR suppresses noise compared to classical LSSVR, its performance against outliers remains suboptimal owing to the inherent quadratic error characteristic shared like LSSVR. In this section, we apply the weighting technique to ε-insensitive LSSVR to improve its performance against outliers, resulting in the following optimization formulation. (19)

(23) The robustness of the developed ε-WLSSVR model against outliers is attained by appropriately selecting the δs weights based on the relationship delineated in [13].

where the parameter is defined regarding Inter Quartile Range (IQR) denoting the difference between the the 25th percentile (lower quartile) and 75th percentile (upper quartile) of the error distribution [13]. (25) The choices of c1 = 2.5 and c2 = 3 are recognized as appropriate for a Gaussian error distribution. The minimization problem of ε-WLSSVR, as described by Equations (22) to (23), is convex, and therefore any convex algorithm from the existing literature can be employed for its solution, similar to ε-LSSVR.

(20) In this formulation, the parameters δs are employed to weight the influence of errors relative to data points on the loss function. The * symbol distinguishes optimization variables from those of ε-LSSVR. Initially, the δs remain constant in the initial execute of ε-WLSSVR and are subsequently determined as described in equation (24) to calibrate the effects of data point errors based on their distribution. Employing a derivation akin to that in Section 2, we obtain the ε-LSSVR optimization regarding Lagrange multipliers as follows.

Pruned Least Squares Support Vector Regression

As can be seen from (4), the decision hyperplane of LSSVR contains all the data in the training dataset. This means that LSSVR loses sparsity. The pruning approach for sparse LSSVR aims to obtain a sparse decision hyperplane with fewer data. For this, non-support vectors are extracted recursively from the training dataset according to some specified criteria (error rate, number of support vectors, etc.). First, an initial model is built based on the

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

entire training dataset and a spectrum of support vectors is plotted. The data that contributes the least to the model are omitted gradually. The reduced LSSVR is rebuilt with the remaining data. These processes are continued until the desired error value is reached [12], which is described in algorithm 1. Algorithm 1. PLSSVR

2. Omit a small amount of training samples (5% of the

training set) with the smallest value in the sorted support vector spectrum.

Weighted Pruned Least Squares Support Vector Regression

The weighted PLSSVR minimization problem in dual space is as follows [13].

The difference between PLSSVR and WPLSSVR is the δs parameter. The pruning approach is performed in WPLSSVR as follows [13]. Algorithm 2. WPLSSVR

1. Set L = Ltot equal to the number of training samples.

2. Given Ltot training samples, find an optimal combination (kernel parameter and C) by solving (3).

7. Delete a small amount of N sample points (5% of the

Ltot samples) that have the smallest values in the sorted spectrum.

Table 1. Optimization formulations for PLSSVR, WPLSSVR, ε-LSSVR, ε-WLSSVR, and LSSVR models in dual space representations Models

Wplssvr

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

9. Go to step 2 and retrain on the reduced training set,

unless the user-specified performance index degrades. Optimization formulations in dual space for PLSSVR, WPLSSVR, ε-LSSVR, ε-WLSSVR, and LSSVR models, are shown in Table 1. From Table 1 it can be clearly seen that the only dif-

are reported in Sections 3.2 and 3.3, respectively. Finally, in Section 3.4, the effects of the compared models on performance are discussed in detail and the observed findings are reported.

If ε=0, ε-LSSVR is equivalent to conventional LSSVR. In addition, PLSSVR and classical LSSVR are shown with the same optimization formula. However, an LSSVR model is created based on the whole training dataset, and then the number of samples is iteratively reduced until it reaches the specified error value and the PLSSVR model is obtained.

Experimental Setup

In all the compared models, the Gaussian function was selected as the kernel function [33]. Optimal values of regularization parameter (C) and kernel parameter (σ) were determined from sets and , respectively, by employing classical LSSVR with 5-fold cross-validation approach. Root Mean Square Error (RMSE), defined as follows, was used as the performance index in the study.

On the other hand, the only difference between ε-WLSSVR and WPLSSVR is again

equivalent to WPLSSVR. Similarly, all samples are used when creating the first model, and then the weighted and pruned model (WPLSSVR) is provided. Computational Complexity Analysis In academic literature, the computational complexity of algorithms is frequently evaluated by using Big-O notation. The computational complexity of the standard LSSVR solution (i.e., Ax=B) is O(kL2) using the conjugate gradient method [13]. Here, A=I+C and A∈RLxL with row(C)=k. As discussed in [31], iterative algorithms (such as PLSSVR and WPLSSVR) incur a cost around O(tL2); where t is considered the number of iterations. Together with the SMO technique [32], ε-WLSSVR and ε-LSSVR algorithms generate a cost around (pL). Because p is generally less than k, it provides an additional falling in the computational complexity of ε-WLSSVR and ε-LSSVR algorithms. If the matrix A requires a large amount of memory, it may be recomputed at each iteration step. However, this incurs a cost of O(L2) per step and decreases the memory requirement to O(L). It’s worth noting that the computational complexity can vary depending on the chosen kernel type and regularization parameter.

Results And Discussion

In this section, direct models (ε-LSSVR and ε-WLSSVR) and iterative models (PLSSVR and WPLSSVR) are comparatively analyzed on synthetic and real-life benchmark datasets. In order to ensure identical circumstances for all models, experiments were conducted using SMO algorithm [31, 32] in MATLAB 2012b environment on a PC with Intel Core I5 processors clocked at 3.0 GHz, 4 GB RAM, 64-bit Windows-7 operation system. The parameters and performance metric used in the comparison are given in section

Wplssvr

analyzed with 8 distinct real life benchmark datasets given in Table 3. Space, CPU small, and Mg are from Statlib collection1 while the remaining datasets are from the UCI machine learning repository2. To provide consistency, the inputs were normalized within the closed range [0,1]. However, no normalization was applied to the outputs, as scaling is carried out by the C and ε model parameters. For further evaluation, the performances of the ε-WLSSVR and ε-LSSVR models were compared with WPLSSVR and PLSSVR with respect to percentage of support vectors (%SV), the flatness (w), number of support vectors (#SV), computation time, and training and test approach error, with test performances of all models nearly equivalent. The experimental findings of LSSVR, ε-LSSVR, ε-WLSSVR, PLSSVR, and WPLSSVR, models on each dataset are presented in Table 4. The user-defined σ and C parameters of the model used for each dataset are presented under their respective names in the first column of Table 4. From Table 4, it is evident that the sparseness of the weighted and unvweighted ε-LSSVR models surpasses

Table 3. In-depth details regarding benchmark regression datasets Datasets

that of PLSSVR, WPLSSVR and LSSVR, across all datasets. For instance, in the Concrete dataset, PLSSVR, WPLSSVR, LSSVR, ε-LSSVR and ε-WLSSVR models required 356, 369, 450,197 and 103 support vectors, respectively. This indicates that ε-LSSVR, and ε-WLSSVR models require fewer support vectors to achieve almost the same test performance. Furthermore, the flatness measure of ε-WLSSVR is lower compared to all LSSVR methods, resulting in a sparser solution within the input space. For example, on the Boston dataset, PLSSVR, WPLSSVR, LSSVR, ε-LSSVR, and ε-WLSSVR have flatness measures of 246, 208, 258,172, and 141, respectively, under identical circumstances. Moreover, ε-LSSVR outperforms all models in terms of computational time. Given the superior performance of the ε-LSSVR and ε-WLSSVR methods, they can be applied to any engineering field such as energy [36] and mechanics [37]. It is evident from the last column of the Table 4 that ε-LSSVR requires less training time compared to LSSVR, PLSSVR and WPLSSVR. This difference can be attributed to the iterative nature of pruning-based algorithms, which continuously refine the objective function by removing less significant training examples until the user-specified error threshold is met. In contrast, during the training process, ε-LSSVR disregards training samples situated within the ε-insensitive region of the target function, all without the necessity of employing recursive (and computationally expensive) algorithms. The user-defined error tolerance parameter ε directly affects the sparsity and computational efficiency of the solution by controlling the number of support vectors. However, it’s important to note that ε-LSSVR, like LSSVR, remains sensitive to outliers. To address this limitation, the ε-WLSSVR model incorporates a weighting technique to enhance its robustness.

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/regression.html. http://archive.ics.uci.edu/ml/datasets.html.

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

Table 4. Experimental results on real word regression benchmark datasets Dataset

Wplssvr

Sigma J Eng Nat Sci, Vol. 42, No. 2, pp. 578−589, April, 2024

Ethics

LSSVR stands out as a computationally efficient method for tackling regression problems. Nevertheless, it does have two notable disadvantages. Firstly, LSSVR tends to lack of sparsity, resulting in every input sample treated as a support vector. Secondly, the solution obtained with LSSVR is sensitive to outliers and noise within the training dataset. In order to address these issues, theoretically derives ε-LSSVR from the LSSVR model. In addition, a weighted version, ε-WLSSVR, is introduced to improve robustness against outliers. To improve the sparsity of classical LSSVR, the performances of the PLSSVR, ε-LSSVR, WPLSSVR and ε-WLSSVR methods are analyzed in terms of generalization ability, sparsity, and computation time on both artificial and 8 different real-life datasets. Experimental results show that ε-LSSVR and ε-WLSSVR models achieve sparser solution representation compared to PLSSVR, WPLSSVR, and LSSVR across all datasets while maintaining nearly same generalization performance (RMSE test values). These models exhibit advantages over PLSSVR, WPLSSVR, and classical LSSVR regarding the number of support vectors. For example, in the space dataset, PLSSVR, WPLSSVR, LSSVR, ε-LSSVR and ε-WLSSVR models required 1135, 1094, 1600, 540 and 522 support vectors, respectively, to achieve almost the nearly identical circumstances. The norm of w (flatness measure) of both weighted and unweighted ε-LSSVR models is lower than those of all LSSVR models, indicating sparser solution representations in the primal space. For instance, in the CPU Small dataset, PLSSVR, WPLSSVR, LSSVR, ε-LSSVR, and ε-WLSSVR demonstrates flatness measures of 497, 460, 504, 346, and 276, respectively. Additionally, ε-LSSVR outperforms all models in terms of computational time. The regression models introduced in this study can be optimized using any optimization algorithm developed for nonlinear convex large-scale quadratic problems subject to linear inequalities/equalities, potentially increasing computational efficiency. Furthermore, these models can be applied to various engineering problems in which other regression models have shown success.

There are no ethical issues with the publication of this manuscript.

Share and Cite