Dans le domaine de l'apprentissage par renforcement, la planifi ation dans les processus de décisions markoviens est une approche en ligne utilisée pour contrôler un système dont on possède un modèle génératif. Nous nous proposons d'adresser ce problème dans le cas déterministe avec espace d'action discret ou continu. Cette thèse s'attache au chapitre 2 à présenter succinctement les processus de décision markoviens puis l'apprentissage par renforcement. Nous présentons en particulier trois algorithmes centraux que sont l'itération de la valeur, l'itération de la politique et le Q-Learning. Au chapitre 3, nous expliquons l'approche de la planifi cation dans les processus de décision markoviens pour contrôler des systèmes en ligne. Ainsi, nous supposons posséder un modèle génératif d'un système à contrôler et nous l'utilisons pour décider, à chaque pas de temps du système à contrôler, de l'action à lui appliquer en vue de le faire transiter dans un état maximisant la somme future des récompenses dépréciées. Nous considérons un modèle génératif comme une boite noire, laquelle étant donnée un état et une action, nous retourne un état successeur ainsi qu'une récompense associée. L'approche optimiste est détaillée dans sa philosophie et dans son application à la résolution du dilemme exploration-exploitation au travers de di fférentes techniques présentes dans la littérature. Nous présentons di fférents algorithmes issus de la littérature et s'appliquant dans le cadre de la plani fication dans les processus de décision markoviens. Nous nous concentrons en particulier sur les algorithmes effectuant une recherche avant par construction d'un arbre des possibilités look-ahead tree en anglais. Les algorithmes sont présentés et mis en relation les uns avec les autres. L'algorithme de recherche du plus court chemin dans un graphe A est présenté en vue d'être relié à notre première contribution, l'algorithme de plani fication optimiste. Nous détaillons cette première contribution au chapitre 4. Dans un premier temps, nous présentons en détail le contexte de la planification sous contrainte de ressources computationnelles ainsi que la notion de regret. Dans un second temps, l'algorithme de plani cation uniforme est présenté et son regret est analysé pour obtenir une base comparative avec l'algorithme de plani cation optimiste. Enfi n, celui-ci est présenté et son regret est analysé. L'analyse est étendue à une classe de problèmes dé finie par la proportion de chemins -optimaux, permettant ainsi d'établir une borne supérieure sur le regret de l'algorithme de plani cation optimiste meilleure que celle de l'algorithme de plani cation uniforme dans le pire des cas. Des expérimentations sont menées pour valider la théorie et chi rer les performances de l'algorithme de plani cation optimiste par le biais de problèmes issus de la littérature comme le cart-pole, l'acrobot ou le mountain car et en comparaison à l'algorithme de plani cation uniforme, à l'algorithme UCT ainsi qu'à l'algorithme de recherche aléatoire. Nous verrons que, comme suggéré par la dé nition de la borne supérieure sur son regret, l'algorithme de plani cation optimiste est sensible au facteur de branchement ce qui nous mène à envisager le cas où l'espace d'action est continu. Ceci fait l'objet de nos deux autres contributions au chapitre 5. Notre deuxième contribution est l'algorithme de plani cation lipschitzienne reposant sur une hypothèse de régularité sur les récompenses menant à supposer que la fonction de transition et la fonction récompense du processus de décision markovien modélisant le système à contrôler sont lipschitziennes. De cette hypothèse, nous formulons une borne sur un sous-ensemble de sousespaces de l'espace d'action continu nous permettant de l'explorer par discr étisations successives. L'algorithme demande cependant la connaissance de la constante de Lipschitz associée au système à contrôler. Des expérimentations sont menées pour évaluer l'approche utilisée pour diff érentes constantes de Lipschitz sur des problèmes de la littérature comme le cart-pole, l'acrobot ou la lévitation magnétique d'une boule en acier. Les résultats montrent que l'estimation de la constante de Lipschitz est diffi cile et ne permet pas de prendre en compte le paysage local des récompenses. Notre troisième contribution est l'algorithme de plani cation séquentielle découlant d'une approche intuitive où une séquence d'instances d'un algorithme d'optimisation globale est utilisée pour construire des séquences d'actions issues de l'espace d'action continu. Des expérimentations sont menées pour évaluer cet approche intuitive pour diff érents algorithmes d'optimisation globale sur des problèmes de la littérature comme le cart-pole, le bateau ou le nageur. Les résultats obtenus sont encourageants et valident l'approche intuitive. Finalement, nous concluons en résumant les di érentes contributions et en ouvrant sur de nouvelles perspectives et extensions.

L'apprentissage statistique propose un vaste ensemble de techniques capables de construire des modèles prédictifs à partir d'observations passées. Ces techniques ont montré leurs capacités à traiter des volumétries importantes de données sur des problèmes réels. Cependant, de nouvelles applications génèrent de plus en plus de données qui sont seulement visibles sous la forme d'un flux et doivent être traitées séquentiellement. Parmi ces applications on citera : la gestion de réseaux de télécommunications, la modélisation des utilisateurs au sein d'un réseau social, le web mining. L'un des défis techniques est de concevoir des algorithmes permettant l'apprentissage avec les nouvelles contraintes imposées par les flux de données. Nous proposons d'abord ce problème en proposant de nouvelles techniques de résumé de flux de données dans le cadre de l'apprentissage supervisé. Notre méthode est constituée de deux niveaux. Le premier niveau utilise des techniques incrémentales de résumé en-ligne pour les flux qui prennent en compte les ressources mémoire et processeur et possèdent des garanties en termes d'erreur. Le second niveau utilise les résumés de faible taille, issus du premier niveau, pour construire le résumé final à l'aide d'une méthode supervisée performante hors-ligne. Ces résumés constituent un prétraitement qui nous permet de proposer de nouvelles versions du classifieur bayésien naïf et des arbres de décision fonctionnant en-ligne sur flux de données. Les flux de données peuvent ne pas être stationnaires mais comporter des changements de concept. Nous proposons aussi une nouvelle technique pour détecter ces changements et mettre à jour nos classifieurs.

Nous nous intéressons ici à une interface cerveau-machine (BCI, Brain Computer Interface) permettant de commander une prothèse par la pensée. Le rôle du BCI est de décoder à partir de signaux électroencéphalographiques (EEG) le mouvement désiré par le sujet. Le coeur du BCI est un algorithme de classification caractérisé par le choix des descripteurs des signaux et des règles de décision. L'objet de cette thèse est de développer un système BCI précis, capable d'améliorer ses performances en cours d'utilisation et de s'adapter à l'utilisateur sans nécessiter de multiples sessions d'apprentissage. Nous combinons deux moyens pour y parvenir. Le premier consiste à augmenter la précision du système de décision en recherchant des descripteurs pertinents vis à vis de l'objectif de classification. Le second est d'inclure un retour de l'utilisateur sur le système de décision : l'idée est d'estimer l'erreur du BCI à partir de potentiels cérébraux évoqués, reflétant l'état émotionnel du patient corrélé au succès ou à l'échec de la décision prise par le BCI, et de corriger le système de décision du BCI en conséquence. Les principales contributions de la thèse sont les suivantes : nous avons proposé une méthode d'optimisation de descripteurs à bases d'ondelettes pour des signaux EEG multivoies ; nous avons quantifié théoriquement l'amélioration des performances apportée par le détecteur ; un simulateur du système corrigé et bouclé a été développé pour observer le comportement du système global et comparer différentes stratégies de mise à jour de l'ensemble d'apprentissage ; le système complet a été implémenté et fonctionne en ligne dans des conditions réelles.

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.

Cette thèse aborde le calcul de l'opérateur LASSO (Least Absolute Shrinkage and Selection Operator), ainsi que des problématiques qui lui sont associées, dans le domaine de la régression. Cet opérateur a suscité une attention croissante depuis son introduction par Robert Tibshirani en 1996, par sa capacité à produire ou identi fier des modèles linéaires parcimonieux à partir d'observations bruitées, la parcimonie signi fiant que seules quelques unes parmi de nombreuses variables explicatives apparaissent dans le modèle proposé. Cette sélection est produite par l'ajout à la méthode des moindres-carrés d'une contrainte ou pénalisation sur la somme des valeurs absolues des coe fficients linéaires, également appelée norme l1 du vecteur de coeffi cients. Après un rappel des motivations, principes et problématiques de la régression, des estimateurs linéaires, de la méthode des moindres-carrés, de la sélection de modèle et de la régularisation, les deux formulations équivalentes du LASSO contrainte ou régularisée sont présentées; elles dé finissent toutes deux un problème de calcul non trivial pour associer un estimateur à un ensemble d'observations et un paramètre de sélection. Un bref historique des algorithmes résolvant ce problème est dressé, et les deux approches permettant de gérer la non-di fferentiabilité de la norme l1 sont présentées, ainsi que l'équivalence de ces problèmes avec un programme quadratique. La seconde partie se concentre sur l'aspect pratique des algorithmes de résolution du LASSO. L'un d'eux, proposé par Michael Osborne en 2000, est reformulé. Cette reformulation consiste à donner une défi nition et explication générales de la méthode d'ensemble actif, qui généralise l'algorithme du simplex à la programmation convexe, puis à la spéci fier progressivement pour la programmation LASSO, et à adresser les questions d'optimisation des calculs algébriques. Bien que décrivant essentiellement le même algorithme que celui de Michael Osborne, la présentation qui en est faite ici a l'ambition d'en exposer clairement les mécanismes, et utilise des variables di fférentes. Outre le fait d'aider à mieux comprendre cet algorithme visiblement sous-estimé, l'angle par lequel il est présenté éclaire le fait nouveau que la même méthode s'applique naturellement à la formulation régularisée du LASSO, et non uniquement à la formulation contrainte. La populaire méthode par homotopie (ou LAR-LASSO, ou LARS) est ensuite présentée comme une dérivation de la méthode d'ensemble actif, amenant une formulation alternative et quelque peu simpli fiée de cet algorithme qui fournit les solutions du LASSO pour chaque valeur de son paramètre. Il est montré que, contrairement aux résultats d'une étude récente de Jerome H. Friedman, des implémentations de ces algorithmes suivant ces reformulations sont plus effi caces en terme de temps de calcul qu'une méthode de descente par coordonnées. La troisième partie étudie dans quelles mesures ces trois algorithmes (ensemble actif, homotopie, et descente par coordonnées) peuvent gérer certains cas particuliers, et peuvent être appliqués à des extensions du LASSO ou d'autres problèmes similaires. Les cas particuliers incluent les dégénérescences, comme la présence de variables lineairement dépendantes, ou la sélection/désélection simultanée de variables. Cette dernière problématique, qui était délaissée dans les travaux précédents, est ici expliquée plus largement et une solution simple et efficace y est apportée. Une autre cas particulier est la sélection LASSO à partir d'un nombre très large, voire infi ni de variables, cas pour lequel la méthode d'ensemble actif présente un avantage majeur. Une des extensions du LASSO est sa transposition dans un cadre d'apprentissage en ligne, où il est désirable ou nécessaire de résoudre le problème sur un ensemble d'observations qui évolue dans le temps. A nouveau, la flexibilité limitée de la méthode par homotopie la disquali fie au pro fit des deux autres. Une autre extension est l'utilisation de la pénalisation l1 sur d'autres fonction coûts que la norme l2 du résidu, ou en association avec d'autres pénalisations, et il est rappelé ou établi dans quelles mesures et de quelle façon chaque algorithme peut être transposé à ces problèmes.

Nous présentons dans cette thèse une nouvelle méthode pour la conception de moteurs de reconnaissance personnalisables et auto-évolutifs. La contribution majeure de cette thèse consiste à proposer une approche incrémentale pour l'apprentissage de classifieurs basés sur les systèmes d'inférence floue de type Takagi-Sugeno d'ordre 1. Cette approche comprend, d'une part, une adaptation des paramètres linéaires associés aux conclusions des règles en utilisant la méthode des moindres carrés récursive, et, d'autre part, un apprentissage incrémental des prémisses de ces règles afin de modifier les fonctions d'appartenance suivant l'évolution de la densité des données dans l'espace de classification. La méthode proposée, Evolve++, résout les problèmes d'instabilité d'apprentissage incrémental de ce type de systèmes grâce à un paradigme global d'apprentissage où les prémisses et les conclusions sont apprises en synergie et non de façon indépendante. La performance de ce système a été démontrée sur des bancs d'essai connus, en mettant en évidence notamment sa capacité d'apprentissage à la volée de nouvelles classes. Dans le contexte applicatif de la reconnaissance de gestes manuscrits, ce système permet de s'adapter en continue aux styles d'écriture (personnalisation des symboles) et aux nouveaux besoins des utilisateurs (introduction à la volée des nouveaux symboles). Dans ce domaine, une autre contribution a été d'accélérer l'apprentissage de nouveaux symboles par la synthèse automatique de données artificielles. La technique de synthèse repose sur la théorie Sigma-lognormal qui propose un nouvel espace de représentation des tracés manuscrits basé sur un modèle neuromusculaire du mécanisme d'écriture. L'application de déformations sur le profil Sigma-lognormal permet d'obtenir des tracés manuscrits synthétiques qui sont réalistes et proches de la déformation humaine. L'utilisation de ces tracés synthétiques dans notre système accélère l'apprentissage et améliore de façon significative sa performance globale.

En réponse au besoin croissant de réutiliser les connaissances déjà existantes lors de l'apprentissage des réseaux bayésiens causaux, les connaissances sémantiques contenues dans les ontologies de domaine présentent une excellente alternative pour assister le processus de découverte causale avec le minimum de coût et d'eff ort. Dans ce contexte, la présente thèse s'intéresse plus particulièrement au crossing-over entre les réseaux bayésiens causaux et les ontologies et établit les bases théoriques d'une approche cyclique intégrant les deux formalismes de manière interchangeable. En premier lieu, on va intégrer les connaissances sémantiques contenues dans les ontologies de domaine pour anticiper les meilleures expérimentations au travers d'une stratégie fortuite (qui, comme son nom l'indique, mise sur l'imprévu pour dégager les résultats les plus impressionnants). En e et, les connaissances sémantiques peuvent inclure des relations causales en plus de la structure hiérarchique. Donc au lieu de refaire les mêmes efforts qui ont déjà été menés par les concepteurs et éditeurs d'ontologies, nous proposons de réutiliser les relations (sémantiquement) causales en les adoptant comme étant des connaissances à priori. Ces relations seront alors intégrées dans le processus d'apprentissage de structure (partiellement) causale à partir des données d'observation. Pour compléter l'orientation du graphe causal, nous serons en mesure d'intervenir activement sur le système étudié. Nous présentons également une stratégie décisionnelle basée sur le calcul de distances sémantiques pour guider le processus de découverte causale et s'engager davantage sur des pistes inexplorées. L'idée provient principalement du fait que les concepts les plus rapprochés sont souvent les plus étudiés. Pour cela, nous proposons de renforcer la capacité des ordinateurs à fournir des éclairs de perspicacité en favorisant les expérimentations au niveau des concepts les plus distants selon la structure hiérarchique. La seconde direction complémentaire concerne un procédé d'enrichissement par lequel il sera possible de réutiliser ces découvertes causales et soutenir le caractère évolutif de l'ontologie. Une étude expérimentale a été conduite en utilisant les données génomiques concernant Saccharomyces cerevisiae et l'Ontologie des Gènes pour montrer les potentialités de l'approche SemCaDo dans des domaines ou les expérimentations sont généralement très coûteuses, complexes et fastidieuses.

Quand on cherche à situer l'Inférence Grammaticale dans le paysage de la Recherche, on la place volontiers au sein de l'Apprentissage Automatique, qu'on place lui-même volontiers dans le champ de l'Intelligence Artificielle. Ainsi, dans leur livre de référence, Laurent Miclet et Antoine Cornuéjols préfèrent-ils parler d'Apprentissage Artificiel plutôt que d'Apprentissage Automatique, et consacrent-ils un chapitre complet à l'Inférence Grammaticale. C'est l'histoire du Machine Learning qui explique cette hiérarchie. Pourtant, en 2010, elle n'est pas toujours facile à justifier : combien de chercheurs dans le domaine du Machine Learning connaissent-ils le paradigme d'identification à la limite ? Et combien de chercheurs en Inférence Grammaticale maîtrisent-ils la théorie de la régularisation utilisée en optimisation ? Il suffit de suivre des conférences comme ICGI ou ECML pour constater que les communautés sont différentes, tant sur le plan de leurs motivations que sur celui de leurs cultures scientifiques. En outre, lorsqu'on étudie l'histoire des deux domaines, on observe des points de divergence depuis longtemps déjà. D'un autre côté, plusieurs éléments consolident cette hiérarchie. En effet, tous les algorithmes d'identification fournissent in fine des grammaires qui acceptent les données positives et rejettent les données négatives. Donc les grammaires peuvent être vues comme des sortes de classifieurs, et un algorithme d'Inférence Grammaticale comme un apprenant visant à résoudre un problème de classification. De même, le but de l'Inférence Grammaticale Stochastique est d'identifier des distributions de probabilité, et c'est une thématique qu'on retrouve également en Machine Learning. Ainsi, dans ce manuscrit, nous avons choisi d'étudier, à la lumière de nos travaux, les relations entre Inférence Grammaticale et Classification Supervisée.

Cette thèse propose une contribution en matière d'analyse de données, dans la perspective de systèmes informatiques distribués non-centralisés, pour le partage de données numériques. De tels systèmes se développent en particulier sur internet, possiblement à large échelle, mais aussi, par exemple, par des réseaux de capteurs. Notre objectif général est d'estimer la distribution de probabilité d'un jeu de données distribuées, à partir d'estimations locales de cette distribution, calculées sur des sous- jeux de données locaux. En d'autres termes, il s'est agi de proposer une technique pour agréger des estimés locaux pour en faire un estimé global. Notre proposition s'appuie sur la forme particulière que doivent prendre toutes les distributions de probabilité manipulées : elles doivent se formuler comme un mélange de lois gaussiennes multivariées. Notre contribution est une solution à la fois décentralisée et statistiquement robuste aux modèles locaux aberrants, pour mener à bien l'agrégation globale, à partir d'agrégations locales de mélanges de lois gaussiennes. Ces agrégations locales ne requièrent un accès qu'aux seuls paramètres des modèles de mélanges, et non aux données originales.

Ce travail de recherche entre dans le cadre de la conception pluridisciplinaire de systèmes techniques. Son contexte est le processus support à l'optimisation en conception organique suivant l'approche d'Ingénierie Système. La problématique est l'affectation des variables et le choix de composants en tenant compte des possibilités de couplage entre les disciplines et des objectifs multiples à satisfaire. L'objectif poursuivi est un apport méthodologique et outillé pour l'aide à l'optimisation multiobjectif et multidisciplinaire. La contribution comporte deux volets principaux. D'une part, deux méthodes de recherche basées sur les méta-heuristiques permettent de déterminer rapidement un ensemble des solutions efficaces. D'autre part, l'application de méthodes de discrimination fournit aux concepteurs une aide à l'interprétation des ensembles de solutions efficaces dégagés dans la phase d'optimisation. Ces propositions sont illustrées par deux exemples de conception en robotique.