A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization

Résumé technique : Un cadre unifié pour la recherche d'entropie et l'amélioration espérée dans l'optimisation bayésienne

Énoncé du problème
L'optimisation bayésienne (OB) est une technique standard pour l'optimisation de fonctions boîte noire coûteuses, reposant sur des fonctions d'acquisition (FA) pour équilibrer exploration et exploitation. Deux paradigmes dominants existent :

1. L'amélioration espérée (AE) : Une FA heuristique qui maximise l'amélioration espérée par rapport à la meilleure valeur observée actuelle. Elle est efficace sur le plan computationnel et largement utilisée, mais est souvent considérée comme fondamentalement distincte des méthodes théoriques de l'information.
2. Les FA théoriques de l'information (par exemple, la recherche d'entropie de la valeur maximale - MES) : Ces méthodes visent à réduire l'incertitude concernant la localisation ou la valeur de l'optimum global en utilisant des mesures basées sur l'entropie. Bien qu'elles soient théoriquement fondées, elles sont souvent considérées comme distinctes de l'AE en raison de philosophies sous-jacentes différentes.

La perspective prédominante dans la communauté de l'OB traite l'AE et les FA théoriques de l'information comme des méthodologies séparées. Cet article remet en cause cette vision, soutenant qu'un lien théorique plus profond existe entre elles, lien qui n'avait pas été précédemment reconnu.

Méthodologie : Recherche d'entropie variationnelle (VES)
Les auteurs introduisent la recherche d'entropie variationnelle (VES), un cadre théorique unifié qui interprète l'AE comme une approximation par inférence variationnelle de la recherche d'entropie de la valeur maximale (MES) théorique de l'information.

• Unification théorique : Le cadre établit une borne inférieure pour la fonction d'acquisition MES en utilisant la borne de Barber-Agakov (BA). En définissant une famille variationnelle $Q$ pour approximer la densité conditionnelle $p(y^* | D_t, y_x)$ (où $y^*$ est la valeur du maximum global), les auteurs dérivent une borne inférieure de recherche d'entropie (ESLBO).
• Récupération de l'AE : Lorsque la famille variationnelle $Q$ est restreinte aux distributions exponentielles, la maximisation de l'ESLBO produit une solution identique à l'amélioration espérée (AE) standard. Cela prouve que l'AE est un cas particulier de MES sous une approximation variationnelle spécifique.
• VES-Gamma : Reconnaissant que la distribution exponentielle est trop rigide pour capturer la véritable structure de $p(y^* | D_t, y_x)$ (qui est souvent non monotone), les auteurs proposent VES-Gamma. Cette nouvelle FA utilise une distribution Gamma comme famille variationnelle. La distribution Gamma généralise la distribution exponentielle, permettant une approximation plus flexible qui capture mieux la forme de la densité.
• Optimisation : L'algorithme VES-Gamma emploie une approche de style Maximisation de l'Espérance (EM). Il itère de la manière suivante :
  1. Estime les paramètres ($k, \beta$) de la distribution Gamma qui maximisent l'ESLBO pour un point candidat fixe $x$.
  2. Met à jour le point candidat $x$ pour maximiser l'ESLBO étant donné les paramètres actuels.
     Les paramètres $k$ et $\beta$ sont déterminés automatiquement via une analyse dérivée et une régularisation, équilibrant dynamiquement les composantes de la fonction objectif.

Contributions clés

1. Cadre unifié : L'introduction du cadre VES, qui démontre que l'AE est une approximation variationnelle de MES, unifiant ainsi deux paradigmes de fonctions d'acquisition précédemment distincts.
2. Nouvelle fonction d'acquisition : La proposition de VES-Gamma, une FA qui hérite des forces de performance de l'AE tout en incorporant des principes théoriques de l'information grâce à une approximation variationnelle Gamma plus flexible.
3. Évaluation complète : Des évaluations empiriques extensives sur des benchmarks synthétiques de faible et de haute dimension, des échantillons de processus gaussiens (GP) et des problèmes réels.

Résultats
L'article évalue VES-Gamma par rapport à l'AE, à la MES et à d'autres méthodes de l'état de l'art (telles que UCB et LogEI) sur divers benchmarks :

• Benchmarks synthétiques : Sur des fonctions comme Branin, Levy, Hartmann et Griewank, VES-Gamma se montre constamment compétitive. Elle atteint les meilleures performances sur Branin et Hartmann, tout en égalant ou surpassant légèrement l'AE sur Levy et Griewank.
• Échantillons GP : Dans des expériences avec des a priori GP de 100 dimensions, VES-Gamma surpasse significativement à la fois l'AE et la MES pour de petites échelles de longueur ($\ell = 0,05, 0,1, 0,25$), où l'AE et la MES tendent à converger vers des solutions sous-optimales.
• Benchmarks réels : Sur des problèmes de haute dimension (Rover 60D, Mopta08 124D, Lasso-DNA 180D, SVM 388D), VES-Gamma démontre une performance robuste. Elle surpasse significativement toutes les autres méthodes sur le benchmark SVM et se classe parmi les meilleurs performants sur Mopta08 et Lasso-DNA.
• Validation théorique : Un test de Kolmogorov-Smirnov confirme l'équivalence empirique entre VES-Exp (la variante exponentielle) et l'AE, avec des taux de réussite dépassant 90 % sur divers benchmarks.

Signification et affirmations
L'article affirme que le cadre VES fournit un nouvel aperçu théorique : la fonction d'acquisition la plus populaire (l'AE) n'est pas fondamentalement distincte des méthodes théoriques de l'information, mais constitue plutôt une approximation variationnelle spécifique de celles-ci.

En reliant ces perspectives, les auteurs présentent VES-Gamma comme une fonction d'acquisition robuste et polyvalente qui équilibre efficacement les forces de l'AE (performance et simplicité) et de la MES (réduction de l'incertitude). Les résultats suggèrent que VES-Gamma est un candidat solide pour divers problèmes d'optimisation, en particulier dans des contextes de haute dimension où les méthodes traditionnelles peuvent éprouver des difficultés. Les auteurs notent que, bien que VES-Gamma engendre un coût computationnel par itération plus élevé que l'AE ou la MES, cela est souvent négligeable par rapport au coût d'évaluation de fonctions boîte noire coûteuses dans les applications réelles. Les travaux futurs sont identifiés comme l'exploration de distributions variationnelles alternatives et l'extension du cadre à des contextes bruyants.