Apprentissage profond pour les problèmes d'optimisation combinatoire (APOC)

dernière modif : le 18/12/2023 à 18:40:31
Titre :
Apprentissage profond pour les problèmes d'optimisation combinatoire (APOC)
Section :
Optionnel
État pour cette année :
OPEN
Mots clés :
Apprentissage profond, couches d'optimisation combinatoire, end to end learning pour l'optimisation combinatoire
Ects :
2
Responsable :
Axel Parmentier (ENPC/CERMICS)
Intervenants :
Axel Parmentier (ENPC/CERMICS)
Prérequis :

Fondamentaux de la recherche opérationnelle. Bases d'apprentissage supervisé.

Objectif :

L'utilisation de couches d'optimisation combinatoire dans les pipelines d'apprentissage profond constitue un domaine récent et très dynamique à la frontière de la recherche opérationnelle et de l'apprentissage automatique. Du point de vue de l'apprentissage automatique, ces approches permettent de faire des prédictions sur des domaines combinatoires. Du point de vue de la recherche opérationnelle, ces techniques permettent de fournir de nouvelles heuristiques rapides pour des problèmes d'optimisation combinatoire data-driven ou des variantes de problèmes classiques. Les objectifs de ce cours sont (1) d'introduire ces pipelines et leurs applications, (2) de donner les éléments théoriques et pratique pour construire des architectures efficaces, et (3) d'introduire des méthodes d'apprentissage pour calibrer ces approches. Ce cours permettra également (4) d'introduire le calcul des probabilités dans les familles exponentielles, des outils de calcul des probabilités sur des espaces combinatoires qui trouvent leur origine en physique statistique et en apprentissage automatique.

Contenu / Plan :

Nota: Partiellement existant (premières séances du cours RODM).

  • Couches d'optimisation combinatoire dans les pipelines d'apprentissage profond. La séance introduira la notion de pipeline de deep learning, la notion de couche d'optimisation combinatoire dans de tels pipelines, les challenges présentés par l'utilisation de telles couches et le type de problèmes de recherche opérationnelle pour lesquels ces approches fournissent des méthodes efficaces.

  • Maximum de vraisemblance et familles exponentielles. Après une introduction de la notion de familles exponentielle, la séance illustrera son utilité pour modéliser des distributions de probabilité sur des espaces combinatoires en grande dimension. La notion de maximum de vraisemblance sera introduite dans ce contexte.

  • Fonctions de pertes de Fenchel Young et apprentissage par imitation. La dualité de Fenchel-Young en optimisation convexe sera introduite en début de séance. Celle-ci permettra d'introduire la notion de régularisation convexe d'un problème d'optimisation combinatoire, puis les fonctions de perte de Fenchel Young pour l'apprentissage par imitation de prédicteurs à valeur dans des espaces combinatoires. Les approches de type smart predict then optimize seront introduites en fin de séance.

  • Apprentissage par expérience. Les liens entre régularisation d'un problème d'optimisation combinatoire et distribution de probabilité sur un espace combinatoire sous-jacent seront introduits. On introduira ensuite la notion de regret et l'apprentissage par expérience.

  • TP et Inférence variationnelle La première partie de la séance sera consacrée à l'inférence variationnelle (ou à rattraper le retard éventuel pris sur les autres séances). La seconde partie de séance sera consacrée au TP.

  • Optimisation stochastique contextuelle et examen final. La première heure sera consacrée aux liens entre les méthodes présentées et l'optimisation stochastique contextuelle. Le reste de la séance sera consacrée à l'examen.

Bibliographie :
  • Nowozin, S., & Lampert, C. H. (2011). Structured learning and prediction in computer vision. Foundations and Trends in Computer Graphics and Vision, 6(3--4), 185-365.

  • Blondel, M., Martins, A. F., & Niculae, V. (2020). Learning with Fenchel-Young losses. J. Mach. Learn. Res., 21(35), 1-69.

  • Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2), 405-421.

  • Murphy, K.P, (2023) Probabilistic Machine Learning: Advanced Topics, MIT press

  • Dalle, G., Baty, L., Bouvier, L., & Parmentier, A. (2022). Learning with Combinatorial Optimization Layers: a Probabilistic Approach. arXiv preprint arXiv:2207.13513.

Liens :
(aucun)
Compétences visées :

Savoir construire, apprendre, implémenter et analyser des pipelines d'apprentissage profond contenant des couches d'optimisation combinatoire. Connaitre les fondamentaux sur les familles exponentielles et l'inférence variationnelle.

Modalités de contrôle :
  • Un compte rendu de TP
  • Un examen final