Les problèmes d’investissements d’énergie sont difficiles à cause des incertitudes. Certaines incertitudes peuvent être modélisées par les probabilités. Mais il y a des problèmes difficiles tels que l'évolution de technologie et la pénalisation de CO2, délicats à modéliser par des probabilités. Aussi, les travaux sur l’optimisation des systèmes d’énergie est souvent déterministe. Cette thèse s’intéresse à appliquer l’optimisation bruitée aux systèmes d’énergie. Cette thèse se concentre sur trois parties principales: les études des méthodes pour gérer le bruit, y compris utiliser des méthodes de ré-échantillonnage pour améliorer la vitesse de convergence; les applications des méthodes de portefeuilles à l’optimisation bruitée dans le continu; les applications des méthodes de portefeuilles aux cas avec incertitudes pour la planification des investissements d’énergie et aux jeux, y compris l’utilisation de l’algorithme de bandit adversarial pour calculer l’équilibre de Nash d'un jeu matriciel à somme nulle et l’utilisation de “sparsity” pour accélérer le calcul de l’équilibre de Nash. / This manuscript concentrates in studying methods to handle the noise, including using resampling methods to improve the convergence rates and applying portfolio methods to cases with uncertainties (games, and noisy optimization in continuous domains).Part I will introduce the manuscript, then review the state of the art in noisy optimization, portfolio algorithm, multi-armed bandit algorithms and games.Part II concentrates on the work on noisy optimization:∙ Chapter 4 provides a generic algorithm for noisy optimization recovering most of the existing bounds in one single noisy optimization algorithm.∙ Chapter5 applies different resampling rules in evolution strategies for noisy optimization, without the assumption of variance vanishing in the neighborhood of the optimum, and shows mathematically log-log convergence results and studies experimentally the slope of this convergence.∙ Chapter 6 compares resampling rules used in the differential evolution algorithm for strongly noisy optimization. By mathematical analysis, a new rule is designed for choosing the number of resamplings, as a function of the dimension, and validate its efficiency compared to existing heuristics - though there is no clear improvement over other empirically derived rules.∙ Chapter 7 applies “common random numbers”, also known as pairing, to an intermediate case between black-box and white-box cases for improving the convergence.Part III is devoted to portfolio in adversarial problems:∙ Nash equilibria are cases in which combining pure strategies is necessary for designing optimal strategies. Two chapters are dedicated to the computation of Nash equilibria:– Chapter 9 investigates combinations of pure strategies, when a small set of pure strategies is concerned; basically, we get improved rates when the support of the Nash equilibrium is small.– Chapter 10 applies these results to a power system problem. This compares several bandit algorithms for Nash equilibria, defines parameter-free bandit algorithms, and shows the relevance of the sparsity approach dis- cussed in Chapter 9.∙ Then, two chapters are dedicated to portfolios of game methods:– Chapter 11 shows how to generate multiple policies, from a single one, when only one such policy is available. This kind of bootstrap (based on random seeds) generates many deterministic policies, and then combines them into one better policy. This has been tested on several games.– Chapter 12 extends chapter 11 by combining policies in a position-specific manner. In particular, we get a better asymptotic behavior than MCTS.Part IV is devoted to portfolios in noisy optimization:∙ Chapter 14 is devoted to portfolio of noisy optimization methods in continuous domains;∙ Chapter 15 proposed differential evolution as a tool for non- stationary bandit problems.

L'inférence grammaticale s'intéresse à l'apprentissage automatique de langages formels. Ces derniers sont organisés en plusieurs classes formant la hiérarchie de Chomsky. Parmi elles, les langages réguliers, reconnus par des automates finis déterministes, forment la classe la plus « simple » à apprendre : l'apprentissage des automates a largement été étudié et a donné naissance à plusieurs algorithmes d'inférence grammaticale.<br /><br />Toutefois, un problème concernant les données est devenu crucial : celui du bruit. Des propositions d'algorithmes ont vu le jour pour essayer de résoudre ce problème, mais nous montrons que les résultats ne sont toujours pas satisfaisants, y compris pour les langages réguliers. Or, puisqu'ils forment la base de la hiérarchie de Chomsky, ce sont toutes les classes de la hiérarchie qui ne peuvent être apprises en situations bruitées.<br /><br />Aussi, nous proposons une nouvelle classe de langages qui semble ne pas souffrir de ce handicap : celle des boules de mots. Nous démontrons que cette classe, de prime abord peu orthodoxe mais utilisée dans de nombreuses applications comme la correction orthographique ou la recherche de plus proches voisins, reste identifiable à la limite même lorsque les données d'apprentissage subissent l'influence d'un bruit non statistique.<br /><br />De plus, nous introduisons les requêtes de correction basées sur la distance d'édition et nous présentons un algorithme d'apprentissage des boules de mots à partir de telles requêtes. Nous montrons expérimentalement que de simples heuristiques a posteriori suffisent à le rendre résistant lorsque l'oracle répond approximativement à de telles requêtes. Ceci justifie encore une<br />fois la robustesse des boules de mots au bruit.<br /><br />Contrairement aux idées reçues, le bruit n'est donc pas une malédiction en inférence grammaticale : les langages à base de distance offrent de nouvelles perspectives.

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). Le contexte applicatif est l'apprentissage et l'optimisation de modèles simplifiés en ingénierie numérique, pour des problèmes industriels pour lesquels les exemples sont coûteux à obtenir. Il est nécessaire d'en utiliser le moins possible pour l'apprentissage; c'est le principe de l'apprentissage actif et de l'optimisation de fonction chères. 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).

Ces recherches sont motivées par la nécessité de développer de nouvelles méthodes d'optimisation des systèmes électriques. Dans ce domaine, les méthodes usuelles de contrôle et d'investissement sont à présent limitées de par les problèmes comportant une grande part d'aléa, qui interviennent lors de l'introduction massive d'énergies renouvelables. Après la présentation des différentes facettes de l'optimisation d'un système électrique, nous discuterons le problème d'optimisation continue bruitée de type boîte noire puis des cas bruités comprenant des caractéristiques supplémentaires.Concernant la contribution à l'optimisation continue bruitée de type boîte noire, nous nous intéresserons aux bornes inférieures et supérieures du taux de convergence de différentes familles d'algorithmes. Nous étudierons la convergence d'algorithmes basés sur les comparaisons, en particuliers les Stratégies d'Evolution, face à différents niveaux de bruit (faible, modéré et fort). Nous étendrons également les résultats de convergence des algorithmes basés sur les évaluations lors d'un bruit faible. Finalement, nous proposerons une méthode de sélection pour choisir le meilleur algorithme, parmi un éventail d'algorithme d'optimisation bruitée, sur un problème donné.Pour ce qui est de la contribution aux cas bruités avec des contraintes supplémentaires, les cas délicats, nous introduirons des concepts issus de l'apprentissage par renforcement, de la théorie de la décision et des statistiques. L'objectif est de proposer des méthodes d'optimisation plus proches de la réalité (en termes de modélisation) et plus robuste. Nous rechercherons également des critères de fiabilité des systèmes électriques moins conservatifs. / This research is motivated by the need to find out new methods to optimize a power system. In this field, traditional management and investment methods are limited in front of highly stochastic problems which occur when introducing renewable energies at a large scale. After introducing the various facets of power system optimization, we discuss the continuous black-box noisy optimization problem and then some noisy cases with extra features.Regarding the contribution to continuous black-box noisy optimization, we are interested into finding lower and upper bounds on the rate of convergence of various families of algorithms. We study the convergence of comparison-based algorithms, including Evolution Strategies, in front of different strength of noise (small, moderate and big). We also extend the convergence results in the case of value-based algorithms when dealing with small noise. Last, we propose a selection tool to choose, between several noisy optimization algorithms, the best one on a given problem.For the contribution to noisy cases with additional constraints, the delicate cases, we introduce concepts from reinforcement learning, decision theory and statistic fields. We aim to propose optimization methods closer from the reality (in terms of modelling) and more robust. We also look for less conservative power system reliability criteria.

Cette thèse montre des contributions à l'analyse d'algorithmes pour l'optimisation de fonctions bruitées. Les taux de convergences (regret simple et regret cumulatif) sont analysés pour les algorithmes de recherche linéaire ainsi que pour les algorithmes de recherche aléatoires. Nous prouvons que les algorithmes basé sur la matrice hessienne peuvent atteindre le même résultat que certaines algorithmes optimaux, lorsque les paramètres sont bien choisis. De plus, nous analysons l'ordre de convergence des stratégies évolutionnistes pour des fonctions bruitées. Nous déduisons une convergence log-log. Nous prouvons aussi une borne basse pour le taux de convergence de stratégies évolutionnistes. Nous étendons le travail effectué sur les mécanismes de réévaluations en les appliquant au cas discret. Finalement, nous analysons la mesure de performance en elle-même et prouvons que l'utilisation d'une mauvaise mesure de performance peut mener à des résultats trompeurs lorsque différentes méthodes d'optimisation sont évaluées. / This thesis exposes contributions to the analysis of algorithms for noisy functions. It exposes convergence rates for linesearch algorithms as well as for random search algorithms. We prove in terms of Simple Regret and Cumulative Regret that a Hessian based algorithm can reach the same results as some optimal algorithms in the literature, when parameters are tuned correctly. On the other hand we analyse the convergence order of Evolution Strategies when solving noisy functions. We deduce log-log convergence. We also give a lower bound for the convergence rate of the Evolution Strategies. We extend the work on revaluation by applying it to a discrete settings. Finally we analyse the performance measure itself and prove that the use of an erroneus performance measure can lead to misleading results on the evaluation of different methods.

Dans cette thèse, le mouvement brownien branchant (MBB) est un système aléatoire de particules, où celles-ci diffusent sur la droite réelle selon des mouvements browniens et branchent à taux constant en un nombre aléatoire de particules d'espérance supérieure à 1. Nous étudions deux modèles de MBB avec sélection : le MBB avec absorption à une droite espace-temps et le N -MBB, où, dès que le nombre de particules dépasse un nombre donné N , seules les N particules les plus à droite sont gardées tandis que les autres sont enlevées du système. Pour le premier modèle, nous étudions la loi du nombre de particules absorbées dans le cas où le processus s'éteint presque sûrement, en utilisant un lien entre les équations de Fisher-Kolmogorov-Petrovskii-Piskounov (FKPP) et de Briot-Bouquet. Pour le deuxième modèle, dont l'étude représente la plus grande partie de cette thèse, nous donnons des asymptotiques précises sur la position du nuage de particules quand N est grand. Plus précisément, nous montrons qu'elle converge à l'échelle de temps log³ N vers un processus de Lévy plus une dérive linéaire, tous les deux explicites, confirmant des prévisions de Brunet, Derrida, Mueller et Munier. Cette étude contribue à la compréhension de fronts du type FKPP sous l'influence de bruit. Enfin, une troisième partie montre le lien qui existe entre le MBB et des processus ponctuels stables.

L'analyse des données fonctionnelles constitue une branche de la statistique dont le développement s'est fortement intensifié ces dernières années. Dans cette thèse, on s'intéresse à des problèmes de régression fonctionnelle pour lesquels il s'agit d'expliquer les variations d'une variable d'intérêt réelle à partir d'une variable explicative fonctionnelle, c'est-à-dire à valeur dans un espace de dimension éventuellement infinie. On considère plus précisément des modèles de régression linéaire. Deux types d'estimation sont proposés: l'estimation de quantiles conditionnels et l'estimation de la moyenne conditionnelle (cette dernière étant considérée dans le cas où la variable explicative est non bruitée, puis lorsque celle-ci est soumise à des erreurs de mesure). Dans chaque cas, des estimateurs basés sur les fonctions splines sont proposés, solutions de problèmes de minimisation pénalisés, la pénalisation intervenant pour contourner le problème lié au fait que la variable explicative est à valeurs dans un espace de dimension infinie. Finalement, on s'intéresse aux aspects pratique de cette étude, au moyen de simulations, puis sur un jeu de données réelles concernant la prévision de pics de pollution à l'ozone à Toulouse.

Cette thèse s’articule autour de deux séries de travaux motivés par des expériences sur des fourmis. Bien qu’inspirés par labiologie, les modèles que nous développons utilisent une terminologie et une approche typique de l’informatique théorique.Le premier modèle s’inspire du transport collaboratif de nourriture au sein de l’espèce P. Longicornis. Certains aspectsfondamentaux du processus peuvent être décrits par un problème de recherche sur un graphe en présence d’un certain typed’indications bruitées à chaque noeud. Ces indications représentent de courtes traces de phéromones déposées devant l’objettransporté afin de faciliter la navigation. Dans cette thèse, nous donnons une analyse complète du problème lorsque le graphesous-jacent est un arbre, une hypothèse pertinente dans un cadre informatique. En particulier, notre modèle peut être vucomme une généralisation de la recherche binaire aux arbres, en présence de bruit. De manière surprenante, lescomportements des algorithmes optimaux dans ce cadre diffèrent suivant le type de garantie que l’on étudie : convergence enmoyenne ou avec grande probabilité.Le deuxième modèle présenté dans cette thèse a été conçu pour décrire la dissémination d’informations au sein de fourmis dudésert. Dans notre modèle, les échanges ont lieu uniformément au hasard, et sont sujets à du bruit. Nous prouvons une borneinférieure sur le nombre d’interactions requis en fonction de la taille du groupe. La borne, de même que les hypothèses dumodèle, semblent compatible avec les données expérimentales.Une conséquence théorique de ce résultat est une séparation dans ce cadre des variantes PUSH et PULL pour le problème du broadcast avec bruit. Nous étudions aussi une version du problème avec des garanties de convergence plus fortes. Dans cecas, le problème peut-être résolu efficacement, même si les échanges d’information au cours de chaque interaction sont très limités / This thesis is built around two series of works, each motivated by experiments on ants. We derive and analyse new models,that use computer science concepts and methodology, despite their biological roots and motivation.The first model studied in this thesis takes its inspiration in collaborative transport of food in the P. Longicornis species. Wefind that some key aspects of the process are well described by a graph search problem with noisy advice. The advicecorresponds to characteristic short scent marks laid in front of the load in order to facilitate its navigation. In this thesis, weprovide detailed analysis of the model on trees, which are relevant graph structures from a computer science standpoint. Inparticular our model may be viewed as a noisy extension of binary search to trees. Tight results in expectation and highprobability are derived with matching upper and lower bounds. Interestingly, there is a sharp phase transition phenomenon forthe expected runtime, but not when the algorithms are only required to succeed with high probability.The second model we work with was initially designed to capture information broadcast amongst desert ants. The model usesa stochastic meeting pattern and noise in the interactions, in a way that matches experimental data. Within this theoreticalmodel, we present in this document a strong lower bound on the number of interactions required before information can bespread reliably. Experimentally, we see that the time required for the recruitment process of even few ants increases sharplywith the group size, in accordance with our result. A theoretical consequence of the lower bound is a separation between theuniform noisy PUSH and PULL models of interaction. We also study a close variant of broadcast, without noise this time butunder more strict convergence requirements and show that in this case, the problem can be solved efficiently, even with verylimited exchange of information on each interaction.

Durant ces dernières années, les architectures de réseaux de neurones (RN) ont été appliquées avec succès à de nombreuses applications en Traitement Automatique de Langues (TAL), comme par exemple en Reconnaissance Automatique de la Parole (RAP) ainsi qu'en Traduction Automatique (TA).Pour la tâche de modélisation statique de la langue, ces modèles considèrent les unités linguistiques (c'est-à-dire des mots et des segments) à travers leurs projections dans un espace continu (multi-dimensionnel), et la distribution de probabilité à estimer est une fonction de ces projections.Ainsi connus sous le nom de "modèles continus" (MC), la particularité de ces derniers se trouve dans l'exploitation de la représentation continue qui peut être considérée comme une solution au problème de données creuses rencontré lors de l'utilisation des modèles discrets conventionnels.Dans le cadre de la TA, ces techniques ont été appliquées dans les modèles de langue neuronaux (MLN) utilisés dans les systèmes de TA, et dans les modèles continus de traduction (MCT).L'utilisation de ces modèles se sont traduit par d'importantes et significatives améliorations des performances des systèmes de TA. Ils sont néanmoins très coûteux lors des phrases d'apprentissage et d'inférence, notamment pour les systèmes ayant un grand vocabulaire.Afin de surmonter ce problème, l'architecture SOUL (pour "Structured Output Layer" en anglais) et l'algorithme NCE (pour "Noise Contrastive Estimation", ou l'estimation contrastive bruitée) ont été proposés: le premier modifie la structure standard de la couche de sortie, alors que le second cherche à approximer l'estimation du maximum de vraisemblance (MV) par une méthode d’échantillonnage.Toutes ces approches partagent le même critère d'estimation qui est la log-vraisemblance; pourtant son utilisation mène à une incohérence entre la fonction objectif définie pour l'estimation des modèles, et la manière dont ces modèles seront utilisés dans les systèmes de TA.Cette dissertation vise à concevoir de nouvelles procédures d'entraînement des MC, afin de surmonter ces problèmes.Les contributions principales se trouvent dans l'investigation et l'évaluation des méthodes d'entraînement efficaces pour MC qui visent à: (i) réduire le temps total de l'entraînement, et (ii) améliorer l'efficacité de ces modèles lors de leur utilisation dans les systèmes de TA.D'un côté, le coût d'entraînement et d'inférence peut être réduit (en utilisant l'architecture SOUL ou l'algorithme NCE), ou la convergence peut être accélérée.La dissertation présente une analyse empirique de ces approches pour des tâches de traduction automatique à grande échelle.D'un autre côté, nous proposons un cadre d'apprentissage discriminant qui optimise la performance du système entier ayant incorporé un modèle continu.Les résultats expérimentaux montrent que ce cadre d'entraînement est efficace pour l'apprentissage ainsi que pour l'adaptation des MC au sein des systèmes de TA, ce qui ouvre de nouvelles perspectives prometteuses. / Over the past few years, neural network (NN) architectures have been successfully applied to many Natural Language Processing (NLP) applications, such as Automatic Speech Recognition (ASR) and Statistical Machine Translation (SMT).For the language modeling task, these models consider linguistic units (i.e words and phrases) through their projections into a continuous (multi-dimensional) space, and the estimated distribution is a function of these projections. Also qualified continuous-space models (CSMs), their peculiarity hence lies in this exploitation of a continuous representation that can be seen as an attempt to address the sparsity issue of the conventional discrete models. In the context of SMT, these echniques have been applied on neural network-based language models (NNLMs) included in SMT systems, and oncontinuous-space translation models (CSTMs). These models have led to significant and consistent gains in the SMT performance, but are also considered as very expensive in training and inference, especially for systems involving large vocabularies. To overcome this issue, Structured Output Layer (SOUL) and Noise Contrastive Estimation (NCE) have been proposed; the former modifies the standard structure on vocabulary words, while the latter approximates the maximum-likelihood estimation (MLE) by a sampling method. All these approaches share the same estimation criterion which is the MLE ; however using this procedure results in an inconsistency between theobjective function defined for parameter stimation and the way models are used in the SMT application. The work presented in this dissertation aims to design new performance-oriented and global training procedures for CSMs to overcome these issues. The main contributions lie in the investigation and evaluation of efficient training methods for (large-vocabulary) CSMs which aim~:(a) to reduce the total training cost, and (b) to improve the efficiency of these models when used within the SMT application. On the one hand, the training and inference cost can be reduced (using the SOUL structure or the NCE algorithm), or by reducing the number of iterations via a faster convergence. This thesis provides an empirical analysis of these solutions on different large-scale SMT tasks. On the other hand, we propose a discriminative training framework which optimizes the performance of the whole system containing the CSM as a component model. The experimental results show that this framework is efficient to both train and adapt CSM within SMT systems, opening promising research perspectives.

No description available.