Résumé Technique : BEACON

Formulation du Problème

L'article traite du défi de la Recherche de Nouveauté (Novelty Search - NS) dans le contexte de systèmes à boîte noire coûteux et bruités, courants en chimie, en science des matériaux et en conception moléculaire. Contrairement à l'optimisation traditionnelle, qui cherche un optimum scalaire unique, l'objectif ici est de découvrir un ensemble diversifié de comportements de système (résultats) atteignables au sein d'un budget d'évaluation limité.

Formellement, le problème implique une fonction à boîte noire à valeurs vectorielles $f: \mathcal{X} \to \mathcal{O}$, où $\mathcal{X} \subset \mathbb{R}^d$ est l'espace d'entrée et $\mathcal{O} \subset \mathbb{R}^n$ est l'espace des résultats (comportements). L'objectif est de maximiser la accessibilité (reachability), définie comme la fraction de régions de comportement distinctes découvertes au sein d'une partition finie de l'espace des résultats.

Les méthodes de NS existantes, souvent basées sur des méta-heuristiques comme les algorithmes évolutionnaires, sont généralement peu efficaces en termes d'échantillonnage. Elles peinent dans les contextes où chaque évaluation de fonction (par exemple, une simulation ou une expérience physique) est coûteuse. De plus, l'Optimisation Bayésienne (BO) standard est mal adaptée car elle réduit les résultats en une seule fonction d'utilité, risquant ainsi de négliger des comportements intermédiaires ou rares scientifiquement précieux.

Méthodologie : BEACON

Les auteurs proposent BEACON (Bayesian Exploration Algorithm for outCOme Novelty), une stratégie d'échantillonnage efficace inspirée des principes de l'Optimisation Bayésienne mais adaptée à la recherche de nouveauté.

Composants Clés

1. Surrogate Multi-Sortie par Processus Gaussien (MOGP) :
   Au lieu de modéliser un objectif scalaire, BEACON place un modèle de substitution probabiliste directement sur la correspondance entrée-résultat $f$. Le cadre utilise des MOGP pour modéliser la fonction vectorielle complète. Dans la plupart des expériences, les auteurs emploient des modèles GP à sorties indépendantes (ajustant un GP scalaire par coordonnée de sortie) pour maintenir la simplicité, bien que le cadre supporte des sorties corrélées et des noyaux adaptés à la chimie (ex: Tanimoto-fragprint) pour des domaines spécifiques.

2. Fonction d'Acquisition basée sur l'Échantillonnage de Thompson :
   BEACON introduit une nouvelle fonction d'acquisition qui évalue les candidats en fonction de la distance entre leurs résultats plausibles et une archive débruitée des résultats précédemment observés.

   • Débruitage : Les observations brutes sont remplacées par des prédictions de la moyenne postérieure ($\mu_D$) pour atténuer les effets du bruit d'observation.
   • Quantification de l'Incertitude : L'algorithme tire une fonction échantillon $g(x)$ de la distribution postérieure du MOGP (via l'échantillonnage de Thompson).
   • Score : Le score de nouveauté $\alpha_{NS}$ pour un candidat $x$ est la distance moyenne entre l'issue échantillonnée $g(x)$ et les $k$ plus proches voisins dans l'archive débruitée :
     $$\alpha_{NS}(x | g, D) = \frac{1}{k} \sum_{i=1}^{k} \text{dist}(g(x), \mu_D(x_i^*))$$
   • Optimisation : Cette fonction d'acquisition est optimisée à l'aide de méthodes basées sur le gradient (ex: L-BFGS-B) avec plusieurs redémarrages. L'utilisation de relaxations différentiables pour l'opération de tri dans le calcul des $k$-plus proches voisins permet une maximisation efficace par gradient.

3. Extensions :

   • Mise à l'échelle de Haute Dimension : Pour les espaces d'entrée de haute dimension, BEACON intègre des priors SAAS (Sparse Axis-Aligned Subspace) pour induire la parcimonie dans les échelles de longueur du GP, ou utilise des surrogates conscients de la chimie (ex: noyaux moléculaires) pour les entrées discrètes structurées.
   • Contraintes Guidées par l'Utilisateur (UG-BEACON) : Le cadre permet aux utilisateurs de définir des partitions de l'espace des résultats pour soit exclure les régions déjà explorées, soit concentrer les efforts de recherche sur des régimes d'intérêt spécifiques.

Contributions Clés

L'article présente quatre contributions principales :

1. Développement d'Algorithme : Introduction de BEACON, un nouvel algorithme de NS conçu spécifiquement pour les systèmes à boîte noire bruités et coûteux, qui améliore l'accessibilité de l'espace des comportements avec un nombre limité d'évaluations.
2. Nouvelle Stratégie d'Acquisition : Une fonction d'acquisition basée sur l'échantillonnage de Thompson qui opère dans un espace de résultats continu. Elle prend en compte l'incertitude prédictive et le bruit d'observation sans nécessiter d'optimisation directe sur une partition de comportement discrétisée et fixe.
3. Scalabilité : Extensions vers des contextes de haute dimension via des priors induisant la parcimonie et une modélisation de substitut spécifique au domaine (ex: graphes moléculaires).
4. Validation Empirique : Démonstration de l'efficacité de l'algorithme à travers des benchmarks synthétiques, la découverte de matériaux (Metal-Organic Frameworks), la découverte de propriétés moléculaires et des tâches d'apprentissage par renforcement.

Résultats

Les auteurs ont évalué BEACON par rapport à plusieurs bases de référence, incluant la recherche de nouveauté évolutionnaire (NS-EA), la recherche par distance à la zone explorée (NS-DEA), l'échantillonnage de variance maximale et la recherche aléatoire.

• Benchmarks Synthétiques : Sur les fonctions Ackley, Rosenbrock et Styblinski-Tang, BEACON a systématiquement atteint la plus haute accessibilité, particulièrement dans les espaces d'entrée de haute dimension (jusqu'à 12 dimensions). Il a également surpassé les bases de référence sur un problème multi-sorties synthétique à distribution à longue traîne, couvrant efficacement les régions de faible densité que les autres méthodes ont manquées.
• Découverte de Matériaux : Dans les tâches impliquant l'absorption d'hydrogène, l'absorption d'azote et l'absorption conjointe de CO2/CH4 dans les réseaux organométalliques (MOF), BEACON a atteint une couverture complète de l'espace de comportement discrétisé dans le budget d'évaluation, surpassant les bases de référence applicables.
• Découverte Moléculaire : Pour la solubilité dans l'eau, l'ESOL (solubilité aqueuse avec des entrées de dimension 2 133) et les tâches LogD, BEACON a démontré une couverture supérieure. L'utilisation de noyaux spécifiques aux tâches (Tanimoto-fragprint) et des priors SAAS a été cruciale pour la performance dans les espaces moléculaires de haute dimension.
• Paysages Trompeurs : Dans une tâche de navigation de labyrinthe par apprentissage par renforcement avec un paysage de récompense trompeur, BEACON était la seule méthode à résoudre systématiquement la tâche sur tous les essais, là où les méthodes pilotées par la récompense (comme l'Amélioration Attendue) et les autres bases de référence de nouveauté ont échoué à sortir des pièges locaux.
• Découverte Guidée par l'Utilisateur : Dans les tâches contraintes (découverte de chiffres MNIST et conception de matériaux absorbants d'huile), UG-BEACON a réussi à incorporer les préférences de l'utilisateur pour découvrir des comportements cibles plus rapidement que les versions non contraintes.

Signification et Revendications

L'article affirme que BEACON rend la recherche de nouveauté pratique pour les domaines où les approches évolutionnaires traditionnelles sont trop inefficaces en termes d'échantillonnage. En exploitant la modélisation de substitution bayésienne, BEACON peut diriger les évaluations vers des régions inexplorées de l'espace des résultats tout en tenant rigoureusement compte de l'incertitude du modèle et du bruit.

Les auteurs positionnent BEACON comme un outil pour les contextes de découverte à faibles données, où l'objectif scientifique est une couverture large des propriétés atteignables plutôt qu'un optimum unique. Ils suggèrent que cette approche est particulièrement précieuse pour les flux de travail d'expérimentation autonome en chimie et en science des matériaux, où la découverte de phénomènes auparavant inconnus est aussi critique que l'optimisation de cibles connues.

L'article reconnaît les limites concernant les espaces de résultats "tranchants" (ex: changements de phase) où le modèle de substitution pourrait trop lisser les sauts abrupts, notant que la découverte dans ces cas peut encore dépendre d'une exploration large ou d'un échantillonnage par chance si aucune structure apprenable n'existe. Cependant, ils soutiennent que le cadre est suffisamment flexible pour incorporer des stratégies hybrides (ex: initialisation par remplissage d'espace) pour atténuer ces problèmes.