Historique: PhD Theses
Aperçu de cette version: 85
Click on the + signs for more details on a PhD
Efficient End-to-End Monitoring for Fault Management in Distributed Systems Dawei Feng Mar. 2014
[+]- Defended on March 27., 2014 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Cécile Germain-Renaud
- Abstract: In this dissertation, we present our work on fault management in distributed systems, with motivating application roots in monitoring fault and abrupt change of large computing systems like the grid and the cloud. Instead of building a complete a priori knowledge of the software and hardware infrastructures as in conventional detection or diagnosis methods, we propose to use appropriate techniques to perform end-to-end monitoring for such large scale systems, leaving the inaccessible details of involved components in a black box.For the fault monitoring of a distributed system, we first model this probe-based application as a static collaborative prediction (CP) task, and experimentally demonstrate the effectiveness of CP methods by using the max margin matrix factorization method. We further introduce active learning to the CP framework and exhibit its critical advantage in dealing with highly imbalanced data, which is specially useful for identifying the minority fault class.Further we extend the static fault monitoring to the sequential case by proposing the sequential matrix factorization (SMF) method. SMF takes a sequence of partially observed matrices as input, and produces predictions with information both from the current and history time windows. Active learning is also employed to SMF, such that the highly imbalanced data can be coped with properly. In addition to the sequential methods, a smoothing action taken on the estimation sequence has shown to be a practically useful trick for enhancing sequential prediction performance.Since the stationary assumption employed in the static and sequential fault monitoring becomes unrealistic in the presence of abrupt changes, we propose a semi-supervised online change detection (SSOCD) framework to detect intended changes in time series data. In this way, the static model of the system can be recomputed once an abrupt change is detected. In SSOCD, an unsupervised offline method is proposed to analyze a sample data series. The change points thus detected are used to train a supervised online model, which gives online decision about whether there is a change presented in the arriving data sequence. State-of-the-art change detection methods are employed to demonstrate the usefulness of the framework.All presented work is verified on real-world datasets. Specifically, the fault monitoring experiments are conducted on a dataset collected from the Biomed grid infrastructure within the European Grid Initiative, and the abrupt change detection framework is verified on a dataset concerning the performance change of an online site with large amount of traffic.
Monte Carlo Tree Search pour les problèmes de décision séquentielle en milieu continus et stochastiques Adrien Couétoux Sept. 2013
[+]- Defended on September 30., 2013 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Olivier Teytaud
Learning Deep Representations : Toward a better new understanding of the deep learning paradigm Ludovic Arnold Juin 2013
[+]- Defended on June 25., 2013 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Hélène Paugam-Moisy;Philippe Tarroux
- Abstract: Since 2006, deep learning algorithms which rely on deep architectures with several layers of increasingly complex representations have been able to outperform state-of-the-art methods in several settings. Deep architectures can be very efficient in terms of the number of parameters required to represent complex operations which makes them very appealing to achieve good generalization with small amounts of data. Although training deep architectures has traditionally been considered a difficult problem, a successful approach has been to employ an unsupervised layer-wise pre-training step to initialize deep supervised models. First, unsupervised learning has many benefits w.r.t. generalization because it only relies on unlabeled data which is easily found. Second, the possibility to learn representations layer by layer instead of all layers at once further improves generalization and reduces computational time. However, deep learning is a very recent approach and still poses a lot of theoretical and practical questions concerning the consistency of layer-wise learning with many layers and difficulties such as evaluating performance, performing model selection and optimizing layers. In this thesis we first discuss the limitations of the current variational justification for layer-wise learning which does not generalize well to many layers. We ask if a layer-wise method can ever be truly consistent, i.e. capable of finding an optimal deep model by training one layer at a time without knowledge of the upper layers. We find that layer-wise learning can in fact be consistent and can lead to optimal deep generative models. To that end, we introduce the Best Latent Marginal (BLM) upper bound, a new criterion which represents the maximum log-likelihood of a deep generative model where the upper layers are unspecified. We prove that maximizing this criterion for each layer leads to an optimal deep architecture, provided the rest of the training goes well. Although this criterion cannot be computed exactly, we show that it can be maximized respectively by auto-encoders when the encoder part of the model is allowed to be as rich as possible. This gives a new justification for stacking models trained to reproduce their input and yields better results than the state-of-the-art variational approach. Additionally, we give a tractable approximation of the BLM upper-bound and show that it can accurately estimate the final log-likelihood of models. Taking advantage of these theoretical advances, we propose a new method for performing layer-wise model selection in deep architectures, and a new criterion to assess whether adding more layers is justified. As for the difficulty of training layers, we also study the impact of metrics and parametrization on the commonly used gradient descent procedure for log-likelihood maximization. We show that gradient descent is implicitly linked to the metric of the underlying space and that the Euclidean metric may often be an unsuitable choice as it introduces a dependence on parametrization and can lead to a breach of symmetry. To alleviate this issue, we study the benefits of the natural gradient and show that it can restore symmetry, regrettably at a high computational cost. We thus propose that a centered parametrization may alleviate the problem with almost no computational overhead.
Contributions to Simulation-based High-dimensional Sequential Decision Making Jean-Baptiste Hoock Apr. 2013
[+]- Defended on April 10., 2013 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Olivier Teytaud
- Abstract: My thesis is entitled "Contributions to Simulation-based High-dimensional Sequential Decision Making". The context of the thesis is about games, planning and Markov Decision Processes.
from an initial state until a final state in which the agent can not make decision anymore. At each
timestep, the agent receives an observation of the state of the environment. From this observation
and its knowledge, the agent makes a decision which modifies the state of the environment. Then,
the agent receives a reward and a new observation. The goal is to maximize the sum of rewards
obtained during a simulation from an initial state to a final state. The policy of the agent is the
function which, from the history of observations, returns a decision.
We work in a context where (i) the number of states is huge, (ii) reward carries little
information, (iii) the probability to reach quickly a good final state is weak and (iv) prior knowledge
is either nonexistent or hardly exploitable.
Both applications described in this thesis present these constraints : the game of Go and a
3D simulator of the european project MASH (Massive Sets of Heuristics).
In order to take a satisfying decision in this context, several solutions are brought :
1. Simulating with the compromise exploration/exploitation (MCTS)
2. Reducing the complexity by local solving (GoldenEye)
3. Building a policy which improves itself (RBGP)
4. Learning prior knowledge (CluVo+GMCTS)
Monte-Carlo Tree Search (MCTS) is the state of the art for the game of Go. From a model of
the environment, MCTS builds incrementally and asymetrically a tree of possible futures by
performing Monte-Carlo simulations. The tree starts from the current observation of the agent. The
agent switches between the exploration of the model and the exploitation of decisions which
statistically give a good cumulative reward. We discuss 2 ways for improving MCTS : the
parallelization and the addition of prior knowledge.
The parallelization does not solve some weaknesses of MCTS; in particular some local
problems remain challenges. We propose an algorithm (GoldenEye) which is composed of 2 parts :
detection of a local problem and then its resolution. The algorithm of resolution reuses some
concepts of MCTS and it solves difficult problems of a classical database.
The addition of prior knowledge by hand is laborious and boring. We propose a method
called Racing-based Genetic Programming (RBGP) in order to add automatically prior knowledge.
The strong point is that RBGP rigorously validates the addition of a prior knowledge and RBGP can
be used for building a policy (instead of only optimizing an algorithm).
In some applications such as MASH, simulations are too expensive in time and there is no
prior knowledge and no model of the environment; therefore Monte-Carlo Tree Search can not be
used. So that MCTS becomes usable in this context, we propose a method for learning prior
knowledge (CluVo). Then we use pieces of prior knowledge for improving the rapidity of learning
of the agent and for building a model, too. We use from this model an adapted version of Monte-
Carlo Tree Search (GMCTS). This method solves difficult problems of MASH and gives good
results in an application to a word game.
Environment-driven Distributed Evolutionary Adaptation for Collective Robotic Systems Jean-Marc Montanier Mar. 2013
[+]- Defended on March 1.., 2013 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Nicolas Bredèche
- Abstract: Cette thèse décrit une partie du travail effectué dans le cadre du projet européen Symbrion 1 . Ce projet vise à la réalisation de tâches complexes nécessitant la coopération de multiples robots dans un cadre de robotique en essaim (au moins 100 robots opérant ensemble). De multiples problèmes sont étudiés par le projet dont : l'auto-assemblage de robots en structures complexes et l'auto-organisation d'un grand nombre de robots afin de réaliser une tâche commune. Le principal sujet porte sur les mécanismes d'auto-adaptation pour la robotique modulaire et en essaim, avec un intérêt pour des capacités de forte coordination et de coopération à l'échelle de l'essaim.Les difficultés rencontrées dans la réalisation de ce projet sont dues à l'utilisation de robots dans des environnements ouverts restant inconnus jusqu'à la phase de déploiement. Puisque les conditions d'opérations ne peuvent être prédites à l'avance, des algorithmes d'apprentissage en ligne doivent être utilisés pour élaborer les comportements utilisés. Lorsqu'un grand nombre de robots sont utilisés, plusieurs considérations doivent être prise en compte : capacité de communication réduite, faible mémoire, faible capacité de calcul. Par conséquent les algorithmes d'apprentissage en ligne doivent être distribués à travers l'essaim.De multiples approches ont déjà été proposées pour faire face aux problèmes posés par l'apprentissage en ligne décentralisé de comportements robotiques, parmi lesquels la robotique probabiliste, l'apprentissage par renforcement, et la robotique évolutionnaire. Cependant, le problème abordé dans le cadre de cette thèse se caractérise par le fait que l'on considère un groupe de robots (en lieu et place d'un seul et unique robot). De plus, dû à la nature ouverte de l'environnement, il n'est pas possible de supposer que l'ingénieur humain ait les connaissances nécessaires pour définir les éléments indispensables aux processus d'apprentissage.Assurer l'intégrité de l'essaim est placé en tant que premier élément d'une feuille de route visant à définir un ensemble d'étapes nécessaires à la réalisation d'une tâche par un groupe de robot dans un environnement ouvert :- Étape 1 : Assurer l'intégrité de l'essaim.- Étape 2 : Maintenir les robots disponibles en tant que service à l'utilisateur.- Étape 3 : Réaliser la tâche définie par l'utilisateur.Dans le cadre de cette thèse nous travaillons à la réalisation de l'étape 1 de cette feuille de route, et assumons l'hypothèse de travail suivante :Hypothèse de travail : Dans un cadre de robotique collective en environnement ouvert, la réalisation d'une tâche définie par l'utilisateur implique tout d'abord un comportement auto-adaptatif.Le sujet de cette thèse est la réalisation de solutions algorithmiques décentralisées pouvant garantir l'in- tégrité d'un essaim de robots en environnement ouvert lorsque un système robotique collectif utilise une communication locale. La principale difficulté à sa résolution est le besoin de prendre en compte l'envi- ronnement. En effet, en fonction de l'environnement courant, les robots peuvent avoir à démontrer une grande variété de comportements à l'échelle globale comme la coopération, la spécialisation, l'altruisme, ou la division du travail.Dans cette thèse nous introduisons et définissons le problème de l'Adaptation Evolutionnaire Distribuée Guidée par l'Environnement. Nous proposons un algorithme pour résoudre ce problem. Cet algorithme a été validé aussi bien en simulation que sur des robots réels. Il a été utilisé pour étudier le problème de l'auto-adaptation dans les environnements suivants :- Environnement où l'émergence de consensus comportementaux est nécessaire.- Environnements où la robustesse face à des changements environnementaux est nécessaires.- Environnements où des comportements altruistes sont nécessaires.
Surrogate-Assisted Evolutionary Algorithms Ilya Loshchilov Jan. 2013
[+]- Defended on Jan. 8., 2013 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Marc Schoenauer and Michèle Sebag
- Abstract: Les Algorithmes Évolutionnaires (AEs) ont été très étudiés en raison de leur capacité à résoudre des problèmes d'optimisation complexes en utilisant des opérateurs de variation adaptés à des problèmes spécifiques. Une recherche dirigée par une population de solutions offre une bonne robustesse par rapport à un bruit modéré et la multi-modalité de la fonction optimisée, contrairement à d'autres méthodes d'optimisation classiques telles que les méthodes de quasi-Newton. La principale limitation de AEs, le grand nombre d'évaluations de la fonction objectif, pénalise toutefois l'usage des AEs pour l'optimisation de fonctions chères en temps calcul. La présente thèse se concentre sur un algorithme évolutionnaire, Covariance Matrix Adaptation Evolution Strategy (CMA-ES), connu comme un algorithme puissant pour l'optimisation continue boîte noire. Nous présentons l'état de l'art des algorithmes, dérivés de CMA-ES, pour résoudre les problèmes d'optimisation mono- et multi-objectifs dans le scénario boîte noire. Une première contribution, visant l'optimisation de fonctions coûteuses, concerne l'approximation scalaire de la fonction objectif. Le meta-modèle appris respecte l'ordre des solutions (induit par la valeur de la fonction objectif pour ces solutions) ; il est ainsi invariant par transformation monotone de la fonction objectif. L'algorithme ainsi défini, saACM-ES, intègre étroitement l'optimisation réalisée par CMA-ES et l'apprentissage statistique de meta-modèles adaptatifs ; en particulier les meta-modèles reposent sur la matrice de covariance adaptée par CMA-ES. saACM-ES préserve ainsi les deux propriété clé d'invariance de CMA-ES~: invariance i) par rapport aux transformations monotones de la fonction objectif; et ii) par rapport aux transformations orthogonales de l'espace de recherche. L'approche est étendue au cadre de l'optimisation multi-objectifs, en proposant deux types de meta-modèles (scalaires). La première repose sur la caractérisation du front de Pareto courant (utilisant une variante mixte de One Class Support Vector Machone (SVM) pour les points dominés et de Regression SVM pour les points non-dominés). La seconde repose sur l'apprentissage d'ordre des solutions (rang de Pareto) des solutions. Ces deux approches sont intégrées à CMA-ES pour l'optimisation multi-objectif (MO-CMA-ES) et nous discutons quelques aspects de l'exploitation de meta-modèles dans le contexte de l'optimisation multi-objectif. Une seconde contribution concerne la conception d'algorithmes nouveaux pour l'optimi\-sation mono-objectif, multi-objectifs et multi-modale, développés pour comprendre, explorer et élargir les frontières du domaine des algorithmes évolutionnaires et CMA-ES en particulier. Spécifiquement, l'adaptation du système de coordonnées proposée par CMA-ES est couplée à une méthode adaptative de descente coordonnée par coordonnée. Une stratégie adaptative de redémarrage de CMA-ES est proposée pour l'optimisation multi-modale. Enfin, des stratégies de sélection adaptées aux cas de l'optimisation multi-objectifs et remédiant aux difficultés rencontrées par MO-CMA-ES sont proposées.
Contributions à l'apprentissage et l'inférence adaptatifs : Applications à l'ajustement d'hyperparamètres et à la physique des astroparticules Rémi Bardenet Nov. 2012
[+]- Defended on Nov. 19., 2012 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisor: Balazs Kégl
- Abstract: Les algorithmes d'inférence ou d'optimisation possèdent généralement des hyperparamètres qu'il est nécessaire d'ajuster. Nous nous intéressons ici à l'automatisation de cette étape d'ajustement et considérons différentes méthodes qui y parviennent en apprenant en ligne la structure du problème considéré.La première moitié de cette thèse explore l'ajustement des hyperparamètres en apprentissage artificiel. Après avoir présenté et amélioré le cadre générique de l'optimisation séquentielle à base de modèles (SMBO), nous montrons que SMBO s'applique avec succès à l'ajustement des hyperparamètres de réseaux de neurones profonds. Nous proposons ensuite un algorithme collaboratif d'ajustement qui mime la mémoire qu'ont les humains d'expériences passées avec le même algorithme sur d'autres données.La seconde moitié de cette thèse porte sur les algorithmes MCMC adaptatifs, des algorithmes d'échantillonnage qui explorent des distributions de probabilité souvent complexes en ajustant leurs paramètres internes en ligne. Pour motiver leur étude, nous décrivons d'abord l'observatoire Pierre Auger, une expérience de physique des particules dédiée à l'étude des rayons cosmiques. Nous proposons une première partie du modèle génératif d'Auger et introduisons une procédure d'inférence des paramètres individuels de chaque événement d'Auger qui ne requiert que ce premier modèle. Ensuite, nous remarquons que ce modèle est sujet à un problème connu sous le nom de label switching. Après avoir présenté les solutions existantes, nous proposons AMOR, le premier algorithme MCMC adaptatif doté d'un réétiquetage en ligne qui résout le label switching. Nous présentons une étude empirique et des résultats théoriques de consistance d'AMOR, qui mettent en lumière des liens entre le réétiquetage et la quantification vectorielle.
Optimisation évolutionnaire multi-objectif parallèle : application à la combustion Diesel Mouadh Yagoubi July 2012
[+]- Defended on july. 3. 2012 at LRI (Univ. Paris-Sud)
- Dissertation in PDF
- Advisors: Ludovic thobois and Marc Schoenauer
- Abstract: Avec la sévérisation des réglementations environnementales sur les émissions polluantes (normes Euro) des moteurs d’automobiles, la nécessité de maitriser les phénomènes de combustion a motivé le développement de la simulation numérique comme outil d’aide à la conception. Tenant compte de la complexité des phénomènes à modéliser, et de l’antagonisme des objectifs à optimiser, l’optimisation évolutionnaire multi-objectif semble être la mieux adaptée pour résoudre ce type de problèmes. Cependant, l’inconvénient principal de cette approche reste le coût très élevé en termes de nombre d’évaluations qui peut devenir très contraignant dans le contexte des optimisations réelles caractérisées par des évaluations très coûteuses.
Motivés par le phénomène d’hétérogénéité des coûts des évaluations, nous nous proposons d’étudier les schémas d’évolution stationnaires asynchrones dans une configuration parallèle de type « maître-esclave ». Ces schémas permettent une utilisation plus efficace des processeurs sur la grille de calcul, et par conséquent de réduire le coût global de l’optimisation.
Ce problème a été attaqué dans un premier temps d’un point de vue algorithmique, à travers une adaptation artificielle des algorithmes évolutionnaires multi-objectifs au contexte des optimisations réelles caractérisées par un coût d’évaluation hétérogène. Dans un deuxième temps, les approches développées et validées dans la première partie sur des problèmes analytiques, ont été appliquées sur la problématique de la combustion Diesel qui représente le contexte industriel de cette thèse. Dans ce cadre, deux types de modélisations ont été utilisés : la modélisation phénoménologique 0D et la modélisation multidimensionnelle 3D.
La modélisation 0D a permis par son temps de retour raisonnable (quelques heures par évaluation) de comparer l’approche stationnaire asynchrone avec celle de l’état de l’art en réalisant deux optimisations distinctes. Un gain de l’ordre de 42 % a été réalisé avec l’approche stationnaire asynchrone.
Compte tenu du temps de retour très coûteux de la modélisation complète 3D (quelques jours par évaluation), l’approche asynchrone stationnaire déjà validée a été directement appliquée. L’analyse physique des résultats a permis de dégager un concept intéressant de bol de combustion permettant de réaliser un gain en termes d’émissions polluantes.
Well Placement Optimization Zyed Bouzarkouna Apr. 2012
[+]- Defended on Apr. 3. 2012 at LRI (Univ. Paris-Sud)
- Advisors: Marc Schoenauer and Anne Auger
- Dissertation in PDF
- Abstract: The amount of hydrocarbon recovered can be considerably increased by finding optimal placement of non-conventional wells. For that purpose, the use of optimization algorithms, where the objective function is evaluated using a reservoir simulator, is needed. Furthermore, for complex reservoir geologies with high heterogeneities, the optimization problem requires algorithms able to cope with the non-regularity of the objective function. The goal of this thesis was to develop an efficient methodology for determining optimal well locations and trajectories, that offers the maximum asset value using a technically feasible number of reservoir simulations.
In this thesis, we show a successful application of the Covariance Matrix Adaptation - Evolution Strategy (CMA-ES) which is recognized as one of the most powerful derivative-free optimizers for continuous optimization. Furthermore, in order to reduce the number of reservoir simulations (objective function evaluations), we design two new algorithms. First, we propose a new variant of CMA-ES with meta-models, called the new-local-meta-model CMA-ES (nlmm-CMA), improving over the already existing variant of the local-meta-model CMA-ES (lmm-CMA) on most benchmark functions, in particular for population sizes larger than the default one. Then, we propose to exploit the partial separability of the objective function in the optimization process to define a new algorithm called the partially separable local-meta-model CMA-ES (p-sep lmm-CMA), leading to an important speedup compared to the standard CMA-ES.
In this thesis, we apply also the developed algorithms (nlmm-CMA and p-sep lmm-CMA) on the well placement problem to show, through several examples, a significant reduction of the number of reservoir simulations needed to find optimal well configurations. The proposed approaches are shown to be promising when considering a restricted budget of reservoir simulations, which is the imposed context in practice.
Finally, we propose a new approach to handle geological uncertainty for the well placement optimization problem. The proposed approach uses only one realization together with the neighborhood of each well configuration in order to estimate its objective function instead of using multiple realizations. The approach is illustrated on a synthetic benchmark reservoir case, and is shown to be able to capture the geological uncertainty using a reduced number of reservoir simulations.
Introduction of Statistics in Optimization Fabien Teytaud Dec. 2011
[+]- Defended on Dec. 8. 2011 at LRI (Univ. Paris-Sud)
- Advisors: Marc Schoenauer and Olivier Teytaud
- Dissertation in PDF
- Abstract: In this thesis we study two optimization fields. In a first part, we study the use of evolutionary algorithms for solving derivative-free optimization problems in continuous space. In a second part we are interested in multistage optimization. In that case, we have to make decisions in a discrete environment with finite horizon and a large number of states. In this part we use in particular Monte-Carlo Tree Search algorithms.
In the first part, we work on evolutionary algorithms in a parallel context, when a large number of processors are available. We start by presenting some state of the art evolutionary algorithms, and then, show that these algorithms are not well designed for parallel optimization. Because these algorithms are population based, they should be we well suitable for parallelization, but the experiments show that the results are far from the theoretical bounds. In order to solve this discrepancy, we propose some rules (such as a new selection ratio or a faster decrease of the step-size) to improve the evolutionary algorithms. Experiments are done on some evolutionary algorithms and show that these algorithms reach the theoretical speedup with the help of these new rules.
Concerning the work on multistage optimization, we start by presenting some of the state of the art algorithms (Min-Max, Alpha-Beta, Monte-Carlo Tree Search, Nested Monte-Carlo). After that, we show the generality of the Monte-Carlo Tree Search algorithm by successfully applying it to the game of Havannah. The application has been a real success, because today, every Havannah program uses Monte-Carlo Tree Search algorithms instead of the classical Alpha-Beta. Next, we study more precisely the Monte-Carlo part of the Monte-Carlo Tree Search algorithm. 3 generic rules are proposed in order to improve this Monte-Carlo policy. Experiments are done in order to show the efficiency of these rules.
Learning During Search Alejandro Arbelaez May 2011
[+]- Defended on May 22. 2011 at LRI (Univ. Paris-Sud)
- Advisors: Youssef Hamadi and Michèle Sebag
- Abstract:
Adaptive Operator Selection for Optimization Alvaro Fialho Dec. 2010
[+]- Defended on Dec. 22. 2010 at LRI (Univ. Paris-Sud)
- Advisors: Marc Schoenauer and Michèle Sebag
- Dissertation in PDF
- Abstract: Evolutionary Algorithms (EAs) are stochastic optimization algorithms which have already shown their efficiency on many different application domains. This flexibility is achieved mainly due to the many parameters that can be defined by the user according to the problem at hand. However, EAs are very sensitive to the definition of these parameters, and there are no general guidelines for an efficient setting; as a consequence, EAs are rarely used by researchers from other domains. The methods proposed in this thesis contribute into alleviating the user from the need of defining two very sensitive and problem-dependent choices: which variation operators should be used for the generation of new solutions, and at which rate each operator should be applied. The paradigm, referred to as Adaptive Operator Selection (AOS), provides the on-line autonomous control of the operator that should be applied at each instant of the search, i.e., while solving the problem. In order to do so, one needs to define a Credit Assignment scheme, which rewards the operators based on the impact of their recent applications on the current search process, and an Operator Selection mechanism, that decides which should be the next operator to be applied, based on the empirical quality estimates built by the rewards received. In this work, the Operator Selection problem has been tackled as yet another instance of the Exploration versus Exploitation dilemma: the best operator needs to be exploited as much as possible, while the others should also be minimally explored from time to time, as one of them might become the best in a further moment of the search; different Operator Selection techniques based have been proposed to extend the Multi-Armed Bandit paradigm to the very dynamic context of AOS. On the Credit Assignment side, rewarding schemes based on extreme values and on ranks have been proposed, in order to provide more robust operator assessments, while promoting the use of outlier operators.
The different AOS methods formed by the combinations of the proposed Operator Selection and Credit Assignment mechanisms have been validated on a very diverse set of benchmark problems. Based on empirical evidences gathered from this empirical analysis, the final recommended method, which uses the Rank-based Multi-Armed Bandit Operator Selection and the Area-Under-Curve Credit Assignment schemes, has been shown to achieve state-of-the-art performance while also being very robust with respect to different problems.
Éléments pour l'apprentissage et l'optimisation de fonctions chères Philippe Rolet Dec. 2010
[+]- Defended on Dec. 22. 2010 at LRI (Univ. Paris-Sud)
- Advisors: Michèle Sebag and Olivier Teytaud
- Dissertation in PDF
- Abstract: Ces travaux de doctorat sont centrés sur l’apprentissage artificiel et l’optimisation, c’est à dire la construction de programmes apprenant à identifier un concept, à approximer une fonction ou à trouver un optimum à partir d’exemples de ce concept (ou de points de la fonction).
Mes efforts de recherche ont d’abord porté sur la conception et le développement d’une nouvelle approche de l’apprentissage Actif, fondée sur l’apprentissage par renforcement. Les fondements théoriques de l’approche ont été établis. Parallèlement, l’implémentation d’un logiciel fondé sur cette approche, BAAL, a permis une validation expérimentale (publications: CAP’09, ECML’09). Une extension de cette approche a été réalisée pour l’optimisation de fonction chères (publication: GECCO 2009).
La deuxième partie de mon doctorat s’intéresse aux potentiels et aux limites de l’apprentissage actif et de l’optimisation chère d’un point de vue théorique. Une étude des bornes de complexités de l’apprentissage actif par ”paquets” a été réalisée (publication: ECML 2010). Dans le domaine de l’optimisation bruitée, des résultats sur le nombre minimal d’exemples nécessaires pour trouver un optimum ont été obtenus (publications: LION 2010, EvoSTAR 2010).
Paramètres d'ordre et sélection de modèles en apprentissage : caractérisation des modèles et sélection d'attributs Romaric Gaudel Dec. 2010
[+]- Defended on Dec. 14. 2010 at LRI (Univ. Paris-Sud)
- Advisors: Michèle Sebag and Antoine Cornuéjols
- Dissertation under final revision (in french)
- Abstract: This thesis focuses on model selection in Machine Learning from two points of view.
The first part of the thesis focuses on relational kernel methods. Kernel methods hope to overcome the instances propositionalization, and to bridge the gap between relational and propositional problems. This thesis examines this objective in a particular case: the multiple instance problem, which is considered to be intermediate between relational and propositional problems. Concretely, we determine under which conditions the averaging kernel used for multiple instance problems, allows to reconstruct the target concept. This study follows the standard sketch of phase transition studies and relies on a new criterion to test the efficiency of of the propositionalization induced by the averaging kernel.
The second part of the thesis focuses on feature selection. A solution to solve multiple instance problems, as presented in the first part, is to construct a propositionalization where each instance of the problem leads to a feature. This propositionalization constructs a huge number of features, which implies the need to look for a subset of features with only relevant features. Thus, the second part of the thesis presents a new framework for feature selection.
Feature Selection is formalized as a Reinforcement Learning problem, leading to a provably optimal though intractable selection policy. This optimal policy is approximated, based on a one-player game approach and relying on the Monte-Carlo tree search UCT (Upper Confidence bound applied to Trees) proposed by Kocsis and Szepesvári (2006). The Feature Uct SElection (FUSE) algorithm extends UCT to deal with i) a finite unknown horizon (the target number of relevant features); ii) the huge branching factor of the search tree, reflecting the size of the feature set. Finally, a frugal reward function is proposed as a rough but unbiased estimate of the relevance of a feature subset. A proof of concept of FUSE is shown on benchmark data sets.
Segmentation et évolution pour la planification : le système Divide-And-Evolve Jacques Bibai Oct. 2010
[+]- Defended on Oct. 8. 2010 at LRI (Univ. Paris-Sud)
- Advisors: Marc Schoenauer and Pierre Savéant (Thalès TRT)
- Fetch dissertation in PDF (and in French)
- Abstract: DAEX is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DAEX is based on a state decomposition strategy, driven by an evolutionary algorithm, which benefits from the use of a classical planning heuristic to maintain an ordering of atoms within the individuals. The proof of concept is achieved by embedding the domain-independent satisficing YAHSP planner and using the critical path h1 heuristic. Experiments with the resulting algorithm are performed on a selection of IPC benchmarks from classical, cost-based and temporal domains. Under the experimental conditions of the IPC, and in particular with a universal parameter setting common to all domains, DAEYAHSP is compared to the best planner for each type of domain. Results show that DAEYAHSP performs very well both on coverage and quality metrics. It is particularly noticeable that DAEX improves a lot on plan quality when compared to YAHSP, which is known to provide largely suboptimal solutions, making it competitive with state-of-the-art planners. This article gives a full account of the algorithm, reports on the experiments and provides some insights on the algorithm behavior.
Apprentissage artificiel pour l'ordonnancement des tâches dans les grilles de calcul Julien Perez Sept. 2010
[+]- Defended on Sept. 8. 2010 at LRI (Univ. Paris-Sud)
- Advisors: Cécile Germain-Renaud
- Dissertation in PDF (and in French)
- Abstract: DAEX is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DAEX is based on a state decomposition strategy, driven by an evolutionary algorithm, which benefits from the use of a classical planning heuristic to maintain an ordering of atoms within the individuals. The proof of concept is achieved by embedding the domain-independent satisficing YAHSP planner and using the critical path h1 heuristic. Experiments with the resulting algorithm are performed on a selection of IPC benchmarks from classical, cost-based and temporal domains. Under the experimental conditions of the IPC, and in particular with a universal parameter setting common to all domains, DAEYAHSP is compared to the best planner for each type of domain. Results show that DAEYAHSP performs very well both on coverage and quality metrics. It is particularly noticeable that DAEX improves a lot on plan quality when compared to YAHSP, which is known to provide largely suboptimal solutions, making it competitive with state-of-the-art planners. This article gives a full account of the algorithm, reports on the experiments and provides some insights on the algorithm behavior.
Contributions to Large Scale Data Clustering and Streaming with Affinity Propagation. Application to Autonomic Grids. Xiangliang Zhang Jul. 2010
[+]- Defended on Jul. 28. 2010 at LRI (Univ. Paris-Sud)
- Advisors: Michèle Sebag and Cécile Germain-Renaud
- Dissertation (in English)
- Abstract: In this dissertation, we present our study of the clustering issues on large-scale data and streaming data, with the applicative purpose of building autonomic grid computing system.
Motivated by the application requirements, we employ a new clustering method called Affinity Propagation (AP) for modeling the grid jobs, the first step towards the long-term goal: Autonomic Grid Computing System. AP fits our clustering requirements by i) guaranteeing better clustering performance; ii) providing representative exemplars as actual data items (especially suitable for non-numerical data space). However, AP suffers from the quadratic computational cost caused by the clustering process. This problem severely hinders its usage on large scale datasets.
We firstly proposed the weighted AP(WAP) method. WAP integrates the neighboring points together and keeps spatial structure between them and other points. It makes sure that the clustering results of WAP on integrated points are equal to that of AP on non-integrated points. The merit of WAP is the lower computational complexity.
Hierarchical AP (Hi-AP) is the algorithm we proposed to solve the large-scale clustering problem. It uses AP and our extension of weighted AP (WAP) in the Divide-and-Conquer schema. In detail, it partitions the dataset, runs AP on each subset, and applies WAP to the collection of exemplars constructed from each subset. Through theoretical proof and experimental validation, Hi-AP was shown to significantly decrease the computational cost (from quadratic to quasi-linear), with negligible increasing of distortion.
Streaming AP (StrAP) is our proposed understandable, stable and computationally efficient data stream clustering method. The online updating clustering model is maintained by StrAP through i) when a data item arrives, checking its fitness against the model; ii) if fitting, simply updating the corresponding cluster in the model, otherwise putting it into the reservoir. Restart criteria are used to monitor the changes of stream distribution. If changes are detected, the stream model is rebuild by applying WAP on the current model and the data in the reservoir. StrAP was validated on the Intrusion Detection benchmark data and was shown to outperform the reference method DenStream in terms of clustering quality.
Based on Hi-AP and StrAP, we proposed a multi-scale online grid monitoring system called G-StrAP. This monitoring system provides an understandable description of the job flow running on the grid and enables the system administrator to spot online some sources of failures. It has the online level to provide the EGEE administrator with a real-time dashboard of the job data flow and enable the discovery of anomalies. It has also offline level to inspect the global temporal patterns of the data flow, and help to detect the long-run trends in the EGEE traffic. Applying G-StrAP on 5-million job trace from EGEE grid, through the monitoring outputs, it was shown that GStrAP discovers device problems (e.g., clogging of LogMonitor) with good clustering quality (clustering accuracy > 85% and purity > 90%).
Optimisation Continue Boîte Noire : Comparaison et Conception d'Algorithmes Raymond Ros Dec. 2009
[+]- Defended on Dec. 21. 2009 at LRI (Univ. Paris-Sud)
- Advisors: Michèle Sebag and Nikolaus Hansen
- Dissertation (in English)
- Abstract: In continuous optimisation a given problem can be stated as follows: given the objective function f from R^n to R with n the dimension of the problem, find a suitable vector that minimises f up to an arbitrary numerical precision. In this context, the black-box scenario assumes that no information but the evaluation of f is available to guide its optimisation.
In the first part, we study the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) which is a well-established stochastic approach for solving Black-Box Optimisation (BBO) problems. We show its time and space complexity limits when addressing high-dimensional BBO problems. To overcome such limits, we provide variants of the CMA-ES that update only block-diagonal elements of the covariance matrix, and exploit the separability of the problem. We show that on non-separable functions these variants can outperform the standard CMA-ES, given that the dimension of the problem is large enough.
In the second part, we define and exploit an experimental framework BBO Benchmarking (BBOB) in which practitioners of BBO can test and compare algorithms on function testbeds. Results show dependencies on the budget (number of function evaluations) assigned to the optimisation of the objective function. Some methods such as NEWUOA or BFGS are more appropriate for small budgets. The CMA-ES approach using restarts and a population size management policy performs well for larger budgets.
The COmparing Continuous Optimisers (COCO) software, used for the BBOB, is described technically in the third part. COCO implements our experimental framework as well as outputs the results that we have been exploiting.
Optimisation de la Topologie de Grands Réseaux de Neurones Fei Jiang Dec. 2009
[+]- Defended on Dec. 16. 2009 at LRI (Univ. Paris-Sud)
- Advisors: Hugues Berry et Marc Schoenauer
- Dissertation in PDF (in English)
- Abstract: In this dissertation, we present our study regarding the influence of the topology on the learning performances of neural networks with complex topologies. Three different neural networks have been investigated: the classical Self-Organizing Maps (SOM) with complex graph topology, the Echo State Network (ESN) and the Standard Model Features(SMF). In each case, we begin by comparing the performances of different topologies for the same task. We then try to optimize the topology of some neural network in order to improve such performance.
The first part deals with Self-Organizing Maps, and the task is the standard handwritten digits recognition of the MNIST database. We show that topology has a small impact on performance and robustness to neuron failures, at least at long learning times. Performance may however be increased by almost $10\%$ by artificial evolution of the network topology. In our experimental conditions, the evolved networks are more random than their parents, but display a more broad degree distribution.
In the second part, we proposes to apply CMA-ES, the state-of-the-art method in evolutionary continuous parameter optimization, to the evolutionary learning of the parameters of an Echo State Network (the Readout weights, of course, but also, Spectral Radius, Slopes of the neurons active function). First, a standard supervised learning problem is used to validate the approach and compare it to the original one. But the flexibility of evolutionary optimization allows us to optimize not only the outgoing weights but also, or alternatively, other ESN parameters, sometimes leading to improved results. The classical double pole balancing control problem is used to demonstrate the feasibility of evolutionary reinforcement learning of ESN. We show that the evolutionary ESN obtain results that are comparable with those of the best topology-learning neuro-evolution methods.
Finally, the last part presents our initial research of the SMF - a visual object recognition model which is inspired by the visual cortex. Two version based on SMF are applied to the PASCAL Visual multi-Object recognition Challenge (VOC2008). The long term goal is to find the optimal topology of the SMF model, but the computation cost is however too expensive to optimize the complete topology directly. So as a first step, we apply an Evolutionary Algorithm to auto-select the features used by the systems. We show that, for the VOC2008 challenge, with only 20\% selected feature, the system can perform as well as with all 1000 randomly selected feature.
Improvements and Evaluation of the Monte Carlo Tree Search Algorithm Arpad Rimmel Dec. 2009
[+]- Defended on Dec. 15. 2009 at LRI (Univ. Paris-Sud)
- Advisors: Antoine Cornuéjols and Olivier Teytaud
- Dissertation in PDF (in English)
- Abstract: My thesis deals with planification in a discrete environment with finite horizon and with a number of tates too large to be explored entirely. The goal is to maximize a reward function that associates a value to final states. This thesis focuses on particular on improving and evaluating a new algorithm: bandit-based Monte Carlo tree search. After resenting the state of the art (Minimax and Alphabeta for the two-players case; nested Monte Carlo and Dynamic Programing for the one-player case), I describe the principle of the algorithm. Then, I propose an efficient parallelization method for the case of separated memories. This method can be combined with classical parallelization methods for shared memories. I propose also a way of constructing an opening book and show its efficiency in the concrete case of the game of Go. I introduce also several ways of using expert knowledge, in the part concerning bandits as well as in the Monte Carlo part. Finally, I show that this algorithm that gives very good results in the context of two-players applications is also efficient in a one-player context. I propose an adaptation of the algorithm in order to handle graphs and use a different bandit formula in order to solve the problem of the automatic generation of linear transforms libraries. I obtain results much better than by using a classical dynamic programming algorithm.
Robust Robotic behavior Optimization Cédric Hartland Nov. 2009
[+]- Defended on Nov. 16. 2009 at LRI (Univ. Paris-Sud)
- Advisors: Nicolas Bredèche and Michèle Sebag
- Dissertation in PDF (in English)
- Abstract:
Building processes optimization: Toward an arti?cial ontogeny based approach Alexandre Devert, May 2009
[+]- Defended on May 5. 2009 at LRI (Univ. Paris-Sud)
- Advisors: Nicolas Bredèche et Marc Schoenauer
- Dissertation (in English)
- Abstract:
Optimisation par Stratégies d'Evolution : Convergence et vitesses de convergence pour des fonctions bruitées - Résolution d'un problème d'identification Mohamed Jebalia, Dec. 2008
[+]- Defended on December.19.2008 at LRI (at Univ. Paris Sud)
- Advisors: Anne Auger, Marc Schoenauer and Taïeb Hadhri
- Manuscript (in English)
- Abstract: Le cadre général de cette thèse est la résolution du problème d'optimisation non linéaire continu suivant : Etant donnée une fonction objectif f non-linéaire définie sur un ouvert de R^d, le but est de chercher le vecteur (donc d paramètres) qui minimise (ou maximise) la fonction f.
Dans cette thèse, on s'intéresse plus particulièrement à la résolution de ce problème par les Stratégies d'Evolution (SE). Les SE, algorithmes évolutionnaires opérant sur des espaces d'états continus, ont montré leur efficacité pratique pour la résolution de problèmes d'optimisation réels. Cependant les SE, comme l'ensemble des algorithmes évolutionnaires, ne sont pas basés sur une approche théorique, mais adaptés d'une imitation des principes de l'évolution naturelle, la survie des plus adaptés.
Dans une première partie de cette thèse, on étudie théoriquement et numériquement la convergence des SE. On étudie en particulier l'optimisation des fonctions objectifs bruitées. On montre en particulier que des niveaux assez élevés du bruit peuvent engendrer la non convergence de l'algorithme. Les expressions des vitesses de convergence sont établies théoriquement. Les cas de convergence et divergence sont distingués théoriquement et numériquement.
La seconde partie traite une application à un problème réel en génie chimique, l'identification de paramètres pour le système de la chromatographie analytique. L'approche évolutionnaire est comparée à une méthode déterministe basée sur le calcul du gradient numérique. L'approche évolutionnaire est plus robuste sur ce spécifique cas d'étude.
Evaluation d'algorithmes pour et par l'apprentissage Nicolas Baskiotis, Sept. 2008
[+]- Defended on June 22. Sept. 2008 at LRI (Univ. Paris-Sud)
- Advisor: Michèle sebag
- Dissertation in PDF
- Abstract: One of the main concerns involving machine learning applications is the a priori choice of an algorithm likely to yield the best classification performances. Our work is inspired by research in combinatorial optimisation on the phase transition problem. We suggest a dual approach to the standard view on this problem through metaleraning. Our goal is to build a competence map according to descriptors on the problem space which enables to identify the regimes where the system's performance are steady. We assess this approach on C4.5.
The second part of our work deals with machine learning problems in software testing. More precisely, we study a statistical structural method of software testing that uses the sampling of the so-called feasible paths in the control graph of the problems that is to be tested. In certain cases, the portion of feasible paths is very low, which hinders this method. Our goal is to design a learning and optimisation system that yields a random generator biaised towards the feasible paths and that warrantees a suitable sampling of the target concept. We designed the MLST system that implements active learning in a graph. We tested our work on both real and artificial problems and showed that our system achieves significantly improvement regarding the coverage of target concepts with respect to the initial data.
Une contribution à l'apprendissage par renforcement ; application au Computer GO Sylvain Gelly, Sept. 2007
[+]- 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.
Evolutionary Algorithms for velocity model identification from seismic data Vijay Pratap Singh, Dec. 2006
[+]- Defended on Dec. 18. 2006 at École des Mines de Paris (GéoSciences)
- Advisor : Marc Schoenauer
- Manuscript
- Abstract :
Evolutionary Design of Geometric-based Fuzzy Systems Carlos Kavka, July 2006
[+]- 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.
Étude de l'apprentissage actif. Application à la conduite d'expériences Jérémie Mary, Dec. 2005
[+]- Defended on December 12. 2005 at Université Paris-Sud (Computer Science)
- Advisor : Antoine Cornuéjols and Michèle Sebag
- Manuscript(in French)
- Abstract :
Approches évolutionnaires pour la robotique modulaire et anticipatoire Nicolas Godzik, Sep. 2005
[+]- Defended on September 29. 2005 at Université Paris-Sud (Computer Science)
- Advisor : Marc Schoenauer and Michèle Sebag
- 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.
Contributions théoriques et numériques à l'optimisation continue par Algorithmes Evolutionnaires Anne Auger, Dec. 2004
[+]- 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.
Intégration de la construction de la terminologie de domaines spécialisés dans un processus global de fouille de textes Mathieu Roche, Dec. 2004
[+]- 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".
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.
Algorithmes évolutionnaires assistés par des méthodes d'apprentissage en grandes dimensions Kamal Abboud, Oct. 2004
[+]- 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.
Application des Algorithmes Evolutionnaires aux problèmes d'optimisation multi-critère avec contraintes Olga Roudenko, March 2004
[+]- Defended on March 5. 2004 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- PDF file or gzipped Postscript (in French)
- Abstract :
Extraction de connaissances à partir de données textuelles et numériques Jérôme Azé, Dec. 2003
[+]- 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 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.
Old PhD Theses (prepared at CMAP - Ecole Polytechnique)
Optimisation de Formes multi-critères par algorithmes évolutionnaires H. Hamda, May 2003
[+]- 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 :
Algorithmes Evolutionnaires: Prise en Compte des Contraintes et Application Réelle Sana Ben Hamida, Mar. 2001
[+]- Defended on March 27. 2001 at Université Paris Sud (Computer Science)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.
Application de l'évolution artificielle à la décongestion du trafic aérien Sofiane Oussedik, Dec. 2000
[+]- Defended on december 14. 2000 at Université Paris-Sud (Computer Science)
- Advisor: Marc Schoenauer and Daniel Delahaye
- gzipped Postscript in French.
Analyse d'Algorithmes d'Évolution Artificielle appliqués au domaine pétrolier : Inversion sismique et approximation de fonctions Frédéric Mansanné, Dec. 2000
[+]- Defended on December 13. 2000 at Université de Pau (Applied Maths)
- Advisors: Mohamed Amara and Marc Schoenauer
- gzipped Postscript in French.
Algorithmes d'évolution stochastique : du cadre binaire aux représentations de longueur variable. - Etudes théoriques et heuristiques de la convergence, aspects spatiaux et temporels Leila Kallel, Feb. 1999
[+]- Defended on February 5. 1999 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- gzipped Postscript in English, except the firts introductory 40 pages.
Méthodes d'optimisation pour l'évitement aérien : systèmes centralisés, systèmes embarqués Frédéric Medioni, Dec. 1998
[+]- Defended in December 1998 at Ecole Polytechnique (Computer Sciences)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.
Etude de problèmes inverses par algorithmes d'évolution et réseaux de neurones Alessandro Fadda, June 1998
[+]- Defended in June 1998 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer -
- gzipped Postscript in French.
Optimisation d'interféromètres par algorithmes génétiques Lionel Taieb, May 1997
[+]- Defended in May 1997 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.
Optimum Design et Algorithmes Génétiques Couro Kane, July 1996
[+]- Defended in July 1996 at Université Paris 6 (Applied Maths)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.