IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i2p467-479.html
   My bibliography  Save this article

Support Vector Machines with the Ramp Loss and the Hard Margin Loss

Author

Listed:
  • J. Paul Brooks

    (Department of Statistical Sciences and Operations Research, Virginia Commonwealth University, Richmond, Virginia 23284)

Abstract

In the interest of deriving classifiers that are robust to outlier observations, we present integer programming formulations of Vapnik's support vector machine (SVM) with the ramp loss and hard margin loss. The ramp loss allows a maximum error of 2 for each training observation, while the hard margin loss calculates error by counting the number of training observations that are in the margin or misclassified outside of the margin. SVM with these loss functions is shown to be a consistent estimator when used with certain kernel functions. In computational studies with simulated and real-world data, SVM with the robust loss functions ignores outlier observations effectively, providing an advantage over SVM with the traditional hinge loss when using the linear kernel. Despite the fact that training SVM with the robust loss functions requires the solution of a quadratic mixed-integer program (QMIP) and is NP-hard, while traditional SVM requires only the solution of a continuous quadratic program (QP), we are able to find good solutions and prove optimality for instances with up to 500 observations. Solution methods are presented for the new formulations that improve computational performance over industry-standard integer programming solvers alone.

Suggested Citation

  • J. Paul Brooks, 2011. "Support Vector Machines with the Ramp Loss and the Hard Margin Loss," Operations Research, INFORMS, vol. 59(2), pages 467-479, April.
  • Handle: RePEc:inm:oropre:v:59:y:2011:i:2:p:467-479
    DOI: 10.1287/opre.1100.0854
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1100.0854
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.1100.0854?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. J. Brooks & Eva Lee, 2010. "Analysis of the consistency of a mixed integer programming-based multi-category constrained discriminant model," Annals of Operations Research, Springer, vol. 174(1), pages 147-168, February.
    2. O. L. Mangasarian, 1965. "Linear and Nonlinear Separation of Patterns by Linear Programming," Operations Research, INFORMS, vol. 13(3), pages 444-452, June.
    3. Richard Gallagher & Eva Lee & David Patterson, 1997. "Constrained discriminant analysis via 0/1 mixed integer programming," Annals of Operations Research, Springer, vol. 74(0), pages 65-88, November.
    4. Dimitris Bertsimas & Romy Shioda, 2007. "Classification and Regression via Integer Optimization," Operations Research, INFORMS, vol. 55(2), pages 252-271, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jian Luo & Shu-Cherng Fang & Zhibin Deng & Xiaoling Guo, 2016. "Soft Quadratic Surface Support Vector Machine for Binary Classification," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(06), pages 1-22, December.
    2. Blanquero, R. & Carrizosa, E. & Jiménez-Cordero, A. & Martín-Barragán, B., 2019. "Functional-bandwidth kernel for Support Vector Machine with Functional Data: An alternating optimization algorithm," European Journal of Operational Research, Elsevier, vol. 275(1), pages 195-207.
    3. Baldomero-Naranjo, Marta & Martínez-Merino, Luisa I. & Rodríguez-Chía, Antonio M., 2020. "Tightening big Ms in integer programming formulations for support vector machines with ramp loss," European Journal of Operational Research, Elsevier, vol. 286(1), pages 84-100.
    4. J. Paul Brooks & Eva K. Lee, 2014. "Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 567-585, August.
    5. Xianning Wang & Zhengang Ma & Jingrong Dong, 2021. "Quantitative Impact Analysis of Climate Change on Residents’ Health Conditions with Improving Eco-Efficiency in China: A Machine Learning Perspective," IJERPH, MDPI, vol. 18(23), pages 1-23, December.
    6. Pietro Belotti & Pierre Bonami & Matteo Fischetti & Andrea Lodi & Michele Monaci & Amaya Nogales-Gómez & Domenico Salvagnin, 2016. "On handling indicator constraints in mixed integer programming," Computational Optimization and Applications, Springer, vol. 65(3), pages 545-566, December.
    7. Mohammad Poursaeidi & O. Kundakcioglu, 2014. "Robust support vector machines for multiple instance learning," Annals of Operations Research, Springer, vol. 216(1), pages 205-227, May.
    8. Jin Xiao & Yuhang Tian & Yanlin Jia & Xiaoyi Jiang & Lean Yu & Shouyang Wang, 2023. "Black-Box Attack-Based Security Evaluation Framework for Credit Card Fraud Detection Models," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 986-1001, September.
    9. Xianning Wang & Zhengang Ma & Jiusheng Chen & Jingrong Dong, 2023. "Can Regional Eco-Efficiency Forecast the Changes in Local Public Health: Evidence Based on Statistical Learning in China," IJERPH, MDPI, vol. 20(2), pages 1-19, January.
    10. Pedro Duarte Silva, A., 2017. "Optimization approaches to Supervised Classification," European Journal of Operational Research, Elsevier, vol. 261(2), pages 772-788.
    11. Carrizosa, Emilio & Nogales-Gómez, Amaya & Romero Morales, Dolores, 2017. "Clustering categories in support vector machines," Omega, Elsevier, vol. 66(PA), pages 28-37.
    12. Zhou, Jingke & Zhu, Lixing, 2016. "Principal minimax support vector machine for sufficient dimension reduction with contaminated data," Computational Statistics & Data Analysis, Elsevier, vol. 94(C), pages 33-48.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Brandner, Hubertus & Lessmann, Stefan & Voß, Stefan, 2013. "A memetic approach to construct transductive discrete support vector machines," European Journal of Operational Research, Elsevier, vol. 230(3), pages 581-595.
    2. J. Paul Brooks & Eva K. Lee, 2014. "Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 567-585, August.
    3. Z. R. Gabidullina, 2013. "A Linear Separability Criterion for Sets of Euclidean Space," Journal of Optimization Theory and Applications, Springer, vol. 158(1), pages 145-171, July.
    4. Wanpracha Art Chaovalitwongse, 2008. "Novel quadratic programming approach for time series clustering with biomedical application," Journal of Combinatorial Optimization, Springer, vol. 15(3), pages 225-241, April.
    5. Emilio Carrizosa & Belen Martin-Barragan, 2011. "Maximizing upgrading and downgrading margins for ordinal regression," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(3), pages 381-407, December.
    6. Yu, Lean & Wang, Shouyang & Lai, Kin Keung, 2009. "An intelligent-agent-based fuzzy group decision making model for financial multicriteria decision support: The case of credit scoring," European Journal of Operational Research, Elsevier, vol. 195(3), pages 942-959, June.
    7. Young Woong Park & Yan Jiang & Diego Klabjan & Loren Williams, 2017. "Algorithms for Generalized Clusterwise Linear Regression," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 301-317, May.
    8. Nieddu, Luciano & Patrizi, Giacomo, 2000. "Formal methods in pattern recognition: A review," European Journal of Operational Research, Elsevier, vol. 120(3), pages 459-495, February.
    9. Araújo, Paulo H. M. & Campêlo, Manoel & Corrêa, Ricardo C. & Labbé, Martine, 2024. "Integer programming models and polyhedral study for the geodesic classification problem on graphs," European Journal of Operational Research, Elsevier, vol. 314(3), pages 894-911.
    10. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.
    11. R Fildes & K Nikolopoulos & S F Crone & A A Syntetos, 2008. "Forecasting and operational research: a review," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1150-1172, September.
    12. Laura Palagi, 2017. "Global Optimization issues in Supervised Learning. An overview," DIAG Technical Reports 2017-11, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    13. Eva K. Lee & Helder I. Nakaya & Fan Yuan & Troy D. Querec & Greg Burel & Ferdinand H. Pietz & Bernard A. Benecke & Bali Pulendran, 2016. "Machine Learning for Predicting Vaccine Immunogenicity," Interfaces, INFORMS, vol. 46(5), pages 368-390, October.
    14. Emilio Carrizosa & Belen Martin-Barragan & Dolores Romero Morales, 2010. "Binarized Support Vector Machines," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 154-167, February.
    15. Baldomero-Naranjo, Marta & Martínez-Merino, Luisa I. & Rodríguez-Chía, Antonio M., 2020. "Tightening big Ms in integer programming formulations for support vector machines with ramp loss," European Journal of Operational Research, Elsevier, vol. 286(1), pages 84-100.
    16. Eva K. Lee & Ferdinand Pietz & Bernard Benecke & Jacquelyn Mason & Greg Burel, 2013. "Advancing Public Health and Medical Preparedness with Operations Research," Interfaces, INFORMS, vol. 43(1), pages 79-98, February.
    17. Dimitris Bertsimas & Romy Shioda, 2007. "Classification and Regression via Integer Optimization," Operations Research, INFORMS, vol. 55(2), pages 252-271, April.
    18. Orsenigo, Carlotta & Vercellis, Carlo, 2004. "Discrete support vector decision trees via tabu search," Computational Statistics & Data Analysis, Elsevier, vol. 47(2), pages 311-322, September.
    19. Heydari Majeed & Yousefli Amir, 2017. "A new optimization model for market basket analysis with allocation considerations: A genetic algorithm solution approach," Management & Marketing, Sciendo, vol. 12(1), pages 1-11, March.
    20. Lean Yu & Zebin Yang & Ling Tang, 2016. "A novel multistage deep belief network based extreme learning machine ensemble learning paradigm for credit risk assessment," Flexible Services and Manufacturing Journal, Springer, vol. 28(4), pages 576-592, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:59:y:2011:i:2:p:467-479. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.