Informatique

Le premier objectif de ce cours est de montrer aux étudiants comment formuler un problème d’apprentissage automatique sous la forme d’un problème d’optimisation. Différentes classes de problèmes d’optimisation et les fondements algorithmiques pour leur résolution seront présentés avec une attention particulière pour les problèmes convexes. Un objectif essentiel est de sensibiliser aux spécificités du contexte d’optimisation cible et à l’adéquation d’une méthode de résolution plutôt qu’une autre à ce contexte. Outre l’apprentissage de quelques algorithmes standards et avancés en optimisation, ce point de vue offre aux étudiants une perspective riche permettant l’appréhension de l’omniprésence des problèmes d’optimisation dans les applications actuelles. En particulier, ce point de vue permettra d’aborder des problématiques d’optimisation en lien spécifique à l’apprentissage automatique, mais aussi de comprendre de façon plus profonde la richesse et les caractéristiques des méthodes d’optimisation existantes. Muni de cette compréhension, les étudiants pourrons faire face à un problème particulier et s’orienter vers le choix de la méthode présentant le plus d’intérêt. Il s’agit enfin de pouvoir mettre en pratique ces méthodes en particulier à travers l’implémentation d’application simples et la manipulation de bibliothèques existantes.

Résoudre un problème d’optimisation consiste à trouver une solution de bonne qualité, par rapport à une fonction objectif à minimiser (ou de façon équivalente à maximiser). D’un côté, la fonction objectif peut avoir une forme mathématique précise et des propriétés connues. Ceci est par exemple le cas pour de nombreux problèmes d’apprentissage se modélisant sous la forme de problèmes d’optimisation ayant des caractéristiques particulières. D’un autre côté, la forme de la fonction objectif peut être inconnue et seule une information restreinte quant aux caractéristiques de la fonction peut être disponible. Ceci est par exemple le cas pour de nombreux problèmes de réglage d’hyper-paramètres, de sélection d’attributs, de robotique, ou de problèmes nécessitant une simulation. Selon la nature de la fonction objectif, différentes classes d’approches sont considérées. Par ailleurs, quand bien même une information concernant la fonction à optimiser est disponible, d’autres caractéristiques telles que la dimension et la taille de l’espace de recherche, le coût d’évaluation d’une solution, l’incertitude liée à l’évaluation, peuvent impacter la difficulté de la résolution et ainsi le choix d’une méthode plutôt qu’une autre. Dans ce cours, nous aborderons différentes classes d’approches du point de vue de la complexité et la quantité d’information disponible concernant la fonction objectif à optimiser.

Nous commencerons par le contexte ‘simple’ où la fonction objectif a une forme particulière ou possède des caractéristiques remarquables permettant de simplifier le processus de résolution, tel que le cas d’une fonction linéaire, ou d’une fonction convexe. Des approches standards constituant les bases d’ingénierie des méthodes d’optimisation, en programmation linéaire et ses variantes, en descente de gradients et ses variantes, seront présentées et leurs principaux composants algorithmiques étudiés.

Le contexte de problèmes d’optimisation plus complexes, où éventuellement aucune information sur la fonction objectif n’est disponible, sera ensuite approfondi. Dans un premier temps, nous aborderons des méthodes offrant des garanties d’optimalité et de convergence, par exemple celles issues de la théorie des bandits, et ayant des propriétés théoriquement prouvées sous certaines conditions. Dans un second temps, nous présenterons les fondements de méthodes heuristiques dite boite-noire (black-box) s’appuyant sur l’aléatoire et la recherche stochastique. Des méthodes de nature locale, par exemple la recherche locale adaptative et la recherche par matrices de covariances, et des méthodes plus globales, telles que les algorithmes évolutionnaires, seront étudiés. Nous aborderons brièvement les méthodes d’optimisation dites boite-grise, où une information partielle sur la fonction objectif, telle que les interactions entre variables, peut être exploiter. De façon générale, l’accent sera mis sur les fondements des composants algorithmiques sous-jacents, ainsi que sur l’automatisation du processus de leur conception et leur évaluation.

Enfin, nous donnons un aperçu de méthodes de résolution permettant de prendre en compte des caractéristiques particulières du contexte de l’application cible. Par exemple, nous présenterons les notions fondamentales d’aide à la décision pour des problèmes d’optimisation multi-objectif. En outre, des méthodes se basant sur les modèles de substitutions en apprentissage automatique, seront présentées notamment pour des problématiques d’optimisation de fonction coûteuses telle que le calibrage d’hyper-paramètres, la sélection de portfolio d’algorithmes, etc. L’accent sera mis sur la sensibilisation à la nécessité de s’orienter vers des méthodes de résolution spécifiques selon les caractéristiques du contexte d’optimisation visé.

• d’appréhender les méthodes d’optimisation en fonction des caractéristiques d’un problème cible
• de comprendre la richesse des méthodes d’optimisation dans le contexte de l’apprentissage automatique
• de mettre en oeuvre une méthode de descente de gradient
• de s’affranchir de la connaissance du gradient lors de l’optimisation
• de mettre en oeuvre une méthode de recherche stochastique
• de s’adapter la complexité du contexte d’optimisation et de choisir une technique d’optimisation adéquate