Historique: PhD Theses

• Defended on Sept. 25. 2007 at Univ. Paris-Sud
• Advisors: Michèle Sebag and Nicolas Bredèche
• Manuscript (in English after the title
• Abstract : Reinforcement Learning (RL) is at the interface of control theory, supervised and unsupervised learning, optimization and cognitive sciences. While RL addresses many objectives with major economic impact, it raises deep theoretical and practical difficulties. This thesis brings some contributions to RL, mainly on three axis. The first axis corresponds to environment modeling, i.e. learning the transition function between two time steps. Factored approaches give an efficiently framework for the learning and use of this model. The Bayesian Networks are a tool to represent such a model, and this work brings new learning criterion, either in parametric learning (conditional probabilities) and non parametric (structure). The second axis is a study in continuous space and action RL, thanks to the dynamic programming algorithm. This analysis tackles three fundamental steps: optimization (action choice from the value function), supervised learning (regression) of the value function and choice of the learning examples (active learning). The third axis tackles the applicative domain of the game of Go, as a high dimensional discrete control problem, one of the greatest challenge in Machine Learning. The presented algorithms with their improvements made the resulting program, MoGo, win numerous international competitions, becoming for example the first go program playing at an amateur dan level on 9x9.

• Defended on Dec. 18. 2006 at École des Mines de Paris (GéoSciences)
• Advisor : Marc Schoenauer
• Manuscript
• Abstract :

• Defended on July 6. 2006 at Université Paris-Sud (Computer Science)
• Advisor : Marc Schoenauer
• Manuscript
• Abstract : The main contribution of this thesis is the definition of a new model of fuzzy system where the exponential growth of the number of rules with respect to the number of input variables is reduced, with an efficient representation for the design, using evolutionary algorithms. In the proposed model, the partition of the input space is not defined as a regular structure built as the intersection of the linguistic labels of input variables, as usual in fuzzy systems, but in terms of multidimensional regions, each one associated with a single fuzzy rule.
  
  The partition is defined based on well known concepts of computational geometry: the Voronoi diagrams and the Delaunay triangulations. The fuzzy system defined in terms of this partition has a clear and appealing structure. The representation of the individuals for evolutionary algorithms is simple, since each region in the multidimensional input space is represented with a single point. This geometric representation allows the use of geometric based operators for evolution. As an added advantage, the model allows an interesting approach for the inclusion of a priori knowledge about the solution of the problem in the individuals before and during the evolution.
  
  Experimental results on evolutionary design of Voronoi based fuzzy systems are presented in two control problems: an inverted cart pole system and a typical robot control application. The approach is extended to the design of recurrent Voronoi-based fuzzy systems. This extension is evaluated in two other control problems: a system identification problem, where the outputs are defined in terms of past inputs and outputs, and a problem from evolutionary robotics, where the ability to introduce a priori knowledge in the form of recursive rules is demonstrated.

• Defended on December 12. 2005 at Université Paris-Sud (Computer Science)
• Advisor : Antoine Cornuéjols and Michèle Sebag
• Manuscript(in French)
• Abstract :

• Defended on September 29. 2005 at Université Paris-Sud (Computer Science)
• Advisor : Marc Schoenauer
• Manuscript(in French)
• Abstract : L'architecture de subsomption de Brooks basée sur la modularité et sur une hiérarchie de comportements s'avéra être un grand pas vers les applications réelles après l'échec relatif des méthodes classiques. Cependant, l'inconvénient de cette méthode réside dans le fait que tout est mis en place par un concepteur humain, et plus la tâche du robot est ardue, plus la conception des modules nécessaires l'est aussi.

D'autre part, la robotique évolutionnaire, qui optimise par évolution artificielle des contrôleurs neuronaux (poids et éventuellement architecture), est une approche boîte noire par rapport aux comportements, mais requiert la définition d'une (ou plusieurs) fonction objectif dont la complexité va elle aussi croître avec la difficulté de la tâche demandée au robot.

L'approche des ``contrôleurs symboliques et des ``superviseurs proposée dans cette thèse tente d'établir un compromis entre les deux précédentes. Les sorties ne sont plus des ordres moteurs élémentaires mais des comportements plus évolués (comme ``aller tout droit, ``tourner à gauche, ...). Le choix peut également être effectué avec une librairie de comportements de plus haut niveau (comme ``explorer, ``aller vers la lumière, ...). Cette approche a été validée expérimentalement dans une expérience d'exploration, ou bien encore de recharge d'énergie.

Le second axe de recherche de cette thèse s'intéresse à l'apprentissage dans le cadre de la robotique évolutionnaire. Le baldwinisme qui consiste à modifier le génotype pendant la vie du robot (pendant l'évaluation des individus), mais qui reste sans conséquence sur le génotype lui-même pour la suite de l'évolution artificielle, est étudié ici à travers diverses expériences.

Les réseaux dits "auto-teaching", qui permettent au robot de modifier son comportement durant sa vie en s'appuyant sur un réseau modèle lui aussi obtenu par évolution, sont étudiés ici avec attention. Des défauts patents de ses propriétés de généralisation ont été mis en évidence.

Une architecture baptisée Action, Anticipation, Adaptation (AAA) a été créée pour tenter de pallier ces défauts. Cette architecture neuronale a donc trois tâches à remplir: l'action (contrôler les moteurs du robot), l'anticipation (basée sur les perceptions du robot mais également sur ses actions moteurs) et l'adaptation (basée sur la différence entre les sensations prédites au temps t et les sensations réellement observées au temps t+1). Les erreurs sur la prédiction des futures sensations du robot sont utilisées pour modifier en ligne les poids du contrôleur.

L'analyse détaillée de cette architecture d'une part a montré des capacités de généralisation plus robustes que celles des réseaux auto-teaching, et d'autre part a mis en évidence quelques capacités d'adaptation.

• Defended on December 20. 2004 at Université Paris 6 (Applied Maths)
• Advisor : Marc Schoenauer
• Manuscript(in French)
• Abstract : Les Algorithmes Evolutionnaires sont des algorithmes d'optimisation stochastique inspirés de la théorie de l'évolution des espèces de Darwin. Nous les étudions ici dans le cadre de l'optimisation continue, c'est-à-dire pour la minimisation de fonctions à variables relles.

Le principe de ces algorithmes consiste à faire évoluer un ensemble de points en rajoutant typiquement un vecteur gaussien centré aux points existants (ceci constitue l'opération dite de mutation), puis à slectionner certains de ces points (ceux ayant les valeurs de fonction les plus basses) et recommencer. Un point crucial de ces algorithmes est l'adaptation des paramètres de l'algorithme aux différentes phases de la recherche d'un optimum : la phase d'exploration et la phase d'exploitation. En particulier, l'adaptation des paramtères du vecteur gaussien utilisé pour la mutation a constitué une part importante des développements effectués sur ces algorithmes ces dernières années. On distingue les méthodes adaptant seulement le pas de la mutation des méthodes adaptant également la matrice de covariance de la mutation.

Dans une première partie, nous proposons une méthode d'apprentissage de la matrice de covariance pour la mutation, basée sur une approximation locale de la fonction optimiser.

Dans une deuxième partie, nous étudions sur un plan théorique les méthodes d'adaptation du pas de la mutation et démontrons des conditions suffisantes reliant la taille de la population et les paramètres de la mutation garantissant la convergence linaire de certaines de ces méthodes sur certaines classes de fonctions. Ces études théoriques utilisent d'une part la théorie des martingales et d'autre part reposent sur l'étude du modèle markovien associé à l'algorithme évolutionnaire. Dans ce dernier cas, la convergence de l'algorithme précisment étudi repose sur l'étude de conditions de stabilité d'une chaîne de Markov sous-jacente à l'algorithme. Ces conditions de stabilité sont établies à l'aide de conditions de drift de Foster-Lyapunov.

Dans une troisième partie, nous présentons une application des algorithmes évolutionnaires à un problème de contrôle en physique quantique.

• Defended on December 13. 2004 at Université Paris-Sud
• Advisor : Yves Kodratoff
• Dissertation should be available soon.
• Abstract : L'extraction d'information à partir de textes spécialisés exige l'application d'un processus complet de fouille de textes. Une des étapes de ce processus consiste à extraire les termes dans les textes. Les termes sont définis comme des groupes de mots représentant des traces linguistiques de concepts. Le terme "data mining" évoque, par exemple, le concept de "technique informatique".

La tâche d'acquisition de la terminologie consiste, dans un premier temps, à extraire les mots voisins vérifiant des patrons syntaxiques simples tels que Nom-Nom, Adjectif-Nom, etc. Une des spécificités de notre algorithme est son aspect itératif utilisé pour construire des termes complexes. Par exemple, si lors de la première itération le terme "data mining" de type Nom-Nom est extrait, à l'étape suivante le terme "data-mining application" peut être obtenu. De plus, avec EXIT (EXtraction Itérative de la Terminologie) l'expert est placé au centre du processus d'extraction de la terminologie et il peut intervenir tout au long du processus. Outre l'aspect itératif du système mis en place, de nombreux paramètres ont été ajoutés. Un des paramètres permet d'utiliser différents critères statistiques pour classer les termes selon leur pertinence par rapport à une tâche à réaliser. Notre approche a été validée à partir de quatre corpus de langues, de tailles et de domaines de spécialité différents.
Enfin, une méthode fondée sur un processus d'apprentissage supervisé est proposée afin d'améliorer la qualité de la terminologie extraite.

• Defended October 6. 2004 at Ecole Polytechnique (Applied Maths)
• Advisor : Marc Schoenauer
• Manuscript (in French)
• Abstract : Les algorithmes évolutionnaires sont des algorithmes d'optimisation stochastique d'ordre zéro qui s'appliquent à des espaces de recherche non standard, pouvant par exemple combiner des variables continues et discrètes. Ces algorithmes sont utilisés pour résoudre des problèmes difficiles où ils permettent souvent de proposer de meilleures solutions que les algorithmes classiques d'optimisation lorsque ces derniers s'appliquent. Leur principal point faible est la nécessité d'évaluer la fonction objectif un grand nombre de fois. Ceci les rend inapplicables en pratique pour des problèmes où l'évaluation de cette fonction est coûteuse en temps de calcul (résultat d'un lourd calcul d'éléments finis par exemple). Le but de la thèse est de proposer une méthode permettant de diminuer le nombre de calculs de la fonction objectif dans le cas de fonctions coûteuses en temps de calcul et ainsi de diminuer le coût calcul. La méthode consiste à introduire un nouvel opérateur de mutation, nommé SDM (pour {\em Surrogate Deterministic Mutation}, basé sur une méthode d'approximation (nous étudierons en particulier comme méthodes d'approximation les Machines à Support Vecteur — SVM — et la méthode du Krigeage). L'opérateur SDM utilise des individus déjà évalués et se trouvant localement autour de l'individu devant être muté, pour définir une fonction modèle qui est facile à optimiser. Pour obtenir un bon modèle, non seulement le nombre de points d'exemples est important, mais aussi leur disposition autour de l'individu à muter. L'individu trouvé après optimisation du modèle est évalué avec la vraie fonction objectif et réinjecté dans la population. Nous avons démontré sur différentes fonctions-tests une nette amélioration de la convergence locale par rapport à un algorithme évolutionnaire classique, en l'occurrence les stratégies d'évolution (ES).

La thèse est formée de six chapitres :

• Le premier chapitre consiste en un survol de l'état de l'art des différentes techniques qui seront utilisées ensuite dans le reste de la thèse. En premier lieu, nous présentons les algorithmes d'optimisation déterministes d'ordre supérieur à un (optimisation différentiable). Ensuite, nous introduisons les algorithmes stochastiques allant des méthodes de Monte Carlo, passant par le recuit simulé, les algorithmes évolutionnaires (dont les stratégies d'évolutions (ES)) et pour finir la méthode de l'Adaptation de la Matrice de Covariance (CMA). Puis nous passons en revue les principales méthodes d'approximation disponibles : des représentations sous forme de maillage éléments finis aux méthodes spectrales (dont lapproximation de Legendre) et les méthodes à noyau (dont la méthode de Machines à Support Vecteur et la méthode de Krigeage). Finalement, nous faisons un état de l'art détaillé des méthodes hybrides précédemment proposées combinant une approche déterministe et/ou une approche stochastique et/ou une méthode d'approximation. Le chapitre se termine sur la présentation de l'ensemble des fonctions-tests qui seront ensuite utilisées pour valider notre approche.
• Le deuxième chapitre discute la possibilité de modéliser la fonction objectif à partir de points pré-évalués et d'utiliser les optimaux des modèles approchés comme des candidats-optima de la fonction objectif. Nous utilisons comme méthodes d'approximations les SVM et le Krigeage. Pour déterminer les optima du modèle nous utilisons comme algorithme déterministe la méthode L-BFGS-B. Ces méthodes d'approximation déterminent d'une manière unique un mo\-dè\-le à partir des points évalués et des paramètres représentant la régularité et l'erreur souhaitée sur les points (SVM). Le choix de ces paramètres offre la possibilité de contrôler les modèles de façon à trouver un modèle adapté à nos besoins. Nous testons différents critères pour le choix de ces paramètres. Notons que le but de l'approximation n'est pas ici d'interpoler le mieux possible la fonction objectif, mais de trouver un individu meilleur que les points d'apprentissage en un temps raisonnable. Les différents tests de ce chapitre seront faits sur la fonction sphère.
• Le troisième chapitre a pour but de définir un algorithme stochastique itératif simple, nommé AlgoAlea, basé sur une loi définie à travers des paramètres constants. Après une brève étude de la convergence de cet algorithme, nous l'hybridons respectivement avec une méthode déterministe (BFGS) pour définir un premier algorithme nommé AlgoDet, puis avec une méthode d'approximation (SVM ou Krigeage) et une méthode déterministe (BFGS), définissant l'algorithme AlgoApp. Dans le cadre itératif et dans le souci d'optimiser la recherche des paramètres de régularité et les autres paramètres définissant le modèle, nous proposons une approche dynamique dans la recherche des paramètres d'une itération à l'autre. Nous validons notre approche sur les fonctions-tests décrites au chapitre 2. Pour finir, nous définissons une variante de l'algorithme hybride, variante nommée AlgoAppBis. Au lieu d'utiliser un algorithme déterministe pour optimiser le modèle, nous utilisons un algorithme évolutionnaire, les stratégies d'évolution (ES). Nous comparons enfin les différents algorithmes sur les fonctions-tests, et nous montrons que les algorithmes itératifs AlgoApp et AlgoAppbis ont un comportement quasi-déterministe, et nous pointons des difficultés d'un algorithme déterministe comme BFGS sur certaines fonctions-tests.
• Le quatrième chapitre consiste à pallier les problèmes rencontrés dans le chapitre précédant en proposant une hybridation de l'algorithme AlgoApp avec un algorithme évolutionnaire global, ici les Stratégies d'évolution isotropes, l'algorithme AlgoApp se chargeant de la recherche locale, et ES de la recherche globale. Pour cela nous introduisons l'opérateur de mutation SDM ({\em Surrogate Determnistic Mutation}). Chaque mutation correspond de fait à une itération élémentaire de l'algorithme AlgoApp. L'interaction entre SDM et ES s'effectue à travers les paramètres des mutations gaussiennes. Nous définissons ainsi un paramètre de contrôle qui agit directement sur l'équilibre exploration-exploitation. Nous comparons notre approche avec une autre approche, inspirée de MAES introduite par Thomas Bäck (elle-même représentante de l'approche dynamique définie par Andy Keane), et nous la validons sur les fonctions-tests.
• Dans le cinquième chapitre, nous appliquons SDM-ES à un problème pratique provenant de la finance quantitative. Il s'agit d'un modèle de marché incomplet qui traite la problématique du {\em smile} tout en proposant une couverture dynamique optimale. La calibration d'un tel modèle conduit à la résolution d'un problème de minimisation mal posé. Nous montrons que les méthodes hybrides de type SDM-ES peuvent apporter un plus par rapport à des méthodes déterministes comme L-BFGS-B qui ne donnent pas toujours la bonne solution.
• Enfin, le sixième chapitre conclut la thèse par un bref rappel des principaux résultats obtenus. Prenant comme exemple le cas de la fonction Rosenbrock, réputée difficile, nous donnons quelques perspectives sur les adaptations possibles des hybridations proposées aux cas mal conditionnés. Nous montrons qu'un couplage de SDM avec la méthode plus récente de l'Adaptation de la Matrice de Covariance (CMA) semble une voie très prometteuse. Nous montrons également que le noyau sigmoïde, bien que beaucoup plus délicat à maîtriser que le noyau Gaussien le plus utilisé (et en particulier utilisé dans la thèse), est très intéressant et mérite une étude systématique.

• Defended on March 5. 2004 at Ecole Polytechnique (Applied Maths)
• Advisor : Marc Schoenauer
• PDF file or gzipped Postscript (in French)
• Abstract :

• Defended on December 16. 2003 at Université Paris-Sud (Computer Science)
• Advisor : Yves Kodratoff
• Manuscript (in French)
• Abstract : Le travail réalisé dans le cadre de cette thèse concerne l'extraction de connaissances dans des données transactionnelles. L'analyse de telles données est souvent contrainte par la définition d'un support minimal utilisé pour filtrer les connaissances non intéressantes. Les experts des données ont souvent des difficultés pour déterminer ce support.

Nous avons proposé une méthode permettant de ne pas fixer un support minimal et fondée sur l'utilisation de mesures de qualité. Nous nous sommes focalisés sur l'extraction de connaissances de la forme "règles d'association". Ces règles doivent vérifier un ou plusieurs critères de qualité pour être considérées comme intéressantes et proposées à l'expert. Nous avons proposé deux mesures de qualité combinant différents critères et permettant d'extraire des règles intéressantes.
Nous avons ainsi pu proposer un algorithme permettant d'extraire ces règles sans utiliser la contrainte du support minimal. Le comportement de notre algorithme a été étudié en présence de données bruitées et nous avons pu mettre en évidence la difficulté d'extraire automatiquement des connaissances fiables à partir de données bruitées. Une des solutions que nous avons proposée consiste à évaluer la résistance au bruit de chaque règle et d'en informer l'expert lors de l'analyse et de la validation des connaissances obtenues.
Enfin, une étude sur des données réelles a été effectuée dans le cadre d'un processus de fouille de textes. Les connaissances recherchées dans ces textes sont des règles d'association entre des concepts définis par l'expert et propres au domaine étudié. Nous avons proposé un outil permettant d'extraire les connaissances et d'assister l'expert lors de la validation de celles-ci. Les différents résultats obtenus montrent qu'il est possible d'obtenir des connaissances intéressantes à partir de données textuelles en minimisant la sollicitation de l'expert dans la phase d'extraction des règles d'association.

• Defended on May 6. 2003 at École Polytechnique (Applied Maths)
• Advisor : Marc Schoenauer and Taieb Hadhri (École Polytechnique de Tunis)
• PDF file (2 Mo, in French)
• Abstract :

• Defended on March 27. 2001 at Université Paris Sud (Computer Science)
• Advisor : Marc Schoenauer
• gzipped Postscript in French.

• Defended on december 14. 2000 at Université Paris-Sud (Computer Science)
• Advisor: Marc Schoenauer and Daniel Delahaye
• gzipped Postscript in French.

• Defended on December 13. 2000 at Université de Pau (Applied Maths)
• Advisors: Mohamed Amara and Marc Schoenauer
• gzipped Postscript in French.

• Defended on February 5. 1999 at Ecole Polytechnique (Applied Maths)
• Advisor : Marc Schoenauer
• gzipped Postscript in English, except the firts introductory 40 pages.

• Defended in December 1998 at Ecole Polytechnique (Computer Sciences)
• Advisor : Marc Schoenauer
• gzipped Postscript in French.

• Defended in June 1998 at Ecole Polytechnique (Applied Maths)
• Advisor : Marc Schoenauer -
• gzipped Postscript in French.

• Defended in May 1997 at Ecole Polytechnique (Applied Maths)
• Advisor : Marc Schoenauer
• gzipped Postscript in French.

• Defended in July 1996 at Université Paris 6 (Applied Maths)
• Advisor : Marc Schoenauer
• gzipped Postscript in French.