Integer Optimization for Machine Learning (IOML)

Zacharie Ales (ENSTA Paris)

Zacharie Ales (ENSTA Paris)

2

Science des données, classification supervisée, arbres de classification, interprétabilité, robustesse

Programmation mathématique (simplexe, dualité, Branch & Bound), Méthodes de décomposition en PLNE

Présenter les principales applications de la recherche opérationnelle aux sciences des données

• Régression linéaire par résolution d'un problème d'optimisation robuste

  Le problème de régression linéaire est très majoritairement résolu en introduisant un terme de biais dans l'objectif permettant d'éviter le sur-apprentissage. Dans cette séance nous verrons qu'il peut être plus efficace de considérer une modélisation robuste du problème dans laquelle on cherche à minimiser l'erreur pour la pire incertitude possible sur les données.

• Arbres de décision et de régression optimaux

  Les arbres de décision sont des classifieurs interprétables très populaires. Ils sont généralement entraînés en utilisant des algorithmes gloutons tels que CART. Nous présentons différents programmes linéaires en nombres entiers permettant d'obtenir des arbres de décisions optimaux.

• Optimisation interprétable

  Il est généralement difficile de déterminer pourquoi une solution est optimale pour une instance donnée et pas pour une autre. L'objectif de cette séance est de présenter une méthode permettant de déterminer un classifieur interprétable capable d'associer une solution (idéalement optimale) à une instance.

• Analyse en composantes principales parcimonieuses

  L'ACP permet d'obtenir des composantes représentant au mieux la variabilité d'un ensemble de données. Cependant, ces composantes sont peu interprétables car tous leurs coefficients sont généralement non nuls. Pour pallier cela, on modélise dans cette séance le problème d'obtention de composantes interprétables que l'on résout par un branch-and-bound.

• Examen

• Dimitris Bertsimas and Jack Dunn. Optimal classification trees. , 106(7):1039--1082, 2017.

• Dimitris Bertsimas and Jack Dunn. . Dynamic Ideas LLC, 2019.

• Dimitris Bertsimas and Bartolomeo Stellato. The voice of optimization. , 110(2):249--277, 2021.

• Axel Parmentier and Thibaut Vidal. Optimal counterfactual explanations in tree ensembles. In International Conference on Machine Learning, pages 8422--8431. PMLR, 2021.

Modélisation de programmes linéaires en nombres entiers, robustesse, implémentation.

Examen et projet.