2004 TheEntireRegulPathForTheSVM

From GM-RKB
Jump to: navigation, search

Subject Headings: SVM Classification Algorithm, Regularization Path, Algorithm Tuning Parameter, Regularization Cost Parameter, Kernel Function Parameter, Cost Parameter.

Notes

Cited By

Quotes

Author Keywords

Abstract

The support vector machine (SVM) is a widely used tool for classification. Many efficient implementations exist for fitting a two-class SVM model. The user has to supply values for the tuning parameters: the regularization cost parameter, and the kernel parameters. It seems a common practice is to use a default value for the cost parameter, often leading to the least restrictive model. In this paper we argue that the choice of the cost parameter can be critical. We then derive an algorithm that can fit the entire path of SVM solutions for every value of the cost parameter, with essentially the same computational cost as fitting one SVM model. We illustrate our algorithm on some examples, and use our representation to give further insight into the range of SVM solutions.


References

  • 1. Eugene Allgower and Kurt Georg. Continuation and path following. Acta Numerica, pages 1-64, 1992.
  • 2. Francis R. Bach, Michael I. Jordan, Kernel independent component analysis, The Journal of Machine Learning Research, 3, p.1-48, 3/1/2003
  • 3. Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support vector machine learning. In Advances in Neural Information Processing Systems (NIPS 2000), volume 13. MIT Press, Cambridge, MA, 2001.
  • 4. Dennis DeCoste, Kiri Wagstaff, Alpha seeding for support vector machines, Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p.345-349, August 20-23, 2000, Boston, Massachusetts, United States doi:10.1145/347090.347165
  • 5. Christopher Diehl and Gert Cauwenberghs. SVM incremental learning, adaptation and optimization. In Proceedings of the 2003 International Joint Conference on Neural Networks, pages 2685-2690, 2003. Special series on Incremental Learning.
  • 6. Brad Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. Technical report, Stanford University, 2002.
  • 7. Brad Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. Annals of Statistics, 2004. (to appear, with discussion).
  • 8. (Evgeniou et al., 2000) ⇒ Theodorus Evgeniou, Massimiliano Pontil, and Tomaso Poggio. (2000). “Regularization Networks and Support Vector Machines.” In: Advances in Computational Mathematics, 13(1). doi:10.1023/A:1018946025316
  • 9. Shai Fine and Katya Scheinberg. Incas: An incremental active set method for SVM. Technical report, IBM Research Labs, Haifa, 2002.
  • 10. Trevor Hastie and Robert Tibshirani. Generalized Additive Models. Chapman and Hall, 1990.
  • 11. Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning; Data Mining, Inference and Prediction. Springer Verlag, New York, 2001.
  • 12. Trevor Hastie and Rob Tibshirani. Efficient quadratic regularization for expression arrays. Technical report, Stanford University, 2003.
  • 13. Chih-Wei Hsu, Chih-Chung Chang, and Chih-Jen Lin. A practical guide to support vector classification. Technical report, Department of Computer Science and Information Engineering, National Taiwan University, Taipei, 2003. http://www.csie.ntu.edu.tw/~cjlin/libsvm/.
  • 14. Thorsten Joachims. Practical Advances in Kernel Methods -- Support Vector Learning, chapter Making large scale SVM learning practical. MIT Press, 1999. See http://svmlight.joachims.org.
  • 15. Steve Marron. An overview of support vector machines and kernel methods. Talk, 2003. Available from author's website: http://www.stat.unc.edu/postscript/papers/marron/Talks/.
  • 16. Massimiliano Pontil, Alessandro Verri, Properties of support vector machines, Neural Computation, v.10 n.4, p.955-974, May 15,1998 doi:10.1162/089976698300017575
  • 17. Sridhar Ramaswamy, P. Tamayo, R. Rifkin, S. Mukherjee, C. Yeang, M. Angelo, C. Ladd, M. Reich, E. Latulippe, J. Mesirov, T. Poggio, W. Gerald, M. Loda, E. Lander, and T. Golub. Multiclass cancer diagnosis using tumor gene expression signature. PNAS, 98:15149-15154, 2001.
  • 18. B. D. Ripley. Pattern recognition and neural networks. Cambridge University Press, 1996.
  • 19. Saharon Rosset. Tracking curved regularized optimization solution paths. In Advances in Neural Information Processing Systems (NIPS 2004), volume 17. MIT Press, Cambridge, MA, 2005. to appear.
  • 20. Saharon Rosset and Ji Zhu. Piecewise linear regularized solution paths. Technical report, Stanford University, 2003. http://www-stat.stanford.edu/~saharon/papers/piecewise.ps.
  • 21. Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. In Advances in Neural Information Processing Systems (NIPS 2003), volume 16. MIT Press, Cambridge, MA, 2004.
  • 22. Bernhard Schölkopf, Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, 2001
  • 23. Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society B., 58:267-288, 1996.
  • 24. Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
  • 25. G. Wahba. Spline Models for Observational Data. SIAM, Philadelphia, 1990.
  • 26. G. Wahba, Y. Lin, and H. Zhang. Gacv for support vector machines. In A.J. Smola, P.L. Bartlett, Bernhard Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 297- 311, Cambridge, MA, 2000. MIT Press.
  • 27. J. Weston and C. Watkins. Multi-class support vector machines, 1998. URL citeseer.nj.nec.com/8884.html.
  • 28. Christopher K. I. Williams, Matthias Seeger, The Effect of the Input Density Distribution on Kernel-based Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.1159-1166, June 29-July 02, 2000
  • 29. Ji Zhu and Trevor Hastie. Classification of gene microarrays by penalized logistic regression. Biostatistics, 2004. (to appear).
  • 30. Ji Zhu, Saharon Rosset, Trevor Hastie, and Robert Tibshirani. L1 norm support vector machines. Technical report, Stanford University, 2003.,


 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2004 TheEntireRegulPathForTheSVMTrevor Hastie
Saharon Rosset
Robert Tibshirani
Ji Zhu
The Entire Regularization Path for the Support Vector MachineThe Journal of Machine Learning Researchhttp://www.jmlr.org/papers/volume5/hastie04a/hastie04a.pdf2004