Soutenance mémoire
Contexte et formalisme
Ce travail de thèse s’intéresse au problème de l’optimisation globale d’une fonction coûteuse, dans un cadre bayésien. Il s’agit de déterminer le maximum d’une fonction sur un domaine généralement compact et continu. Nous disons qu’une fonction est coûteuse lorsque l’évaluation de celle-ci en un point de son domaine de définition nécessite l’utilisation de ressources importantes. Dans l’industrie, il s’agit généralement de ressources informatiques, lorsque la fonction à optimiser correspond à une grandeur d’intérêt calculée au moyen de simulations numériques. Certaines simulations numériques peuvent durer des heures ou des jours sur des moyens de calcul performants, ce qui implique le plus souvent un coût financier conséquent également.
Les méthodes d’optimisation globale forment un domaine assez vaste. Une vue d’ensemble du domaine peut être appréhendée à partir d’ouvrages de références tels que Törn et Zilinskas (1989) ; Pintér (1996) ; Zhigljavsky et Zilinskas (2007) ; Conn et al. (2009) ; Tenne et Goh (2010). Parmi les méthodes classiques d’optimisation globale, citons par exemple l’existence d’algorithmes du type séparation et évaluation (branch and bound en anglais) ou bien l’algorithme DIRECT introduit par Jones et al. (1993). D’autres approches comme le recuit simulé ou les algorithmes génétiques font quant à elles intervenir des processus d’exploration par simulation de variables aléatoires, et donnent lieu à une littérature spécifique (Kirkpatrick et al., 1983 ; Glover et Laguna, 1997 ; Storn et Price, 1997 ; Beyer et Schwefel, 2002). Un algorithme d’optimisation globale nécessite généralement un nombre d’évaluations élevé afin d’obtenir une optimisation de bonne qualité, comme mis en évidence par de nombreux résultats numériques (voir, par exemple, les travaux de Egea Larrosa, 2008). Pourtant, dans le contexte de l’optimisation d’une fonction coûteuse, il apparaît évident que l’optimisation ne peut être effectuée qu’à l’aide d’un nombre limité d’évaluations. Nous parlerons de budget d’évaluation pour désigner le nombre maximal d’évaluations qu’il est possible de conduire.
Construction bayésienne d’un critère d’échantillonnage
Nous considérons ici une approche bayésienne qui consiste à affecter à f un a priori sous la forme d’un processus aléatoire ξ. L’idée est ensuite de conditionner ξ par les résultats d’évaluations bien choisies, afin de guider l’échantillonnage des futurs points (voir, par exemple les articles de Mockus et al., 1978 ; Jones et al., 1998 ; Gutmann, 2001). Plusieurs articles (Betrò, 1991 ; Mockus, 1994 ; Jones, 2001 ; Brochu et al., 2010) offrent un panorama de l’approche bayésienne pour l’optimisation globale. Historiquement, le mouvement brownien a été le premier modèle utilisé dans le domaine de l’optimisation bayésienne (Kushner, 1964), puis diverses heuristiques se sont développées, en particulier pour généraliser l’approche à des fonctions à plusieurs variables (Mockus, 1989 ; Perttunen, 1991). Le modèle est par la suite choisi gaussien par Jones et al. (1998) et, dès lors, dans la plupart des publications concernant cette approche, que ce soit pour des variantes (Williams et al., 2000 ; Huang et al., 2006), ou pour un objectif autre (études comparatives, nouveaux algorithmes. . .) dans les articles de Jones (2001); Sasena (2002) ; Villemonteix (2008).
Approche complètement bayésienne
Une solution pour prendre en compte l’incertitude liée aux paramètres est de considérer une approche complètement bayésienne, comme évoqué par Locatelli et Schoen (1995) ; Locatelli (1997) ; Williams et al. (2000) et, plus récemment, par Osborne et al. (2008, 2009) ; Osborne (2010) ; Gramacy et Polson (2011). Il faut entendre ici, par complètement bayésien, le principe de ne plus chercher à substituer une estimation de θ directement dans le critère d’échantillonnage mais d’intégrer ce critère par rapport à la loi a posteriori du paramètre. Que ce soit dans un contexte complètement bayésien ou éventuellement par substitution, l’introduction de la loi a posteriori implique le choix, par l’utilisateur, d’un a priori. Dans le cas général, un a priori permet d’affecter une pondération aux différentes valeurs possibles de θ selon la plausibilité supposée de chacune d’elles. L’avantage d’une approche complètement bayésienne par rapport à une approche par substitution, est la prise en compte de la méconnaissance de la valeur de θ.
Optimisation d’une fonction modélisée par un processus gaussien
Critères d’échantillonnage
Nous considérons un modèle de processus aléatoire gaussien ξ sur f, avec des fonctions moyenne et covariance connues, et nous supposons que n résultats d’évaluation ont déjà été obtenus. Nous notons Mn = max(ξ(x1), . . . , ξ(xn)) le maximum courant et M = supx∈X ξ(x). Pour rappel, les notations bξn et sn correspondent respectivement au prédicteur par krigeage et à l’écart-type de l’erreur de prédiction de ξ à partir de l’information disponible Fn. Les critères d’échantillonnage considérés dans ce chapitre sont calculés à partir de Fn, résumée par la connaissance de bξn et sn. De manière générale, les notations En, Pn et Hn représentent respectivement l’espérance, la probabilité et l’entropie conditionnellement à Fn.
Probabilité d’amélioration
Historiquement, le premier critère utilisé dans un cadre de l’optimisation bayésienne fut introduit par Kushner (1964), et correspond à la probabilité d’amélioration. L’amélioration dont il est question est celle relative au maximum courant entre la n-ième et la n+1-ième évaluation. Le point du domaine X en lequel la probabilité d’améliorer est maximale, constitue ainsi la position de la nouvelle évaluation. Initialement proposé pour l’optimisation de trajectoires browniennes dans des espaces à une dimension, ce critère a ensuite été étendu à des cas plus généraux (voir, par exemple, Perttunen, 1991 ; Mockus, 1994).
Depuis (Zilinskas, 1992), l’algorithme utilisant la probabilité d’amélioration comme ritère d’échantillonnage est le plus souvent présenté sous le nom P-algorithm. Des résultats de convergence sont disponibles dans (Calvin et Zilinskas, 2001).
Espérance de l’amélioration (critère EI)
Une alternative pour contourner les limites présentées par la probabilité d’amélioration est de considérer comme critère d’échantillonnage l’espérance de l’amélioration, Expected Improvement en anglais, généralement noté EI. Ce critère est initialement introduit par Mockus et al. (1978), puis popularisé dans un article de Jones et al. (1998) qui l’utilise au sein de l’algorithme d’optimisation EGO. La valeur du critère, noté ρn, en un point x du domaine correspond à l’espérance de l’amélioration offerte par une évaluation en x (par rapport au maximum courant Mn), sachant l’information disponible Fn,
ρn(x) := En((ξ(x) − Mn)+). (2.4)
L’avantage de l’EI est qu’il ne favorise pas nécéssairement une amélioration probable mais faible au détriment d’une amélioration moins probable mais plus importante.
Entropie conditionnelle des maximiseurs globaux (critère ECM)
Une autre approche possible consiste à minimiser un critère d’échantillonnage caractérisant l’entropie conditionnelle des maximiseurs globaux (critère ECM) introduit dans (Villemonteix et al., 2009). Ce qui distingue ce critère est qu’il est orienté vers une caractérisation des maximiseurs plutôt que sur celle des maxima. Concrètement, l’entropie sert ici à quantifier l’information gagnée sur la position des maximiseurs à partir d’une nouvelle évaluation de f. En reprenant le formalisme de Villemonteix et al. (2009), nous considérons une approximation discrète G du domaine X, ainsi que MG l’ensemble des maximiseurs globaux de ξ sur G.
|
Table des matières
1 Introduction
1.1 Contexte et formalisme
1.2 Construction bayésienne d’un critère d’échantillonnage
1.3 Approche complètement bayésienne
1.4 Plan du manuscrit
1.5 Publications
2 Optimisation d’une fonction modélisée par un processus gaussien
2.1 Critères d’échantillonnage
2.1.1 Probabilité d’amélioration
2.1.2 Espérance de l’amélioration (critère EI)
2.1.3 Entropie conditionnelle des maximiseurs globaux (critère ECM)
2.1.4 Borne supérieure de confiance (UCB)
2.2 Prise en compte du budget d’évaluations
2.2.1 EI et programmation dynamique
2.2.2 Stratégie optimale à deux pas
2.3 Résumé du chapitre
3 Approche complètement bayésienne
3.1 Algorithme EGO et fonctions trompeuses
3.1.1 Algorithme EGO
3.1.2 Un exemple de fonction trompeuse
3.2 Approche bayésienne pour l’optimisation par EI
3.2.1 État de l’art
3.2.2 Principe
3.3 Problème de l’intégration
3.4 Comparaison approche par substitution, approche complètement bayésienne
3.4.1 Optimisation d’une fonction trompeuse
3.4.2 Résultats sur des fonction tests
3.4.3 Paramètres de simulation
3.4.4 Résultats
3.5 Résumé du chapitre
4 Construction d’un algorithme complètement bayésien utilisant une approche Monte-Carlo séquentielle
4.1 Intégration en θ par méthode de Monte Carlo sequentielle
4.1.1 Principe
4.1.2 Étapes de la mise en œuvre proposée
4.1.3 Algorithme de Metropolis Hastings indépendant
4.2 Stratégies de maximisation du critère EI
4.3 SMC en (θ, x) : description de l’algorithme
4.3.1 Construction d’une densité sur le domaine X
4.3.2 Principe de l’algorithme SMC(θ, x)
4.3.3 Étape 1 : Démarginalisation
4.3.4 Étape 2 : Calcul et maximisation du critère EI
4.3.5 Étape 3 : Pondération, réchantillonnage et déplacement
4.3.6 Étape 4 : Choix de la densité instrumentale qn
4.4 Complexité algorithmique
4.5 Illustration et comparaisons
4.6 Résumé du chapitre
5 Applications
6 Conclusion
