Sensitivity analysis in linear programming approach to optimal SVM classification

  • Authors

    • Roberto Ragona ENEA
    2014-06-04
    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: 2014-04-14

    Accepted date: 2014-05-09

    Published date: 2014-06-04