TSVR: An efficient Twin Support Vector Machine for regression
Introduction
Support vector machine (SVM) is an excellent kernel-based tool for binary data classification and regression (Burges, 1998, Christianini and Shawe-Taylor, 2002, Vapnik, 1995, Vapnik, 1998). This learning strategy introduced by Vapnik and co-worker (Vapnik, 1995, Vapnik, 1998) is a principled and very powerful method in machine learning algorithms. Within a few years after its introduction, SVM has already outperformed most other systems in a wide variety of applications. These include a wide spectrum of research areas, ranging from pattern recognition (Osuna, Freund, & Girosi, 1997), text categorization (Joachims, Ndellec, & Rouveriol, 1998), biomedicine (Brown, Grundy, Lin, et al., 2000), brain–computer interface (Ebrahimi, Garcia, & Vesin, 2003), and financial regression (Ince & Trafalis, 2002), etc.
Although SVM owns better generalization classification ability compared with other machine learning methods like artificial neural network (ANN), its training cost is expensive, i.e., , where is the total size of training data. So far, many fast algorithms such as Chunking (Cortes & Vapnik, 1995), SMO (Platt, 1999), ISMO (Keerthi, Shevade, Bhattacharyya et al., 2001), SVMlight (Joachims, 1999), SVMTorch (Collobert & Bengio, 2001), LS-SVM (Suykens and Vandewalle, 1999, Suykens et al., 1999), and LIBSVM (Chang & Lin, 0000) have been presented to reduce the difficulties associated to training. Traditionally, the above algorithms solve the optimization problem of SVM by optimizing a small subset of the variables in the dual during the iteration procedure. Thus, it could be very easy to give readers the impression that this is the only possible way to train an SVM. All the above classifiers discriminate a pattern by determining in which half space it lies. Recently, Jayadeva, Khemchandani, and Chandra (2007) have proposed a Twin Support Vector Machine (TSVM) classifier for binary data classification, which is in the spirit of generalized eigenvalue proximal support vector machine (GEPSVM) (Mangasarian & Wild, 2006). The formulation of TSVM is very much similar to a classical SVM except that it aims at generating two nonparallel planes such that each plane is closer to one class and is as far as possible from the other. TSVM has become one of the popular methods in machine learning because of its low computational complexity; see e.g. Ghorai, Mukherjee, and Dutta (2009) and Kumar and Gopal, 2008, Kumar and Gopal, 2009.
As for Support Vector Regression (SVR), there exist some corresponding algorithms for learning the optimal regressor as classification, such as SMO (Shevade, Keerthi, Bhattacharyya, et al., 2000), Smooth SVR (SSVR) (Lee, Hsieh, & Huang, 2005), LS-SVM (Suykens and Vandewalle, 1999, Suykens et al., 1999), etc. On the other hand, some researchers have proposed some new SVR models based on different loss function, such as the Huber loss function (Vapnik, 1995, Vapnik, 1998). Some other methods include heuristic training (Wang & Xu, 2004), geometric method (Bi & Bennett, 2003), etc. However, all those algorithms for SVR have at least two groups of constraints, each of which ensures that more training samples locate in the given -insensitive field as far as possible. Introducing more variables and constraints in the formulation enlarges the problem size and can increase the computational complexity for solving the regression problem.
In this paper, we propose a new nonparallel plane regressor in the spirit of TSVM, termed as the Twin Support Vector Regression (TSVR). TSVR also aims at generating two nonparallel functions such that each function determines the -insensitive down- or up-bounds of the unknown regressor. Similar to TSVM (Jayadeva et al., 2007), TSVR also solves two smaller sized quadratic programming problems (QPPs) instead of solving large one as in a classical SVR. The formulation of TSVR is totally different from that of SVR in one fundamental way. In TSVR we solve a pair of QPPs, whereas, in SVR we only solve one single QPP. Further, in SVR the QPP has two groups of constraints for all data points, but in TSVR, only one group of constraints for all data points are used in each QPP. This strategy of solving two smaller sized QPPs, rather than one large QPP, makes TSVR work faster than standard SVR. Computational comparisons on TSVR and SVR in terms of generalization performance and training time have been made on several artificial and UCI datasets, indicating TSVR is not only fast, but also shows good generalization.
The paper is organized as follows: Section 2 briefly dwells on SVRs and also introduces the notation used in the rest of the paper. Section 3 introduces the linear Twin Support Vector Regression, while, in Section 4, we extend TSVR for nonlinear kernels. Section 5 deals with experimental results and Section 6 contains concluding remarks.
Section snippets
Background
Let the samples to be trained be denoted by a set of row vector in the -dimensional real space , where the th sample . Also let and let denote the response vector of training samples, where . We now consider the standard SVR and LS-SVR.
Twin Support Vector Regression
In this section, we introduce an efficient approach to SVR which we have termed as Twin Support Vector Regression (TSVR). As mentioned earlier, TSVR is similar to TSVM in spirit, as it also derives a pair of nonparallel planes around the data points. However, there are some differences in essence. First, the targets of TSVR and TSVM are different, TSVR aims to find the suitable regressor while TSVM is to construct the classifier. Second, each of the two QPPs in the TSVM pair has the formulation
Kernel Twin Support Vector Regression
In order to extend our results to nonlinear regressors, we consider the following kernel-generated functions instead of linear functions. Note that if the linear kernel is used both linear functions are the special ones of (25). As the discussion in Section 3, we construct a pair of optimization problems as follows:
Experiments and discussion
To check the validity of the proposed TSVR, we compare it with the classical SVR and LS-SVR on several datasets, including two groups of artificial datasets and seven benchmark datasets. All the regression methods are implemented in MATLAB (1994–2001) 6.5 on Windows XP running on a PC with system configuration Intel P4 processor (2.4 GHz) with 1 GB of RAM. To compare the CPU time and accuracies of three algorithms, we use the “qp.m” function in Matlab to realize the proposed TSVR and
Conclusions
In this paper we have proposed an SVR approach to data regression, termed TSVR. In TSVR, we solve two quadratic programming problems of a smaller size without any equality constraint instead of a large sized one as we do in traditional SVR. This makes TSVR much faster than a standard SVR. Furthermore, in contrast to a single regressor as given by the traditional SVR, TSVR yields two nonparallel functions such that each function determines one of the insensitive up- and down-bounds of training
Acknowledgements
This work has been partly supported by the Shanghai Leading Academic Discipline Project (No. S30405), and the Natural Science Foundation of Shanghai Normal University (No. SK200937).
References (37)
- et al.
A geometric approach to support vector regression
Neurocomputing
(2003) - et al.
Nonparallel plane proximal classifier
Signal Processing
(2009) - et al.
Application of smoothing technique on twin support vector machines
Pattern Recognition Letter
(2008) - et al.
A heuristic training for support vector regression
Neurocomputing
(2004) - et al.
A heuristic weight-setting strategy and iteratively updating algorithm for weighted least-squares support vector regression
Neurocomputing
(2008) The relationship between variable selection and prediction
Technometrics
(1974)- et al.
Nonlinear regression analysis and its applications
(1988) - Blake, C. I., & Merz, C. J. (1998). UCI repository for machine learning databases:...
- et al.
Knowledge-based analysis of microarray gene expression data by using support vector machine
Proceedings of National Academy of Science USA
(2000) A tutorial on support vector machines for pattern recognition
Data Mining Knowledge Discovery
(1998)
An introduction to support vector machines
An improved conjugate gradient method scheme to the solution of least squares SVM
IEEE Transactions on Neural Networks
SVMTorch: support vector machines for large-scale regression problems
Journal of Machine Learning
Support vector networks
Machine Learning
Joint time-frequency-space classification of EEG in a brain–computer interface application
Journal of Apply Signal Process
Cited by (424)
Sparse least-squares Universum twin bounded support vector machine with adaptive L<inf>p</inf>-norms and feature selection
2024, Expert Systems with ApplicationsMulti-hyperplane twin support vector regression guided with fuzzy clustering
2024, Information SciencesTwin support vector quantile regression[Formula presented]
2024, Expert Systems with ApplicationsOn reliability enhancement of solar PV arrays using hybrid SVR for soiling forecasting based on WT and EMD decomposition methods
2024, Ain Shams Engineering JournalNewton-based approach to solving K-SVCR and Twin-KSVC multi-class classification in the primal space
2023, Computers and Operations Research