Two-dimensional solution path for support vector regression

ABSTRACT

Recently, a very appealing approach was proposed to compute the entire solution path for support vector classification (SVC) with very low extra computational cost. This approach was later extended to a support vector regression (SVR) model called ε-SVR. However, the method requires that the error parameter ε be set a priori, which is only possible if the desired accuracy of the approximation can be specified in advance. In this paper, we show that the solution path for ε-SVR is also piecewise linear with respect to ε. We further propose an efficient algorithm for exploring the two-dimensional solution space defined by the regularization and error parameters. As opposed to the algorithm for SVC, our proposed algorithm for ε-SVR initializes the number of support vectors to zero and then increases it gradually as the algorithm proceeds. As such, a good regression function possessing the sparseness property can be obtained after only a few iterations.

REFERENCES

• 1: Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2002). Least angle regression (Technical Report). Stanford University.
• 2: Gunter, L., & Zhu, J. (2005). Computing the solution path for the regularized support vector regression. Advances in Neural Information Processing Systems 18 (NIPS-05).
• 3: Trevor Hastie , Saharon Rosset , Robert Tibshirani , Ji Zhu, The Entire Regularization Path for the Support Vector Machine, The Journal of Machine Learning Research, 5, p.1391-1415, 12/1/2004
• 4: Rosset, S., & Zhu, J. (2003). Piecewise linear regularized solution paths (Technical Report). Stanford University.
• 5: Saharon Rosset , Ji Zhu , Trevor Hastie, Boosting as a Regularized Path to a Maximum Margin Classifier, The Journal of Machine Learning Research, 5, p.941-973, 12/1/2004
• 6: Schölkopf, B., & Smola, A. J. (2002). Learning with kernels. MIT Press.
• 7: Bernhard Schölkopf , Alex J. Smola , Robert C. Williamson , Peter L. Bartlett, New Support Vector Algorithms, Neural Computation, v.12 n.5, p.1207-1245, May 2000 [doi>10.1162/089976600300015565]
• 8: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 9: Zhu, J., Rosset, S., Hastie, T., & Tibshirani, R. (2003). 1-norm support vector machines. Advances in Neural Information Processing Systems 16 (NIPS-03).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Algorithms, Theory