Yasha Pushak

Les concepteurs d'algorithmes sont régulièrement confrontés à la tâche fastidieuse de trouver des valeurs par défaut appropriées pour les paramètres qui influencent les performances des algorithmes. L'évaluation approfondie de la configuration d'un seul paramètre nécessite généralement l'exécution de l'algorithme sur un grand nombre d'instances de problèmes, ce qui peut rendre le processus très lent. Pour résoudre ce problème, de nombreuses procédures automatisées de configuration d'algorithmes ont été proposées. La grande majorité d'entre elles sont basées sur de puissantes méta-heuristiques dotées de mécanismes de diversification puissants, garantissant ainsi qu'elles explorent suffisamment l'espace de configuration des paramètres.

Cependant, malgré l'importance de la configuration automatisée des algorithmes, on sait relativement peu de choses sur les paysages de configuration d'algorithmes recherchés par ces procédures, qui établissent un lien entre les valeurs des paramètres et les performances des algorithmes. Par conséquent, bien que ces mécanismes de forte diversification rendent les configurateurs existants plus robustes, on ne sait pas s'ils sont réellement nécessaires ou s'ils augmentent simplement le temps d'exécution des configurateurs.

L'un des premiers travaux particulièrement remarquables dans ce domaine a montré que les paysages de configuration de deux algorithmes d'optimisation sont, en fait, proches de l'uni-modalité. Cependant, les techniques existantes d'analyse du paysage de la forme physique sont incapables de tenir compte de la stochasticité des mesures de performance des algorithmes d'une manière statistiquement fondée, ce qui constitue un obstacle majeur à leur application à l'étude des scénarios de configuration des algorithmes. Nous comblons cette lacune en développant la première méthode statistiquement fondée pour détecter les écarts significatifs par rapport à l'uni-modalité dans un paysage stochastique.

Nous appliquons cette méthode, ainsi que d'autres techniques (nouvelles et existantes) d'analyse des paysages, à une variété de scénarios de configuration d'algorithmes apparaissant dans l'apprentissage automatique des machines (AutoML) et la minimisation du temps d'exécution des algorithmes pour la résolution de N P-problèmes difficiles. Nous montrons que les paysages de configuration d'algorithmes sont le plus souvent très structurés et relativement simples.

En utilisant l'intuition de cette analyse, nous développons deux prototypes de procédures de configuration d'algorithmes conçus pour AutoML. Nous montrons que les méthodes font des hypothèses trop fortes, ce qui conduit à des résultats mitigés. Cependant, nous nous appuyons sur cette intuition et développons une autre procédure pour la configuration de N P algorithmes difficiles. Comparée à l'état de l'art, nous montrons que notre nouvelle méthode trouve souvent des configurations similaires ou meilleures dans le même temps ou moins de temps.

Défiler vers le haut
Skip to content