Variable selection and outlier detection viamixed integer programming
Sélection des variables et détection des valeurs aberrantes via programmation mixte en nombres entiers
Résumé
Two principles at the forefront of modern machine learning and statistics are sparse modeling and robustness. Sparse modeling enables the construction of simpler statistical models. At the same time, statistical models need to be robust they should perform well when data is noisy in order to make reliable decisions. While sparsity and robustness are often closely related, the exact relationship and subsequent trade-offs are not always transparent. For example, convex penalties like the Lasso are often motivated by sparsity considerations, yet the success of these methods is also driven by their robustness. In this thesis, we work at improving the quality of the estimators in supervised machine learning in terms of robustness and sparsity. We propose methods that, jointly, perform variable selection and outlier detection, and formulate the obtained optimization problems using mixed integer programming (MIP) benefiting from the significant improvement of MIP solvers. First we focus on proposing a robust and sparse method for linear regression. To solve the problem exactly, we recast it as a mixed integer programming problem. In addition, and in order to decrease the computational time, we propose a discrete first algorithm providing a near-optimal solution in a very short time. The obtained solution is used as a warm start for the MIP solver. However, the proposed problem suffered from overfitting for low signal-to-noise ratio values. Then, to fix the overfitting behavior of the proposed method, we use penalized regularization to improve its performance when the noise is high. We also propose a discrete first order algorithm to solve the regularized approach. Finally, we propose a robust and sparse classification method based on the classical hinge-loss classifier. The obtained problem is formulated using mixed integer programming and shown to be efficient on both real and synthetic data sets.
Deux points clés de l’apprentissage machine et des statistiques modernes sont la modélisation parcimonieuse et la robustesse. La modélisation parcimonieuse permet la construction de modèles statistiques plus performant et économes en ressources. Dans un même temps, les modèles statistiques doivent être robustes ; ils doivent être performants lorsque les données sont bruitées afin de permettre de prendre des décisions fiables. Si la parcimonie et la robustesse sont souvent étroitement liées, la relation qui les unit et les compromis qui en découlent ne sont pas toujours explicitement formulés. Par exemple, des pénalités convexes comme celle du Lasso sont souvent motivés par des considérations de sélection de variable, mais le succès de ces méthodes est aussi dû à leur robustesse. Dans cette thèse, nous travaillons à l’amélioration de la qualité des estimateurs dans le cadre de l’apprentissage supervisé simultanément en termes de robustesse et de parcimonie. Nous proposons des méthodes qui réalisent simultanément les deux tâches de sélection de variables et de détection de points aberrants. Ce problème est formulé dans différents contextes sous la forme de problèmes d’optimisation utilisant la programmation mixte en nombres entiers (MIP), dont la résolution bénéficie de l’amélioration significative des solveurs MIP. Nous nous concentrons d’abord sur la proposition d’une méthode robuste et peu répandue pour la régression linéaire. Pour résoudre le problème exactement, nous le reformulons en un problème de programmation mixte en nombres entiers. Ensuite, afin de réduire le temps de calcul, nous proposons un premier algorithme discret fournissant une solution quasi optimale en un temps très court. La solution obtenue est utilisée comme un démarrage à chaud pour le solveur MIP. Cependant, la solution proposée souffre de surapprentissage pour de faibles valeurs du rapport signal/bruit. Afin de corriger ce surapprentissage, nous utilisons une régularisation pénalisée pour améliorer ses performances lorsque le bruit est élevé. Nous proposons également un algorithme discret du premier ordre pour résoudre l’approche régularisée. Enfin, nous proposons une méthode de classification robuste parcimonieuse basée sur le classificateur classique séparateur à vaste marge (SVM) associé à la fonction de perte «charnière». Le problème obtenu est là aussi formulé comme un programme mixte en nombres entiers et s’avère efficace sur des ensembles de données réelles et synthétiques.
Origine : Version validée par le jury (STAR)