Robust and Sparse Support Vector Machines via Mixed Integer Programming

In machine learning problems in general, and in classification in particular, overfitting and inaccuracies can be obtained because of the presence of spurious features and outliers. Unfortunately, this is a frequent situation when dealing with real data. To handle outliers proneness and achieve variable selection, we propose a robust method performing the outright rejection of discordant observations together with the selection of relevant variables. A natural way to define the corresponding optimization problem is to use the ℓ norm and recast it as a mixed integer optimization problem (MIO) having a unique global solution, benefiting from algorithmic advances in integer optimization combined with hardware improvements. We also present an empirical comparison between the ℓ norm approach, the 0–1 loss and the hinge loss classification problems. Results on both synthetic and real data sets showed that, the proposed approach provides high quality solutions.