La prévision de la profitabilité du client, ainsi que la tarification, sont des pièces centrales dans le monde des sciences actuarielles. En utilisant des données sur les historiques des clients et en optimisant des modèles statistiques, les actuaires peuvent prévoir, dans une certaine mesure, le montant qu’un client réclamera durant une certaine période. Cependant, ces modèles utilisent souvent des données sensibles reliées au client qui sont considérées comme étant des facteurs de risque très importants dans la prédiction de pertes futures. Ceci est considéré comme étant légal dans plusieurs jurisdictions tant que leur utilisation est supportée par des données actuarielles, car ces attributs permettent aux clients d’obtenir une prime plus précise. Toutefois, comme soulevé dans la littérature récente en apprentissage machine, ces modèles peuvent cacher des biais qui les rendent discriminants envers certains groupes. Dans ce mémoire, nous proposons un modèle de prévision de la profitabilité du client utilisant des avancées récentes provenant du domaine de l’apprentissage machine pour assurer que ces algorithmes ne discriminent pas disproportionnellement envers certains sous-groupes faisant partie de l’intersection de plusieurs attributs protégés, tel que l’âge, la race, la religion et l’état civil. En d’autres mots, nous prédisons équitablement la prime théorique de n’importe quel client en combinant l’état de l’art en prédiction de pertes en assurance et appliquant certaines contraintes d’équité sur des modèles de régression. Suite à l’exécution de l’estimation de la profitabilité du client sur plusieurs jeux de données réels, les résultats obtenus de l’approche proposée sont plus précis que les modèles utilisés traditionnellement pour cette tâche, tout en satisfaisant des contraintes d’équité. Ceci montre que cette méthode est viable et peut être utilisée dans des scénarios concrets pour offrir des primes précises et équitables aux clients. Additionnellement, notre modèle, ainsi que notre application de contraintes d’équité, s’adapte facilement à l’utilisation d’un grand jeu de données qui contiennent plusieurs sous-groupes. Ceci peut être considérable dans le cas où un critère d’équité intersectionnel doit être respecté. Finalement, nous notons les différences entre l’équité actuarielle et les définitions d’équité provenant du monde de l’apprentissage machine, ainsi que les compromis reliés à ceux-ci. / Customer profitability forecasting, along with ratemaking, are central pieces in the world of actuarial science. By using historical data and by optimising statistical models, actuaries can predict whether a client with certain liabilities will claim any loss and what amount will be claimed inside a defined policy period. However, these models often use sensitive attributesrelated to the customer that are considered to be crucial risk factors to consider in predicting future losses. This is considered legal in many jurisdictions, as long as their use is backedby actuarial data, as these attributes give a more accurate premium to clients. Nonetheless,as it has been noted in recent machine learning literature, models can hide biases that makethem discriminate against certain groups. In this thesis, we propose a customer profitability forecasting model that uses recent advancements in the domain of machine learning to ensurethat these algorithms do not discriminate disproportionately on a subgroup of any intersectionof protected attributes, such as age, gender, race, religion and marital status. In other words,we fairly predict the theoretical premium of any client by combining state-of-the-art methodsin insurance loss prediction and the application of fairness constraints on regression models. After performing customer profitability estimation on multiple real world datasets, it is shownthat the proposed approach outperforms traditional models usually used for this task, whilealso satisfying fairness constraints. This shows that this method is viable and can be used inreal world scenarios to offer fair and accurate premiums to clients. Additionally, our model andour application of fairness constraints scale easily when using large datasets that contain many subgroups. This can be substantial in the case of satisfying an intersectional fairness criterion.Finally, we highlight the differences between actuarial fairness and fairness definitions in theworld of machine learning, along with its related trade offs.

Les problèmes d’optimisation apparaissent dans presque tous les domaines scientifiques. Cependant, le processus laborieux de conception d’un optimiseur approprié peut demeurer infructueux. La question la plus ambitieuse de l’optimisation est peut-être de savoir comment concevoir des optimiseurs suffisamment flexibles pour s’adapter à un grand nombre de scénarios, tout en atteignant des performances de pointe. Dans ce travail, nous visons donner une réponse potentielle à cette question en étudiant comment faire un méta-apprentissage d’optimiseurs à base de population. Nous motivons et décrivons une modélisation commune pour la plupart des algorithmes basés sur la population, qui présentent des principes d’adaptation générale. Cette structure permet de dériver un cadre de méta-apprentissage basé sur un processus de décision de Markov partiellement observable (POMDP). Notre formulation conceptuelle fournit une méthodologie générale pour apprendre l’algorithme d’optimisation lui-même, présenté comme un problème de méta-apprentissage ou d’apprentissage pour optimiser à l’aide d’ensembles de données d’analyse comparative en boîte noire, pour former des optimiseurs polyvalents efficaces. Nous estimons une fonction d’apprentissage de méta-perte basée sur les performances d’algorithmes stochastiques. Notre analyse expérimentale indique que cette nouvelle fonction de méta-perte encourage l’algorithme appris à être efficace et robuste à une convergence prématurée. En outre, nous montrons que notre approche peut modifier le comportement de recherche d’un algorithme pour s’adapter facilement à un nouveau contexte et être efficace par rapport aux algorithmes de pointe, tels que CMA-ES. / Optimization problems appear in almost any scientific field. However, the laborious process to design a suitable optimizer may lead to an unsuccessful outcome. Perhaps the most ambitious question in optimization is how we can design optimizers that can be flexible enough to adapt to a vast number of scenarios while at the same time reaching state-of-the-art performance. In this work, we aim to give a potential answer to this question by investigating how to metalearn population-based optimizers. We motivate and describe a common structure for most population-based algorithms, which present principles for general adaptation. This structure can derive a meta-learning framework based on a Partially observable Markov decision process (POMDP). Our conceptual formulation provides a general methodology to learn the optimizer algorithm itself, framed as a meta-learning or learning-to-optimize problem using black-box benchmarking datasets to train efficient general-purpose optimizers. We estimate a meta-loss training function based on stochastic algorithms’ performance. Our experimental analysis indicates that this new meta-loss function encourages the learned algorithm to be sample efficient and robust to premature convergence. Besides, we show that our approach can alter an algorithm’s search behavior to fit easily in a new context and be sample efficient compared to state-of-the-art algorithms, such as CMA-ES.

L'apprentissage et la mémoire aux niveaux cellulaire et moléculaire se caractérisent par la modulation de la force synaptique en recrutant et relocalisant des protéines synaptiques à l'échelle nanométrique. La plupart des études portant sur les mécanismes de la plasticité synaptique se sont concentrées sur des synapses spécifiques, manquant ainsi d'une vue d'ensemble de la diversité des changements de force synaptique et de la réorganisation des protéines dans les circuits neuronaux. Nous utilisons une combinaison d'imagerie fonctionnelle et à super résolution dans des cultures dissociées d'hippocampe et des outils d'intelligence artificielle pour classifier la diversité de synapses en fonction de leurs caractéristiques fonctionnelles et organisationnelles. Nous avons mesuré l'activité synaptique en utilisant la microscopie à grand champ pour enregistrer des événements calciques dans des neurones exprimant le senseur calcique fluorescent GCaMP6f. Nous avons développé une approche d'apprentissage profond pour détecter et segmenter ces événements calciques. Nous montrons la modulation de l'amplitude et de la fréquence des événements calciques en fonction de l'activité neuronale. En outre, nous avons classifié les synapses actives et nous avons identifié un recrutement différentiel de certains types de synapses en fonction du paradigme de plasticité utilisé. Comme l'organisation des protéines synaptiques à l'intérieur de domaines nanométriques des synapses joue un rôle central dans la force et la plasticité synaptiques, nous résolvons l'organisation des protéines d'échafaudage présynaptiques (Bassoon, RIM1/2) et postsynaptiques (PSD95, Homer1c) en utilisant la nanoscopie STED (Déplétion par émission stimulée). Nous avons quantifié l'organisation synaptique à l'aide d'une analyse statistique de la distance entre objets basée sur Python (pySODA). Nous montrons que les stimuli induisant la plasticité modifient de manière différentielle l'organisation de ces protéines. En particulier, les protéines PSD95 et Bassoon présentent un changement d'organisation dépendant d'un traitement induisant une potentiation synaptique ou une dépression synaptique. De plus, à l'aide d'approches d'apprentissage automatique non supervisées, nous révélons la riche diversité des sous-types de protéines synaptiques présentant un remodelage différentiel. Pour étudier le lien entre l'architecture des protéines synaptiques et la force synaptique, nous avons combiné l'imagerie fonctionnelle et l'imagerie à super-résolution. Nous avons donc utilisé une approche d'apprentissage automatique pour optimiser les paramètres d'imagerie des cellules vivantes pour l'imagerie à haute résolution et nous avons combiné cela avec l'optimisation des paramètres de déblocage du glutamate pour sonder les signaux calciques correspondants. Notre approche permet de caractériser la population de synapses en fonction de leur taux d'activité et de leur organisation de protéines synaptiques et devrait fournir une base pour explorer davantage les divers mécanismes moléculaires de la plasticité synaptique. / Learning and memory at the cellular and molecular levels are characterized by modulation of synaptic strength, involving the recruitment and re-localization of proteins within specific nanoscale synaptic domains. Most studies investigating the mechanisms of synaptic plasticity have been focussed on specific synapses, lacking a broad view of the diversity of synaptic changes in strength and protein re-organization across neural circuits. We use a combination of functional and super-resolution optical imaging in dissociated hippocampal cultures and artificial intelligence tools to classify the diversity of synapses, based on their functional and organizational characteristics. We measured synaptic activity using wide field microscopy to record miniature synaptic calcium transients (MSCTs) in neurons expressing the fluorescent calcium sensor GCaMP6f. We developed a deep learning approach to detect and segment these calcium events. Our results show that the amplitude and frequency of miniature calcium events are modulated by prior levels of circuit activity. In addition, we classified active synapses and identify differential recruitment of certain calcium dynamics depending on the plasticity paradigm used. To link the nanoscale organization of synaptic proteins with synaptic strength and plasticity, we optically resolved the organization of presynaptic (Bassoon, RIM1/2) and postsynaptic (PSD95, Homer1c) scaffolding proteins using STED (Stimulated Emission Depletion) nanoscopy. Using Python-based statistical object distance analysis (pySODA), we show that plasticity-inducing stimuli differentially alter the spatial organization of these proteins. In particular, PSD95 and Bassoon proteins show a treatment-dependent change in organization, associated either with synaptic potentiation or depression. Furthermore, using unsupervised machine learning approaches, we reveal the rich diversity of synaptic protein subtypes exhibiting differential remodeling. To investigate further the link between synaptic protein architecture and synaptic function, we aimed to combine functional and super-resolution imaging. We therefore used a machine learning approach to optimize live-cell imaging parameters for time-lapse imaging and combined this with the optimization of glutamate uncaging parameters to probe corresponding calcium signals. Our approach allows to characterize the population of synapses in terms of their activity rate and synaptic protein organization, providing a basis for further exploring the diverse molecular mechanisms of synaptic plasticity.

Thèse ou mémoire avec insertion d’articles. / Les maladies cardiométaboliques affectent de nombreuses populations à l'échelle mondiale, notamment les populations autochtones qui résident dans le nord du Canada. Des travaux scientifiques récents suggèrent que ces maladies peuvent avoir été causées en partie par des perturbations du microbiote intestinal. Le profilage métabolique d'acides biliaires (AB) est un moyen reconnu pour analyser le microbiote. Cependant, ces analyses sont principalement effectuées a posteriori sur des échantillons fécaux et ne fournissent aucune information spatiale ou temporelle sur les variations métaboliques au sein du tractus gastro-intestinal. Le présent projet vise à développer une méthode de détection sélective aux AB basée sur la spectroscopie Raman exaltée en surface (SERS), une technique d'identification moléculaire. Les capteurs développés à partir de cette méthode permettront une étude en temps réel du microbiote avec une résolution spatiale et temporelle inégalée. La spectroscopie Raman est une technique d'identification moléculaire non invasive et non destructive qui produit un spectre hautement spécifique avec diverses bandes corrélées à la structure moléculaire de l'échantillon. Il est possible d'améliorer sa sensibilité de détection en utilisant une surface métallique nanostructurée amplificatrice de signal, ce qui permet de mesurer différentes espèces moléculaires dans des concentrations réduites et un temps de mesure relativement court. La combinaison du SERS avec des méthodes d'apprentissage machine permet dans certains cas d'augmenter davantage les capacités de détection et de classification. Afin de détecter les AB, un microscope confocal Raman à balayage laser a été construit en laboratoire. Des substrats actifs en SERS et sélectifs aux AB ont par la suite été développés en immobilisant des nanoétoiles d'or sur des lamelles de verre. Afin de réaliser une analyse approfondie avec des algorithmes d'apprentissage machine, une base de données spectrales a été conçue en mesurant plusieurs spectres SERS provenant d'AB individuelles ou de mélanges d'AB, et ce dans diverses matrices moléculaires. Un modèle du type « réseau de neurones convolutif » a été entraîné et jumelé à plusieurs techniques de traitement spectral et d'augmentation des données afin d'effectuer la classification de différentes espèces d'AB à partir de leur spectre. Le modèle résultant a été appliqué avec succès sur cinq espèces d'AB et validé à différentes concentrations. / Cardiometabolic diseases are affecting many populations worldwide, including indigenous populations residing in northern Canada. Recent scientific evidence suggests that these diseases may be caused in part by disorders of the gut microbiota. Bile acid (BA) metabolic profiling is a recognized method for analyzing the gut microbiota. However, these analyses are mostly performed on fecal samples and do not provide any spatial or temporal information on metabolic variations in the gastrointestinal tract. The present project aims to develop an AB-selective sensing method based on Surface Enhanced Raman Spectroscopy (SERS), a molecular identification technique. The resulting sensors will allow a real time study of the microbiota with an unmatched spatial and temporal resolution. Raman spectroscopy is a non-invasive and non-destructive molecular identification technique that produces a highly specific spectrum with various bands correlated to the molecular structure of the sample. Its detection sensitivity can be improved using a signal enhancing nanostructured metal surface, which allows the measurement of various chemical species at lower concentrations and/or shorter measurement times. Combining SERS with machine learning methods can, in some cases, increase even further detection and classification capabilities. In order to detect ABs, a confocal laser scanning Raman microscope was built in the laboratory. AB-selective SERS active substrates were developed by immobilizing gold nanostars on glass coverslips. In order to perform an extensive analysis with machine learning algorithms, a database of spectra was developed by measuring several SERS spectra from individual ABs or mixtures of ABs in various molecular matrices. A convolutional neural network model was trained and combined with several spectral processing and data augmentation techniques to perform classification of different BA species based on their spectra. The resulting model was successfully applied to five species of BA and validated at different concentrations.

L'industrie actuelle est en plein développement suite à la mise en œuvre du concept de l'industrie 4.0 visant à rendre l'usine une entité intelligente, en combinant les processus et pratiques industriels avec les technologies de l'information et de communication récentes comme les systèmes cyber-physiques et l'internet des objets connectés (IoT), entre autres. Ce développement industriel, ainsi que le besoin d'innover pour atteindre et maintenir la compétitivité favorisent une augmentation phénoménale du volume de données (connue sous le nom de Big Data), rendant ainsi (i) les processus de conception et de supervision des systèmes de plus en plus chaotiques, (ii) les données au sein des organisations de plus en plus difficiles à exploiter et (iii) les ingénieurs de plus en plus perdus lors de la prise de décision. En effet, plusieurs problèmes sont identifiés dans les milieux industriels et qui peuvent être classés en trois catégories : (i) difficultés lors de la recherche, la visualisation et l'échange de l'information, (ii) difficultés lors de la prise de décision et (iii) difficultés lors de la gestion des changements de contexte. A travers ce travail, nous proposons un système d'aide à la décision intelligent et modulaire, dont chacun des quatre modules résout un des problèmes identifiés. Les modules de modélisation et de traçabilité des processus permettent de modéliser les processus et de capturer la façon comment ils sont exécutés. Le module d'aide à la décision permet de proposer le pattern le plus adapté au contexte de la décision ainsi que les paramètres de ses activités les plus significatifs. Le module de gestion des changements contextuels permet de continuellement mettre à jour le module de prise de décision, lui permettant ainsi de tenir compte de l'aspect dynamique du contexte. Le système proposé est entièrement vérifié et à moitié validé dans le contexte du projet Gontrand, visant la supervision intelligente et en temps réel des réseaux de gaz favorisant l'injection du gaz vert. Pour qu'il soit entièrement validé, les performances du système doivent être analysées après l'intégration et l'exploitation de ce dernier dans un milieu industriel réel. / Data sets are growing rapidly because of two things. First, the fourth industrial revolution that aims to transform factories into smart entities in which cyber physical systems monitor the physical processes of the factory. Second, the need to innovate in order to achieve and maintain competitiveness. Due to this huge volume of data (Big Data), (i) design and supervision processes are becoming chaotic, (ii) data within organizations is increasingly becoming difficult to exploit and (iii) engineers are increasingly lost when making decisions. Indeed, several issues are identified in industry: (i) when researching, visualizing and exchanging information, (ii) when making decisions and (iii) when managing contextual changes. Through this research work, we propose an Intelligent and modular Decision Support System (IDSS), where each of the four modules solves one of the identified issues. Process modelling and traceability modules aim to model processes and capture how they are actualy executed. The decision support module proposes the process patterns that best fit the decision context, as well as their most significant activity parameters. The contextual change management module continuously updates the decision-making module, in order to handle the dynamic aspect of the decision context. The proposed system is fully verified and half-validated in the context of the Gontrand project, aiming at intelligent and real-time supervision of gas networks favoring the injection of green gas. In order to be fully validated, the performance of the system must be analyzed after integrating and exploitating it in a real industrial environment.

Le laboratoire DOMUS développe des applications pour assister les personnes en perte d'autonomie et les personnes avec des troubles cognitifs. Chaque application est ou a déjà été le sujet de plusieurs études d'utilisabilité qui permettent de les améliorer. Ces études prennent beaucoup de temps à mettre en place, car l'on rencontre souvent des problèmes de logistique (format et sensibilité des données, chercheurs répartis sur une grande aire géographique). C'est pourquoi un outil appelé GEDOPAL a été développé. Il permet de partager entre chercheurs de différents centres les données créées et utilisées lors de la mise en place des études d'utilisabilité. La conception et la réalisation de cet outil ont nécessité une réflexion en amont sur la nature et la sensibilité de ces données. Cette réflexion est l'objet du Chapitre 3. Ces études prennent aussi beaucoup de temps lors de l'analyse des résultats. De plus, certaines données créées lors de ces études, telles que les traces d'utilisation ont des volumétries trop importantes pour être analysées manuellement. C'est pourquoi nous avons créé un processus permettant d'analyser ces traces d'utilisation pour y détecter les erreurs utilisateurs dans l'espoir de les relier à des problèmes d'utilisabilité. Ce processus se compose de deux parties : la première est une analyse formelle de l'application, qui sera présentée au Chapitre 4, et la seconde l'application d'un outil d'apprentissage automatique aux traces d'utilisation pour y détecter les erreurs utilisateurs. Cet outil est présenté au Chapitre 5.

Dans cette thèse, nous explorons l'analyse syntaxique robuste statistique du français. Notre principal souci est de trouver des méthodes qui permettent au linguiste d'injecter des connaissances et/ou des ressources linguistiques dans un moteur statistique afin d'améliorer les résultats de certains phénomènes spécifiques. D'abord nous décrivons le schéma d'annotation en dépendances du français, et les algorithmes capables de produire cette annotation, en particulier le parsing par transitions. Après avoir exploré les algorithmes d'apprentissage automatique supervisé pour les problèmes de classification en TAL, nous présentons l'analyseur syntaxique Talismane développé dans le cadre de cette thèse et comprenant quatre modules statistiques – le découpage en phrases, la segmentation en mots, l'étiquetage morpho-syntaxique et le parsing – ainsi que les diverses ressources linguistiques utilisées par le modèle de base. Nos premières expériences tentent d'identifier la meilleure configuration de base parmi de nombreuses configurations possibles. Ensuite nous explorons les améliorations apportées par la recherche par faisceau et la propagation du faisceau. Enfin nous présentons une série d'expériences dont le but est de corriger des erreurs linguistiques spécifiques au moyen de traits ciblés. Une de nos innovations est l'introduction des règles qui imposent ou interdisent certaines décisions locales, permettant ainsi de contourner le modèle statistique. Nous explorons l'utilisation de règles pour les erreurs que les traits n'ont pu corriger. Finalement, nous présentons une expérience semi-supervisée avec une ressource de sémantique distributionnelle. / In this thesis we explore robust statistical syntax analysis for French. Our main concern is to explore methods whereby the linguist can inject linguistic knowledge and/or resources into the robust statistical engine in order to improve results for specific phenomena. We first explore the dependency annotation schema for French, concentrating on certain phenomena. Next, we look into the various algorithms capable of producing this annotation, and in particular on the transition-based parsing algorithm used in the rest of this thesis. After exploring supervised machine learning algorithms for NLP classification problems, we present the Talismane toolkit for syntax analysis, built within the framework of this thesis, including four statistical modules - sentence boundary detection, tokenisation, pos-tagging and parsing - as well as the various linguistic resources used for the baseline model, including corpora, lexicons and feature sets. Our first experiments attempt various machine learning configurations in order to identify the best baseline. We then look into improvements made possible by beam search and beam propagation. Finally, we present a series of experiments aimed at correcting errors related to specific linguistic phenomena, using targeted features. One our innovation is the introduction of rules that can impose or prohibit certain decisions locally, thus bypassing the statistical model. We explore the usage of rules for errors that the features are unable to correct. Finally, we look into the enhancement of targeted features by large scale linguistic resources, and in particular a semi-supervised approach using a distributional semantic resource.

De nombreuses applications informatiques nécessitent l’utilisation de distances. Dans le cadre de données structurées, chaînes ou arbres, nous utilisons majoritairement la distance d’édition. Celle-ci correspond au nombre minimal d’opérations d’édition (insertion, délétion et substitution) nécessaire pour transformer la première donnée en la seconde. Suivant l’application traitée, il est possible de paramétrer la distance d’édition en associant à chaque opération d’édition un poids. Dans le cadre de ce manuscrit, nous proposons une technique d’apprentissage automatique supervisée pour apprendre les poids de la distance décrite précédemment. L’algorithme utilisé, appelé Expectation-Maximisation, maximise la vraisemblance des paramètres du modèle à l’aide d’un échantillon d’apprentissage composé de paires d’exemples considérés comme similaires. La première contribution de ce manuscrit est une extension de précédents travaux sur les chaînes aux arbres sous la forme de transducteur à un unique état. Nous montrons sur une tâche de reconnaissance de caractères manuscrits, l’efficacité de l’apprentissage par rapport à l’utilisation de poids non appris. La seconde est une approche sur les chaînes sous contraintes. Le modèle est représenté par un ensemble fini d’états dans lequel les transitions sont contraintes. Une contrainte est représentée par un ensemble fini de fonctions booléennes définies sur la chaîne d’entrée et une de ses positions. Nous utilisons notre modèle pour aborder une application de recherche de sites de facteur de transcription dans des séquences génomiques / In computer science, a lot of applications use distances. In the context of structured data, strings or trees, we mainly use the edit distance. The edit distance is defined as the minimum number of edit operation (insertion, deletion and substitution) needed to transform one data into the other one. Given the application, it is possible to tune the edit distance by adding a weight to each edit operation. In this work, we use a supervised machine learning approach to learn the weight of edit operation. The exploited algorithm, called Expectation-Maximisation, is a method for finding maximum likelihood estimates of parameters in a model given a learning sample of pairs of similar examples. The first contribution is an extension of earlier works on string to trees. The model is represent by a transducer with a single state. We apply successfully our method on a handwritten character recognition task. In a last part, we introduce a new model on strings under constraints. The model is made of a finite set of states where the transitions are constrained. A constraint is a finite set of boolean functions defined over an input string and one of its position. We show the relevance of our approach on a molecular biology task. We consider the problem of detecting Transcription Factor Binding Site in DNA sequences

L'avantage principal des méthodes d'apprentissage non-paramétriques réside dans le fait que la nombre de degrés de libertés du modèle appris s'adapte automatiquement au nombre d'échantillons. Ces méthodes sont cependant limitées par le "fléau de la kernelisation": apprendre le modèle requière dans un premier temps de construire une matrice de similitude entre tous les échantillons. La complexité est alors quadratique en temps et espace, ce qui s'avère rapidement trop coûteux pour les jeux de données de grande dimension. Cependant, la dimension "effective" d'un jeu de donnée est bien souvent beaucoup plus petite que le nombre d'échantillons lui-même. Il est alors possible de substituer le jeu de donnée réel par un jeu de données de taille réduite (appelé "dictionnaire") composé exclusivement d'échantillons informatifs. Malheureusement, les méthodes avec garanties théoriques utilisant des dictionnaires comme "Ridge Leverage Score" (RLS) ont aussi une complexité quadratique. Dans cette thèse nous présentons une nouvelle méthode d'échantillonage RLS qui met à jour le dictionnaire séquentiellement en ne comparant chaque nouvel échantillon qu'avec le dictionnaire actuel, et non avec l'ensemble des échantillons passés. Nous montrons que la taille de tous les dictionnaires ainsi construits est de l'ordre de la dimension effective du jeu de données final, garantissant ainsi une complexité en temps et espace à chaque étape indépendante du nombre total d'échantillons. Cette méthode présente l’avantage de pouvoir être parallélisée. Enfin, nous montrons que de nombreux problèmes d'apprentissage non-paramétriques peuvent être résolus de manière approchée grâce à notre méthode. / The main advantage of non-parametric models is that the accuracy of the model (degrees of freedom) adapts to the number of samples. The main drawback is the so-called "curse of kernelization": to learn the model we must first compute a similarity matrix among all samples, which requires quadratic space and time and is unfeasible for large datasets. Nonetheless the underlying effective dimension (effective d.o.f.) of the dataset is often much smaller than its size, and we can replace the dataset with a subset (dictionary) of highly informative samples. Unfortunately, fast data-oblivious selection methods (e.g., uniform sampling) almost always discard useful information, while data-adaptive methods that provably construct an accurate dictionary, such as ridge leverage score (RLS) sampling, have a quadratic time/space cost. In this thesis we introduce a new single-pass streaming RLS sampling approach that sequentially construct the dictionary, where each step compares a new sample only with the current intermediate dictionary and not all past samples. We prove that the size of all intermediate dictionaries scales only with the effective dimension of the dataset, and therefore guarantee a per-step time and space complexity independent from the number of samples. This reduces the overall time required to construct provably accurate dictionaries from quadratic to near-linear, or even logarithmic when parallelized. Finally, for many non-parametric learning problems (e.g., K-PCA, graph SSL, online kernel learning) we we show that we can can use the generated dictionaries to compute approximate solutions in near-linear that are both provably accurate and empirically competitive.

Dans cette thèse, nous nous concentrons sur le codage du séjour d'hospitalisation en codes standards. Ce codage est une tâche médicale hautement sensible dans les hôpitaux français, nécessitant des détails minutieux et une haute précision, car le revenu de l'hôpital en dépend directement. L'encodage du séjour d'hospitalisation comprend l'encodage du diagnostic principal qui motive le séjour d'hospitalisation et d'autres diagnostics secondaires qui surviennent pendant le séjour. Nous proposons une analyse rétrospective mettant en oeuvre des méthodes d'apprentissage, sur la tâche d'encodage de certains diagnostics secondaires sélectionnés. Par conséquent, la base de données PMSI, une grande base de données médicales qui documente toutes les informations sur les séjours d'hospitalisation en France.} est analysée afin d'extraire à partir de séjours de patients hospitalisés antérieurement, des variables décisives (Features). Identifier ces variables permet de pronostiquer le codage d'un diagnostic secondaire difficile qui a eu lieu avec un diagnostic principal fréquent. Ainsi, à la fin d'une session de codage, nous proposons une aide pour les codeurs en proposant une liste des encodages pertinents ainsi que des variables utilisées pour prédire ces encodages. Les défis nécessitent une connaissance métier dans le domaine médical et une méthodologie d'exploitation efficace de la base de données médicales par les méthodes d'apprentissage automatique. En ce qui concerne le défi lié à la connaissance du domaine médical, nous collaborons avec des codeurs experts dans un hôpital local afin de fournir un aperçu expert sur certains diagnostics secondaires difficiles à coder et afin d'évaluer les résultats de la méthodologie proposée. En ce qui concerne le défi lié à l'exploitation des bases de données médicales par des méthodes d'apprentissage automatique, plus spécifiquement par des méthodes de "Feature Selection" (FS), nous nous concentrons sur la résolution de certains points : le format des bases de données médicales, le nombre de variables dans les bases de données médicales et les variables instables extraites des bases de données médicales. Nous proposons une série de transformations afin de rendre le format de la base de données médicales, en général sous forme de bases de données relationnelles, exploitable par toutes les méthodes de type FS. Pour limiter l'explosion du nombre de variables représentées dans la base de données médicales, généralement motivée par la quantité de diagnostics et d'actes médicaux, nous analysons l'impact d'un regroupement de ces variables dans un niveau de représentation approprié et nous choisissons le meilleur niveau de représentation. Enfin, les bases de données médicales sont souvent déséquilibrées à cause de la répartition inégale des exemples positifs et négatifs. / In the thesis we focus on encoding inpatient episode into standard codes, a highly sensitive medical task in French hospitals, requiring minute detail and accuracy, since the hospital's income directly depends on it. Encoding inpatient episode includes encoding the primary diagnosis that motivates the hospitalisation stay and other secondary diagnoses that occur during the stay. Unlike primary diagnosis, encoding secondary diagnoses is prone to human error, due to the difficulty of collecting relevant data from different medical sources, or to the outright absence of relevant data that helps encoding the diagnosis. We propose a retrospective analysis on the encoding task of some selected secondary diagnoses. Hence, the PMSI database is analysed in order to extract, from previously encoded inpatient episodes, the decisive features to encode a difficult secondary diagnosis occurred with frequent primary diagnosis. Consequently, at the end of an encoding session, once all the features are available, we propose to help the coders by proposing a list of relevant encodings as well as the features used to predict these encodings. Nonetheless, a set of challenges need to be addressed for the development of an efficient encoding help system. The challenges include, an expert knowledge in the medical domain and an efficient exploitation methodology of the medical database by Machine Learning methods. With respect to the medical domain knowledge challenge, we collaborate with expert coders in a local hospital in order to provide expert insight on some difficult secondary diagnoses to encode and in order to evaluate the results of the proposed methodology. With respect to the medical databases exploitation challenge, we use ML methods such as Feature Selection (FS), focusing on resolving several issues such as the incompatible format of the medical databases, the excessive number features of the medical databases in addition to the unstable features extracted from the medical databases. Regarding to issue of the incompatible format of the medical databases caused by relational databases, we propose a series of transformation in order to make the database and its features more exploitable by any FS methods. To limit the effect of the excessive number of features in the medical database, usually motivated by the amount of the diagnoses and the medical procedures, we propose to group the excessive number features into a proper representation level and to study the best representation level. Regarding to issue of unstable features extracted from medical databases, as the dataset linked with diagnoses are highly imbalanced due to classification categories that are unequally represented, most existing FS methods tend not to perform well on them even if sampling strategies are used. We propose a methodology to extract stable features by sampling the dataset multiple times and extracting the relevant features from each sampled dataset. Thus, we propose a methodology that resolves these issues and extracts stable set of features from medical database regardless to the sampling method and the FS method used in the methodology. Lastly, we evaluate the methodology by building a classification model that predicts the studied diagnoses out of the extracted features. The performance of the classification model indicates the quality of the extracted features, since good quality features produces good classification model. Two scales of PMSI database are used: local and regional scales. The classification model is built using the local scale of PMSI and tested out using both local and regional scales. Hence, we propose applying our methodology to increase the integrity of the encoded diagnoses and to prevent missing important encodings. We propose modifying the encoding process and providing the coders with the potential encodings of the secondary diagnoses as well as the features that lead to this encoding.