Extending Genetic Programming for supervised learning from very large datasets (Big data)

Dans cette thèse, nous étudions l'adaptation des Programmes Génétiques (GP) pour surmonter l'obstacle du volume de données dans les problèmes Big Data. GP est une méta‐heuristique qui a fait ses preuves pour les problèmes de classification. Néanmoins, son coût de calcul est un frein à son utilisation avec les larges bases d’apprentissage. Tout d'abord, nous effectuons une revue approfondie enrichie par une étude comparative expérimentale des algorithmes d'échantillonnage utilisés avec GP. Puis, à partir des résultats de l'étude précédente, nous proposons quelques extensions basées sur l'échantillonnage hiérarchique. Ce dernier combine des algorithmes d'échantillonnage actif à plusieurs niveaux et s’est prouvé une solution appropriée pour mettre à l’échelle certaines techniques comme TBS et pour appliquer GP à un problème Big Data (cas de la classification des bosons de Higgs). Par ailleurs, nous formulons une nouvelle approche d'échantillonnage appelée échantillonnage adaptatif, basée sur le contrôle de la fréquence d'échantillonnage en fonction du processus d'apprentissage, selon les schémas fixe, déterministe et adaptatif. Enfin, nous présentons comment transformer une implémentation GP existante (DEAP) en distribuant les évaluations sur un cluster Spark. Nous démontrons comment cette implémentation peut être exécutée sur des clusters à nombre de nœuds réduit grâce à l’échantillonnage. Les expériences montrent les grands avantages de l'utilisation de Spark pour la parallélisation de GP.In this thesis, we investigate the adaptation of GP to overcome the data Volume hurdle in Big Data problems. GP is a well-established meta-heuristic for classification problems but is impaired with its computing cost. First, we conduct an extensive review enriched with an experimental comparative study of training set sampling algorithms used for GP. Then, based on the previous study results, we propose some extensions based on hierarchical sampling. The latter combines active sampling algorithms on several levels and has proven to be an appropriate solution for sampling techniques that can’t deal with large datatsets (like TBS) and for applying GP to a Big Data problem as Higgs Boson classification.Moreover, we formulate a new sampling approach called “adaptive sampling”, based on controlling sampling frequency depending on learning process and through fixed, determinist and adaptive control schemes. Finally, we present how an existing GP implementation (DEAP) can be adapted by distributing evaluations on a Spark cluster. Then, we demonstrate how this implementation can be run on tiny clusters by sampling.Experiments show the great benefits of using Spark as parallelization technology for GP