Dissertations / Theses on the topic 'Algorithmes d'apprentissage automatique'

Dans un premier temps, ce mémoire présente un théorème PAC-Bayes général, duquel il est possible d'obtenir simplement plusieurs bornes PAC-Bayes connues. Ces bornes permettent de calculer une garantie sur le risque d'un classificateur à partir de ses performances sur l'ensemble de données d'entraînement. Par l'interprétation du comportement de deux bornes PAC-Bayes, nous énonçons les caractéristiques propres aux classificateurs qu'elles favorisent. Enfin, une spécialisation de ces bornes à la famille des classificateurs linéaires est détaillée. Dans un deuxième temps, nous concevons trois nouveaux algorithmes d'apprentissage automatique basés sur la minimisation, par la méthode de descente de gradient conjugué, de l'expression mathématique de diverses formulations des bornes PAC-Bayes. Le dernier algorithme présenté utilise une fraction de l'ensemble d'entraînement pour l'acquisition de connaissances a priori. Ces algorithmes sont aptes à construire des classificateurs exprimés par vote de majorité ainsi que des classificateurs linéaires exprimés implicitement à l'aide de la stratégie du noyau. Finalement, une étude empirique élaborée compare les trois algorithmes entre eux et révèle que certaines versions de ces algorithmes construisent des classificateurs compétitifs avec ceux obtenus par AdaBoost et les SVM.
At first, this master thesis presents a general PAC-Bayes theorem, from which we can easily obtain some well-known PAC-Bayes bounds. Those bounds allow us to compute a guarantee on the risk of a classifier from its achievements on the training set. We analyze the behavior of two PAC-Bayes bounds and we determine peculiar characteristics of classifiers favoured by those bounds. Then, we present a specialization of those bounds to the linear classifiers family. Secondly, we conceive three new machine learning algorithms based on the minimization, by conjugate gradient descent, of various mathematical expressions of the PAC-Bayes bounds. The last algorithm uses a part of the training set to capture a priori knowledges. One can use those algorithms to construct majority vote classifiers as well as linear classifiers implicitly represented by the kernel trick. Finally, an elaborated empirical study compares the three algorithms and shows that some versions of those algorithms are competitive with both AdaBoost and SVM.
Inscrit au Tableau d'honneur de la Faculté des études supérieures

This thesis addresses text-independent speaker verification from a machine learning point of view. We use the machine learning framework to better define the problem and to develop new unbiased performance measures and statistical tests to compare objectively new approaches. We propose a new interpretation of the state-of-the-art Gaussian Mixture Model based system and show that they are discriminant and equivalent to a mixture of linear classifiers. A general framework for score normalization is also given for both probability and non-probability based models. With this new framework we better show the hypotheses made for the well known Z- and T- score normalization techniques. Several uses of discriminant models are then proposed. In particular, we develop a new sequence kernel for Support Vector Machines that generalizes an other sequence kernel found in the literature. If the latter is limited to a polynomial form the former allows the use of infinite space kernels such as Radial Basis Functions. A variant of this kernel that finds the best match for each frame of the sequence to be compared, actually outperforms the state-of-the-art systems. As our new sequence kernel is computationally costly for long sequences, a clustering technique is proposed for reducing the complexity. We also address in this thesis some problems specific to speaker verification such as the fact that the classes are highly unbalanced. And the use of a specific intra- and inter-class distance distribution is proposed by modifying the kernel in order to assume a Gaussian noise distribution over negative examples. Even if this approach misses some theoretical justification, it gives very good empirical results and opens a new research direction
Dans cette thèse le problème de la vérification du locuteur indépendante du texte est abordée du point de vue de l'apprentissage statistique (machine learning). Les théories développées en apprentissage statistique permettent de mieux définir ce problème, de développer de nouvelles mesures de performance non-biaisées et de proposer de nouveaux tests statistiques afin de comparer objectivement les modèles proposés. Une nouvelle interprétation des modèles de l'état de l'art basée sur des mixtures de gaussiennes (GMM) montre que ces modèles sont en fait discriminants et équivalents à une mixture d'experts linéaires. Un cadre théorique général pour la normalisation des scores est aussi proposé pour des modèles probabilistes et non-probabilistes. Grâce à ce nouveau cadre théorique, les hypothèses faites lors de l'utilisation de la normalisation Z et T (T- and Z-norm) sont mises en évidence. Différents modèles discriminants sont proposés. On présente un nouveau noyau utilisé par des machines à vecteurs de support (SVM) qui permet de traîter des séquences. Ce noyau est en fait la généralisation d'un noyau déjà existant qui présente l'inconvénient d'être limité à une forme polynomiale. La nouvelle approche proposée permet la projection des données dans un espace de dimension infinie, comme c'est le cas, par exemple, avec l'utilisation d'un noyau gaussien. Une variante de ce noyau cherchant le meilleur vecteur acoustique (frame) dans la séquence à comparer, améliore les résultats actuellement connus. Comme cette approche est particulièrement coûteuse pour les séquences longues, un algorithme de regroupement (clustering) est utilisé pour en réduire la complexité. Finalement, cette thèse aborde aussi des problèmes spécifiques de la vé-ri-fi-ca-tion du locuteur, comme le fait que les nombres d'exemples positifs et négatifs sont très déséquilibrés et que la distribution des distances intra et inter classes est spécifique de ce type de problème. Ainsi, le noyau est modifié en ajoutant un bruit gaussien sur chaque exemple négatif. Même si cette approche manque de justification théorique pour l'instant, elle produit de très bons résultats empiriques et ouvre des perspectives intéressantes pour de futures recherches

L’objet principale de cette thèse est l’étude théorique et la conception d’algorithmes d’apprentissage concevant des classificateurs par vote de majorité. En particulier, nous présentons un théorème PAC-Bayes s’appliquant pour borner, entre autres, la variance de la perte de Gibbs (en plus de son espérance). Nous déduisons de ce théorème une borne du risque du vote de majorité plus serrée que la fameuse borne basée sur le risque de Gibbs. Nous présentons également un théorème permettant de borner le risque associé à des fonctions de perte générale. À partir de ce théorème, nous concevons des algorithmes d’apprentissage construisant des classificateurs par vote de majorité pondérés par une distribution minimisant une borne sur les risques associés aux fonctions de perte linéaire, quadratique, exponentielle, ainsi qu’à la fonction de perte du classificateur de Gibbs à piges multiples. Certains de ces algorithmes se comparent favorablement avec AdaBoost.
The main purpose of this thesis is the theoretical study and the design of learning algorithms returning majority-vote classifiers. In particular, we present a PAC-Bayes theorem allowing us to bound the variance of the Gibbs’ loss (not only its expectation). We deduce from this theorem a bound on the risk of a majority vote tighter than the famous bound based on the Gibbs’ risk. We also present a theorem that allows to bound the risk associated with general loss functions. From this theorem, we design learning algorithms building weighted majority vote classifiers minimizing a bound on the risk associated with the following loss functions : linear, quadratic and exponential. Also, we present algorithms based on the randomized majority vote. Some of these algorithms compare favorably with AdaBoost.

La découverte de composés pharmaceutiques est actuellement trop longue et trop coûteuse, et le taux d’échec, trop élevé. Les bases de données biochimiques et génomiques ne cessent de grossir et il est maintenant impraticable d’interpréter ces données. Un changement radical est nécessaire ; certaines étapes de ce processus doivent être automatisées. Les peptides jouent un rôle important dans le système immunitaire et dans la signalisation cellulaire. Leurs propriétés favorables en font des candidats de choix pour initier la conception de nouveaux médicaments et assister la production de nouveaux vaccins. De plus, les techniques de synthèse modernes permettent de rapidement synthétiser ces molécules à faible coût. Les algorithmes d’apprentissage statistique sont particulièrement bien adaptés pour apprendre de façon automatisée des modèles, possiblement biochimiques, à partir des données existantes. Ces méthodes et les peptides offrent donc une solution de choix aux défis auxquels fait face la recherche pharmaceutique. Nous proposons un noyau permettant l’apprentissage de modèles statistiques de phénomènes biochimiques impliquant des peptides. Celui-ci permet, entre autres, l’apprentissage d’un modèle universel pouvant raisonnablement quantifier l’énergie de liaison entre toute séquence peptidique et tout site de liaison d’une protéine cristallisée. De plus, il unifie la théorie de plusieurs noyaux existants tout en conservant une faible complexité algorithmique. Ce noyau s’avère particulièrement adapté pour quantifier l’interaction entre les antigènes et les complexes majeurs d’histocompatibilité. Nous proposons un outil pour prédire les peptides qui survivront au processus de présentation antigénique. Cet outil a gagné une compétition internationale et aura plusieurs applications en immunologie, dont la conception de vaccins. Ultimement, un peptide doit maximiser l’interaction avec une protéine cible ou maximiser la bioactivité chez l’hôte. Nous formalisons ce problème comme un problème de prédiction de structures. Puis, nous proposons un algorithme exploitant les plus longs chemins dans un graphe pour déterminer les peptides maximisant la bioactivité prédite par un modèle préalablement appris. Nous validons cette nouvelle approche en laboratoire par la découverte de peptides antimicrobiens. Finalement, nous fournissons des garanties de performance de type PAC-Bayes pour deux algorithmes de prédiction de structure dont un est nouveau.
The discovery of pharmaceutical compounds is currently too time-consuming, too expensive, and the failure rate is too high. Biochemical and genomic databases continue to grow and it is now impracticable to interpret these data. A radical change is needed; some steps in this process must be automated. Peptides are molecules that play an important role in the immune system and in cell signaling. Their favorable properties make them prime candidates for initiating the design of new drugs and assist in the design of vaccines. In addition, modern synthesis techniques can quickly generate these molecules at low cost. Statistical learning algorithms are well suited to manage large amount of data and to learn models in an automated fashion. These methods and peptides thus offer a solution of choice to the challenges facing pharmaceutical research. We propose a kernel for learning statistical models of biochemical phenomena involving peptides. This allows, among other things, to learn a universal model that can reasonably quantify the binding energy between any peptide sequence and any binding site of a protein. In addition, it unifies the theory of many existing string kernels while maintaining a low computational complexity. This kernel is particularly suitable for quantifying the interaction between antigens and proteins of the major histocompatibility complex. We provide a tool to predict peptides that are likely to be processed by the antigen presentation pathway. This tool has won an international competition and has several applications in immunology, including vaccine design. Ultimately, a peptide should maximize the interaction with a target protein or maximize bioactivity in the host. We formalize this problem as a structured prediction problem. Then, we propose an algorithm exploiting the longest paths in a graph to identify peptides maximizing the predicted bioactivity of a previously learned model. We validate this new approach in the laboratory with the discovery of new antimicrobial peptides. Finally, we provide PAC-Bayes bound for two structured prediction algorithms, one of which is new.

Différentes disciplines des sciences humaines telles la philologie ou la paléographie font face à des tâches complexes et fastidieuses pour l'examen des sources de données. La proposition d'approches computationnelles en humanités permet d'adresser les problématiques rencontrées telles que la lecture, l'analyse et l'archivage de façon systématique. Les modèles conceptuels élaborés reposent sur des algorithmes et ces derniers donnent lieu à des implémentations informatiques qui automatisent ces tâches fastidieuses. La première partie de la thèse vise, d'une part, à établir la structuration thématique d'un corpus, en construisant des espaces sémantiques de grande dimension. D'autre part, elle vise au suivi dynamique des thématiques qui constitue un réel défi scientifique, notamment en raison du passage à l'échelle. La seconde partie de la thèse traite de manière holistique la page d'un document numérisé sans aucune intervention préalable. Le but est d'apprendre automatiquement des représentations du trait de l'écriture ou du tracé d'un certain script par rapport au tracé d'un autre script. Il faut dans ce cadre tenir compte de l'environnement où se trouve le tracé : image, artefact, bruits dus à la détérioration de la qualité du papier, etc. Notre approche propose un empilement de réseaux de neurones auto-encodeurs afin de fournir une représentation alternative des données reçues en entrée
Different disciplines in the humanities, such as philology or palaeography, face complex and time-consuming tasks whenever it comes to examining the data sources. The introduction of computational approaches in humanities makes it possible to address issues such as semantic analysis and systematic archiving. The conceptual models developed are based on algorithms that are later hard coded in order to automate these tedious tasks. In the first part of the thesis we propose a novel method to build a semantic space based on topics modeling. In the second part and in order to classify historical documents according to their script. We propose a novel representation learning method based on stacking convolutional auto-encoder. The goal is to automatically learn plot representations of the script or the written language

La problématique de ce travail repose sur la qualité de modélisation de données (appelées observations) faite par des chaines de Markov cachées (CMC). Notre objectif est alors de proposer des algorithmes permettant d'améliorer cette qualité. Le critère retenu pour quantifier la qualité de la modélisation est la probabilité que la CMC génère des observations données. La résolution de ce problème fait appel à des techniques d'hybridation. Les outils employés conjointement aux CMC dans ce travail sont les algorithmes génétiques. Nous les utilisons ici pour répondre à une double attente. Premièrement, ils vont nous permettre d'explorer l'espace de recherche des CMC en évitant les optima locaux. Deuxièmement, l'algorithme génétique gère une caractéristique importante des CMC : leur nombre d'états. Au final, l'algorithme hybride le plus évolué détermine seul la meilleure CMC par rapport à un problème donné. C'est à dire qu'il conçoit une architecture (nombre d'états) et détermine les transitions nécessaires entre ces états. Différentes applications ont été réalisées dans le cadre de ce travail dans le domaine de la reconnaissance d'images, de la prévision de séries temporelles, de la ségmentation d'images et du suivi d'objets dans une séquence d'images. Les nouveaux algorithmes proposés par ce travail sont applicables à n'importe quel domaine, sous les hypothèses nécessaires aux CMC. Ils permettent un apprentissage rapide des modèles, et une détermination entièrement automatique de l'architecture (nombre d'états et transitions autorisées) des CMC
The main point of this work is based on the quality of modelization of data (called observations) made by hidden Markov models (HMMs). Our goal is to propose algorithms that improve this quality. The criterion used to quantify the quality of HMM is the probability that a given model generates a given observation. To solve this problem, we use a genetic hybridization of HMM. Using genetic algorithms (GAs) jointly to HMM permits two things. First, GAs let us to explore more efficiently the set of models, avoiding local optima. Second, GAs optimize an important characteristic of HMM : its number of hidden states. The most efficient hybrid algorithm finds the best HMM for a given problem, by itself. This means that the GA designs a set of states and the associated transition probabilities. Many explications have been done in the framework of this thesis, in many domains like image recognition, time series prediction, unsupervised image segmentation and object tracking in sequences of images. The new algorithms proposed here are appliable to all domains (peovided that hypothesis related to HMM are satisfied). They allow a fast and efficient training of HMM, and an entirely automatic determination of the architecture (number of states, transition probabilities) of the HMM

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019
La compréhension du lien entre les caractéristiques génomiques d’un individu, le génotype, et son état biologique, le phénotype, est un élément essentiel au développement d’une médecine personnalisée où les traitements sont adaptés à chacun. Elle permet notamment d’anticiper des maladies, d’estimer la réponse à des traitements et même d’identifier de nouvelles cibles pharmaceutiques. L’apprentissage automatique est une science visant à développer des algorithmes capables d’apprendre à partir d’exemples. Ces algorithmes peuvent être utilisés pour produire des modèles qui estiment des phénotypes à partir de génotypes, lesquels peuvent ensuite être étudiés pour élucider les mécanismes biologiques sous-jacents aux phénotypes. Toutefois, l’utilisation d’algorithmes d’apprentissage dans ce contexte pose d’importants défis algorithmiques et théoriques. La haute dimensionnalité des données génomiques et la petite taille des échantillons de données peuvent mener au surapprentissage; le volume des données requiert des algorithmes adaptés qui limitent leur utilisation des ressources computationnelles; et finalement, les modèles obtenus doivent pouvoir être interprétés par des experts du domaine, ce qui n’est pas toujours possible. Cette thèse présente des algorithmes d’apprentissage produisant des modèles interprétables pour la prédiction de phénotypes à partir de génotypes. En premier lieu, nous explorons la prédiction de phénotypes discrets à l’aide d’algorithmes à base de règles. Nous proposons de nouvelles implémentations hautement optimisées et des garanties de généralisation adaptées aux données génomiques. En second lieu, nous nous intéressons à un problème plus théorique, soit la régression par intervalles, et nous proposons deux nouveaux algorithmes d’apprentissage, dont un à base de règles. Finalement, nous montrons que ce type de régression peut être utilisé pour prédire des phénotypes continus et que ceci mène à des modèles plus précis que ceux des méthodes conventionnelles en présence de données censurées ou bruitées. Le thème applicatif de cette thèse est la prédiction de la résistance aux antibiotiques, un problème de santé publique d’envergure mondiale. Nous démontrons que nos algorithmes peuvent servir à prédire, de façon très précise, des phénotypes de résistance, tout en contribuant à en améliorer la compréhension. Ultimement, nos algorithmes pourront servir au développement d’outils permettant une meilleure utilisation des antibiotiques et un meilleur suivi épidémiologique, un élément clé de la solution à ce problème.
A thorough understanding of the relationship between the genomic characteristics of an individual (the genotype) and its biological state (the phenotype) is essential to personalized medicine, where treatments are tailored to each individual. This notably allows to anticipate diseases, estimate response to treatments, and even identify new pharmaceutical targets. Machine learning is a science that aims to develop algorithms that learn from examples. Such algorithms can be used to learn models that estimate phenotypes based on genotypes, which can then be studied to elucidate the biological mechanisms that underlie the phenotypes. Nonetheless, the application of machine learning in this context poses significant algorithmic and theoretical challenges. The high dimensionality of genomic data and the small size of data samples can lead to overfitting; the large volume of genomic data requires adapted algorithms that limit their use of computational resources; and importantly, the learned models must be interpretable by domain experts, which is not always possible. This thesis presents learning algorithms that produce interpretable models for the prediction of phenotypes based on genotypes. Firstly, we explore the prediction of discrete phenotypes using rule-based learning algorithms. We propose new implementations that are highly optimized and generalization guarantees that are adapted to genomic data. Secondly, we study a more theoretical problem, namely interval regression. We propose two new learning algorithms, one which is rule-based. Finally, we show that this type of regression can be used to predict continuous phenotypes and that this leads to models that are more accurate than those of conventional approaches in the presence of censored or noisy data. The overarching theme of this thesis is an application to the prediction of antibiotic resistance, a global public health problem of high significance. We demonstrate that our algorithms can be used to accurately predict resistance phenotypes and contribute to the improvement of their understanding. Ultimately, we expect that our algorithms will take part in the development of tools that will allow a better use of antibiotics and improved epidemiological surveillance, a key component of the solution to this problem.

Internet ainsi que tous les moyens numériques modernes disponibles pour communiquer, s'informer ou se divertir génèrent des données en quantités de plus en plus importantes. Dans des domaines aussi variés que la recherche d'information, la bio-informatique, la linguistique computationnelle ou la sécurité numérique, des méthodes automatiques capables d'organiser, classifier, ou transformer des téraoctets de données apportent une aide précieuse. L'apprentissage artificiel traite de la conception d'algorithmes qui permettent d'entraîner de tels outils à l'aide d'exemples d'apprentissage. Utiliser certaines de ces méthodes pour automatiser le traitement de problèmes complexes, en particulier quand les quantités de données en jeu sont insurmontables pour des opérateurs humains, paraît inévitable. Malheureusement, la plupart des algorithmes d'apprentissage actuels, bien qu'efficaces sur de petites bases de données, présentent une complexité importante qui les rend inutilisables sur de trop grandes masses de données. Ainsi, il existe un besoin certain dans la communauté de l'apprentissage artificiel pour des méthodes capables d'être entraînées sur des ensembles d'apprentissage de grande échelle, et pouvant ainsi gérer les quantités colossales d'informations générées quotidiennement. Nous développons ces enjeux et défis dans le Chapitre 1. Dans ce manuscrit, nous proposons des solutions pour réduire le temps d'entraînement et les besoins en mémoire d'algorithmes d'apprentissage sans pour autant dégrader leur précision. Nous nous intéressons en particulier aux Machines à Vecteurs Supports (SVMs), des méthodes populaires utilisées en général pour des tâches de classification automatique mais qui peuvent être adaptées à d'autres applications. Nous décrivons les SVMs en détail dans le Chapitre 2. Ensuite, dans le Chapitre 3, nous étudions le processus d'apprentissage par descente de gradient stochastique pour les SVMs linéaires. Cela nous amène à définir et étudier le nouvel algorithme, SGD-QN. Après cela, nous introduisons une nouvelle procédure d'apprentissage : le principe du “Process/Reprocess”. Nous déclinons alors trois algorithmes qui l'utilisent. Le Huller et LaSVM sont présentés dans le Chapitre 4. Ils servent à apprendre des SVMs destinés à traiter des problèmes de classification binaire (décision entre deux classes). Pour la tˆache plus complexe de prédiction de sorties structurées, nous modifions par la suite en profondeur l'algorithme LaSVM, ce qui conduit à l'algorithme LaRank présenté dans le Chapitre 5. Notre dernière contribution concerne le problème récent de l'apprentissage avec une supervision ambigüe pour lequel nous proposons un nouveau cadre théorique (et un algorithme associé) dans le Chapitre 6. Nous l'appliquons alors au problème de l'étiquetage sémantique du langage naturel. Tous les algorithmes introduits dans cette thèse atteignent les performances de l'état-de-l'art, en particulier en ce qui concerne les vitesses d'entraînement. La plupart d'entre eux ont été publiés dans des journaux ou actes de conférences internationaux. Des implantations efficaces de chaque méthode ont également été rendues disponibles. Dans la mesure du possible, nous décrivons nos nouveaux algorithmes de la manière la plus générale possible afin de faciliter leur application à des tâches nouvelles. Nous esquissons certaines d'entre elles dans le Chapitre 7.

L'objectif de cette thèse est de développer des algorithmes d'apprentissage adaptés aux grandes masses de données. Dans un premier temps, nous considérons le problème de la classification avec un grand nombre de classes. Afin d'obtenir un algorithme adapté à la grande dimension, nous proposons un algorithme qui transforme le problème multi-classes en un problème de classification binaire que nous sous-échantillonnons de manière drastique. Afin de valider cette méthode, nous fournissons une analyse théorique et expérimentale détaillée.Dans la seconde partie, nous approchons le problème de l'apprentissage sur données distribuées en introduisant un cadre asynchrone pour le traitement des données. Nous appliquons ce cadre à deux applications phares : la factorisation de matrice pour les systèmes de recommandation en grande dimension et la classification binaire
This thesis focuses on developing scalable algorithms for large scale machine learning. In this work, we present two perspectives to handle large data. First, we consider the problem of large-scale multiclass classification. We introduce the task of multiclass classification and the challenge of classifying with a large number of classes. To alleviate these challenges, we propose an algorithm which reduces the original multiclass problem to an equivalent binary one. Based on this reduction technique, we introduce a scalable method to tackle the multiclass classification problem for very large number of classes and perform detailed theoretical and empirical analyses.In the second part, we discuss the problem of distributed machine learning. In this domain, we introduce an asynchronous framework for performing distributed optimization. We present application of the proposed asynchronous framework on two popular domains: matrix factorization for large-scale recommender systems and large-scale binary classification. In the case of matrix factorization, we perform Stochastic Gradient Descent (SGD) in an asynchronous distributed manner. Whereas, in the case of large-scale binary classification we use a variant of SGD which uses variance reduction technique, SVRG as our optimization algorithm

L'objectif initial de la première partie de cette thèse est d'éclairer par la théorie une pratique communément répandue au sein des practiciens pour l'audit (ou risk assessment en anglais) de méthodes prédictives (ou prédicteurs) : la validation croisée (ou cross-validation en anglais). La seconde partie s'inscrit principalement dans la théorie des processus et son apport concerne essentiellement les applications à des données économiques et financières. Le chapitre 1 s'intéresse au cas classique de prédicteurs de Vapnik-Chernovenkis dimension (VC-dimension dans la suite) finie obtenus par minimisation du risque empirique. Le chapitre 2 s'intéresse donc à une autre classe de prédicteurs plus large que celle du chapitre 1 : les estimateurs stables. Dans ce cadre, nous montrons que les méthodes de validation croisée sont encore consistantes. Dans le chapitre 3, nous exhibons un cas particulier important le subagging où la méthode de validation croisée permet de construire des intervalles de confiance plus étroits que la méthodologie traditionnelle issue de la minimisation du risque empirique sous l'hypothèse de VC-dimension finie. Le chapitre 4 propose un proxy mensuel du taux de croissance du Produit Intérieur Brut français qui est disponible officiellement uniquement à fréquence trimestrielle. Le chapitre 5 décrit la méthodologie pour construire un indicateur synthétique mensuel dans les enquêtes de conjoncture dans le secteur des services en France. L'indicateur synthétique construit est publié mensuellement par l'Insee dans les Informations Rapides. Le chapitre 6 décrit d'un modèle semi-paramétrique de prix spot d'électricité sur les marchés de gros ayant des applications dans la gestion du risque de la production d'électricité.

La prise de décision stratégique concernant des ressources de valeur devrait tenir compte du degré d'aversion au risque. D'ailleurs, de nombreux domaines d'application mettent le risque au cœur de la prise de décision. Toutefois, ce n'est pas le cas de l'apprentissage automatique. Ainsi, il semble essentiel de devoir fournir des indicateurs et des algorithmes dotant l'apprentissage automatique de la possibilité de prendre en considération le risque dans la prise de décision. En particulier, nous souhaiterions pouvoir estimer ce dernier sur de courtes séquences dépendantes générées à partir de la classe la plus générale possible de processus stochastiques en utilisant des outils théoriques d'inférence statistique et d'aversion au risque dans la prise de décision séquentielle. Cette thèse étudie ces deux problèmes en fournissant des méthodes algorithmiques prenant en considération le risque dans le cadre de la prise de décision en apprentissage automatique. Un algorithme avec des performances de pointe est proposé pour une estimation précise des statistiques de risque avec la classe la plus générale de processus ergodiques et stochastiques. De plus, la notion d'aversion au risque est introduite dans la prise de décision séquentielle (apprentissage en ligne) à la fois dans les jeux de bandits stochastiques et dans l'apprentissage séquentiel antagoniste
Strategic decision-making over valuable resources should consider risk-averse objectives. Many practical areas of application consider risk as central to decision-making. However, machine learning does not. As a result, research should provide insights and algorithms that endow machine learning with the ability to consider decision-theoretic risk. In particular, in estimating decision-theoretic risk on short dependent sequences generated from the most general possible class of processes for statistical inference and through decision-theoretic risk objectives in sequential decision-making. This thesis studies these two problems to provide principled algorithmic methods for considering decision-theoretic risk in machine learning. An algorithm with state-of-the-art performance is introduced for accurate estimation of risk statistics on the most general class of stationary--ergodic processes and risk-averse objectives are introduced in sequential decision-making (online learning) in both the stochastic multi-arm bandit setting and the adversarial full-information setting

Ces dernières années, les ontologies ont suscité de nombreux travaux dans le domaine du web sémantique. Elles sont utilisées pour fournir le vocabulaire sémantique permettant de rendre la connaissance du domaine disponible pour l'échange et l'interprétation au travers des systèmes d'information. Toutefois, en raison de la nature décentralisée du web sémantique, les ontologies sont très hétérogènes. Cette hétérogénéité provoque le problème de la variation de sens ou ambiguïté dans l'interprétation des entités et, par conséquent, elle empêche le partage des connaissances du domaine. L'alignement d'ontologies, qui a pour but la découverte des correspondances sémantiques entre des ontologies, devient une tâche cruciale pour résoudre ce problème d'hétérogénéité dans les applications du web sémantique. Les principaux défis dans le domaine de l'alignement d'ontologies ont été décrits dans des études récentes. Parmi eux, la sélection de mesures de similarité appropriées ainsi que le réglage de la configuration de leur combinaison sont connus pour être des problèmes fondamentaux que la communauté doit traiter. En outre, la vérification de la cohérence sémantique des correspondances est connue pour être une tâche importante. Par ailleurs, la difficulté du problème augmente avec la taille des ontologies. Pour faire face à ces défis, nous proposons dans cette thèse une nouvelle approche, qui combine différentes techniques issues des domaines de l'apprentissage automatique, d'appariement de graphes et de recherche d'information en vue d'améliorer la qualité de l'alignement d'ontologies. En effet, nous utilisons des techniques de recherche d'information pour concevoir de nouvelles mesures de similarité efficaces afin de comparer les étiquettes et les profils d'entités de contexte au niveau des entités. Nous appliquons également une méthode d'appariement de graphes appelée propagation de similarité au niveau de la structure qui découvre effectivement des correspondances en exploitant des informations structurelles des entités. Pour combiner les mesures de similarité au niveau des entités, nous transformons la tâche de l'alignement d'ontologie en une tâche de classification de l'apprentissage automatique. Par ailleurs, nous proposons une méthode dynamique de la somme pondérée pour combiner automatiquement les correspondances obtenues au niveau des entités et celles obtenues au niveau de la structure. Afin d'écarter les correspondances incohérentes, nous avons conçu une nouvelle méthode de filtrage sémantique. Enfin, pour traiter le problème de l'alignement d'ontologies à large échelle, nous proposons deux méthodes de sélection des candidats pour réduire l'espace de calcul. Toutes ces contributions ont été mises en œuvre dans un prototype nommé YAM++. Pour évaluer notre approche, nous avons utilisé des données du banc d'essai de la compétition OAEI : Benchmark, Conference, Multifarm, Anatomy, Library and Large Biomedical Ontologies. Les résultats expérimentaux montrent que les méthodes proposées sont très efficaces. De plus, en comparaison avec les autres participants à la compétition OAEI, YAM++ a montré sa compétitivité et a acquis une position de haut rang.

Les réseaux domestiques sont confrontés à une évolution continue et deviennent de plus en plus complexes. Leur complexité a évolué selon deux dimensions interdépendantes. D'une part, la topologie du réseau domestique devient plus complexe avec la multiplication des équipements et des technologies de connectivité. D'autre part, l'ensemble des services accessibles via le réseau domestique ne cesse de s’élargir. Un tel contexte a rendu la gestion du réseau domestique plus difficile pour les Fournisseurs d’Accès Internet (FAI) et les utilisateurs finaux. Dans ce manuscrit, nous nous concentrons sur la deuxième dimension de la complexité décrite ci-dessus liée au trafic circulant depuis/vers le réseau domestique. Notre première contribution consiste à proposer une architecture pour la supervision du trafic dans les réseaux domestiques. Nous fournissons une étude comparative de certains outils open source existants. Ensuite, nous effectuons une évaluation de performances expérimentale d’un sous ensemble des processus impliqués dans notre architecture. Sur la base des résultats obtenus, nous discutons les limites et les possibilités de déploiement de ce type de solution. Dans notre deuxième contribution, nous présentons notre analyse à large échelle des usages et du trafic résidentiel basée sur une trace de trafic réelle impliquant plus de 34 000 clients. Premièrement, nous présentons notre méthode de collecte et de traitement des données. Deuxièmement, nous présentons nos observations statistiques vis-à-vis des différentes couches de l’architecture Internet. Ensuite, nous effectuons une analyse subjective auprès de 645 clients résidentiels. Enfin, nos résultats fournissent une synthèse complète des usages et des caractéristiques des applications résidentielles. Dans notre troisième contribution, nous proposons une nouvelle méthode pour la classification en temps réel du trafic résidentiel. Notre méthode, laquelle est basée sur l’utilisation d’un algorithme d’apprentissage statistique de type C5.0, vise à combler les carences identifiées dans la littérature. Ensuite, nous détaillons notre implémentation d’une sonde légère sur un prototype de passerelle résidentielle capable de capturer, de suivre et d'identifier d’une manière fine les applications actives dans le réseau domestique. Cette implémentation nous permet, en outre, de valider nos principes de conception via un banc d'essai réaliste mis en place à cet effet. Les résultats obtenus indiquent que notre solution est efficace et faisable
Home networks are facing a continuous evolution and are becoming more and more complex. Their complexity has evolved according to two interrelated dimensions. On the one hand, the home network topology (devices and connectivity technologies) tends to produce more complex configurations. On the other hand, the set of services accessed through the home network is growing in a tremendous fashion. Such context has made the home network management more challenging for both Internet Service Provider (ISP) and end-users. In this dissertation, we focus on the traffic dimension of the above described complexity. Our first contribution consists on proposing an architecture for traffic monitoring in home networks. We provide a comparative study of some existing open source tools. Then, we perform a testbed evaluation of the main software components implied in our architecture. Based on the experiments results, we discuss several deployment limits and possibilities. In our second contribution, we conduct a residential traffic and usages analysis based on real trace involving more than 34 000 customers. First, we present our data collection and processing methodology. Second, we present our findings with respect to the different layers of the TCP/IP protocol stack characteristics. Then, we perform a subjective analysis across 645 of residential customers. The results of both evaluations provide a complete synthesis of residential usage patterns and applications characteristics. In our third contribution, we propose a novel scheme for real-time residential traffic classification. Our scheme, which is based on a machine learning approach called C5.0, aims to fulfil the lacks identified in the literature. At this aim, our algorithm is evaluated using several traffic inputs. Then, we detail how we implemented a lightweight probe able to capture, track and identify finely applications running in the home network. This implementation allowed us to validate our designing principles upon realistic test conditions. The obtained results show clearly the efficiency and feasibility of our solution

Ce travail de thèse s'inscrit dans le domaine du machine learning et concerne plus particulièrement les sous-catégories de l'optimisation stochastique, du online learning et du clustering. Ces sous-domaines existent depuis plusieurs décennies mais ils ont tous reçu un éclairage différent au cours de ces dernières années. Notamment, les jeux de bandits offrent aujourd'hui un cadre commun pour l'optimisation stochastique et l'online learning. Ce point de vue conduit a de nombreuses extensions du jeu de base. C'est sur l'étude mathématique de ces jeux que se concentre la première partie de cette thèse. La seconde partie est quant à elle dédiée au clustering et plus particulièrement à deux notions importantes: la consistance asymptotique des algorithmes et la stabilité comme méthode de sélection de modèles.

L'objet de cette thèse est l'étude de diverses propriétés d'apprentissage à partir d'exemples par des méthodes de Physique Statistique, notamment, par la méthode des répliques. Des tâches supervisées, correspondant à la classification binaire de données, ainsi que des tâches non supervisées, comme l'estimation paramétrique d'une densité de probabilité, sont considérées. Dans la première partie, une approche variationnelle permet de déterminer la performance de l'apprentissage optimal d'une direction d'anisotropie, et de déduire une fonction de coût permettant d'obtenir ces performances optimales. Dans le cas de l'apprentissage supervisé d'une tâche linéairement séparable, des simulations numériques confirmant nos résultats théoriques ont permis de déterminer les effets de taille finie. Dans le cas d'une densité de probabilité constituée de deux gaussiennes, la performance de l'apprentissage optimal présente de nombreuses transitions de phases en fonction du nombre de données. Ces résultats soulèvent une controverse entre la théorie variationnelle et l'approche bayesienne de l'apprentissage optimal. Dans la deuxième partie, nous étudions deux approches différentes de l'apprentissage de tâches de classification complexes. La première approche considérée est celle des machines à exemples supports. Nous avons étudié une famille de ces machines pour laquelle les séparateurs linéaire et quadratique sont deux cas particuliers. La capacité, les valeurs typiques de la marge et du nombre d'exemples supports, sont déterminées. La deuxième approche considérée est celle d'une machine de parité apprenant avec un algorithme incrémental. Cet algorithme construit progressivement un réseau de neurones à une couche cachée. La capacité théorique obtenue pour l'algorithme considéré est proche de celle de la machine de parité.

Dans le domaine de l'apprentissage machine, les caractéristiques des données varient généralement dans l'espace des entrées : la distribution globale pourrait être multimodale et contenir des non-linéarités. Afin d'obtenir de bonnes performances, l'algorithme d'apprentissage devrait alors être capable de capturer et de s'adapter à ces changements. Même si les modèles linéaires ne parviennent pas à décrire des distributions complexes, ils sont réputés pour leur passage à l'échelle, en entraînement et en test, aux grands ensembles de données en termes de nombre d'exemples et de nombre de fonctionnalités. Plusieurs méthodes ont été proposées pour tirer parti du passage à l'échelle et de la simplicité des hypothèses linéaires afin de construire des modèles aux grandes capacités discriminatoires. Ces méthodes améliorent les modèles linéaires, dans le sens où elles renforcent leur expressivité grâce à différentes techniques. Cette thèse porte sur l'amélioration des approches d'apprentissage locales, une famille de techniques qui infère des modèles en capturant les caractéristiques locales de l'espace dans lequel les observations sont intégrées.L'hypothèse fondatrice de ces techniques est que le modèle appris doit se comporter de manière cohérente sur des exemples qui sont proches, ce qui implique que ses résultats doivent aussi changer de façon continue dans l'espace des entrées. La localité peut être définie sur la base de critères spatiaux (par exemple, la proximité en fonction d'une métrique choisie) ou d'autres relations fournies, telles que l'association à la même catégorie d'exemples ou un attribut commun. On sait que les approches locales d'apprentissage sont efficaces pour capturer des distributions complexes de données, évitant de recourir à la sélection d'un modèle spécifique pour la tâche. Cependant, les techniques de pointe souffrent de trois inconvénients majeurs :ils mémorisent facilement l'ensemble d'entraînement, ce qui se traduit par des performances médiocres sur de nouvelles données ; leurs prédictions manquent de continuité dans des endroits particuliers de l'espace ; elles évoluent mal avec la taille des ensembles des données. Les contributions de cette thèse examinent les problèmes susmentionnés dans deux directions : nous proposons d'introduire des informations secondaires dans la formulation du problème pour renforcer la continuité de la prédiction et atténuer le phénomène de la mémorisation ; nous fournissons une nouvelle représentation de l'ensemble de données qui tient compte de ses spécificités locales et améliore son évolutivité. Des études approfondies sont menées pour mettre en évidence l'efficacité de ces contributions pour confirmer le bien-fondé de leurs intuitions. Nous étudions empiriquement les performances des méthodes proposées tant sur des jeux de données synthétiques que sur des tâches réelles, en termes de précision et de temps d'exécution, et les comparons aux résultats de l'état de l'art. Nous analysons également nos approches d'un point de vue théorique, en étudiant leurs complexités de calcul et de mémoire et en dérivant des bornes de généralisation serrées
In Machine Learning field, data characteristics usually vary over the space: the overall distribution might be multi-modal and contain non-linearities.In order to achieve good performance, the learning algorithm should then be able to capture and adapt to these changes. Even though linear models fail to describe complex distributions, they are renowned for their scalability, at training and at testing, to datasets big in terms of number of examples and of number of features. Several methods have been proposed to take advantage of the scalability and the simplicity of linear hypotheses to build models with great discriminatory capabilities. These methods empower linear models, in the sense that they enhance their expressive power through different techniques. This dissertation focuses on enhancing local learning approaches, a family of techniques that infers models by capturing the local characteristics of the space in which the observations are embedded. The founding assumption of these techniques is that the learned model should behave consistently on examples that are close, implying that its results should also change smoothly over the space. The locality can be defined on spatial criteria (e.g. closeness according to a selected metric) or other provided relations, such as the association to the same category of examples or a shared attribute. Local learning approaches are known to be effective in capturing complex distributions of the data, avoiding to resort to selecting a model specific for the task. However, state of the art techniques suffer from three major drawbacks: they easily memorize the training set, resulting in poor performance on unseen data; their predictions lack of smoothness in particular locations of the space;they scale poorly with the size of the datasets. The contributions of this dissertation investigate the aforementioned pitfalls in two directions: we propose to introduce side information in the problem formulation to enforce smoothness in prediction and attenuate the memorization phenomenon; we provide a new representation for the dataset which takes into account its local specificities and improves scalability. Thorough studies are conducted to highlight the effectiveness of the said contributions which confirmed the soundness of their intuitions. We empirically study the performance of the proposed methods both on toy and real tasks, in terms of accuracy and execution time, and compare it to state of the art results. We also analyze our approaches from a theoretical standpoint, by studying their computational and memory complexities and by deriving tight generalization bounds

Traditionnellement, l'optimisation du réseau est utilisée afin de fournir de bonnes options de configuration basées sur des modèles mathématiques et des hypothèses statistiques. La tendance actuelle en ce qui concerne des problèmes de réseau consiste à exploiter le pouvoir des données afin d’extraire des modèles et gérer les incertitudes. Cette thèse, propose des cadres algorithmiques pour les réseaux sans fil, basés à la fois sur l'optimisation classique ou des données et sur l'apprentissage automatique. Nous ciblons deux cas, l'association d'utilisateurs et la réservation de ressources en nuages. Dans le premier cas, l'approche de base pour l'association d'utilisateurs qui consiste à connecter des périphériques sans fil à la station de base fournissant le signal le plus puissant, conduit à des configurations inefficaces. De prime abord, nous étudions, l’association d’utilisateurs distribués avec des garanties de qualité de service prioritaires, puis nous prenons en considération l’équilibrage de charge centralisé évolutif, basé sur le transport optimal par calcul et enfin nous prenons l’exemple d’une association d’utilisateurs robuste basée sur la prédiction de trafic approximative.Ensuite, nous développons un nouveau cadre pour la réservation de ressources en nuages dans les scénarios les plus défavorables, dans lequel la demande est gérée par un adversaire. Nous proposons des politiques «no regret» et nous garantissons une faisabilité asymptotique des contraintes budgétaires. Nous développons un cadre général, pour des problèmes d’optimisation, convexe en ligne (OCO) avec contraintes budgétaires à long terme complétant les résultats de la littérature récente
Traditionally, network optimization is used to provide good configurations in real network system problems based on mathematical models and statistical assumptions. Recently, this paradigm is evolving, fueled by an explosion of availability of data. The modern trend in networking problems is to tap into the power of data to extract models and deal with uncertainty. This thesis proposes algorithmic frameworks for wireless networks, based both on classical or data-driven optimization and machine learning. We target two use cases, user association and cloud resource reservation.The baseline approach for user association, connecting wireless devices to the base station that provides the strongest signal, leads to very inefficient configurations even in current wireless networks. We focus on tailoring user association based on resource efficiency and service requirement satisfaction, depending on the underlying network demand. We first study distributed user association with priority QoS guarantees, then scalable centralized load balancing based on computational optimal transport and finally robust user association based on approximate traffic prediction.Moving to the topic of cloud resource reservation, we develop a novel framework for resource reservation in worst-case scenaria, where the demand is engineered by an adversary aiming to harm our performance. We provide policies that have ``no regret'' and guarantee asymptotic feasibility in budget constraints under such workloads. More importantly we expand to a general framework for online convex optimization (OCO) problems with long term budget constraints complementing the results of recent literature in OCO

L'apprentissage machine est une technologie désormais omniprésente dans notre quotidien. Toutefois, ce domaine reste encore largement empirique et ses enjeux scientifiques manquent d'une compréhension théorique profonde. Cette thèse se penche vers la découverte des mécanismes sous-tendant l'apprentissage dans les réseaux de neurones artificiels à travers le prisme de la physique statistique. Dans une première partie, nous nous intéressons aux propriétés statiques des problèmes d'apprentissage, que nous introduisons au chapitre 1.1. Dans le chapitre 1.2, nous considérons la classification d'un mélange binaire de nuages gaussiens et nous dérivons des expressions rigoureuses pour les erreurs en dimension infinie, que nous appliquons pour éclairer le rôle des différents paramètres du problème. Dans le chapitre 1.3, nous montrons comment étendre le modèle de perceptron enseignant-étudiant pour considérer la classification multi-classes, en dérivant des expressions asymptotiques pour la performance optimale et la performance de la minimisation du risque empirique régularisé. Dans la deuxième partie, nous nous concentrons sur la dynamique de l'apprentissage, que nous introduisons dans le chapitre 2.1. Dans le chapitre 2.2, nous montrons comment décrire analytiquement la dynamique de l'algorithme du gradient stochastique à échantillonage mini-lots (mini-batch SGD) dans la classification binaire de mélanges gaussiens, en utilisant la théorie dynamique du champ moyen. Le chapitre 2.3 présente une analyse du bruit effectif introduit par SGD. Dans le chapitre 2.4, nous considérons le problème de la récupération des signes comme exemple d'optimisation hautement non convexe et montrons que la stochasticité est cruciale pour la généralisation. La conclusion de la thèse est présentée dans la troisième partie
Machine learning technologies have become ubiquitous in our daily lives. However, this field still remains largely empirical and its scientific stakes lack a deep theoretical understanding.This thesis explores the mechanisms underlying learning in artificial neural networks through the prism of statistical physics. In the first part, we focus on the static properties of learning problems, that we introduce in Chapter 1.1. In Chapter 1.2, we consider the prototype classification of a binary mixture of Gaussian clusters and we derive rigorous closed-form expressions for the errors in the infinite-dimensional regime, that we apply to shed light on the role of different problem parameters. In Chapter 1.3, we show how to extend the teacher-student perceptron model to encompass multi-class classification deriving asymptotic expressions for the optimal performance and the performance of regularised empirical risk minimisation. In the second part, we turn our focus to the dynamics of learning, that we introduce in Chapter 2.1. In Chapter 2.2, we show how to track analytically the training dynamics of multi-pass stochastic gradient descent (SGD) via dynamical mean-field theory for generic non convex loss functions and Gaussian mixture data. Chapter 2.3 presents a late-time analysis of the effective noise introduced by SGD in the underparametrised and overparametrised regimes. In Chapter 2.4, we take the sign retrieval problem as a benchmark highly non-convex optimisation problem and show that stochasticity is crucial to achieve perfect generalisation. The third part of the thesis contains the conclusions and some future perspectives

Cette thèse traite des domaines suivant en Apprentissage Automatique: la théorie des Bandits, l'Apprentissage statistique et l'Apprentissage par renforcement. Son fil rouge est l'étude de plusieurs notions d'adaptation, d'un point de vue non asymptotique : à un environnement ou à un adversaire dans la partie I, à la structure d'un signal dans la partie II, à la structure de récompenses ou à un modèle des états du monde dans la partie III. Tout d'abord nous dérivons une analyse non asymptotique d'un algorithme de bandit à plusieurs bras utilisant la divergence de Kullback-Leibler. Celle-ci permet d'atteindre, dans le cas de distributions à support fini, la borne inférieure de performance asymptotique dépendante des distributions de probabilité connue pour ce problème. Puis, pour un bandit avec un adversaire possiblement adaptatif, nous introduisons des modèles dépendants de l'histoire et traduisant une possible faiblesse de l'adversaire et montrons comment en tirer parti pour concevoir des algorithmes adaptatifs à cette faiblesse. Nous contribuons au problème de la régression en montrant l'utilité des projections aléatoires, à la fois sur le plan théorique et pratique, lorsque l'espace d'hypothèses considéré est de dimension grande, voire infinie. Nous utilisons également des opérateurs d'échantillonnage aléatoires dans le cadre de la reconstruction parcimonieuse lorsque la base est loin d'être orthogonale. Enfin, nous combinons la partie I et II : pour fournir une analyse non-asymptotique d'algorithmes d'apprentissage par renforcement; puis, en amont du cadre des Processus Décisionnel de Markov, pour discuter du problème pratique du choix d'un bon modèle d'états.