Sensitivity analysis in linear programming approach to optimal SVM classification

Authors

  • Roberto Ragona

    ENEA

Received date: April 14, 2014

Accepted date: May 9, 2014

Published date: June 4, 2014

DOI:

https://doi.org/10.14419/ijamr.v3i3.2449

Abstract

At present, linear programming (LP) techniques for optimal one-class and two-class classification can be considered well established and feasible; they pose an alternative to the quadratic programming (QP) approach, which is usually credited with having greater complexity. Sensitivity analysis, well developed in the LP context, is generally employed to furnish answers describing how an optimal solution changes when varying the parameters in an LP problem; as a possible application in optimal classification, it can be employed for the definition of the free parameters present in LP procedures, reducing the events of computational restart from scratch when searching for a satisfactory classifier through repeated trials. The proposed method is demonstrated on a simple example which exhibits its effectiveness in reducing the computational burden, but this procedure can be extrapolated to large problems as well.

Keywords: Linear Programming, Optimal Classification, Sensitivity Analysis, Support Vector Machines.

Author Biography

  • Roberto Ragona, ENEA
    Dept. of Advanced Technologies for Energy and Industry

References

  1. B.E. Boser, I.M.Guyon, V.Vapnik, A training algorithm for optimal margin classifiers, Proceedings Fifth ACM Workshop on Computational Learning Theory, Pittsburgh, 1992
  2. N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press, 2000
  3. C.J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998, vol. 2, pp. 121–167
  4. D.M.J. Tax, R.P.W. Duin, Support vector data description, Machine Learning, 2004, vol. 54, pp. 45-66
  5. M. C. Ferris, O. L. Mangasarian, S. J. Wright, Linear Programming with MATLAB, MPS-SIAM, Philadelphia, 2007
  6. J.P. Pedroso, N. Murata, Support Vector Machines for Linear Programming: Motivations and Formulations, BSIS Tech. Report No. 99-XXX, August 1999
  7. O.L. Mangasarian, Exact 1-Norm Support Vector Machines via Unconstrained Convex Differentiable Minimization, Journal of Machine Learning Research, 2006, vol. 7, pp. 1517–1530
  8. J. Zhu, S. Rosset, T. Hastie, and R. Tibshirani. 1-norm Support Vector Machines, Advances in Neural Information Processing Systems, 2004, vol. 16
  9. R. Ragona, A Minimax Chebyshev Approach to Optimal Binary Classification, Int. Journal of Applied Mathematical Research, 2013, vol. 2, No. 2, pp. 175-187
  10. R. Ragona, A Linear Programming Solution to Data Description and Novelty Classification, Int. Journal of Applied Mathematical Research, 2013, vol. 2, No. 4, pp. 495-504
  11. T. Joachims, Making large-Scale SVM Learning Practical. Advances in Kernel Methods - Support Vector Learning, B. Schölkopf and C. Burges and A. Smola (ed.), MIT-Press, 1999.
  12. C.-C. Chang and C.-J. Lin. LIBSVM: a Library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology, 2011, vol. 2, No. 3
  13. P. S. Bradley and O. L. Mangasarian. Massive Data Discrimination via Linear Support Vector Machines. Optimization Methods and Software, 2000, vol. 13, No. 1
  14. S. Sra, Efficient Large Scale Linear Programming Support Vector Machines, ECML 2006, Proc. of the 17th European Conference on Machine Learning, Springer-Verlag, Berlin, 2006, pp. 767-774
  15. R. Tibshirani, Regression Shrinkage and Selection via the LASSO. Journal of the Royal Statistical Society, 1996, Series B vol. 58, No. 1
  16. D.G. Luenberger, Linear and Nonlinear Programming, second edition, Stanford University, 1984.

Downloads

How to Cite

Ragona, R. (2014). Sensitivity analysis in linear programming approach to optimal SVM classification. International Journal of Applied Mathematical Research, 3(3), 196-206. https://doi.org/10.14419/ijamr.v3i3.2449

Received date: April 14, 2014

Accepted date: May 9, 2014

Published date: June 4, 2014