Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

Résumé Technique : Sélection Générative en Boucle Fermée

Énoncé du Problème
La sélection générative en boucle fermée est devenue une méthodologie de premier plan dans la découverte computationnelle de médicaments. Dans ce flux de travail, un modèle génératif appris propose des molécules candidates, un oracle de fitness (par exemple, docking ou essai) les évalue, et les meilleurs candidats sont conservés pour réentraîner le modèle pour le tour suivant. Malgré son utilité pratique, la méthode manque d'une théorie de convergence rigoureuse. L'analyse classique des algorithmes évolutionnaires repose sur la propriété de Markov de la population ; cependant, dans la sélection générative, le modèle $G_t$ est réentraîné à chaque tour sur la base de l'historique des pools d'élites. Cette adaptation brise la propriété de Markov de la séquence de populations $(P_t)$, rendant les outils analytiques standards inapplicables. De plus, le domaine manque d'une théorie unifiée traitant du rôle de la mémoire (quelle quantité de données passées informe le modèle), de l'impact des oracles bruités, et du coût réel de la recherche mesuré en évaluations d'oracle plutôt qu'en tours algorithmiques.

Méthodologie et Cadre Mathématique
Les auteurs développent une théorie autonome en reformulant le problème sur un espace d'états élargi pour restaurer une structure de Markov.

1. Formulation de Markov : Au lieu d'analyser la population $P_t$ seule, les auteurs définissent un état augmenté $Z_t = (P_t, G_t)$ ou un processus d'historique $H_t = (P_0, \dots, P_t)$. Ils prouvent que sous des règles de mise à jour déterministes, ces processus augmentés sont des chaînes de Markov homogènes dans le temps.
2. Élitisme et Absorption : L'algorithme emploie une règle de sélection élitiste (conservation des $N$ meilleures molécules), garantissant que la fitness de l'élite $f(P_t)$ est non décroissante. Cela crée une structure absorbante où l'ensemble cible des molécules $\epsilon$-optimales est un état absorbant.
3. Méthode des Niveaux de Fitness : L'analyse décompose la recherche en « séjours » (sojourns) à des niveaux de fitness discrets. Le temps de passage attendu est borné par la somme des temps de sortie attendus de chaque niveau. La probabilité de sortie au niveau $k$ dépend de la capacité du noyau génératif à proposer des molécules strictement plus aptes que le niveau actuel.
4. Modèles de Mémoire : Le papier analyse trois régimes :
   • Statique/Étape unique : $G_t$ dépend uniquement de $P_t$.
   • Mémoire complète : $G_t$ dépend de l'historique complet.
   • Mémoire à $m$-étapes finie : $G_t$ dépend des $m$ derniers pools.
5. Gestion du Bruit : La théorie s'étend aux oracles bruités en remplaçant les évaluations uniques par des requêtes répliquées et des estimateurs robustes (par exemple, médiane de moyennes, tests de signe) pour certifier les écarts de fitness sous des distributions de bruit sub-gaussiennes et à queues lourdes.

Contributions Clés et Résultats

• Convergence et Bornes de Temps de Passage :
  Le papier prouve la convergence presque sûre pour tout algorithme de sélection générative satisfaisant une condition de positivité uniforme (un plancher d'exploration uniforme). Il établit une « Borne de Temps de Passage par Couches » où le nombre attendu de tours est borné par la somme des inverses des probabilités de sortie à travers les niveaux de fitness. Cette borne est plus fine que les bornes de queue géométriques standards car elle tient compte de la structure du paysage.

• Hiérarchie de la Mémoire et Apprentissage Monotone :
  Sous une condition d'« apprentissage monotone » (où le fait de conditionner sur des données passées supplémentaires ne diminue jamais la probabilité de proposer une molécule meilleure), les auteurs prouvent une hiérarchie de la mémoire : une mémoire plus profonde améliore strictement (ou, au minimum, ne nuit pas aux) les probabilités de sortie et réduit le temps de passage attendu. Dans ce régime, la mémoire complète est optimale, et le bénéfice de la mémoire présente des rendements décroissants, avec une saturation exponentielle.

• Apprentissage Non-Monotone et Profondeur de Mémoire Optimale :
  Le papier identifie que l'apprentissage monotone échoue souvent en pratique (par exemple, lorsque la moyenne de pools bruités introduit un biais de vétusté). En l'absence de monotonie, les auteurs dérivent une théorie de temps de sortie non-monotone. Ils définissent un « profil d'apprentissage » $\rho_k(j)$ représentant la probabilité de sortie en fonction du nombre de pools du niveau actuel dans la fenêtre. Le temps de séjour attendu est montré comme étant une fonction en forme de U de la profondeur de la mémoire $m$. Par conséquent, il existe une profondeur de mémoire optimale finie $m^*$ qui équilibre la réduction de la variance par plus de données face au biais des données obsolètes. Cette profondeur optimale correspond au premier pic du profil d'apprentissage.

• Stratégie de Minimisation des Évaluations :
  En recadrant la théorie en termes d'évaluations d'oracle (le véritable goulot d'étranglement dans la conception de médicaments), les auteurs prouvent que l'opération séquentielle ($M=1$) minimise le nombre total d'évaluations. Bien que des tailles de lots plus grandes ($M > 1$) réduisent le nombre de tours, elles gaspillent des évaluations sur des candidats qui sont scorés même après qu'un meilleur candidat a déjà été trouvé au sein du même lot. La stratégie optimale est de proposer un candidat à la fois, potentiellement combinée à la mémoïsation et à l'arrêt précoce.

• Oracles Bruités :
  Pour le bruit sub-gaussien, le coût de la certification s'accroît par un facteur proportionnel à $\sigma^2/\Delta^2$, où $\Delta$ est l'écart de fitness. Pour les bruits à queues lourdes (où la variance peut être infinie), la moyenne de l'échantillon s'avère insuffisante. Les auteurs démontrent que des estimateurs robustes (médiane de moyennes) ou des tests de signe sans distribution restaurent la correction, avec des coûts de requête qui se dégradent de manière graduelle avec la lourdeur des queues de distribution.

Signification et Revendications
Le papier affirme fournir la première analyse rigoureuse de convergence et de temps d'exécution pour la sélection générative en boucle fermée prenant en compte les noyaux d'apprentissage adaptatifs. Sa signification réside dans :

1. Résolution de la Rupture de Markov : En construisant un espace d'états augmenté, il comble le fossé entre les modèles génératifs adaptatifs et la théorie classique des algorithmes évolutionnaires.
2. Quantification de la Mémoire : Il dépasse l'heuristique « plus de données, c'est mieux » pour fournir une analyse précise du compromis biais-variance, identifiant les conditions sous lesquelles une mémoire finie est optimale.
3. Optimisation des Ressources : Il établit que pour la découverte de médicaments sous contrainte de coûts, l'évaluation séquentielle ($M=1$) est théoriquement optimale pour minimiser les appels d'oracle, contestant la pratique courante de l'évaluation parallèle en grands lots.
4. Robustesse : Il offre un cadre pour traiter les données expérimentales réalistes et bruitées, y compris les distributions à queues lourdes communes dans les essais biologiques, sans sacrifier les garanties de convergence.

Les auteurs concluent que bien que la théorie soit abstraite et repose sur des bornes inférieures pour les probabilités de sortie dépendant de mises en œuvre de modèles spécifiques, elle fournit un cadre fondamental pour analyser et concevoir des algorithmes de sélection générative. Ils identifient trois problèmes ouverts : quantifier les probabilités de sortie pour des architectures neuronales spécifiques, concevoir des apprenants qui soient à la fois non-monotones et compositionnellement homogènes pour réaliser des gains de mémoire adaptatifs au niveau, et étendre la certification robuste aux espaces latents continus et aux bruits asymétriques.