Résumé technique : Recherche de modèle de remise pour l'optimisation de la diversité de qualité dans des espaces de mesure de haute dimension

Définition du problème

L'optimisation de la diversité de qualité (QD) vise à découvrir un ensemble de solutions qui maximise une fonction objectif $f$ tout en couvrant simultanément une gamme diversifiée de sorties définies par une fonction de mesure vectorielle spécifiée par l'utilisateur, notée $m$. L'image de $m$ constitue l'espace de mesure $S$. Une limitation critique des algorithmes QD contemporains, en particulier des méthodes de l'état de l'art comme l'adaptation de la matrice de covariance avec recuit MAP (CMA-MAE), réside dans leur incapacité à évoluer efficacement vers des espaces de mesure de haute dimension.

Dans les espaces de haute dimension, les algorithmes souffrent de distorsion, un phénomène où de grands volumes de l'espace des solutions se mappent sur de petites régions de l'espace de mesure. CMA-MAE aborde l'objectif QD en maximisant l'"amélioration de l'archive", définie par $\Delta(\theta) = f(\theta) - f_A(m(\theta))$, où $f_A$ est une fonction de remise. CMA-MAE représente $f_A$ sous la forme d'un histogramme discret (une tessellation de cellules). Dans les contextes de haute dimension, la distorsion fait que de nombreuses solutions distinctes tombent dans la même cellule de l'histogramme, leur attribuant des valeurs de remise identiques. Par conséquent, l'algorithme ne peut pas distinguer les solutions aux mesures similaires, ce qui conduit à des signaux d'amélioration inexacts et à une stagnation de la recherche. De plus, concevoir des fonctions de mesure de faible dimension pour des domaines complexes (par exemple, spécifier "où se trouve un randonneur") est souvent fastidieux et contre-intuitif.

Méthodologie : Recherche de modèle de remise (DMS)

Pour pallier ces limitations, les auteurs proposent la Recherche de modèle de remise (DMS). Au lieu d'utiliser un histogramme discret, DMS emploie un réseau de neurones pour apprendre une représentation lisse et continue de la fonction de remise $f_A$.

Composants principaux

1. Modèle de remise ($\hat{f}_A$) : Un réseau de neurones paramétré par $\psi$ qui prend les valeurs de mesure $s = m(\theta)$ en entrée et produit une valeur de remise scalaire. L'architecture est flexible : les Perceptrons Multicouches (MLP) sont utilisés pour les mesures vectorielles de faible dimension, tandis que les réseaux convolutifs ou les Transformers conviennent aux données de haute dimension comme les images.
2. Archive et Émetteurs : DMS maintient une archive de style MAP-Elites stockant les meilleures solutions trouvées. Il utilise des émetteurs basés sur CMA-ES qui échantillonnent des solutions à partir d'une distribution gaussienne. Contrairement à CMA-MAE, l'archive ne stocke pas de valeurs de remise discrètes ; au lieu de cela, le modèle de remise est interrogé pour calculer les valeurs d'amélioration $\Delta_i = f(\theta_i) - \hat{f}_A(m(\theta_i))$.
3. Entraînement du modèle de remise : Le modèle est entraîné pour approximer la règle de mise à jour du seuil utilisée dans CMA-MAE. L'ensemble de données d'entraînement $D_A$ provient de deux sources :
   • Échantillons d'émetteurs : Pour chaque solution échantillonnée $\theta$, la valeur de remise cible $t_A$ est mise à jour en fonction de savoir si l'objectif de la solution $f(\theta)$ dépasse la prédiction actuelle du modèle $\hat{f}_A(s)$. Si $f(\theta) > \hat{f}_A(s)$, la cible est une combinaison linéaire de l'objectif et de la remise actuelle, contrôlée par un taux d'apprentissage de l'archive $\alpha$.
   • Points vides : Pour empêcher le modèle d'attribuer des valeurs arbitrairement élevées aux régions inexplorées de l'espace de mesure, l'algorithme échantillonne les centres des cellules de l'archive inoccupées et leur assigne une valeur cible de $f_{min}$ (l'objectif minimum). Cela "verrouille" le modèle dans les zones inexplorées, garantissant que les émetteurs sont guidés pour explorer de nouvelles régions.

Insight théorique

En remplaçant l'histogramme discret par une fonction continue, DMS peut attribuer des valeurs de remise distinctes aux solutions, même lorsqu'elles se mappent sur des mesures similaires dans un espace de haute dimension. Cela permet à l'algorithme de maintenir un gradient de signaux d'amélioration, empêchant la stagnation et permettant une exploration continue bien après que les méthodes basées sur des histogrammes auraient échoué.

Contributions clés

1. Recherche de modèle de remise (DMS) : Un algorithme QD novateur qui utilise un modèle de remise lisse et continu pour guider l'exploration dans des espaces de mesure de haute dimension distordus.
2. Diversité de qualité avec des ensembles de données de mesures (QDDM) : Les auteurs introduisent un nouveau cadre où les utilisateurs spécifient les mesures souhaitées via un ensemble de données (par exemple, une collection d'images) plutôt qu'en concevant manuellement une fonction de mesure. Cela traite l'espace de haute dimension de l'ensemble de données (par exemple, l'espace des images) comme l'espace de mesure.
3. Nouveaux domaines : Deux domaines QDDM sont proposés et évalués :
   • Arrangement de triangles (TA) : Disposer des triangles pour correspondre à des images de MNIST ou Fashion MNIST.
   • Éclairage de l'espace latent (LSI) (Randonneur) : Générer des images de visages de randonneurs dans des paysages diversifiés en utilisant StyleGAN3, où l'espace de mesure est l'espace des images de paysages.
4. Validation empirique : Des benchmarks étendus montrant que DMS surpasse CMA-MAE, DDS et les variantes de MAP-Elites sur des benchmarks standards et les nouveaux domaines QDDM.

Résultats expérimentaux

Les auteurs ont évalué DMS sur 9 benchmarks standards (incluant la Projection Linéaire et le Répertoire de Bras) et 3 domaines QDDM.

• Domaines de benchmark : DMS a significativement surpassé tous les points de référence en termes de Score QD (somme des objectifs dans l'archive) et de Couverture (pourcentage de cellules de l'archive remplies) dans la plupart des contextes de haute dimension (par exemple, les benchmarks LP à 10D, 20D, 50D). Notamment, sur le benchmark LP (Sphère) à 10D, la couverture de CMA-MAE a chuté à 6,95 %, tandis que DMS a atteint 89,21 %.
• Domaines QDDM :
  • Dans TA (F-MNIST), DMS a significativement surpassé tous les points de référence sur les deux métriques.
  • Dans TA (MNIST), DMS a égalé CMA-MAE en termes de couverture mais a significativement surpassé les variantes de MAP-Elites en Score QD. Les auteurs notent que DMS n'a pas significativement surpassé CMA-MAE en Score QD ici, en spéculant que le bruit introduit par l'approximation du réseau de neurones pourrait entraver l'optimisation fine de l'objectif dans des tâches de faible distorsion et de haute précision.
  • Dans LSI (Randonneur), DMS a significativement surpassé CMA-MAE, atteignant un Score QD de 214,91 contre 14,61, et une couverture de 3,77 % (377 images uniques de randonneurs). Les auteurs notent que les variantes de MAP-Elites ont atteint une couverture élevée mais avec de grands scores QD négatifs dus à la génération d'images en dehors de la distribution d'entraînement du générateur.
• Coût computationnel : DMS entraîne un coût computationnel plus élevé que CMA-MAE en raison de l'entraînement du modèle de remise, en particulier dans les benchmarks de faible dimension. Cependant, dans les domaines QDDM où la génération d'images est le goulot d'étranglement, cette surcharge est moins perceptible.

Importance et affirmations

L'article affirme que DMS offre deux avantages principaux :

1. Amélioration des performances : DMS améliore les performances dans les applications QD actuelles en surmontant les effets de distorsion qui affectent les espaces de mesure de haute dimension, surpassant les algorithmes boîte noire de l'état de l'art.
2. Accessibilité et nouvelles applications : En introduisant le cadre QDDM, DMS rend la QD plus accessible. Il allège la nécessité de fonctions de mesure conçues manuellement, permettant aux utilisateurs de spécifier des objectifs de diversité simplement en fournissant un ensemble de données. Cela permet de spécifier des mesures complexes de haute dimension (comme des styles visuels ou des emplacements sémantiques) qui sont difficiles à représenter avec des vecteurs de faible dimension.

Les auteurs concluent que, étant donné l'omniprésence des ensembles de données en apprentissage automatique, formuler les problèmes comme QDDM et les résoudre avec DMS est une direction prometteuse. Ils reconnaissent des limitations, notamment la surcharge computationnelle de l'entraînement du modèle et le potentiel du bruit d'approximation à affecter l'optimisation fine, suggérant des travaux futurs sur des architectures de modèles plus avancées et des cibles d'entraînement alternatives.