Que les meilleurs hyperparamètres et variables gagnent : c’est la loi de la jungle des algorithmes génétiques.
Vous avez lu la vignette Optimisation bayésienne à la rescousse et vous êtes tombés en amour avec la recherche d’hyperparamètres? Bonne nouvelle, d’autres algorithmes tout aussi fascinants existent! Dans cette vignette, il sera question d‘algorithme évolutif (génétique) appliqué à la recherche de modèles, d’hyperparamètres et à la sélection de variables.
Retour sur l’optimisation bayésienne avec BayesianOptimization
Les plus perspicaces d’entre vous auront remarqué dans la vignette Optimisation bayésienne à la rescousse qu’il n’y a pas de méthodes explicites pour définir le type de plages d’hyperparamètres. C’est pour cette raison que les transformations d’hyperparamètres doivent être effectuées dans la fonction black-box. Par exemple, les hyperparamètres n_estimators et min_samples_split doivent être discrétisés.
De plus, les hyperparamètres sont tirés dans une distribution uniforme bornée par les valeurs minimales et maximales. Or, pour certains types d’hyperparamètres, il serait intéressant de pouvoir tirer dans un autre type de distribution. Par exemple, pour l’hyperparamètre learning_rate d’un gradient boosting, si la plage d’hyperparamètres est définie de 0.01 à 0.5, alors les itérations de l’exploration initiale (init_points) ont autant de chance de tomber dans l’intervalle [0.4; 0.5] que [0.01; 0.11]. Si l’objectif est de donner plus de poids aux plus petites valeurs sans nécessairement couper la plage initiale, alors une transformation doit être effectuée sur cette plage. Dans cet exemple, on pourrait prendre le logarithme comme transformation. Toutefois, les transformations ne sont pas toujours aussi évidentes.
Il est aussi à noter que les calculs de la librairie Bayesian Optimization ne sont pas parallélisés. Cela n’est pas un enjeu si l’entraînement des modèles est parallélisé, mais pourrait l’être dans le cas contraire.
Algorithme évolutif
Dans les méthodes couvertes précédemment (“babysitting”, “Grid Search”, “Random Search” et optimisation bayésienne), l’objectif était d’optimiser les hyperparamètres d’un seul modèle. Or, un algorithme évolutif attaque ce problème d’un nouvel angle et suggère d’optimiser une population de modèles. Cet algorithme est fortement inspiré de la théorie de l’évolution, qui stipule, entre autres, que :
“[…], ce sont les organismes les mieux adaptés à leur environnement, grâce à de nouvelles mutations, qui survivent et transmettent leurs gènes. (”
Commençons par définir quelques termes et concepts. Le tout sera accompagné de scripts Python, où la librairie Deap sera utilisée comme outil pour construire notre algorithme évolutif. Je vous recommande fortement d’aller lire la documentation de cette libraire. Elle offre des outils pour algorithmes évolutifs, ainsi que de l’inspiration pour différentes méthodes couvertes un peu plus loin (crossover, de mutation, sélection, etc.).
Gènes
Dans ce contexte, les gènes sont représentés par la famille de modèles, par les hyperparamètres respectifs à cette famille et par les variables sélectionnées. Bref, tout ce qu’on cherche à optimiser. Plus spécifiquement, les gènes d’un individu pourraient être forêt aléatoire (rf) pour la famille de modèle, 111 pour n_estimators, 4 pour min_samples_split, 2 pour max_features, 84 pour max_deh, ainsi qu’une liste de booléens déterminant si l’on conserve la variable à l’index respectif. Voici les fonctions qui serviront à générer les gènes de nos individus (modèle).
Pour chaque famille de modèles, les hyperparamètres à optimiser et leur plage de possibilités doivent être spécifiés. Dans cet exemple, la fonction generate_rf_hyperparams tire les hyperparamètres à optimiser pour la forêt aléatoire dans une distribution donnée. Une fonction générant les hyperparamètres est développée pour chaque famille de modèles.
Pour générer un individu, on tire aléatoirement la famille de modèles, les hyperparamètres respectifs à la famille et la sélection de variables.
Afin d’organiser le tout, la classe Model est développée.
Adaptation (Fitness)
L’adaptation est la valeur de la fonction objective associée à un individu. Dans ce contexte de recherche simultanée de modèles, d’hyperparamètres et de sélection de variables, une estimation du taux de bonnes classifications par validation croisée est effectuée.
Population
Il est alors temps d’initialiser la population, la librairie Deap est utilisée à cet effet.
Cette libraire est structurée de façon à ce que les fonctions nécessaires à l’algorithme évolutif soient enregistrées dans un “toolbox”. L’utilisation du “toolbox” est optionnelle, mais permet d’assurer la compatibilité avec des algorithmes évolutifs développés dans la librairie.
Si l’utilisation du “toolbox” est optionnelle, il est nécessaire de créer la classe FitnessMax et Individual afin de spécifier le sens d’optimisation (maximisation ou minimisation) et de permettre à notre classe Model d’hériter de plusieurs méthodes fondamentales au développement de notre algorithme évolutif.
Notons que la librairie Deap permet une optimisation multicritère à l'aide du paramètre weights. L'optimisation simple critère étant un cas particulier d'optimisation multicritère, où un seul critère est défini. C’est pourquoi la fonction evaluate retourne un tuple avec l’estimation du taux de bonne classification comme premier élément et la valeur None pour le deuxième élément. Le sens d’optimisation d’un critère est déterminé par le signe du weight respectif . Un weight positif représentant une maximisation et un weight négatif représentant une minimisation.
Croisement (Crossover)
Pour transmettre leurs gènes, les modèles doivent pouvoir se reproduire. C’est ce qui est appelé un croisement (crossover). La méthode sélectionnée pour effectuer un crossover n’est limitée que par votre imagination. Toutefois, comme on cherche ultimement à converger vers un optimum, il est important de conserver certaines caractéristiques des modèles parents. En d’autres termes, effectuer un crossover qui ne détruit pas complètement la structure des gènes parents.
Les algorithmes évolutifs sont sensibles à la méthode de crossover. Il est donc important de développer ou d’utiliser un crossover en lien avec l’objectif d’optimisation. Par exemple, utiliser un crossover comme additionner les hyperparamètres des modèles parents conduira peu probablement à une solution intéressante. En effet, en supposant que deux modèles performants ont respectivement comme learning rate 0,1 et 0,11, alors la solution générée par ce croisement aurait 0,21 comme learning rate. Ce croisement n’exploite pas le fait que les solutions ayant un learning rate près de 0,1 semblent performantes. Dans ce contexte, ce croisement détruit la structure des gènes parents.
Voici le croisement utilisé dans notre exemple.
Dans un premier temps, la sélection de variables est croisée. Pour chaque variable, il y a une probabilité de 50% que les modèles échangent leur sélection associée à cette variable. Il est à noter qu’une même variable peut avoir été sélectionnée par les deux modèles parents, alors un échange sur celle-ci n’aurait aucun effet. Ce phénomène permet de conserver certains aspects des deux parents tout en générant une variation dans les nouveaux individus.
Dans un deuxième temps, si les deux modèles parents proviennent de la même famille de modèles, alors ils peuvent, par la même procédure, échanger leurs hyperparamètres.
Voici deux exemples de croisement : le premier entre deux forêts aléatoires et le second entre une forêt aléatoire et LightGBM.
Exemple de croisement entre deux forêts aléatoires
Dans l’exemple ci-dessus, les deux modèles parents appartiennent à la même famille. Il est donc possible d’échanger les hyperparamètres.
Exemple de croisement entre une forêt aléatoire et un LightGBM
Dans cet exemple, les deux modèles parents appartiennent à des familles différentes. La sélection de variables peut être échangée. Toutefois, les hyperparamètres n’ont pas la possibilité d’être échangés.
Mutation
L’étape de mutation est ce qui permet d’introduire de nouveaux gènes dans la population et, par conséquent, d’éviter de converger vers un optimum local.
Dans notre exemple, lorsqu’un individu subit une mutation, il y a une probabilité de 5% pour chaque hyperparamètre que celui-ci soit tiré de nouveau. De plus, il y a une probabilité de 5% pour chaque variable, que la sélection soit inversée. Si la mutation est trop destructive, l’algorithme se rapproche d’un “Random Search” et les avantages des algorithmes évolutifs se dissipent. Si au contraire, la mutation n’est pas assez destructive, l’algorithme à de fortes chances de rester piégé dans un optimum local.
Réparation
L’étape de crossover et de mutation ont potentiellement produit une solution enfant qui n’est pas valide. Par exemple, lors de l’échange de variables, une forêt aléatoire peut potentiellement avoir un nombre de variables disponibles plus petit que son hyperparamètre max_feature (générant une erreur). Encore une fois, la méthode de réparation est fonction de votre imagination. Toutefois, comme dans l’étape du crossover, la réparation doit être conçue en fonction du problème à résoudre. Dans cet exemple, si le nombre de variables disponibles est plus petit que l’hyperparamètre max_feature, alors une nouvelle valeur de max_feature est pigée entre 1 et le nouveau nombre de variables sélectionnées.
Sélection
À ce stade, les modèles peuvent être évalués, se croiser et être mutés. Les modèles ont une mesure de Fitness, qui détermine leur niveau d’adaptation à la tâche. Toutefois, il reste à déterminer comment s’effectuera la sélection naturelle. En effet, si l’on retourne à la citation concernant la théorie de l’évolution:
“[…], ce sont les organismes les mieux adaptés à leur environnement, grâce à de nouvelles mutations, qui survivent et transmettent leurs gènes.”
Vous l’aurez deviné, plusieurs méthodes de sélection sont disponibles et vous pouvez même développer la vôtre. Dans notre exemple, nous utiliserons la fonction selTournament de la librairie Deap. Celle-ci compose des groupes aléatoires (dans ce cas présent des paires aléatoires) et sélectionne le meilleur de chaque groupe. Il est à noter que les tirages sont effectués avec remise. Ces modèles sont donc sélectionnés pour la prochaine génération. Un nombre constant d’individus est conservé de génération en génération. Dans notre exemple, 200 piges sont effectuées.
Algorithme complet
Avec toutes ces composantes, on peut finalement faire évoluer notre population. Pour ce faire, la librairie Deap fournit la fonction eaSimple qui effectue les étapes illustrées ci-dessous pour un nombre d’itérations donné. Une itération correspond à une génération.
Voici le code associé à ces opérations. Les paramètres cxpb et mutpb représentent respectivement la probabilité de croisements et la probabilité de mutations des individus dans la population. Le paramètre ngen correspond au nombre de générations désiré.
Résultats sur données synthétiques
Tester une méthode sur des données synthétiques est quelque peu décevant en termes de benchmark. Toutefois, l’objectif n’est pas de comparer ou d’évaluer la performance de l’algorithme, mais plutôt d’illustrer la convergence de celui-ci. Ceci étant dit, je prévois rédiger un article récapitulatif qui comparera les performances des différents algorithmes de recherche d’hyperparamètres et qui inclura des tests de type benchmark.
Les jeux de données d’entraînement et de test contiennent respectivement 1000 et 49 000 observations. Il est à noter que l’algorithme évolutif a seulement accès aux 1000 observations pour l’optimisation et que l’échantillon de test sert à simuler l’erreur de généralisation. De plus, le jeu de données contient 45 variables explicatives, dont 12 informatives et 7 redondantes. La variable cible est de type binaire.
Évolution de la population
Dans la figure ci-dessous, on remarque que la performance moyenne de la population augmente rapidement au départ, puis oscille avec une tendance positive (courbe bleu). C’est ce qui indique que l’algorithme converge. Ensuite, on remarque que l’erreur de généralisation du meilleur modèle reste sous contrôle. En effet, l’écart entre la performance du meilleur modèle estimée par validation croisée (courbe jaune) et sa performance sur l’échantillon de test (courbe verte) se maintient à travers les générations.
Ce graphique montre l’évolution de différentes métriques de la population de modèles à travers les générations.
En termes de sélection de variables, l’algorithme évolutif ne réussit pas à retirer toutes les variables inutiles, mais en diminue tout de même considérablement le nombre (de 45 à 26).
Finalement, voici le nombre de modèles de chaque famille par génération. On remarque une rapide domination des modèles Catboost sur ce jeu de données.
Conclusion
Les algorithmes évolutifs sont flexibles, mais doivent être développés en fonction du problème d’optimisation en question. De plus, optimiser une population de modèles requiert une puissance de calculs considérable. Ces efforts seront-ils récompensés par de meilleures performances? Restez à l’affût pour un comparatif entre l’optimisation bayésienne et les algorithmes évolutifs.
Contact et code source
Ressources
[1] Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, & Christian Gagné ( 2012 ). DEAP: Evolutionary Algorithms Made Easy Journal of Machine Learning Research , 13 , 2171–2175 .
[2] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, D., Brucher, M., Perrot, M., & Duchesnay, E. (2011). Scikit-learn: Machine Learning in PythonJournal of Machine Learning Research, 12, 2825–2830.
[3] Davis, L. (1991). Handbook of genetic algorithms