# Fast Prediction with Sparse Multikernel LS-SVR Using Multiple Relevant Time Series and Its Application in Avionics System

Authors: Yang M. Guo; Pei He; Xiang T. Wang; Ya F. Zheng; Chong Liu; Xiao B. Cai
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Health trend prediction is critical to ensure the safe operation of highly reliable systems. However, complex systems often present complex dynamic behaviors and uncertainty, which makes it difficult to develop a precise physical prediction model. Therefore, time series is often used for prediction in this case. In this paper, in order to obtain better prediction accuracy in shorter computation time, we propose a new scheme which utilizes multiple relevant time series to enhance the completeness of the information and adopts a prediction model based on least squares support vector regression (LS-SVR) to perform prediction. In the scheme, we apply two innovative ways to overcome the drawbacks of the reported approaches. One is to remove certain support vectors by measuring the linear correlation to increase sparseness of LS-SVR; the other one is to determine the linear combination weights of multiple kernels by calculating the root mean squared error of each basis kernel. The results of prediction experiments indicate preliminarily that the proposed method is an effective approach for its good prediction accuracy and low computation time, and it is a valuable method in applications.


---

## Body

## 1. Introduction

Over the past decade, many diagnosis methodologies have been applied successfully in the domain of the reliability and safety of systems [1–7]. However, with the development of prognosis and health management (PHM), health condition diagnosis and prognosis technology has become the key technique for enhancement of reliability and safety of complex systems, especially for high reliability systems. However, these complex systems often exhibit multiple dynamic evolution behaviors, multilevel structures, and incomplete or uncertain information. Therefore, it is difficult to establish an accurate physical model. The time series analysis methods are often utilized to analyze and predict their health conditions in practice [7–10].Numerous methods have been reported to solve these problems, such as artificial neural networks (ANN) and support vector regression (SVR) [5, 6, 8, 10–14]. ANN has been used in several fields due to its universal approximation property. However, it may fall into local minimum traps and there is difficulty in determining the hidden layer size and the learning rate [15–17]. On the other hand, SVR aims at the global optimum and exhibits better prediction accuracy due to its implementation of the structural risk minimization principle [18, 19].SVR is an effective methodology for handling function estimation problems [13, 14, 20]. SVR is performed endogenously as a part of the optimization problem which has a unique solution of a (convex) quadratic programming (QP) problem. The solution of the QP problem provides the necessary information for choosing the most important data points, known as support vectors, among all the sample data. Based on the SVR formulation, support vectors uniquely define the estimated regression function.The application of SVR is initially developed for performing linear regression. The technique called the kernel trick has been extended to handle nonlinear regression applications [18–20]. Firstly, a kernel function φ(x) is used to map the input data x into an arbitrarily high dimensional feature space. Secondly, the linear SVR can be applied to create an approximate linear function in this arbitrarily high dimensional feature space. This way, nonlinear regression in the low dimensional input space corresponds to linear regression in the high dimensional feature space [21].The complexity of SVR depends not only on the input space dimension, but also on the number of sample data points. Therefore, when the sample data size is large, the quadratic programming (QP) problem becomes more complex, which will cost a lot of computation time. For this reason, least squares support vector regression (LS-SVR) was proposed by Suykens et al. [22]. In LS-SVR, the inequality constrains are replaced by equality constrains. This way, solving a QP is converted into solving linear equations. This will directly reduce training computational complexity. Thus, the training time of LS-SVR is reduced greatly.LS-SVR has been demonstrated by simulations and applications that it has better prediction results in most cases [23–26]. Moreover, in order to obtain abundant information on the physical system, researchers proposed multiple relevant time series prediction methods which achieve better prediction results than single time series prediction [27–29]. In the practice of health trend fast prediction for high reliability systems via LS-SVR with multiple relevant time series, we also need to overcome some serious drawbacks in reported methods as described below.(1)
Because all the training sample data are selected as support vectors, this leads to redundant information in the fitting of LS-SVR and lack of sparseness [30]. This drawback may influence the generalization capability of LS-SVR as well as the training complexity, which will increase prediction time, especially for multiple relevant time series.(2)
The information contained in the sample data is very often incomplete and complex. Thus, LS-SVR with a single kernel may not be sufficient to represent the information contained in data, and it cannot solve complex problems satisfactorily, especially for prediction with multiple relevant time series sample data. Moreover, how to select appropriate kernel functions remains unsolved in theory.Aiming at multiple relevant time series fast prediction with LS-SVR, we develop a new scheme to overcome the drawbacks and obtain better prediction performance, that is, accurate prediction results and fast prediction simultaneously. In this paper, combining the merits of LS-SVR with a single kernel for multiple relevant time series [27] and LS-SVR with multikernels for single time series [31], we propose a new fast prediction method to improve the prediction performance with multiple relevant time series and multiple basis kernels. This method provides a regression scheme which integrates multiple kernel learning and enforces sparseness from the training sample data. It includes two aspects.(1)
We apply a simple computational method to determine the combination weights of multiple basis kernels by calculating the root mean squared error (RMSE) of prediction with each basis kernel.(2)
We propose to prune the support vectors by judging the linear correlation among the samples in the high dimensional feature space. This scheme makes the information included in the sample data to be amply represented, reduces the number of support vectors, enhances the generalization performance, and shortens the prediction time with better or acceptable prediction accuracy.The remainder of the paper is organized as follows. Section2 gives a brief introduction of LS-SVR; Section 3 proposes the scheme in detail which includes pruning support vectors of LS-SVR and computing combination coefficients of multikernel, and then the fast prediction steps are presented; Section 4 shows three experiments and results analysis; and conclusions are given in Section 5.


## 2. A Brief Introduction of LS-SVR

Given the labeled data setS={(xi,yi),i=1,2,…,n}, where xi∈Rd is the input sample and yi∈R is the corresponding output label, the main idea of regression based on support vector machines theory is to map the input data to a higher dimensional feature space by means of a nonlinear mapping φ:Rd→F and solve the linear regression model shown as follows:(1)y^i=wTφxi+b,where y^i is the estimation of yi, f is the regression function, w is the coefficient value, and b is the bias term. The rationale behind the support vector regression (SVR) is to find w and b that optimize the generalization ability of the regressor by minimizing the regularized loss function. The case of SVR is also a convex quadratic programming (QP) problem, and it has a unique optimal solution. But the computation process is complex. So, many researchers proposed modifications of SVR.The LS-SVR method is a variant of the SVR [11]. Compared with SVR, LS-SVR preserves the following characteristics: the error variable ei is used to control deviations from the regression function and a squared loss function is used instead of the insensitive loss function. According to the approach of LS-SVR, the model estimate is given by the following optimization problem:(2)min⁡Jw,b=12w2+c2∑i=1nei2s.t.yi=wTφxi+b+eii=1,2,…,n.The above formulation is nothing but a regression cost function formulated in the feature space defined by the mapping functionφ(x). Parameter c determines the trade-off between the model complexity and the goodness of fit to the sample data. In LS-SVR [22], the Lagrangian function is presented as follows:(3)Lw,b,e,α=12wTw+12c∑i=1nei2-∑i=1nαiwTφxi+b+ei-yi,where αi is the ith Lagrange multiplier. Because (2) is also a convex function, it is obvious that the Slater constraint qualification holds [32]. Therefore, the optimal solution of (2) satisfies the KKT conditions. The optimality conditions are shown as follows:(4)∂L∂w=w-∑i=1nαiφ(xi)=0⟹w=∑i=1nαiφxi,∂L∂b=-∑i=1nαi=0⟹∑i=1nαi=0,∂L∂αi=wTφxi+b+ei-yi=0⟹yi=wTφxi+b+ei,∂L∂ei=cei-αi=0⟹ei=1cαi.After eliminatingei and w from (4), the KKT conditions can be expressed as(5)bα=01nT1nK+Ic-10y,where α=α1,α2,…,αnT, Ki,j=k(xi,xj)=φ(xi)Tφ(xj), 1n is an n-dimensional vector of all ones, I is a unity matrix, and y=y1,y2,…,ynT. Equation (5) can be factorized into a positive definite system [33].LetH=K+I/c, and we get the following equations from (5):(6)1nTα=0,(7)1nb+Hα=y.Multiplying1nTH-1 to both sides of (7), we get(8)1nTH-11b+1nTα=1nTH-1y.According to (6), (7), and (8), we have(9)1nTH-11b=1nTH-1y.The Lagrange dual variablesα and the bias term b are then obtained solely by(10)α=H-1y-1nb,b=1nTH-1y1nTH-11n-1.Any unlabeled inputx can be subsequently estimated by the following function:(11)y^x=∑i=1nαiφxiTφx+b=∑i=1nαikxi,x+b.For multiple relevant time series, we can consider all sample data at the same time point as one multidimensional vector, which means the input will become multidimensional vectors.


## 3. Proposed Fast Prediction Method for Multiple Relevant Time Series

In order to obtain better prediction performance, we use multiple relevant time series and multiple kernel learning (MKL) to fully utilize the information contained in data. In this section, we propose an improved scheme with multikernel LS-SVR to accomplish fast prediction. This scheme utilizes new approaches to compute the combination coefficients of multikernel and to decrease the number of support vectors.


### 3.1. Combination Coefficients of Multiple Kernels

The kernel function and the corresponding kernel parameters are the key issues affecting the model prediction accuracy. An effective kernel function should represent sample data adaptively. General kernel methods use a single kernel function and choose the same corresponding parameter for the whole sample data set. However, the distribution of the sample data in a different mapping space is different. So, MKL was proposed by Lanckriet et al. [34].MKL is an active research topic in the field of machine learning. It provides a more flexible framework than a single kernel and mines information in data more adaptively and effectively, especially in improving performance of the regression function.In MKL framework, a combined kernel function is defined as the weighted sum of the individual basis kernels. MKL aims to optimize kernel weights while training the SVR-based methods, such as LS-SVR with multikernel [28, 31, 35]. Though researchers have proposed a variety of methods of integrating multiple kernels from three aspects, which are the composite kernels, the multiscale kernels, and the infinite kernels [35], linear convex combination of basis kernels is still one of the most frequently used methods. For this method, each basis kernel can exploit the full set of features or just use a subset of features. In this paper, using the equations provided by Sonnenburg et al. [36], we consider the combined kernel expressed as follows:(12)kxp,xq=∑j=1mμjkjxp,xqs.t.∑j=1mμj=1μj≥0j=1,2,…,m,where m is the number of basis kernels and μj is the combining weight for the jth basis kernel. According to the properties of kernel functions [37], matrix k is symmetric positive semidefinite; that is, k⪰0. We need to normalize all kernel matrices kj by replacing kjxp,xq with the following equation to get unit diagonal matrices:(13)kjxp,xq⟶kjxp,xqkjxp,xpkjxq,xq.Based on MKL, the LS-SVR optimization problem with the newk matrix derived from (2)–(4) is represented as follows:(14)min⁡w,b,emax⁡αLw,b,e,α=max⁡αmin⁡w,b,eLw,b,e,α.We then transform the new kernel into the matrix formK=∑j=1mμjKj. When the weights μj are constrained to be nonnegative and Kj are positive semidefinite, the constraint ∑j=1mKj⪰0 is satisfied automatically. In this case, with respect to the corresponding parameters motivated by Lanckriet et al. [34] and Ye et al. [38], the solution of (14) can be presented as follows:(15)min⁡μ,κ12y+κ1nT∑j=1mμjKj+Ic-1y+κ1ns.t.∑j=1mμjKj⪰0,∑j=1mμj=1.Using the Schur complement lemma [32, 39], (15) can be cast to the form of semidefinite program (SDP), and then we reduce the SDP under strict constraints to a quadratically constrained quadratic program (QCQP). The objective function of QCQP is convex in μ and α. In other words, the minimization problem is strictly feasible in μ, and the maximization problem is feasible in α [34, 40]. Such a QCQP problem can be solved efficiently by the interior point methods. The obtained dual variables can be used to fix the optimal kernel coefficients.For MKL, with linear convex combination of basis kernels, the key is to obtain the optimal combing weightsμj. Some researchers proposed to simultaneously optimize both the combing weights μj and the parameters of LS-SVR, for example, regularization of the parameter c and the basis kernels parameters and so on. Now, the more common way is to adopt optimization software packages, such as MOSEK [41], which can solve the primal and dual problems simultaneously using the interior point methods. But all these solution methods always require much computation time and are complex for applications in practice.Because the combination of the multiple kernels is a linear combination in this paper, the realistic application will be taken into full account; here, we propose a simple approach to determine the combination weights of the new kernel by calculating the root mean squared error (RMSE) of prediction using each single basis kernel; that is, a smaller RMSE value will result in a bigger weight value.That the prediction value has less relative error means that the LS-SVR model with the basis kernel is a better model. Thus, the RMSE of prediction is used as the evaluation criterion. The RMSE of the multiple variables prediction is defined as follows:(16)δRMSE=1nr∑i=1r∑k=1nyik-y^ik2,where r is the number of relevant variables, n is the number of the original training sample data points, and yi(k) and y^i(k) are the prediction and the actual values, respectively. The combination weights μj of the multiple kernels are computed as follows:(17)μj=∑i=1mδi-δjm-1∑i=1mδi,where δj is the prediction RMSE of the jth kernel, ∑i=1mδi is the sum RMSE of all basis kernels, and ∑i=1mδi-δj presents the contribution of the jth kernel.


### 3.2. Linear Correlation-Based Method of Pruning Support Vectors

LS-SVR has a major drawback that is lack of sparseness [42] because almost each sample data point will be a support vector. In order to get a sparse solution, several methods have been proposed. For example, Suykens et al. [43] proposed a pruning scheme based on support vector spectrum that prunes those support vectors with smaller Lagrange multiplier values. de Kruif and de Vries [42] introduced a procedure of pruning according to the smallest approximation error when the support vector is omitted. Hoegaerts et al. [44] improved the method proposed by Kruif et al. They suggested a variant that improved the performance significantly and assessed its relative performance compared with two other subset selection schemes. Keerthi and Shevade [45] extended the well-known SMO algorithm to LS-SVM to solve problems with large training samples. Based on this study, Zeng and Chen [46] proposed a new pruning algorithm for sparse LS-SVR via SMO algorithm. Jiao et al. [47] presented two fast sparse approximation schemes for LS-SVR.The basic idea of the many approaches reviewed above is to find the support vector with the smaller indicator value and remove the corresponding training sample. It is obvious that the idea is simple, but all the reported schemes require computation duplication in solving linear equations [48, 49]. For this reason, these schemes are not suitable for fast prediction. Thus, Yaakov et al. [50] and Cawley and Talbot [51] presented a more efficient scheme by evaluating the linear correlation among the samples in the mapping space. The merits of [48–51] are that the linear correlation-based sparseness strategy ensures the information in the data to be maximally retained and the sparseness prediction model improves the generalization capability to improve the model’s adaptability to noisy sample data. So, the proposed method bases on [48–51] and uses the following idea.Suppose thatφ(xk) is one of the n support vectors in the high dimensional feature space. If and only if λi=0 (i≠k), the following equation holds:(18)φxk≠∑i=1,i≠knλiφxi.Here,xk is called base vector (BV) and the set consisting of xk is called base vector set (BVS). In order to obtain sparseness in LS-SVR, any support vector linearly related to the BV can be deleted. Assume that there are n support vectors in the sample data and the BVS consists of l support vectors (l<n). If the high dimensional mapping φ(xt) of the (l+1)th sample xt cannot be represented by a linear combination of the l support vectors, it will be added into the BV; otherwise, it does not join the BVS.In many real cases, the new sample data may not be absolutely linearly dependent on the existing support vectors. However, it is very similar to a linear combination of the existing support vectors; that is, for samplext, we will be content with finding coefficients λt,i with at least one nonzero element satisfying the approximate linear dependence condition (19)δt=∑i=1lλt,iφxi-φxt2≤υ,where υ is a small positive constant. Then, [48, 50] rewrote (19) into the following optimization problem:(20)min⁡λtδt=∑i=1l∑j=1lλt,iφxiλt,jφxjT-2φxt∑i=1lλt,iφxiT+φxtφxtT=∑i=1l∑j=1lλt,iλt,jkxi,xj-2∑i=1lλt,ikxt,xi+kxt,xt.By minimizing the left-hand side of (20), we can obtain the linear correlation coefficients λt=λt,1,λt,2,…,λt,lT simultaneously.To sacrifice the optimality ofλt in return for a reduction in the size of the sample data, a l2 norm regularization term of the form γλt2 is added to the minimization problem defined in (20), ending up with the following optimization problem:(21)min⁡λtδt=∑i=1l∑j=1lλt,iλt,jkxi,xj-2∑i=1lλt,ikxt,xi+kxt,xt+γλt2,where γ is a positive constant coefficient. It is obvious that the sparseness level and the model accuracy are controlled by the parameters υ and γ. But no rules have been reported in the literature for the selection of these two parameters.In this paper, we selectυ=λt2/lc2, and then we propose a new sparseness method, which is described as follows:(22)δt=∑i=1lλt,iφxi-φxt2≤λt2lc2.Equation (22) can be solved as the following optimization problem:(23)min⁡λtδt′=∑i=1l∑j=1lλt,iφxiλt,jφxjTmin⁡λtδ′t=-2φxt∑i=1lλt,iφxiT+φxtφxtT-λt2lc2min⁡λtδ′t=∑i=1l∑j=1lλt,iλt,jkxi,xjmin⁡λtδ′t=-2∑i=1lλt,ikxt,xi+kxt,xt-λt2lc2s.t.λt,i≤c,where c is the same as the LS-SVR parameter c. Solving (23) and if δt is bigger than λt2/lc2, add xt into the BVS; otherwise, xt is dropped.Following the ideas outlined above, we propose the following approach to prune support vectors. A detailed pseudocode account of the proposed method is given in  Pseudocode1.Pseudocode 1:Pseudocode of the proposed pruning method.
parameters:l, c, support vectors set x1,x2,…,xt,…,xn
Initialize:l=2,  c equals to the LS-SVR parameter c
(1) choose the initial BV:x1 and x2;
(2) establish the initial BVS:x1,x2;
(3) get new support vectorxt;
(4) approximate the linear dependence compute  via (23)
ifδt′>0
l=l+1,
xl=xt,
addxl into the BVS,
else
dropxt,
l=l
(5) go back to (3).Based on the pseudocode, we choose two sample data points corresponding to the two biggest Lagrange multipliers as the initial BV firstly, and then if the new nonlinear mappingφ(xr) depends linearly on the selected support vectors, it can be dropped; that is, if the new sample data xr satisfies the relation formula(24)φxr=∑j=1mλjφxj,where λi is a constant coefficient and m is the number of independent support vectors, then the new data point is dropped. Combining (24) with (11), we have(25)y^x=∑i=1,i≠rnαikxi,x+αrkxr,x+b=∑i=1,i≠rnαiφxiφx+αrφxrφx+b=∑i=1,i≠rnαiφxiφx+αr∑j=1mλjφxjφx+b,where xj is the sample corresponding to BV. Then, we will get the new regression function with BV, and it can be described by(26)y^x=∑i=1mβikxi,x+b,where βi is combined with Lagrange dual variable coefficient and linear combination coefficient.The proposed method combines advantages of removing smaller support vectors and the advantages of [48–51]. It can retain much of the useful information in the sample data. Thus, the prediction accuracy will not be sacrificed too much while the model’s generalization ability is improved. Although this processing step would increase the calculation time for the LS-SVR model, the training time will not be increased much because almost each middle parameter’s value is already computed and stored in the process of setting up the prediction model, and the prediction time will be reduced because of fewer support vectors. Moreover, the proposed method can avoid a difficult problem in Yaakov’s scheme, the parameters selection, because no rules have been reported to fix the problem. Thus, it may be more valuable in practice.


### 3.3. Prediction Steps of the Proposed Method

By applying the scheme proposed above, we can set up the LS-SVR model with multikernel for multiple relevant time series, called the improved MKLS-SVR (IMKLS-SVR), and we will use this new model to carry out multiple relevant time series prediction. Here, we look at the multiple relevant time series as an integral whole; that is, they are taken as a multidimensional input [52, 53], and the prediction is executed simultaneously.The prediction steps can be described as follows:(1)
choose appropriate basis kernels;(2)
determineμj and then obtain the combination kernel;(3)
computeK, H and α, b;(4)
assess the linear correlation and prune support vectors and compute new BV-based Lagrange multiplierβi;(5)
set up the regression function and perform prediction.


## 3.1. Combination Coefficients of Multiple Kernels

The kernel function and the corresponding kernel parameters are the key issues affecting the model prediction accuracy. An effective kernel function should represent sample data adaptively. General kernel methods use a single kernel function and choose the same corresponding parameter for the whole sample data set. However, the distribution of the sample data in a different mapping space is different. So, MKL was proposed by Lanckriet et al. [34].MKL is an active research topic in the field of machine learning. It provides a more flexible framework than a single kernel and mines information in data more adaptively and effectively, especially in improving performance of the regression function.In MKL framework, a combined kernel function is defined as the weighted sum of the individual basis kernels. MKL aims to optimize kernel weights while training the SVR-based methods, such as LS-SVR with multikernel [28, 31, 35]. Though researchers have proposed a variety of methods of integrating multiple kernels from three aspects, which are the composite kernels, the multiscale kernels, and the infinite kernels [35], linear convex combination of basis kernels is still one of the most frequently used methods. For this method, each basis kernel can exploit the full set of features or just use a subset of features. In this paper, using the equations provided by Sonnenburg et al. [36], we consider the combined kernel expressed as follows:(12)kxp,xq=∑j=1mμjkjxp,xqs.t.∑j=1mμj=1μj≥0j=1,2,…,m,where m is the number of basis kernels and μj is the combining weight for the jth basis kernel. According to the properties of kernel functions [37], matrix k is symmetric positive semidefinite; that is, k⪰0. We need to normalize all kernel matrices kj by replacing kjxp,xq with the following equation to get unit diagonal matrices:(13)kjxp,xq⟶kjxp,xqkjxp,xpkjxq,xq.Based on MKL, the LS-SVR optimization problem with the newk matrix derived from (2)–(4) is represented as follows:(14)min⁡w,b,emax⁡αLw,b,e,α=max⁡αmin⁡w,b,eLw,b,e,α.We then transform the new kernel into the matrix formK=∑j=1mμjKj. When the weights μj are constrained to be nonnegative and Kj are positive semidefinite, the constraint ∑j=1mKj⪰0 is satisfied automatically. In this case, with respect to the corresponding parameters motivated by Lanckriet et al. [34] and Ye et al. [38], the solution of (14) can be presented as follows:(15)min⁡μ,κ12y+κ1nT∑j=1mμjKj+Ic-1y+κ1ns.t.∑j=1mμjKj⪰0,∑j=1mμj=1.Using the Schur complement lemma [32, 39], (15) can be cast to the form of semidefinite program (SDP), and then we reduce the SDP under strict constraints to a quadratically constrained quadratic program (QCQP). The objective function of QCQP is convex in μ and α. In other words, the minimization problem is strictly feasible in μ, and the maximization problem is feasible in α [34, 40]. Such a QCQP problem can be solved efficiently by the interior point methods. The obtained dual variables can be used to fix the optimal kernel coefficients.For MKL, with linear convex combination of basis kernels, the key is to obtain the optimal combing weightsμj. Some researchers proposed to simultaneously optimize both the combing weights μj and the parameters of LS-SVR, for example, regularization of the parameter c and the basis kernels parameters and so on. Now, the more common way is to adopt optimization software packages, such as MOSEK [41], which can solve the primal and dual problems simultaneously using the interior point methods. But all these solution methods always require much computation time and are complex for applications in practice.Because the combination of the multiple kernels is a linear combination in this paper, the realistic application will be taken into full account; here, we propose a simple approach to determine the combination weights of the new kernel by calculating the root mean squared error (RMSE) of prediction using each single basis kernel; that is, a smaller RMSE value will result in a bigger weight value.That the prediction value has less relative error means that the LS-SVR model with the basis kernel is a better model. Thus, the RMSE of prediction is used as the evaluation criterion. The RMSE of the multiple variables prediction is defined as follows:(16)δRMSE=1nr∑i=1r∑k=1nyik-y^ik2,where r is the number of relevant variables, n is the number of the original training sample data points, and yi(k) and y^i(k) are the prediction and the actual values, respectively. The combination weights μj of the multiple kernels are computed as follows:(17)μj=∑i=1mδi-δjm-1∑i=1mδi,where δj is the prediction RMSE of the jth kernel, ∑i=1mδi is the sum RMSE of all basis kernels, and ∑i=1mδi-δj presents the contribution of the jth kernel.


## 3.2. Linear Correlation-Based Method of Pruning Support Vectors

LS-SVR has a major drawback that is lack of sparseness [42] because almost each sample data point will be a support vector. In order to get a sparse solution, several methods have been proposed. For example, Suykens et al. [43] proposed a pruning scheme based on support vector spectrum that prunes those support vectors with smaller Lagrange multiplier values. de Kruif and de Vries [42] introduced a procedure of pruning according to the smallest approximation error when the support vector is omitted. Hoegaerts et al. [44] improved the method proposed by Kruif et al. They suggested a variant that improved the performance significantly and assessed its relative performance compared with two other subset selection schemes. Keerthi and Shevade [45] extended the well-known SMO algorithm to LS-SVM to solve problems with large training samples. Based on this study, Zeng and Chen [46] proposed a new pruning algorithm for sparse LS-SVR via SMO algorithm. Jiao et al. [47] presented two fast sparse approximation schemes for LS-SVR.The basic idea of the many approaches reviewed above is to find the support vector with the smaller indicator value and remove the corresponding training sample. It is obvious that the idea is simple, but all the reported schemes require computation duplication in solving linear equations [48, 49]. For this reason, these schemes are not suitable for fast prediction. Thus, Yaakov et al. [50] and Cawley and Talbot [51] presented a more efficient scheme by evaluating the linear correlation among the samples in the mapping space. The merits of [48–51] are that the linear correlation-based sparseness strategy ensures the information in the data to be maximally retained and the sparseness prediction model improves the generalization capability to improve the model’s adaptability to noisy sample data. So, the proposed method bases on [48–51] and uses the following idea.Suppose thatφ(xk) is one of the n support vectors in the high dimensional feature space. If and only if λi=0 (i≠k), the following equation holds:(18)φxk≠∑i=1,i≠knλiφxi.Here,xk is called base vector (BV) and the set consisting of xk is called base vector set (BVS). In order to obtain sparseness in LS-SVR, any support vector linearly related to the BV can be deleted. Assume that there are n support vectors in the sample data and the BVS consists of l support vectors (l<n). If the high dimensional mapping φ(xt) of the (l+1)th sample xt cannot be represented by a linear combination of the l support vectors, it will be added into the BV; otherwise, it does not join the BVS.In many real cases, the new sample data may not be absolutely linearly dependent on the existing support vectors. However, it is very similar to a linear combination of the existing support vectors; that is, for samplext, we will be content with finding coefficients λt,i with at least one nonzero element satisfying the approximate linear dependence condition (19)δt=∑i=1lλt,iφxi-φxt2≤υ,where υ is a small positive constant. Then, [48, 50] rewrote (19) into the following optimization problem:(20)min⁡λtδt=∑i=1l∑j=1lλt,iφxiλt,jφxjT-2φxt∑i=1lλt,iφxiT+φxtφxtT=∑i=1l∑j=1lλt,iλt,jkxi,xj-2∑i=1lλt,ikxt,xi+kxt,xt.By minimizing the left-hand side of (20), we can obtain the linear correlation coefficients λt=λt,1,λt,2,…,λt,lT simultaneously.To sacrifice the optimality ofλt in return for a reduction in the size of the sample data, a l2 norm regularization term of the form γλt2 is added to the minimization problem defined in (20), ending up with the following optimization problem:(21)min⁡λtδt=∑i=1l∑j=1lλt,iλt,jkxi,xj-2∑i=1lλt,ikxt,xi+kxt,xt+γλt2,where γ is a positive constant coefficient. It is obvious that the sparseness level and the model accuracy are controlled by the parameters υ and γ. But no rules have been reported in the literature for the selection of these two parameters.In this paper, we selectυ=λt2/lc2, and then we propose a new sparseness method, which is described as follows:(22)δt=∑i=1lλt,iφxi-φxt2≤λt2lc2.Equation (22) can be solved as the following optimization problem:(23)min⁡λtδt′=∑i=1l∑j=1lλt,iφxiλt,jφxjTmin⁡λtδ′t=-2φxt∑i=1lλt,iφxiT+φxtφxtT-λt2lc2min⁡λtδ′t=∑i=1l∑j=1lλt,iλt,jkxi,xjmin⁡λtδ′t=-2∑i=1lλt,ikxt,xi+kxt,xt-λt2lc2s.t.λt,i≤c,where c is the same as the LS-SVR parameter c. Solving (23) and if δt is bigger than λt2/lc2, add xt into the BVS; otherwise, xt is dropped.Following the ideas outlined above, we propose the following approach to prune support vectors. A detailed pseudocode account of the proposed method is given in  Pseudocode1.Pseudocode 1:Pseudocode of the proposed pruning method.
parameters:l, c, support vectors set x1,x2,…,xt,…,xn
Initialize:l=2,  c equals to the LS-SVR parameter c
(1) choose the initial BV:x1 and x2;
(2) establish the initial BVS:x1,x2;
(3) get new support vectorxt;
(4) approximate the linear dependence compute  via (23)
ifδt′>0
l=l+1,
xl=xt,
addxl into the BVS,
else
dropxt,
l=l
(5) go back to (3).Based on the pseudocode, we choose two sample data points corresponding to the two biggest Lagrange multipliers as the initial BV firstly, and then if the new nonlinear mappingφ(xr) depends linearly on the selected support vectors, it can be dropped; that is, if the new sample data xr satisfies the relation formula(24)φxr=∑j=1mλjφxj,where λi is a constant coefficient and m is the number of independent support vectors, then the new data point is dropped. Combining (24) with (11), we have(25)y^x=∑i=1,i≠rnαikxi,x+αrkxr,x+b=∑i=1,i≠rnαiφxiφx+αrφxrφx+b=∑i=1,i≠rnαiφxiφx+αr∑j=1mλjφxjφx+b,where xj is the sample corresponding to BV. Then, we will get the new regression function with BV, and it can be described by(26)y^x=∑i=1mβikxi,x+b,where βi is combined with Lagrange dual variable coefficient and linear combination coefficient.The proposed method combines advantages of removing smaller support vectors and the advantages of [48–51]. It can retain much of the useful information in the sample data. Thus, the prediction accuracy will not be sacrificed too much while the model’s generalization ability is improved. Although this processing step would increase the calculation time for the LS-SVR model, the training time will not be increased much because almost each middle parameter’s value is already computed and stored in the process of setting up the prediction model, and the prediction time will be reduced because of fewer support vectors. Moreover, the proposed method can avoid a difficult problem in Yaakov’s scheme, the parameters selection, because no rules have been reported to fix the problem. Thus, it may be more valuable in practice.


## 3.3. Prediction Steps of the Proposed Method

By applying the scheme proposed above, we can set up the LS-SVR model with multikernel for multiple relevant time series, called the improved MKLS-SVR (IMKLS-SVR), and we will use this new model to carry out multiple relevant time series prediction. Here, we look at the multiple relevant time series as an integral whole; that is, they are taken as a multidimensional input [52, 53], and the prediction is executed simultaneously.The prediction steps can be described as follows:(1)
choose appropriate basis kernels;(2)
determineμj and then obtain the combination kernel;(3)
computeK, H and α, b;(4)
assess the linear correlation and prune support vectors and compute new BV-based Lagrange multiplierβi;(5)
set up the regression function and perform prediction.


## 4. Experiments and Result Analysis

In order to examine the prediction efficiency of the proposed method, we provide simulation and application experiments. All the experiments use MatlabR2011b with LS-SVMlab1.8 Toolbox (the software and guide book can be downloaded fromhttp://www.esat.kuleuven.be/sista/lssvmlab) under Windows XP operating system.


### 4.1. Simulation Experiments and Results Analysis

The simulation experiments include two parts. One is to test the proposed method based on linear correlation (Experiment1) and the other is to test the proposed computing method of multikernel combination coefficients (Experiment 2). All tests are repeated 50 times with the results averaged. The two experiments to test the proposed scheme are presented below in detail.Experiment 1.
We first used LS-SVR to learn the 1-dimensional functionx=sin(t)/t defined in the interval t∈[0.1,10]. We collect 100 values of x as our time series. The data points from 1 to 60 in the time series are taken as the 50 initial training sample data points. The first sample data set consists of points 1 through 11, with the first 10 as the input sample vector and the 11th point as the output. The second sample data set consists of points 2 through 12, with the points 2 through 11 as the input sample vector and the 12th point as the output. This way we have 50 training data points out of the first 60 data points.In order to test the efficiency of the proposed pruning method, we compare it with the method which Yaakov et al. presented in [50]. Here, the kernel is Gaussian RBF kernel k(x,y)=exp⁡(-x-y2/2σ2) with standard deviation σ=1. The other parameters are υ=0.01 and υ=0.001. In this experiment, the training time, prediction time, and prediction mean RMSE are compared. The results are shown in Table 1.Table 1
Prediction results of simulation Experiment1.
Method
Training time (s)
Prediction time (s)
Mean RMSE
LS-SVR without sparseness
0.001053
0.018954
1.5032
Method of  [50]
υ=0.01
0.002072
0.009461
1.8673
υ=0.001
0.003179
0.009241
1.7780
The proposed method
0.002242
0.009407
1.6160Table1 shows that the proposed method attains good accuracy with less computation time. In particular, it can reduce the prediction time greatly without losing much prediction accuracy. In addition, this method avoids the problem of parameter selection.Experiment 2.
Henon function is a typical time series, and its variables influence each other. Its corresponding differential equations are given as follows:(27)xt+1=1-ax2t+yt,yt+1=bxt.Leta=1.4 and b=0.3, and points of the initialization of x and y are [0.1,0.1]. 100 data points of variables x and y are selected, respectively, as sample time series. We set the first 80 data points as training samples. We also take any continuous 11 data points of x and y as a sample, where the first 10 data points compose an input sample vector and the last one is the output vector; that is, in this simulation experiment, we have 70 training data points for each variable. And then we predict number 81 to number 100 time series data using the trained model.In order to test the practicability of the proposed computing method of multikernel combination coefficients, we choose one linear kernel functionk(x,y)=xTy representing global information and two Gaussian RBF functions (σ2 equal to 5 and 9, resp.) representing local information [54] and establish multikernel LS-SVR, respectively, by two approaches which are the proposed method and the one described in [31]. After determining the new combination weights of the basis kernels, we compare the training time, prediction time, and prediction mean RMSE with LS-SVR (with single Gaussian RBF kernel, σ2=5) and multikernel LS-SVR. The results are shown in Table 2.Table 2
Prediction results of simulation Experiment2.
Method
Training time (s)
Prediction time (s)
Mean RMSE
x
y
LS-SVR with RBF kernel
1.273911
1.264925
3.1418
4.6412
Method of [31]
2.783566
0.962933
1.4001
0.8322
The Proposed method
1.659715
0.877201
1.5273
1.0125The simulation results in Table2 show that the proposed method can reduce computation time more than the other two methods, although it does not achieve the best prediction results. The proposed method has good prediction accuracy and requires less prediction time.


### 4.2. Avionics System Experiment and Results Analysis

In this section, we use a certain circuit of avionics system (shown in Figure1) to demonstrate the efficiency of the proposed method with multiple relevant time series. The circuit is used to compare the prediction time and prediction accuracy with the traditional LS-SVR model described in [25] and LS-SVR with multikernel, called MKLS-SVR, shown in [31].Figure 1
Local circuit of avionics system.In order to collect the sample data, we measure voltage values at three measuring points named point A, point B, and point C (with pentagram representations, see Figure1). The acquisition step is 0.1 s with time unit of 4.5 s.We take the first 30 measured data points group as the training samples. Again each sample set consists of any continuous 11 data points; that is, we have 20 groups of training data. And then we predict number 31 to number 45 time series data. Here, we look at the time series obtained from point A, point B, and point C (see Figure1) as an integral whole; that is, they are examined as a multidimensional input and do prediction simultaneously. We run 100 times of prediction and take the average of them. Moreover, all the parameters of kernel functions are jointly optimized with the traditional grid search method, where the search range for c and σ2 is [0.01,2000], and the prediction performance is measured by RMSE.Gaussian RBF kernel is adopted as the kernel function of traditional LS-SVR. For MKL-SVR and IMKLS-SVR, we also choose one linear kernel function and two Gaussian RBF functions. The prediction results are shown in Figures2, 3, and 4 (dimensions omitted) and the mean prediction RMSE for three data sets are reported in Table 3.Table 3
Prediction results of application experiment.
Method
Mean RMSE
Mean total prediction time reduced(compare with LS-SVR)
x
y
z
LS-SVR of [25]
3.0662
1.5252
2.3811
MKLS-SVR of [31]
2.4722
0.7416
1.8869
6.18%
The proposed IMKL-SVR
2.5668
0.8651
1.8412
13.83%Figure 2
Prediction results of data collected from point A (see Figure1).Figure 3
Prediction results of data collected from point B (see Figure1).Figure 4
Prediction results of data collected from point C (see Figure1).Figures2–4 and Table 3 show that (1) compared with traditional LS-SVR, the proposed method, IMKLS-SVR, has good prediction accuracy. This may be due to the fact that the proposed method uses relevant information fully and maps them in multikernel high dimensional space; (2) in spite of almost the same accuracy with MKLS-SVR, IMKLS-SVR requires less prediction time than MKLS-SVR and LS-SVR, especially than LS-SVR. This may be due to the fact that we have reduced the support vectors of sample data by measuring the linear correlation of the sample data. Thus, IMKLS-SVR is more valuable in application.


## 4.1. Simulation Experiments and Results Analysis

The simulation experiments include two parts. One is to test the proposed method based on linear correlation (Experiment1) and the other is to test the proposed computing method of multikernel combination coefficients (Experiment 2). All tests are repeated 50 times with the results averaged. The two experiments to test the proposed scheme are presented below in detail.Experiment 1.
We first used LS-SVR to learn the 1-dimensional functionx=sin(t)/t defined in the interval t∈[0.1,10]. We collect 100 values of x as our time series. The data points from 1 to 60 in the time series are taken as the 50 initial training sample data points. The first sample data set consists of points 1 through 11, with the first 10 as the input sample vector and the 11th point as the output. The second sample data set consists of points 2 through 12, with the points 2 through 11 as the input sample vector and the 12th point as the output. This way we have 50 training data points out of the first 60 data points.In order to test the efficiency of the proposed pruning method, we compare it with the method which Yaakov et al. presented in [50]. Here, the kernel is Gaussian RBF kernel k(x,y)=exp⁡(-x-y2/2σ2) with standard deviation σ=1. The other parameters are υ=0.01 and υ=0.001. In this experiment, the training time, prediction time, and prediction mean RMSE are compared. The results are shown in Table 1.Table 1
Prediction results of simulation Experiment1.
Method
Training time (s)
Prediction time (s)
Mean RMSE
LS-SVR without sparseness
0.001053
0.018954
1.5032
Method of  [50]
υ=0.01
0.002072
0.009461
1.8673
υ=0.001
0.003179
0.009241
1.7780
The proposed method
0.002242
0.009407
1.6160Table1 shows that the proposed method attains good accuracy with less computation time. In particular, it can reduce the prediction time greatly without losing much prediction accuracy. In addition, this method avoids the problem of parameter selection.Experiment 2.
Henon function is a typical time series, and its variables influence each other. Its corresponding differential equations are given as follows:(27)xt+1=1-ax2t+yt,yt+1=bxt.Leta=1.4 and b=0.3, and points of the initialization of x and y are [0.1,0.1]. 100 data points of variables x and y are selected, respectively, as sample time series. We set the first 80 data points as training samples. We also take any continuous 11 data points of x and y as a sample, where the first 10 data points compose an input sample vector and the last one is the output vector; that is, in this simulation experiment, we have 70 training data points for each variable. And then we predict number 81 to number 100 time series data using the trained model.In order to test the practicability of the proposed computing method of multikernel combination coefficients, we choose one linear kernel functionk(x,y)=xTy representing global information and two Gaussian RBF functions (σ2 equal to 5 and 9, resp.) representing local information [54] and establish multikernel LS-SVR, respectively, by two approaches which are the proposed method and the one described in [31]. After determining the new combination weights of the basis kernels, we compare the training time, prediction time, and prediction mean RMSE with LS-SVR (with single Gaussian RBF kernel, σ2=5) and multikernel LS-SVR. The results are shown in Table 2.Table 2
Prediction results of simulation Experiment2.
Method
Training time (s)
Prediction time (s)
Mean RMSE
x
y
LS-SVR with RBF kernel
1.273911
1.264925
3.1418
4.6412
Method of [31]
2.783566
0.962933
1.4001
0.8322
The Proposed method
1.659715
0.877201
1.5273
1.0125The simulation results in Table2 show that the proposed method can reduce computation time more than the other two methods, although it does not achieve the best prediction results. The proposed method has good prediction accuracy and requires less prediction time.


## 4.2. Avionics System Experiment and Results Analysis

In this section, we use a certain circuit of avionics system (shown in Figure1) to demonstrate the efficiency of the proposed method with multiple relevant time series. The circuit is used to compare the prediction time and prediction accuracy with the traditional LS-SVR model described in [25] and LS-SVR with multikernel, called MKLS-SVR, shown in [31].Figure 1
Local circuit of avionics system.In order to collect the sample data, we measure voltage values at three measuring points named point A, point B, and point C (with pentagram representations, see Figure1). The acquisition step is 0.1 s with time unit of 4.5 s.We take the first 30 measured data points group as the training samples. Again each sample set consists of any continuous 11 data points; that is, we have 20 groups of training data. And then we predict number 31 to number 45 time series data. Here, we look at the time series obtained from point A, point B, and point C (see Figure1) as an integral whole; that is, they are examined as a multidimensional input and do prediction simultaneously. We run 100 times of prediction and take the average of them. Moreover, all the parameters of kernel functions are jointly optimized with the traditional grid search method, where the search range for c and σ2 is [0.01,2000], and the prediction performance is measured by RMSE.Gaussian RBF kernel is adopted as the kernel function of traditional LS-SVR. For MKL-SVR and IMKLS-SVR, we also choose one linear kernel function and two Gaussian RBF functions. The prediction results are shown in Figures2, 3, and 4 (dimensions omitted) and the mean prediction RMSE for three data sets are reported in Table 3.Table 3
Prediction results of application experiment.
Method
Mean RMSE
Mean total prediction time reduced(compare with LS-SVR)
x
y
z
LS-SVR of [25]
3.0662
1.5252
2.3811
MKLS-SVR of [31]
2.4722
0.7416
1.8869
6.18%
The proposed IMKL-SVR
2.5668
0.8651
1.8412
13.83%Figure 2
Prediction results of data collected from point A (see Figure1).Figure 3
Prediction results of data collected from point B (see Figure1).Figure 4
Prediction results of data collected from point C (see Figure1).Figures2–4 and Table 3 show that (1) compared with traditional LS-SVR, the proposed method, IMKLS-SVR, has good prediction accuracy. This may be due to the fact that the proposed method uses relevant information fully and maps them in multikernel high dimensional space; (2) in spite of almost the same accuracy with MKLS-SVR, IMKLS-SVR requires less prediction time than MKLS-SVR and LS-SVR, especially than LS-SVR. This may be due to the fact that we have reduced the support vectors of sample data by measuring the linear correlation of the sample data. Thus, IMKLS-SVR is more valuable in application.


## 5. Conclusions

In this paper, we study the issue of fast prediction with multikernel LS-SVR for multiple relevant time series. We utilize two approaches to overcome the drawbacks of LS-SVR to meet the requirements of good prediction accuracy and less prediction time cost. Firstly, because each time series data point may have different distribution characteristics, we apply MKL, that is, a linear combination of basis kernels, to enhance the generalization capability of the learning machine and to exploit all discriminative information in the sample data. We determine the linear combination weights by calculating the RMSE of each basis kernel to yield the new kernel. Secondly, we remove the samples by judging the linear correlation to reduce the number of support vectors. This approach can control the loss of useful information of the sample data, reduce computation time, and improve the model’s generalization ability simultaneously.We conducted several experiments to evaluate the proposed methods; we especially utilized a certain prediction application to demonstrate the effectiveness of the proposed method via comparing with the traditional LS-SVR and multikernel LS-SVR. The results show that the proposed prediction scheme has good prediction performance, and it is suitable for multiple relevant time series fast prediction.



---

*Source: 460514-2015-05-18.xml*