détail d'implémentation pratique de l'optimisation bayésienne

8

J'essaye de l'optimisation bayésienne, suivant Snoek, Larochelle et Adams [ http://arxiv.org/pdf/1206.2944.pdf] , en utilisant GPML [ http://www.gaussianprocess.org/gpml/code/matlab / doc /] . J'ai implémenté la fonction d'acquisition Expected Improvement décrite à la page 3, et je suppose que j'ai raison de décider où interroger mon objectif en suivant.x qui maximise:

aEI(x;(xn,yn,θ))

Mais je n'arrive pas à trouver de conseils sur quel ensemble de candidats xest à considérer. En théorie, j'aimerais trouver le meilleurxsur l'ensemble du domaine, et l'article est rédigé de telle manière qu'il semble suggérer que cela est possible ("[EI] a également une forme fermée sous le processus gaussien"). Mais en pratique, je dois calculer les moyennes et les variances prédictives postérieures à toutx Je pourrais considérer avant de pouvoir calculer aEI(x) et bien que ces postérieurs aient une forme fermée, j'ai encore besoin de les calculer en utilisant l'algèbre matricielle, donc je ne vois pas de moyen de contourner la cueillette d'un tas de x's.

La question: quelle est une méthode pratique pour choisir le grand (moyen? Petit?) Ensemble de candidatsxsur laquelle je maximise l'IE (ou toute autre fonction d'acquisition)? (Est-ce quelque part dans le journal et je l'ai juste raté?)

En ce moment, je prends juste mon set actuel xi, en l'échantillonnant avec remplacement 2000 fois, puis en ajoutant du bruit gaussien à chaque point. Semble bien, je suppose.

stackoverflax
la source
Je n'ai pas encore lu cet article, mais avez-vous pensé à échantillonner dans le domaine d'intérêt en utilisant un Latin Hypercube Design? en.wikipedia.org/wiki/Latin_hypercube_sampling
RustyStatistician
Une alternative serait de mettre en grille le domaine (si possible) puis d'évaluer chaque point sur ce domaine maillé.
RustyStatistician
Ce sont deux suggestions judicieuses, merci! Je ne sais pas grand-chose sur les hypercubes latins, mais des domaines maillés réguliers signifieraient que l'algèbre de Toeplitz et de Kronecker pourrait être utilisée, ce qui rendrait les choses agréables et efficaces même avec une très grande grille.
stackoverflax

Réponses:

6

La norme est d'utiliser n'importe quel optimiseur global que vous aimez. Le problème est que la surface EI est hautement multimodale et déconnectée; l'optimisation de cette fonction d'acquisition est un problème non trivial en soi.

Un choix courant que j'ai vu dans divers articles est l' algorithme DIRECT ; j'ai parfois vu CMA-ES qui est une méthode de pointe en optimisation non linéaire. D'après mon expérience pour d'autres formes d'optimisation, MCS ( Multi-Level Coordinate Search ) a tendance à fonctionner relativement bien. Vous pouvez trouver un examen des optimiseurs mondiaux sans dérivés ici :

  • Rios et Sahinidis, «Optimisation sans dérivé: une revue des algorithmes et comparaison des implémentations logicielles», Journal of Global Optimization (2013).

Soit dit en passant, l'IE est analytique, donc si vous le souhaitez, vous pouvez également calculer son gradient pour guider l'optimisation, mais ce n'est pas nécessaire. Une technique efficace consiste à exécuter d'abord un optimiseur global pour trouver des solutions prometteuses, puis à exécuter un optimiseur local pour l'affiner (par exemple, une méthode quasi-Newton telle que BFGS, c'est-à-dire fminunc dans MATLAB; ou fmincon si vous avez des contraintes).

Enfin, si la vitesse d'optimisation de la fonction d'acquisition est un facteur (qui n'est pas le scénario BO "traditionnel"), j'ai trouvé des résultats décents en commençant par un plan Latin Hypercube ou un plan de séquence Sobol quasi aléatoire, puis affiné avec quelques étapes d'un optimiseur local à partir des meilleurs points; voir aussi le commentaire @ user777. Puisque ce n'est pas le scénario BO standard, je n'ai pas de référence spécifique qui utilise réellement cette méthode.


Exemples d'articles faisant référence à DIRECT ou CMA-ES:

  • Calandra, R., Seyfarth, A., Peters, J., et Deisenroth, MP (2015). Optimisation bayésienne pour l'apprentissage des allures sous incertitude. Annals of Mathematics and Artificial Intelligence, 1-19 ( lien ).
  • Mahendran, N., Wang, Z., Hamze, F., et Freitas, ND (2012). MCMC adaptatif avec optimisation bayésienne. Dans International Conference on Artificial Intelligence and Statistics (pp. 751-760) ( lien ).
  • Gunter, T., Osborne, MA, Garnett, R., Hennig, P., et Roberts, SJ (2014). Échantillonnage pour l'inférence dans les modèles probabilistes à quadrature bayésienne rapide. Dans Advances in neural information processing systems (pp. 2789-2797) ( lien ).

Vous pouvez simplement google "Optimisation bayésienne" + l'algorithme d'optimisation globale souhaité, et vous trouverez un tas d'articles. De plus, dans presque tous les autres articles sur BO, vous trouverez une phrase telle que :

[...] BO nécessite généralement un optimiseur global auxiliaire à chaque itération pour optimiser la fonction d'acquisition. Il est courant dans la littérature BO d'utiliser des RECTangles divisés (DIRECT) pour accomplir une telle tâche. D'autres algorithmes d'optimisation globale comme CMA-ES pourraient également être appliqués.

lacerbi
la source
C'est en fait assez surprenant pour moi! Pouvez-vous m'indiquer un document d'optimisation bayésien représentatif que vous avez en tête et qui utilise DIRECT ou CMA-ES? Merci.
stackoverflax
Pourquoi est-ce surprenant? C'est la norme - vous trouverez des références à DIRECT ou à d'autres optimiseurs globaux dans presque tous les articles BO. Il est probablement si bien connu dans la communauté que quelques articles ne prennent même pas la peine de mentionner - c'est juste donné pour acquis. J'ai ajouté quelques références dans mon commentaire principal ci-dessus.
lacerbi
Ce n'est pas nécessairement une bonne solution, mais j'ai trouvé qu'il peut être moins cher d'évaluer simplement l'IE à un ensemble de points échantillonnés à l'aide d'hypercubes latins dans les cas où il suffit d'être proche du minimum mais pas nécessairement au-dessus.
Sycorax dit Réintégrer Monica
@ user777: Oui, si la vitesse est en jeu, j'ai utilisé à la fois des séquences quasi-aléatoires LH et Sobol comme conception initiale (trouver un léger avantage avec cette dernière, mais cela pourrait dépendre du problème), puis exécuter un optimiseur local tels que BFGS du meilleur point (s). J'ajouterai ceci au commentaire principal.
lacerbi
Une façon de justifier la nature ad hoc de l'approche LHS est qu'il n'est pas nécessaire de trouver le minimum d'une fonction stochastique (surface) car l'erreur dans l'estimation du minimum va inonder les gains de précision en minutes. C'est une très bonne réponse, cependant. Je suis content que quelqu'un d'autre se soucie de BO. :-)
Sycorax dit Réintégrer Monica