offres d'emploi formations actualités contact accès annuaire intranet
Thèses >

Contributions à l’apprentissage automatique par programmation génétique

Sébastien Malher - manuscrit

jeudi 20 novembre 2008 à 10h00


Dans cette thèse, la Programmation génétique (PG) est appliquée à l’Apprentissage automatique. Inspirée par l’Evolution darwinienne, l’heuristique de PG (Koza, 1992) génère des programmes pour résoudre un problème posé. Nos comparaisons expérimentales montrent comment mieux utiliser la PG.

Choisir une représentation induit un biais pour tout problème. C’est le cas en robotique, pour le problème du Santa Fe Trail ou SFT, résolu par la PG, Grammatical Evolution et Bayesian Automatic Programming. Ces variantes, basées sur des grammaires explicites et non closes, ont des biais exploratoires différents, mais modifient aussi des caractéristiques du problème. Nos expériences invalident certains résultats, précisent la difficulté du SFT et incitent à ne plus utiliser la séquence de trois actions progn3.

D’autre part, la PG est ralentie par la congestion, croissance excessive des programmes. Poli (2003) régule la taille moyenne par le contrôle tarpéien. Cela aide-t-il à découvrir des hypothèses plus simples, plus générales, phénomène nommé « rasoir d’Occam » ? En observant la généralisation de programme en régression symbolique, nous montrons que ce contrôle peut construire des hypothèses plus généralisables que la PG et validons par l’expérience l’effet de lutte contre la congestion.

Nous proposons enfin ROCBoost,métaheuristique de boosting (Freund et Shapire) qui combine et pondère plusieurs apprenants. Notre calcul des poids maximise l’aire sous la courbe ROC (Receiver Operating Characteristic). Employée avec la PG et avec les Stratégies d’Evolution, ROCBoost améliore des résultats publiés et place la PG comme une heuristique compétitive en classification supervisée.