Optimisation bay©sienne par m©thodes SMC

  • View
    277

  • Download
    0

Embed Size (px)

Text of Optimisation bay©sienne par m©thodes SMC

1. Optimisation baysienne par mthodes SMCRomain Benassi Julien Bect Emmanuel VazquezSUPELEC 21 mars 2012Mascot Num 2012 Bruyres-le-Chtel, FranceBenassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC21 mars 2012 1 / 27 2. Introduction Contexte Optimisation globale nombreuses applications dans lindustrie :Conception dune voilure davion (Forrester et al. 2008)Optimisation de la forme des conduits dadmission dun moteur devoiture (Villemonteix et al. 2007)etc. Fonctions optimiser coteuses valuer (appel des programmes informatiques avec des dures dexcution importantes)Exemples doptimisation de formes en CFDBenassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 2 / 27 3. Introduction Optimisation baysienne 1/2 Soit f : X Rd R, avec X compact et d N Objectif : trouver x = argmaxx X f (x ) et M = f (x ) f ne peut tre value quun nombre limit de fois Nvaluations non bruitesgradient de f non disponible Choix dune approche baysienne pour rsoudre le problme f est vue comme une ralisation dun processus alatoire Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 3 / 27 4. Introduction Optimisation baysienne 2/2 Aprs n valuationsinformation disponible : Fn = (X1 , (X1 ), . . . , Xn , (Xn ))objectif : maximiser MN = (X1 ) . . . (XN ) Nouveau point dvaluation Xn+1 choisi laide dun critre dchantillonnage n (construit partir de Fn ) Xn+1 = argmax n (x ), x X n peut tre valu rapidement Exemples de critres :probabilit damlioration (Kushner 1964)amlioration moyenne (Expected Improvement) (Mockus et al. 1978)entropie de loptimiseur (IAGO) (Villemonteix et al. 2008)Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 4 / 27 5. Introduction Expected Improvement (EI) Stratgie optimale sur un horizon dun pas :Xn+1 = argmin En [M Mn+1 | Xn+1 = x ] x X= argmax En ((Xn+1 ) Mn )+ | Xn+1 = x , x XExpected Improvement (EI) avec En lesprance conditionnelle relative FnBenassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC21 mars 2012 5 / 27 6. Introduction Exemple : itration 13210 1 2 310.5 00.5 1log10 n (x ) 1 2 3 410.5 00.5 1Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 6 / 27 7. Introduction Exemple : itration 23210 1 2 31 0.5 0 0.51log10 n (x )0 2 4 61 0.5 0 0.51Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 6 / 27 8. Introduction Exemple : itration 3 3 2 1 0123 10.50 0.51log10 n (x ) 0 20 40 10.50 0.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 6 / 27 9. Introduction Exemple : itration 42 1.51 0.500.5 11.5 22.5 31 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1 log10 n (x )020401 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 6 / 27 10. Introduction Exemple : itration 5210 1 2 310.500.5 1 log10 n (x )0204010.500.5 1Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 6 / 27 11. Introduction Exemple : itration 6210 1 2 310.500.5 1 log10 n (x )0204010.500.5 1Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 6 / 27 12. Introduction1 Introduction2 Approche plug-in3 Approche compltement baysienne4 Expriences numriques5 ConclusionsBenassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 7 / 27 13. Approche plug-in1 Introduction2 Approche plug-in3 Approche compltement baysienne4 Expriences numriques5 ConclusionsBenassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 8 / 27 14. Approche plug-in Problme : Comment choisir ? processus choisi dans une classe de processus gaussiens paramtrspar (p.ex. processus avec moyenne constante mais inconnue etcovariance exponentielle avec porte inconnue)Approche plug-in est estim par maximum de vraisemblance EI plug-in :n (x ; ) = En x ; Mn,+ avec estim par MV Avantage : existence dune expression analytique de lEI pour gaussienBenassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 9 / 27 15. Approche plug-in EI et processus gaussiens Si est gaussien ( x) : n (x ; ) = En ( (x ) Mn )+ | | = sn (x ) [u(u) + (u)] avecu = n Mn /sn (x )n (x ) = En [(x ; )] (prdicteur par krigeage)sn (x ) cart type a posteriori de n (x ) (x ; ) fonction de rpartition de la loi normale centre rduite Il est facile de calculer n !Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 10 / 27 16. Approche plug-in Problme avec lapproche plug-inFonctions trompeusesLe terme fonctions trompeuses caractrise une fonction pour laquelleun design initial mal choisi peut conduire une trs mauvaiseestimation des paramtres du processus par MVLutilisation dune approche plug-in conduit parfois sous-estimerlargement lerreur de prdiction : problme pour loptimisation par EIBenassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 11 / 27 17. Approche plug-in Exemple : Fonction trompeuse10.50 0.5 11 0.500.5 1Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 18. Approche plug-in Exemple : Fonction trompeuse 1 0.5 00.51 10.5 0 0.51Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 12 / 27 19. Approche plug-in Exemple : Fonction trompeuse 10.5 00.51 10.50 0.5 1Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 12 / 27 20. Approche plug-in Exemple : Fonction trompeuse10.50 0.5 11 0.5 0 0.5 1Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 21. Approche plug-in Exemple : Fonction trompeuse 1 0.5 0 0.5 11 0.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 22. Approche plug-in Exemple : Fonction trompeuse 1 0.5 00.51 1 0.500.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 23. Approche plug-in Exemple : Fonction trompeuse10.50 0.51 1 0.50 0.5 1Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 24. Approche plug-in Exemple : Fonction trompeuse10.50 0.5 11 0.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 25. Approche plug-in Exemple : Fonction trompeuse 1 0.5 00.51 10.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC 21 mars 2012 12 / 27 26. Approche compltement baysienne1 Introduction2 Approche plug-in3 Approche compltement baysienne4 Expriences numriques5 ConclusionsBenassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC 21 mars 2012 13 / 27 27. Approche compltement baysienne EI compltement baysien Utilisation dun critre EI compltement baysien (Williams et al. 2003, Osborne et al. 2009, . . .) choix dun a priori sur Critre dchantillonnage EI compltement baysien :Xn+1 = argmaxx X n := n (x ; ) dn () , o n est la loi a posteriori de , etn (x ; ) := En (((Xn+1 ) Mn )+ | Xn+1 = x ; ), Approche plus robuste quune approche plug-in (Benassi et al. 2011)Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC21 mars 2012 14 / 27 28. Approche compltement baysienne Exemple : itration 11 1.5 1 0.50.500 0.50.51 11.510.5 0 0.5 11 0.5 00.51 log n (x )log n (x )02.22.4 0.2 2.6 0.42.8 0.6 1 0.5 0 0.5 11 0.5 00.51Benassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC21 mars 2012 15 / 27 29. Approche compltement baysienne Exemple : itration 21.51.5 110.50.5 00 0.5 0.51 1 1.5 1.51 0.5 0 0.5 11 0.5 00.51log n (x )log n (x )20.84611 0.5 0 0.5 1 10.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 30. Approche compltement baysienne Exemple : itration 3 1.5 1.5 11 0.5 0.5 000.50.5 111.51.5 10.5 0 0.5 11 0.5 00.51 log n (x )log n (x ) 01.21.4 101.6 201.81 0.5 0 0.5 1 10.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 31. Approche compltement baysienne Exemple : itration 4 1.5 1.5 11 0.5 0.5 000.50.5 111.51.5 10.5 0 0.5 11 0.5 00.51 log n (x )log n (x ) 00.5 20 4011 0.5 0 0.5 1 10.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 32. Approche compltement baysienne Exemple : itration 5 1.5 1.5 11 0.5 0.5 000.50.5 111.51.5 10.5 0 0.5 11 0.5 00.51 log n (x )log n (x ) 00.8 20 1 401.21.41 0.5 0 0.5 11 0.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 33. Approche compltement baysienne Exemple : itration 6 1.5 1.5 11 0.5 0.5 000.50.5 111.51.5 10.5 0 0.5 11 0.5 00.51 log n (x )log n (x ) 01.2 201.4 401.61 0.5 0 0.5 11 0.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 34. Approche compltement baysienne Exemple : itration 7 1.5 1.5 11 0.5 0.5 000.50.5 111.51.5 10.5 0 0.5 11 0.5 00.51 log n (x )log n (x ) 01.5 20 40 21 0.5 0 0.5 1 10.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 35. Approche compltement baysienne Exemple : itration 8 1.5 1.5 11 0.5 0.5 000.50.5 111.51.5 10.5 0 0.5 11 0.5 00.51 log n (x )log n (x ) 0 2 20 2.5 401 0.5 0 0.5 1 10.5 00.51Benassi, Bect, Vazquez (SUPELEC)Optimisation baysienne par SMC21 mars 2012 15 / 27 36. Approche compltement baysienne Limites de lapproche compltement baysienne chaque tape, on choisit une nouvelle valuation Xn+1 = argmaxx X n := n (x ; ) dn () Questions 1 Comment calculer lintgrale apparaissant dans ?n 2 Comment maximiser n ? Nous proposons un nouvel algorithme apportant une rponse ces deuxquestions, de faon simultane, laide dune approche SMC (SequentialMonte Carlo) originaleBenassi, Bect, Vazquez (SUPELEC) Optimisation baysienne par SMC21 mars 2012 16 / 27 37. Approche compltement baysienne Limites de lapproche compltement baysienne chaque tape, on choisit une nouvelle valuation Xn+1 = argmaxx X n := n (x ; ) dn () Questions 1 Comment calculer lintgrale apparaissant dans ?n 2 Comment maximiser n ? Nous proposons un nouvel algorithme apportant une rponse ces