Search

The contributions of this thesis are divided into two parts. The first part is dedicated to the acceleration of kernel methods and the second to optimization under sparsity constraints. Kernel methods are widely known and used in machine learning. However, the complexity of their implementation is high and they become unusable when the number of data is large. We first propose an approximation of Ridge Leverage Scores. We then use these scores to define a probability distribution for the sampling process of the Nyström method in order to speed up the kernel methods. We then propose a new kernel-based framework for representing and comparing discrete probability distributions. We then exploit the link between our framework and the Maximum Mean Discrepancy to propose an accurate and cheap approximation of the latter. The second part of this thesis is devoted to optimization with sparsity constraint for signal optimization and random forest pruning. First, we prove under certain conditions on the coherence of the dictionary, the reconstruction and convergence properties of the Frank-Wolfe algorithm. Then, we use the OMP algorithm to reduce the size of random forests and thus reduce the size needed for its storage. The pruned forest consists of a subset of trees from the initial forest selected and weighted by OMP in order to minimize its empirical prediction error.; Les contributions de cette thèse se divisent en deux parties. Une première partie dédiée à l’accélération des méthodes à noyaux et une seconde à l’optimisation sous contrainte de parcimonie. Les méthodes à noyaux sont largement connues et utilisées en apprentissage automatique. Toutefois, la complexité de leur mise en œuvre est élevée et elles deviennent inutilisables lorsque le nombre de données est grand. Nous proposons dans un premier temps une approximation des Ridge Leverage Scores. Nous utilisons ensuite ces scores pour définir une distribution de probabilité pour le processus d’échantillonnage de la méthode de Nyström afin d’accélérer les méthodes à noyaux. Nous proposons dans un second temps un nouveau framework basé sur les noyaux, permettant de représenter et de comparer les distributions de probabilités discrètes. Nous exploitons ensuite le lien entre notre framework et la Maximum Mean Discrepancy pour proposer une approximation précise et peu coûteuse de cette dernière. La deuxième partie de cette thèse est consacrée à l’optimisation avec contrainte de parcimonie pour l’optimisation de signaux et l’élagage de forêts aléatoires. Tout d’abord, nous prouvons sous certaines conditions sur la cohérence du dictionnaire, les propriétés de reconstruction et de convergence de l’algorithme Frank-Wolfe. Ensuite, nous utilisons l’algorithme OMP pour réduire la taille de forêts aléatoires et ainsi réduire la taille nécessaire pour son stockage. La forêt élaguée est constituée d’un sous-ensemble d’arbres de la forêt initiale sélectionnés et pondérés par OMP de manière à minimiser son erreur empirique de prédiction.

Learning with limited data is one of the biggest problems of deep learning. Current, popular approaches to this issue consist in training models on huge amounts of data, labelled or not, before re-training the model on a smaller dataset of interest from the same modality. Intuitively, this technique allows the model to learn a general representation for some kind of data first, such as images. Then, fewer data should be required to learn a specific task for this particular modality. While this approach coined as "transfer learning" is very effective in domains such as computer vision or natural langage processing, it does not solve common problems of deep learning such as model interpretability or the overall need for data. This thesis explores a different answer to the problem of learning expressive models in data constrained settings. Instead of relying on big datasets to learn the parameters of a neural network, we will replace some of them by known functions reflecting the structure of the data. Very often, these functions will be drawn from the rich litterature of kernel methods. Indeed, many kernels can be interpreted, and/or allow for learning with few data. Our approach falls under thehood of "inductive biases", which can be defined as hypothesis on the data at hand restricting the space of models to explore during learning. In the first two chapters of the thesis, we demonstrate the effectiveness of this approach in the context of sequences, such as sentences in natural language or protein sequences, and graphs, such as molecules. We also highlight the relationship between our work and recent advances in deep learning. The last chapter of this thesis focuses on convex machine learning models. Here, rather than proposing new models, we wonder which proportion of the samples in a dataset is really needed to learn a "good" model. More precisely, we study the problem of safe sample screening, i.e, executing simple tests to discard uninformative samples from a dataset even before fitting a machine learning model, without affecting the optimal model. Such techniques can be used to compress datasets or mine for rare samples.; Apprendre à partir de données limitées est l’un des plus gros problèmes du deep learning. Les approches courantes et populaires de cette question consistent à entraîner un modèle sur d’énormes quantités de données, étiquetées ou non, avant de réentraîner le modèle sur un ensemble de données d’intérêt, plus petit, appartenant à la même modalité. Intuitivement, cette technique permet au modèle d’apprendre d’abord une représentation générale pour un certain type de données, telles que des images. Moins de données seront ensuite nécessaires pour apprendre une tâche spécifique pour cette modalité particulière. Bien que cette approche appelée « apprentissage par transfert » soit très efficace dans des domaines tels que la vision par ordinateur ou le traitement du langage naturel, elle ne résout pas les problèmes courants du deep learning tels que l’interprétabilité des modèles ou le besoin global en données. Cettethèse explore une réponse différente au problème de l’apprentissage de modèles expressifs dans des contextes où les données sont plus rares. Au lieu de s’appuyer sur de grands ensembles de données pour apprendre les paramètres d’un réseau de neurones, nous remplacerons certains de ces paramètres par des fonctions mathématiques connues reflétant la structure des données. Très souvent, ces fonctions seront puisées dans la riche littérature des méthodes à noyau. En effet, de nombreux noyaux peuvent être interprétés, et/ou permettre un apprentissage avec peu de données. Notre approche s’inscrit dans le cadre des « biais inductifs », qui peuvent être définis comme des hypothèses sur les données disponibles restreignant l’espace des modèles à explorer lors de l’apprentissage. Dans les deux premiers chapitres de la thèse, nous démontrons l’efficacité de cette approche dans le cadre de séquences, telles que des phrases en langage naturel ou des séquences protéiques, et de graphes, tels que des molécules. Nous soulignons également larelation entre notre travail et les progrès récents du deep learning. Le dernier chapitre de cette thèse se concentre sur les modèles d’apprentissage automatique convexes. Ici, plutôt que de proposer de nouveaux modèles, nous nous demandons quelle proportion des échantillons d’un jeu de données est vraiment nécessaire pour apprendre un « bon » modèle. Plus précisément, nous étudions le problème du filtrage sûr des échantillons, c’est-à-dire l’exécution de tests simples afin d’éliminer les échantillons non informatifs d’un ensemble de données avant même d’entraîner un modèle d’apprentissage automatique, sans affecter le modèle optimal. De telles techniques peuvent être utilisées pour compresser des jeux de données ou extraire des échantillons rares.

This manuscript focuses on Bayesian modeling of unknown functions with Gaussian processes. This task arises notably for industrial design, with numerical simulators whose computation time can reach several hours. Our work focuses on the problem of model selection and validation and goes in two directions. The first part studies empirically the current practices for stationary Gaussian process modeling. Several issues on Gaussian process parameter selection are tackled. A study of parameter selection criteria is the core of this part. It concludes that the choice of a family of models is more important than that of the selection criterion. More specifically, the study shows that the regularity parameter of the Matérn covariance function is more important than the choice of a likelihood or cross-validation criterion. Moreover, the analysis of the numerical results shows that this parameter can be selected satisfactorily by the criteria, which leads to a practical recommendation. Then, particular attention is given to the numerical optimization of the likelihood criterion. Observing important inconsistencies between the different libraries available for Gaussian process modeling like Erickson et al. (2018), we propose elementary numerical recipes making it possible to obtain significant gains both in terms of likelihood and model accuracy. Finally, the analytical formulas for computing cross-validation criteria are revisited under a new angle and enriched with similar formulas for the gradients. This last contribution aligns the computational cost of a class of cross-validation criteria with that of the likelihood. The second part presents a goal-oriented methodology. It is designed to improve the accuracy of the model in an (output) range of interest. This approach consists in relaxing the interpolation constraints on a relaxation range disjoint from the range of interest. We also propose an approach for automatically selecting the relaxation range. This new method can implicitly manage potentially complex regions of interest in the input space with few parameters. Outside, it learns non-parametrically a transformation improving the predictions on the range of interest. Numerical simulations show the benefits of the approach for Bayesian optimization, where one is interested in low values in the minimization framework. Moreover, the theoretical convergence of the method is established under some assumptions., Cette thèse s’inscrit dans la lignée de travaux portant sur la modélisation bayésienne de fonctions par processus gaussiens, pour des applications en conception industrielle s’appuyant sur des simulateurs numériques dont le temps de calcul peut atteindre jusqu’à plusieurs heures. Notre travail se concentre sur le problème de sélection et de validation de modèle et s’articule autour de deux axes. Le premier consiste à étudier empiriquement les pratiques courantes de modélisation par processus gaussien stationnaire. Plusieurs problèmes sur la sélection automatique de paramètre de processus gaussien sont considérés. Premièrement, une étude empirique des critères de sélection de paramètres constitue le coeur de cet axe de recherche et conclut que, pour améliorer la prédictivité des modèles, le choix d’un critère de sélection parmi les plus courants est un facteur de moindre importance que le choix a priori d’une famille de modèles. Plus spécifiquement, l’étude montre que le paramètre de régularité de la fonction de covariance de Matérn est plus déterminant que le choix d’un critère de vraisemblance ou de validation croisée. De plus, l’analyse des résultats numériques montre que ce paramètre peut-être sélectionné de manière satisfaisante par les critères, ce qui aboutit à une recommandation permettant d’améliorer les pratiques courantes. Ensuite, une attention particulière est réservée à l’optimisation numérique du critère de vraisemblance. Constatant, comme Erickson et al. (2018), des inconsistances importantes entre les différentes librairies disponibles pour la modélisation par processus gaussien, nous proposons une série de recettes numériques élémentaires permettant d’obtenir des gains significatifs tant en termes de vraisemblance que de précision du modèle. Enfin, les formules analytiques pour le calcul de critère de validation croisée sont revisitées sous un angle nouveau et enrichies de formules analogues pour les gradients. Cette dernière contribution permet d’aligner le coût calculatoire d’une classe de critères de validation croisée sur celui de la vraisemblance. Le second axe de recherche porte sur le développement de méthodes dépassant le cadre des modèles gaussiens stationnaires. Constatant l’absence de méthode ciblée dans la littérature, nous proposons une approche permettant d’améliorer la précision d’un modèle sur une plage d’intérêt en sortie. Cette approche consiste à relâcher les contraintes d’interpolation sur une plage de relaxation disjointe de la plage d’intérêt, tout en conservant un coût calculatoire raisonnable. Nous proposons également une approche pour la sélection automatique de la plage de relaxation en fonction de la plage d’intérêt. Cette nouvelle méthode permet de définir des régions d’intérêt potentiellement complexes dans l’espace d’entrée avec peu de paramètres et, en dehors, d’apprendre de manière non-paramétrique une transformation permettant d’améliorer la prédictivité du modèle sur la plage d’intérêt. Des simulations numériques montrent l’intérêt de la méthode pour l’optimisation bayésienne, où l’on est intéressé par les valeurs basses dans le cadre de la minimisation. De plus, la convergence théorique de la méthode est établie, sous certaines hypothèses.

Classification is the branch of supervised learning that aims at estimating a discrete valued mapping from data made of input-output pairs. The most classical and well studied setting is binary classification, where the discrete predictor takes zero or one as value. However, most of the practical classification settings deal with large structured output spaces such as sequences, grids, graphs, permutations, matchings, etc. There are many fundamental differences between structured prediction and vanilla binary or multi-class classification, such as the exponentially large size of the output space with respect to the natural dimension of the output objects and the cost-sensitive nature of the learning task. This thesis focuses on surrogate methods for structured prediction, whereby the typically intractable discrete problem is approached using a convex continuous surrogate problem which in turn can be addressed using techniques from regression.; La classification est la branche de l’apprentissage supervisé qui vise à estimer une fonction à valeurs discrètes à partir de données constituées de paires d’entrées et de sorties. Le cadre le plus classique et le plus étudié est celui de la classification binaire, où le prédicteur discret prend pour valeur zéro ou un. Cependant, la plupart des problèmes de classification qu’on retrouve en pratique sont definis sur de grands espaces de sortie structurés tels que des séquences, des grilles, des graphs, des permutations, etc. Il existe des différences fondamentales entre la prédiction structurée et la classification multiclasse ou binaire non structurée: la grandeur exponentielle de l’espace de sortie par rapport à la dimension naturelle des objets à prédire et la sensibilité des coûts de la tâche de classification. Cette thèse se concentre sur les méthodes de substitution pour la prédiction structurée, dans lesquelles le problème discret typiquement insoluble est abordé à l’aide d’un problème continu convexe qui, à son tour, peut être résolu à l’aide de techniques de régression.

Cette thèse aborde le processus ponctuel déterminantal, un modèle probabiliste qui capture la répulsion entre les points d’un certain espace. Celle-ci est déterminée par une matrice de similarité, la matrice noyau du processus, qui spécifie quels points sont les plus similaires et donc moins susceptibles de figurer dans un même sous-ensemble. Contrairement à la sélection aléatoire uniforme, ce processus ponctuel privilégie les sous-ensembles qui contiennent des points diversifiés et hétérogènes. La notion de diversité acquiert une importante grandissante au sein de sciences comme la médecine, la sociologie, les sciences forensiques et les sciences comportementales. Le processus ponctuel déterminantal offre donc une alternative aux traditionnelles méthodes d’échantillonnage en tenant compte de la diversité des éléments choisis. Actuellement, il est déjà très utilisé en apprentissage automatique comme modèle de sélection de sous-ensembles. Son application en statistique est illustrée par trois articles. Le premier article aborde le partitionnement de données effectué par un algorithme répété un grand nombre de fois sur les mêmes données, le partitionnement par consensus. On montre qu’en utilisant le processus ponctuel déterminantal pour sélectionner les points initiaux de l’algorithme, la partition de données finale a une qualité supérieure à celle que l’on obtient en sélectionnant les points de façon uniforme. Le deuxième article étend la méthodologie du premier article aux données ayant un grand nombre d’observations. Ce cas impose un effort computationnel additionnel, étant donné que la sélection de points par le processus ponctuel déterminantal passe par la décomposition spectrale de la matrice de similarité qui, dans ce cas-ci, est de grande taille. On présente deux approches différentes pour résoudre ce problème. On montre que les résultats obtenus par ces deux approches sont meilleurs que ceux obtenus avec un partitionnement de données basé sur une sélection uniforme de points. Le troisième article présente le problème de sélection de variables en régression linéaire et logistique face à un nombre élevé de covariables par une approche bayésienne. La sélection de variables est faite en recourant aux méthodes de Monte Carlo par chaînes de Markov, en utilisant l’algorithme de Metropolis-Hastings. On montre qu’en choisissant le processus ponctuel déterminantal comme loi a priori de l’espace des modèles, le sous-ensemble final de variables est meilleur que celui que l’on obtient avec une loi a priori uniforme., This thesis presents the determinantal point process, a probabilistic model that captures repulsion between points of a certain space. This repulsion is encompassed by a similarity matrix, the kernel matrix, which selects which points are more similar and then less likely to appear in the same subset. This point process gives more weight to subsets characterized by a larger diversity of its elements, which is not the case with the traditional uniform random sampling. Diversity has become a key concept in domains such as medicine, sociology, forensic sciences and behavioral sciences. The determinantal point process is considered a promising alternative to traditional sampling methods, since it takes into account the diversity of selected elements. It is already actively used in machine learning as a subset selection method. Its application in statistics is illustrated with three papers. The first paper presents the consensus clustering, which consists in running a clustering algorithm on the same data, a large number of times. To sample the initials points of the algorithm, we propose the determinantal point process as a sampling method instead of a uniform random sampling and show that the former option produces better clustering results. The second paper extends the methodology developed in the first paper to large-data. Such datasets impose a computational burden since sampling with the determinantal point process is based on the spectral decomposition of the large kernel matrix. We introduce two methods to deal with this issue. These methods also produce better clustering results than consensus clustering based on a uniform sampling of initial points. The third paper addresses the problem of variable selection for the linear model and the logistic regression, when the number of predictors is large. A Bayesian approach is adopted, using Markov Chain Monte Carlo methods with Metropolis-Hasting algorithm. We show that setting the determinantal point process as the prior distribution for the model space selects a better final model than the model selected by a uniform prior on the model space.

Developing efficient algorithms to learn appropriate representations of structured data, including sequences or graphs, is a major and central challenge in machine learning. To this end, deep learning has become popular in structured data modeling. Deep neural networks have drawn particular attention in various scientific fields such as computer vision, natural language understanding or biology. For instance, they provide computational tools for biologists to possibly understand and uncover biological properties or relationships among macromolecules within living organisms. However, most of the success of deep learning methods in these fields essentially relies on the guidance of empirical insights as well as huge amounts of annotated data. Exploiting more data-efficient models is necessary as labeled data is often scarce.Another line of research is kernel methods, which provide a systematic and principled approach for learning non-linear models from data of arbitrary structure. In addition to their simplicity, they exhibit a natural way to control regularization and thus to avoid overfitting.However, the data representations provided by traditional kernel methods are only defined by simply designed hand-crafted features, which makes them perform worse than neural networks when enough labeled data are available. More complex kernels inspired by prior knowledge used in neural networks have thus been developed to build richer representations and thus bridge this gap. Yet, they are less scalable. By contrast, neural networks are able to learn a compact representation for a specific learning task, which allows them to retain the expressivity of the representation while scaling to large sample size.Incorporating complementary views of kernel methods and deep neural networks to build new frameworks is therefore useful to benefit from both worlds.In this thesis, we build a general kernel-based framework for modeling structured data by leveraging prior knowledge from classical kernel methods and deep networks. Our framework provides efficient algorithmic tools for learning representations without annotations as well as for learning more compact representations in a task-driven way. Our framework can be used to efficiently model sequences and graphs with simple interpretation of predictions. It also offers new insights about designing more expressive kernels and neural networks for sequences and graphs.; Le développement d'algorithmes efficaces pour apprendre des représentations appropriées des données structurées, telles des sequences ou des graphes, est un défi majeur et central de l'apprentissage automatique. Pour atteindre cet objectif, l'apprentissage profond est devenu populaire pour modéliser des données structurées. Les réseaux de neurones profonds ont attiré une attention particulière dans divers domaines scientifiques tels que la vision par ordinateur, la compréhension du langage naturel ou la biologie. Par exemple, ils fournissent aux biologistes des outils de calcul qui leur permettent de comprendre et de découvrir les propriétés biologiques ou les relations entre les macromolécules des organismes vivants. Toutefois, leur succès dans ces domaines repose essentiellement sur des connaissances empiriques ainsi que d'énormes quantités de données annotées. Exploiter des modèles plus efficaces est nécessaire car les données annotées sont souvent rares.Un autre axe de recherche est celui des méthodes à noyaux, qui fournissent une approche systématique et fondée sur des principes théoriquement solides pour l'apprentissage de modèles non linéaires à partir de données de structure arbitraire. Outre leur simplicité, elles présentent une manière naturelle de contrôler la régularisation et ainsi d'éviter le surapprentissage.Cependant, les représentations de données fournies par les méthodes à noyaux ne sont définies que par des caractéristiques artisanales simplement conçues, ce qui les rend moins performantes que les réseaux de neurones lorsque suffisamment de données étiquetées sont disponibles. Des noyaux plus complexes, inspirés des connaissances préalables utilisées dans les réseaux de neurones, ont ainsi été développés pour construire des représentations plus riches et ainsi combler cette lacune. Pourtant, ils sont moins adaptatifs. Par comparaison, les réseaux de neurones sont capables d'apprendre une représentation compacte pour une tâche d'apprentissage spécifique, ce qui leur permet de conserver l'expressivité de la représentation tout en s'adaptant à une grande taille d'échantillon.Il est donc utile d'intégrer les vues complémentaires des méthodes à noyaux et des réseaux de neurones profonds pour construire de nouveaux cadres afin de bénéficier du meilleur des deux mondes.Dans cette thèse, nous construisons un cadre général basé sur les noyaux pour la modélisation des données structurées en tirant parti des connaissances préalables des méthodes à noyaux classiques et des réseaux profonds. Notre cadre fournit des outils algorithmiques efficaces pour l'apprentissage de représentations sans annotations ainsi que pour l'apprentissage de représentations plus compactes de manière supervisée par les tâches. Notre cadre peut être utilisé pour modéliser efficacement des séquences et des graphes avec une interprétation simple. Il offre également de nouvelles perspectives sur la construction des noyaux et de réseaux de neurones plus expressifs pour les séquences et les graphes.

Geometric data analysis, beyond convolutionsTo model interactions between points, a simple option is to rely on weighted sums known as convolutions. Over the last decade, this operation has become a building block for deep learning architectures with an impact on many applied fields. We should not forget, however, that the convolution product is far from being the be-all and end-all of computational mathematics.To let researchers explore new directions, we present robust, efficient and principled implementations of three underrated operations: 1. Generic manipulations of distance-like matrices, including kernel matrix-vector products and nearest-neighbor searches.2. Optimal transport, which generalizes sorting to spaces of dimension D > 1.3. Hamiltonian geodesic shooting, which replaces linear interpolation when no relevant algebraic structure can be defined on a metric space of features.Our PyTorch/NumPy routines fully support automatic differentiation and scale up to millions of samples in seconds. They generally outperform baseline GPU implementations with x10 to x1,000 speed-ups and keep linear instead of quadratic memory footprints. These new tools are packaged in the KeOps (kernel methods) and GeomLoss (optimal transport) libraries, with applications that range from machine learning to medical imaging. Documentation is available at: www.kernel-operations.io/keops and /geomloss.; Analyse de données géométriques, au delà des convolutionsPour modéliser des interactions entre points, une méthode simple est de se reposer sur des sommes pondérées communément appelées "convolutions". Au cours de la dernière décennie, cette opération est devenue la brique de construction essentielle à la révolution du "deep learning". Le produit de convolution est, toutefois, loin d'être l'alpha et l'oméga des mathématiques appliquées.Pour permettre aux chercheurs d'explorer de nouvelles directions, nous présentons des implémentations robustes et efficaces de trois opérations souvent sous-estimées:1. Les manipulations de tenseurs semi-symboliques, comme les matrices de distances ou de noyaux.2. Le transport optimal, qui généralise la notion de "tri" aux espaces de dimension D > 1.3. Le tir géodésique sur une variété Riemannienne, qui se substitue à l'interpolation linéaire sur des espaces de données où aucune structure vectorielle ne peut être correctement définie.Nos routines PyTorch/NumPy sont compatibles avec la différentiation automatique, et s'exécutent en quelques secondes sur des nuages de plusieurs millions de points. Elle sont de 10 à 1,000 fois plus performantes que des implémentations GPU standards et conservent une empreinte mémoire linéaire. Ces nouveaux outils sont empaquetés dans les bibliothèques "KeOps" et "GeomLoss", avec des applications qui vont de l'apprentissage automatique à l'imagerie médicale. Notre documentation est accessible aux adresses www.kernel-operations.io/keops et /geomloss.

My research focuses on the development of machine learning tools for therapeutic research. In particular, my goal is to propose computational tools that can exploit data sets to extract biological hypotheses that explain, at a genomic or molecular level, the differences between samples that can be observed at a macroscopic scale. Such tools are necessary to the development of precision medicine, which requires identifying the characteristics, genomic or otherwise, that explain the differences in prognostic or therapeutic response between patients who exhibit the same symptoms. These questions can often be formulated as feature selection problems. However, the typical data sets contain many more features than samples, which poses statistical challenges. To address these challenges, my work is organized in three axes. First, knowledge accumulated on biological system can often be represented as biological networks. Under the hypothesis that features connected on these networks are likely to work together towards a phenotype, we propose to use biological networks to guide feature selection algorithms. The idea here is to define constraints that encourage the selected features to be connected on a given network. The formulation we proposed, which can be seen as a special case of what I call regularized relevance, allows us to efficiently select features on data sets containing hundreds of thousands of variables.Second, to compensate the small number of available samples, so-called multitask methods solve several related problems, or tasks, simultaneously. We have generalized regularized relevance to this context. I have also worked on the case where one can define a similarity between tasks, to impose that the more similar two tasks are, the more the two sets of features that are selected for them are. Such approaches can be used to study the response to different drug treatments: one can then used the similarity between the molecular structures of the drugs, a topic I have studied in the course of my PhD.Finally, most feature selection methods used in genomics can only explain the phenomenon of interest by linear effects. However, a large body of literature indicates that regions of the genome can interact nonlinearly. Modeling such interactions, which are called epistatic, exacerbate the aforementioned statistical challenges, and creates computational issues: evaluating all possible combinations of variables becomes intractable. My work in this domain addresses these computational issues, as well as the statistical challenges one encounters when modeling quadratic interactions between pairs of regions of the genome. More recently, we have also developed approaches that allow to model more complex interactions thanks to kernel methods.; Mes travaux de recherche s’inscrivent dans le cadre du développement de techniques d’apprentissage statistique (« machine learning ») pour la recherche thérapeutique. Ils visent en particulier à proposer des outils informatiques permettant d’exploiter des jeux de données pour en extraire des hypothèses biologiques expliquant au niveau génomique ou moléculaire les différences entre échantillons observées à un niveau macroscopique. De tels outils sont nécessaires à la mise en œuvre de la médecine de précision, qui requiert d’identifier les caractéristiques, génomiques ou autres, expliquant les différences de pronostic ou de réponse thérapeutique entre patients présentant les mêmes symptômes. Ces questions peuvent souvent être formulées comme des problèmes de sélection de variables. Les jeux de données utilisés, cependant, contiennent généralement largement plus de variables que d’échantillons, ce qui pose des difficultés statistiques. Pour répondre à ces défis, mes travaux s’orientent autour de trois axes. Premièrement, les connaissances accumulées sur les systèmes biologiques peuvent souvent être représentées sous la forme de réseaux biologiques. Sous l’hypothèse que les variables connectées par ces réseaux sont susceptibles d’agir conjointement sur un phénotype, nous proposons d’utiliser ces réseaux pour guider un algorithme de sélection de variables. Il s’agit ici d’utiliser des contraintes qui encouragent les variables sélectionnées à être connectées sur un réseau donné. La formulation que nous avons proposée, qui s’inscrit dans le cadre plus large de ce que j’appelle la pertinence régularisée, permet de résoudre efficacement le problème de sélection de variables sur des jeux de données comportant des centaines de milliers de variables. Deuxièmement, pour compenser le faible nombre d’échantillons disponibles, les méthodes dites multitâches résolvent simultanément plusieurs problèmes, ou tâches, proches. Nous avons étendu la pertinence régularisée à ce contexte. Je me suis aussi intéressée au cas où il est possible de définir une similarité entre tâches, afin d’imposer que les variables sélectionnées pour deux tâches soient d’autant plus similaires que les deux tâches sont semblables. Ces approches sont pertinentes dans le cas de l’étude de la réponse à différents traitements médicamenteux : on peut alors utiliser la similarité entre les structures moléculaires de ces médicaments, sujet que j’ai étudié pendant ma thèse. Enfin, la plupart des approches de sélection de variables utilisées dans le contexte de la génomique ne peuvent expliquer le phénomène d’intérêt que par des effets linéaires. Cependant, de nombreux travaux indiquent que les régions du génome peuvent interagir de façon non-linéaire. Modéliser de telles interactions, que l’on qualifie d’épistatiques, aggrave cependant les problèmes statistiques déjà rencontrés précédemment, et crée aussi des problèmes computationnels : il devient difficile d’évaluer toutes les combinaisons possibles de variables. Mes travaux portent aussi bien sur les difficultés calculatoires que sur les difficultés statistiques rencontrées dans la modélisation d’interactions quadratiques entre paires de régions du génomes. Plus récemment, nous avons aussi développé des approches permettant la modélisation d’interactions plus complexes grâce à des méthodes à noyaux

My research focuses on the development of machine learning tools for therapeutic research. In particular, my goal is to propose computational tools that can exploit data sets to extract biological hypotheses that explain, at a genomic or molecular level, the differences between samples that can be observed at a macroscopic scale. Such tools are necessary to the development of precision medicine, which requires identifying the characteristics, genomic or otherwise, that explain the differences in prognostic or therapeutic response between patients who exhibit the same symptoms. These questions can often be formulated as feature selection problems. However, the typical data sets contain many more features than samples, which poses statistical challenges. To address these challenges, my work is organized in three axes. First, knowledge accumulated on biological system can often be represented as biological networks. Under the hypothesis that features connected on these networks are likely to work together towards a phenotype, we propose to use biological networks to guide feature selection algorithms. The idea here is to define constraints that encourage the selected features to be connected on a given network. The formulation we proposed, which can be seen as a special case of what I call regularized relevance, allows us to efficiently select features on data sets containing hundreds of thousands of variables.Second, to compensate the small number of available samples, so-called multitask methods solve several related problems, or tasks, simultaneously. We have generalized regularized relevance to this context. I have also worked on the case where one can define a similarity between tasks, to impose that the more similar two tasks are, the more the two sets of features that are selected for them are. Such approaches can be used to study the response to different drug treatments: one can then used the similarity between the molecular structures of the drugs, a topic I have studied in the course of my PhD.Finally, most feature selection methods used in genomics can only explain the phenomenon of interest by linear effects. However, a large body of literature indicates that regions of the genome can interact nonlinearly. Modeling such interactions, which are called epistatic, exacerbate the aforementioned statistical challenges, and creates computational issues: evaluating all possible combinations of variables becomes intractable. My work in this domain addresses these computational issues, as well as the statistical challenges one encounters when modeling quadratic interactions between pairs of regions of the genome. More recently, we have also developed approaches that allow to model more complex interactions thanks to kernel methods.; Mes travaux de recherche s’inscrivent dans le cadre du développement de techniques d’apprentissage statistique (« machine learning ») pour la recherche thérapeutique. Ils visent en particulier à proposer des outils informatiques permettant d’exploiter des jeux de données pour en extraire des hypothèses biologiques expliquant au niveau génomique ou moléculaire les différences entre échantillons observées à un niveau macroscopique. De tels outils sont nécessaires à la mise en œuvre de la médecine de précision, qui requiert d’identifier les caractéristiques, génomiques ou autres, expliquant les différences de pronostic ou de réponse thérapeutique entre patients présentant les mêmes symptômes. Ces questions peuvent souvent être formulées comme des problèmes de sélection de variables. Les jeux de données utilisés, cependant, contiennent généralement largement plus de variables que d’échantillons, ce qui pose des difficultés statistiques. Pour répondre à ces défis, mes travaux s’orientent autour de trois axes. Premièrement, les connaissances accumulées sur les systèmes biologiques peuvent souvent être représentées sous la forme de réseaux biologiques. Sous l’hypothèse que les variables connectées par ces réseaux sont susceptibles d’agir conjointement sur un phénotype, nous proposons d’utiliser ces réseaux pour guider un algorithme de sélection de variables. Il s’agit ici d’utiliser des contraintes qui encouragent les variables sélectionnées à être connectées sur un réseau donné. La formulation que nous avons proposée, qui s’inscrit dans le cadre plus large de ce que j’appelle la pertinence régularisée, permet de résoudre efficacement le problème de sélection de variables sur des jeux de données comportant des centaines de milliers de variables. Deuxièmement, pour compenser le faible nombre d’échantillons disponibles, les méthodes dites multitâches résolvent simultanément plusieurs problèmes, ou tâches, proches. Nous avons étendu la pertinence régularisée à ce contexte. Je me suis aussi intéressée au cas où il est possible de définir une similarité entre tâches, afin d’imposer que les variables sélectionnées pour deux tâches soient d’autant plus similaires que les deux tâches sont semblables. Ces approches sont pertinentes dans le cas de l’étude de la réponse à différents traitements médicamenteux : on peut alors utiliser la similarité entre les structures moléculaires de ces médicaments, sujet que j’ai étudié pendant ma thèse. Enfin, la plupart des approches de sélection de variables utilisées dans le contexte de la génomique ne peuvent expliquer le phénomène d’intérêt que par des effets linéaires. Cependant, de nombreux travaux indiquent que les régions du génome peuvent interagir de façon non-linéaire. Modéliser de telles interactions, que l’on qualifie d’épistatiques, aggrave cependant les problèmes statistiques déjà rencontrés précédemment, et crée aussi des problèmes computationnels : il devient difficile d’évaluer toutes les combinaisons possibles de variables. Mes travaux portent aussi bien sur les difficultés calculatoires que sur les difficultés statistiques rencontrées dans la modélisation d’interactions quadratiques entre paires de régions du génomes. Plus récemment, nous avons aussi développé des approches permettant la modélisation d’interactions plus complexes grâce à des méthodes à noyaux

Geometric data analysis, beyond convolutionsTo model interactions between points, a simple option is to rely on weighted sums known as convolutions. Over the last decade, this operation has become a building block for deep learning architectures with an impact on many applied fields. We should not forget, however, that the convolution product is far from being the be-all and end-all of computational mathematics.To let researchers explore new directions, we present robust, efficient and principled implementations of three underrated operations: 1. Generic manipulations of distance-like matrices, including kernel matrix-vector products and nearest-neighbor searches.2. Optimal transport, which generalizes sorting to spaces of dimension D > 1.3. Hamiltonian geodesic shooting, which replaces linear interpolation when no relevant algebraic structure can be defined on a metric space of features.Our PyTorch/NumPy routines fully support automatic differentiation and scale up to millions of samples in seconds. They generally outperform baseline GPU implementations with x10 to x1,000 speed-ups and keep linear instead of quadratic memory footprints. These new tools are packaged in the KeOps (kernel methods) and GeomLoss (optimal transport) libraries, with applications that range from machine learning to medical imaging. Documentation is available at: www.kernel-operations.io/keops and /geomloss., Analyse de données géométriques, au delà des convolutionsPour modéliser des interactions entre points, une méthode simple est de se reposer sur des sommes pondérées communément appelées "convolutions". Au cours de la dernière décennie, cette opération est devenue la brique de construction essentielle à la révolution du "deep learning". Le produit de convolution est, toutefois, loin d'être l'alpha et l'oméga des mathématiques appliquées.Pour permettre aux chercheurs d'explorer de nouvelles directions, nous présentons des implémentations robustes et efficaces de trois opérations souvent sous-estimées:1. Les manipulations de tenseurs semi-symboliques, comme les matrices de distances ou de noyaux.2. Le transport optimal, qui généralise la notion de "tri" aux espaces de dimension D > 1.3. Le tir géodésique sur une variété Riemannienne, qui se substitue à l'interpolation linéaire sur des espaces de données où aucune structure vectorielle ne peut être correctement définie.Nos routines PyTorch/NumPy sont compatibles avec la différentiation automatique, et s'exécutent en quelques secondes sur des nuages de plusieurs millions de points. Elle sont de 10 à 1,000 fois plus performantes que des implémentations GPU standards et conservent une empreinte mémoire linéaire. Ces nouveaux outils sont empaquetés dans les bibliothèques "KeOps" et "GeomLoss", avec des applications qui vont de l'apprentissage automatique à l'imagerie médicale. Notre documentation est accessible aux adresses www.kernel-operations.io/keops et /geomloss.

In this thesis, the diagnosis of a nonlinear system was performed using data analysis. Initially developed to analyze linear system, Principal Component Analysis (PCA) is coupled with kernel methods for detection, isolation and estimation of faults' magnitude for nonlinear systems. Kernel PCA consists in projecting data using a nonlinear mapping function into a higher dimensional space called feature space where the linear PCA is applied. Due to the fact that the projections are done using kernels, the detection can be performed in the feature space. However, estimating the magnitude of the fault requires the resolution of a nonlinear optimization problem. The variables' contributions make it possible to isolate and estimate these magnitudes. The variable with the largest contribution may be considered as faulty. In our work, we proposed new methods for the isolation and estimation phases for which previous work has some limitations. The new proposed method in this thesis is based on contributions under constraints. The effectiveness of the developed methods is illustrated on the simulated continuous stirred tank reactor (CSTR)., Dans cette thèse, le diagnostic d'un système non linéaire a été réalisé par une analyse de données. Initialement conçue pour analyser les données liées par des relations linéaires, l'Analyse en Composantes Principales (ACP) est couplée aux méthodes à noyau pour détecter, localiser et estimer l'amplitude des défauts sur des systèmes non linéaires. L'ACP à noyau consiste à projeter les données par l'intermédiaire d'une application non linéaire dans un espace de dimension élevée dénommé espace des caractéristiques où l'ACP linéaire est appliquée. Ayant fait la projection à l'aide de noyaux, la détection peut facilement être réalisée dans l'espace des caractéristiques. Cependant, l'estimation de l'amplitude du défaut nécessite la résolution d'un problème d'optimisation non linéaire. Une étude de contributions permet de localiser et d'estimer ces amplitudes. La variable ayant la plus grande contribution est susceptible d'être affectée par un défaut. Dans notre travail, nous avons proposé de nouvelles méthodes pour les phases de localisation et d'estimation des défauts pour lesquelles les travaux existants ont des limites. La nouvelle méthode proposée est basée sur les contributions sous contraintes permettant d'obtenir une reconstruction parcimonieuse des variables. L'efficacité des méthodes proposées est montrée sur un réacteur à agitation continue (CSTR).

In this article we tackle the supervised multi-view learning problem with kernel methods and metric learning. In this context we consider a recently developed multi-view metric learning (MVML) framework, and propose a SVM-based algorithm that jointly learns the classifier and metrics between views. These metrics permit taking into account the multi-view characteristics of the learning problem. Experiments on real data were performed to evaluate the performance of the proposed algorithm., Cet article s’intéresse a l'apprentissage multi-vue par des méthodes à noyaux et d'apprentissage de métriques. Dans ce cadre, nous considérons MVML (multi-view metric learning), une méthode récemment développée, et nous proposons un algorithme basé sur les séparateurs à vaste marge (SVM) qui apprend conjointement un classifieur et des métriques entre les vues permettant ainsi de tenir compte des caractéristiques multi-vues du problème d'apprentissage. Des expérimentations sur données réelles ont été réalisées afin d'évaluer les performances de l'algorithme proposé.

In the context of supervised Machine Learning, finding alternate representations, or descriptors, for data is of primary interest since it can greatly enhance the performance of algorithms. Among them, topological descriptors focus on and encode the topological information contained in geometric data. One advantage of using these descriptors is that they enjoy many good and desireable properties, due to their topological nature. For instance, they are invariant to continuous deformations of data. However, the main drawback of these descriptors is that they often lack the structure and operations required by most Machine Learning algorithms, such as a means or scalar products. In this thesis, we study the metric and statistical properties of the most common topological descriptors, the persistence diagrams and the Mappers. In particular, we show that the Mapper, which is empirically instable, can be stabilized with an appropriate metric, that we use later on to conpute confidence regions and automatic tuning of its parameters. Concerning persistence diagrams, we show that scalar products can be defined with kernel methods by defining two kernels, or embeddings, into finite and infinite dimensional Hilbert spaces.; Dans le cadre de l'apprentissage automatique, l'utilisation de représentations alternatives, ou descripteurs, pour les données est un problème fondamental permettant d'améliorer sensiblement les résultats des algorithmes. Parmi eux, les descripteurs topologiques calculent et encodent l'information de nature topologique contenue dans les données géométriques. Ils ont pour avantage de bénéficier de nombreuses bonnes propriétés issues de la topologie, et désirables en pratique, comme par exemple leur invariance aux déformations continues des données. En revanche, la structure et les opérations nécessaires à de nombreuses méthodes d'apprentissage, comme les moyennes ou les produits scalaires, sont souvent absents de l'espace de ces descripteurs. Dans cette thèse, nous étudions en détail les propriétés métriques et statistiques des descripteurs topologiques les plus fréquents, à savoir les diagrammes de persistance et Mapper. En particulier, nous montrons que le Mapper, qui est empiriquement un descripteur instable, peut être stabilisé avec une métrique appropriée, que l'on utilise ensuite pour calculer des régions de confiance et pour régler automatiquement ses paramètres. En ce qui concerne les diagrammes de persistance, nous montrons que des produits scalaires peuvent être utilisés via des méthodes à noyaux, en définissant deux noyaux, ou plongements, dans des espaces de Hilbert en dimension finie et infinie.

In the context of supervised Machine Learning, finding alternate representations, or descriptors, for data is of primary interest since it can greatly enhance the performance of algorithms. Among them, topological descriptors focus on and encode the topological information contained in geometric data. One advantage of using these descriptors is that they enjoy many good and desireable properties, due to their topological nature. For instance, they are invariant to continuous deformations of data. However, the main drawback of these descriptors is that they often lack the structure and operations required by most Machine Learning algorithms, such as a means or scalar products. In this thesis, we study the metric and statistical properties of the most common topological descriptors, the persistence diagrams and the Mappers. In particular, we show that the Mapper, which is empirically instable, can be stabilized with an appropriate metric, that we use later on to conpute confidence regions and automatic tuning of its parameters. Concerning persistence diagrams, we show that scalar products can be defined with kernel methods by defining two kernels, or embeddings, into finite and infinite dimensional Hilbert spaces.; Dans le cadre de l'apprentissage automatique, l'utilisation de représentations alternatives, ou descripteurs, pour les données est un problème fondamental permettant d'améliorer sensiblement les résultats des algorithmes. Parmi eux, les descripteurs topologiques calculent et encodent l'information de nature topologique contenue dans les données géométriques. Ils ont pour avantage de bénéficier de nombreuses bonnes propriétés issues de la topologie, et désirables en pratique, comme par exemple leur invariance aux déformations continues des données. En revanche, la structure et les opérations nécessaires à de nombreuses méthodes d'apprentissage, comme les moyennes ou les produits scalaires, sont souvent absents de l'espace de ces descripteurs. Dans cette thèse, nous étudions en détail les propriétés métriques et statistiques des descripteurs topologiques les plus fréquents, à savoir les diagrammes de persistance et Mapper. En particulier, nous montrons que le Mapper, qui est empiriquement un descripteur instable, peut être stabilisé avec une métrique appropriée, que l'on utilise ensuite pour calculer des régions de confiance et pour régler automatiquement ses paramètres. En ce qui concerne les diagrammes de persistance, nous montrons que des produits scalaires peuvent être utilisés via des méthodes à noyaux, en définissant deux noyaux, ou plongements, dans des espaces de Hilbert en dimension finie et infinie.

In this thesis, we focus on a method for detecting abrupt changes in a sequence of independent observations belonging to an arbitrary set on which a positive semidefinite kernel is defined. That method, kernel changepoint detection, is a kernelized version of a penalized least-squares procedure. Our main contribution is to show that, for any kernel satisfying some reasonably mild hypotheses, this procedure outputs a segmentation close to the true segmentation with high probability. This result is obtained under a bounded assumption on the kernel for a linear penalty and for another penalty function, coming from model selection.The proofs rely on a concentration result for bounded random variables in Hilbert spaces and we prove a less powerful result under relaxed hypotheses—a finite variance assumption. In the asymptotic setting, we show that we recover the minimax rate for the change-point locations without additional hypothesis on the segment sizes. We provide empirical evidence supporting these claims. Another contribution of this thesis is the detailed presentation of the different notions of distances between segmentations. Additionally, we prove a result showing these different notions coincide for sufficiently close segmentations.From a practical point of view, we demonstrate how the so-called dimension jump heuristic can be a reasonable choice of penalty constant when using kernel changepoint detection with a linear penalty. We also show how a key quantity depending on the kernelthat appears in our theoretical results influences the performance of kernel change-point detection in the case of a single change-point. When the kernel is translationinvariant and parametric assumptions are made, it is possible to compute this quantity in closed-form. Thanks to these computations, some of them novel, we are able to study precisely the behavior of the maximal penalty constant. Finally, we study the median heuristic, a popular tool to set the bandwidth of radial basis function kernels. Fora large sample size, we show that it behaves approximately as the median of a distribution that we describe completely in the setting of kernel two-sample test and kernel change-point detection. More precisely, we show that the median heuristic is asymptotically normal around this value.; Dans cette thèse, nous nous intéressons à une méthode de détection des ruptures dans une suite d’observations appartenant à un ensemble muni d’un noyau semi-défini positif. Cette procédure est une version « à noyaux » d’une méthode des moindres carrés pénalisés. Notre principale contribution est de montrer que, pour tout noyau satisfaisant des hypothèses raisonnables, cette méthode fournit une segmentation proche de la véritable segmentation avec grande probabilité. Ce résultat est obtenu pour un noyau borné et une pénalité linéaire, ainsi qu’une autre pénalité venant de la sélection de modèles. Les preuves reposent sur un résultat de concentration pour des variables aléatoires bornées à valeurs dans un espace de Hilbert, et nous obtenons une version moins précise de ce résultat lorsque l’on supposeseulement que la variance des observations est finie. Dans un cadre asymptotique, nous retrouvons les taux minimax usuels en détection de ruptures lorsqu’aucune hypothèse n’est faite sur la taille des segments. Ces résultats théoriques sont confirmés par des simulations. Nous étudions également de manière détaillée les liens entre différentes notions de distances entre segmentations. En particulier, nous prouvons que toutes ces notions coïncident pour des segmentations suffisamment proches. D’un point de vue pratique, nous montrons que l’heuristique du « saut de dimension » pour choisir la constante de pénalisation est un choix raisonnable lorsque celle-ci est linéaire. Nous montrons également qu’une quantité clé dépendant du noyau et qui apparaît dans nos résultats théoriques influe sur les performances de cette méthode pour la détection d’une unique rupture. Dans un cadre paramétrique, et lorsque le noyau utilisé est invariant partranslation, il est possible de calculer cette quantité explicitement. Grâce à ces calculs, nouveaux pour plusieurs d’entre eux, nous sommes capable d’étudier précisément le comportement de la constante de pénalité maximale. Pour finir, nous traitons de l’heuristique de la médiane, un moyen courant de choisir la largeur de bande des noyaux à base de fonctions radiales. Dans un cadre asymptotique, nous montrons que l’heuristique de la médiane se comporte à la limite comme la médiane d’une distribution que nous décrivons complètement dans le cadre du test à deux échantillons à noyaux et de la détection de ruptures. Plus précisément, nous montrons que l’heuristique de la médiane est approximativement normale centrée en cette valeur.

This thesis focuses on multivariate spatial statistics and machine learning applied to hyperspectral and multimodal and images in remote sensing and scanning electron microscopy (SEM). In this thesis the following topics are considered:Fusion of images:SEM allows us to acquire images from a given sample using different modalities. The purpose of these studies is to analyze the interest of fusion of information to improve the multimodal SEM images acquisition. We have modeled and implemented various techniques of image fusion of information, based in particular on spatial regression theory. They have been assessed on various datasets.Spatial classification of multivariate image pixels:We have proposed a novel approach for pixel classification in multi/hyper-spectral images. The aim of this technique is to represent and efficiently describe the spatial/spectral features of multivariate images. These multi-scale deep descriptors aim at representing the content of the image while considering invariances related to the texture and to its geometric transformations.Spatial dimensionality reduction:We have developed a technique to extract a feature space using morphological principal component analysis. Indeed, in order to take into account the spatial and structural information we used mathematical morphology operators; Cette thèse porte sur la statistique spatiale multivariée et l’apprentissage appliqués aux images hyperspectrales et multimodales. Les thèmes suivants sont abordés :Fusion d'images :Le microscope électronique à balayage (MEB) permet d'acquérir des images à partir d'un échantillon donné en utilisant différentes modalités. Le but de ces études est d'analyser l’intérêt de la fusion de l'information pour améliorer les images acquises par MEB. Nous avons mis en œuvre différentes techniques de fusion de l'information des images, basées en particulier sur la théorie de la régression spatiale. Ces solutions ont été testées sur quelques jeux de données réelles et simulées.Classification spatiale des pixels d’images multivariées :Nous avons proposé une nouvelle approche pour la classification de pixels d’images multi/hyper-spectrales. Le but de cette technique est de représenter et de décrire de façon efficace les caractéristiques spatiales / spectrales de ces images. Ces descripteurs multi-échelle profond visent à représenter le contenu de l'image tout en tenant compte des invariances liées à la texture et à ses transformations géométriques.Réduction spatiale de dimensionnalité :Nous proposons une technique pour extraire l'espace des fonctions en utilisant l'analyse en composante morphologiques. Ainsi, pour ajouter de l'information spatiale et structurelle, nous avons utilisé les opérateurs de morphologie mathématique.

This thesis focuses on multivariate spatial statistics and machine learning applied to hyperspectral and multimodal and images in remote sensing and scanning electron microscopy (SEM). In this thesis the following topics are considered:Fusion of images:SEM allows us to acquire images from a given sample using different modalities. The purpose of these studies is to analyze the interest of fusion of information to improve the multimodal SEM images acquisition. We have modeled and implemented various techniques of image fusion of information, based in particular on spatial regression theory. They have been assessed on various datasets.Spatial classification of multivariate image pixels:We have proposed a novel approach for pixel classification in multi/hyper-spectral images. The aim of this technique is to represent and efficiently describe the spatial/spectral features of multivariate images. These multi-scale deep descriptors aim at representing the content of the image while considering invariances related to the texture and to its geometric transformations.Spatial dimensionality reduction:We have developed a technique to extract a feature space using morphological principal component analysis. Indeed, in order to take into account the spatial and structural information we used mathematical morphology operators; Cette thèse porte sur la statistique spatiale multivariée et l’apprentissage appliqués aux images hyperspectrales et multimodales. Les thèmes suivants sont abordés :Fusion d'images :Le microscope électronique à balayage (MEB) permet d'acquérir des images à partir d'un échantillon donné en utilisant différentes modalités. Le but de ces études est d'analyser l’intérêt de la fusion de l'information pour améliorer les images acquises par MEB. Nous avons mis en œuvre différentes techniques de fusion de l'information des images, basées en particulier sur la théorie de la régression spatiale. Ces solutions ont été testées sur quelques jeux de données réelles et simulées.Classification spatiale des pixels d’images multivariées :Nous avons proposé une nouvelle approche pour la classification de pixels d’images multi/hyper-spectrales. Le but de cette technique est de représenter et de décrire de façon efficace les caractéristiques spatiales / spectrales de ces images. Ces descripteurs multi-échelle profond visent à représenter le contenu de l'image tout en tenant compte des invariances liées à la texture et à ses transformations géométriques.Réduction spatiale de dimensionnalité :Nous proposons une technique pour extraire l'espace des fonctions en utilisant l'analyse en composante morphologiques. Ainsi, pour ajouter de l'information spatiale et structurelle, nous avons utilisé les opérateurs de morphologie mathématique.

Kernel methods have been extensively used to transform initial datasets by mapping them into a so-called kernel space or RKHS, before applying some statistical procedure onto transformed data. In particular, this kind of approach has been explored in the literature to try and make some prescribed probabilistic model more accurate in the RKHS, for instance Gaussian mixtures for classification or mere Gaussians for outlier detection. Therefore this thesis studies the relevancy of such models in kernel spaces. In a first time, we focus on a family of parameterized kernels - Gaussian RBF kernels - and study theoretically the distribution of an embedded random variable in a corresponding RKHS. We managed to prove that most marginals of such a distribution converge weakly to a so-called ''scale-mixture'' of Gaussians - basically a Gaussian with a random variance - when the parameter of the kernel tends to infinity. This result is used in practice to device a new method for outlier detection. In a second time, we present a one-sample test for normality in an RKHS based on the Maximum Mean Discrepancy. In particular, our test uses a fast parametric bootstrap procedure which circumvents the need for re-estimating Gaussian parameters for each bootstrap replication., Les méthodes à noyaux ont été beaucoup utilisées pour transformer un jeu de données initial en lesenvoyant dans un espace dit « à noyau » ou RKHS, pour ensuite appliquer une procédure statistique surles données transformées. En particulier, cette approche a été envisagée dans la littérature pour tenterde rendre un modèle probabiliste donné plus juste dans l’espace à noyaux, qu’il s’agisse de mélanges degaussiennes pour faire de la classification ou d’une simple gaussienne pour de la détection d’anomalie.Ainsi, cette thèse s’intéresse à la pertinence de tels modèles probabilistes dans ces espaces à noyaux. Dansun premier temps, nous nous concentrons sur une famille de noyaux paramétrée - la famille des noyauxradiaux gaussiens - et étudions d’un point de vue théorique la distribution d’une variable aléatoire projetéevers un RKHS correspondant. Nous établissons que la plupart des marginales d’une telle distribution estasymptotiquement proche d’un « scale-mixture » de gaussiennes - autrement dit une gaussienne avec unevariance aléatoire - lorsque le paramètre du noyau tend vers l’infini. Une nouvelle méthode de détectiond’anomalie utilisant ce résultat théorique est introduite. Dans un second temps, nous introduisons un testd’adéquation basé sur la Maximum Mean Discrepancy pour tester des modèles gaussiens dans un RKHS.En particulier, notre test utilise une procédure de bootstrap paramétrique rapide qui permet d’éviter deré-estimer les paramètres de la distribution gaussienne à chaque réplication bootstrap.

Kernel methods have been extensively used to transform initial datasets by mapping them into a so-called kernel space or RKHS, before applying some statistical procedure onto transformed data. In particular, this kind of approach has been explored in the literature to try and make some prescribed probabilistic model more accurate in the RKHS, for instance Gaussian mixtures for classification or mere Gaussians for outlier detection. Therefore this thesis studies the relevancy of such models in kernel spaces. In a first time, we focus on a family of parameterized kernels - Gaussian RBF kernels - and study theoretically the distribution of an embedded random variable in a corresponding RKHS. We managed to prove that most marginals of such a distribution converge weakly to a so-called ''scale-mixture'' of Gaussians - basically a Gaussian with a random variance - when the parameter of the kernel tends to infinity. This result is used in practice to device a new method for outlier detection. In a second time, we present a one-sample test for normality in an RKHS based on the Maximum Mean Discrepancy. In particular, our test uses a fast parametric bootstrap procedure which circumvents the need for re-estimating Gaussian parameters for each bootstrap replication., Les méthodes à noyaux ont été beaucoup utilisées pour transformer un jeu de données initial en lesenvoyant dans un espace dit « à noyau » ou RKHS, pour ensuite appliquer une procédure statistique surles données transformées. En particulier, cette approche a été envisagée dans la littérature pour tenterde rendre un modèle probabiliste donné plus juste dans l’espace à noyaux, qu’il s’agisse de mélanges degaussiennes pour faire de la classification ou d’une simple gaussienne pour de la détection d’anomalie.Ainsi, cette thèse s’intéresse à la pertinence de tels modèles probabilistes dans ces espaces à noyaux. Dansun premier temps, nous nous concentrons sur une famille de noyaux paramétrée - la famille des noyauxradiaux gaussiens - et étudions d’un point de vue théorique la distribution d’une variable aléatoire projetéevers un RKHS correspondant. Nous établissons que la plupart des marginales d’une telle distribution estasymptotiquement proche d’un « scale-mixture » de gaussiennes - autrement dit une gaussienne avec unevariance aléatoire - lorsque le paramètre du noyau tend vers l’infini. Une nouvelle méthode de détectiond’anomalie utilisant ce résultat théorique est introduite. Dans un second temps, nous introduisons un testd’adéquation basé sur la Maximum Mean Discrepancy pour tester des modèles gaussiens dans un RKHS.En particulier, notre test utilise une procédure de bootstrap paramétrique rapide qui permet d’éviter deré-estimer les paramètres de la distribution gaussienne à chaque réplication bootstrap.

In transmissions, multipath propagation introduces intersymbols interference (ISI) that can make it difficult to recover transmitted data. Thus, an equalizer can be used to reduce the ISI. Among the equalization techniques, blind equalization approaches have been developed to retrieve symbols transmitted through an unknown channel by only using received data and some knowledge upon the statistics of the original sequence. In the last decade, new blind equalization techniques, based on information theoretic criteria and probability density functions (pdf) estimation of transmitted data, have been proposed. These criteria consider the whole data distribution and are optimized adaptively, in general by means of stochastic gradient techniques. The objective of this thesis is to propose new blind equalization techniques, based on pdf fitting using kernel methods that are more efficient than the existing ones in terms of convergence speed and residual error. We have proposed new equalizers fulfilling these requirements and we have shown that the performance of the most powerful among proposed methods are close to those of the minimum mean square error equalizer (MMSE). Furthermore, in order to tackle the new challenges related to the construction of systems that are intelligent and able to adapt to the transmission conditions, we studied the automatic modulation classification techniques. These techniques are useful in particular for adaptive modulation or for cognitive radio systems where the receiver has no idea neither about the channel nor about the transmitted modulation. We have proposed new approaches for the classification of modulations especially for QAM and PSK modulations.; Dans les communications numériques, le signal transmis de l'émetteur au récepteur subit des perturbations dues au canal de transmission qui agit comme un filtre sur le signal transmis et conduit au phénomène d'interférence inter-symboles (IIS). Afin de bien récupérer les données émises, il est nécessaire de réduire l'effet de l'IIS par des techniques de traitement de signal telles que l'égalisation. Parmi les techniques d'égalisation, l'égalisation aveugle exploite des caractéristiques statistiques du signal émis connues du récepteur et permet d'éviter l'emploi de séquences d'apprentissage, coûteuses en débit utile. Au cours de la dernière décennie, de nouvelles approches en égalisation aveugle ont été proposées qui prennent en compte l'ensemble de la distribution des données. L'objectif de cette thèse est de proposer de nouvelles techniques d'égalisation, basées sur l'ajustement de densité de probabilité par méthodes à noyaux, plus performantes que celles existantes en termes de vitesse de convergence et d'erreur résiduelle. On a proposé une nouvelle structure d'égaliseur satisfaisant à ces exigences et dont on a démontré la convergence de l'erreur quadratique en sortie vers celle de l'égaliseur non aveugle du minimum d'erreur quadratique moyenne (MMSE). Par ailleurs, en vue de répondre aux nouveaux défis liés à la construction de systèmes intelligents et capables de s'adapter aux conditions de transmission, on s'est également intéressé à l'étude des techniques de classification automatique de modulation (CAM). Ces techniques sont utiles notamment pour les systèmes de radio cognitive où le récepteur ne dispose ni de la connaissance du canal ni de celle de la modulation émise. Nous avons ainsi proposé de nouvelles approches pour la classification automatique des modulations MAQ (Modulation d'Amplitude en Quadrature) et MDP (Modulation par Déplacement de Phase).

In transmissions, multipath propagation introduces intersymbols interference (ISI) that can make it difficult to recover transmitted data. Thus, an equalizer can be used to reduce the ISI. Among the equalization techniques, blind equalization approaches have been developed to retrieve symbols transmitted through an unknown channel by only using received data and some knowledge upon the statistics of the original sequence. In the last decade, new blind equalization techniques, based on information theoretic criteria and probability density functions (pdf) estimation of transmitted data, have been proposed. These criteria consider the whole data distribution and are optimized adaptively, in general by means of stochastic gradient techniques. The objective of this thesis is to propose new blind equalization techniques, based on pdf fitting using kernel methods that are more efficient than the existing ones in terms of convergence speed and residual error. We have proposed new equalizers fulfilling these requirements and we have shown that the performance of the most powerful among proposed methods are close to those of the minimum mean square error equalizer (MMSE). Furthermore, in order to tackle the new challenges related to the construction of systems that are intelligent and able to adapt to the transmission conditions, we studied the automatic modulation classification techniques. These techniques are useful in particular for adaptive modulation or for cognitive radio systems where the receiver has no idea neither about the channel nor about the transmitted modulation. We have proposed new approaches for the classification of modulations especially for QAM and PSK modulations., Dans les communications numériques, le signal transmis de l'émetteur au récepteur subit des perturbations dues au canal de transmission qui agit comme un filtre sur le signal transmis et conduit au phénomène d'interférence inter-symboles (IIS). Afin de bien récupérer les données émises, il est nécessaire de réduire l'effet de l'IIS par des techniques de traitement de signal telles que l'égalisation. Parmi les techniques d'égalisation, l'égalisation aveugle exploite des caractéristiques statistiques du signal émis connues du récepteur et permet d'éviter l'emploi de séquences d'apprentissage, coûteuses en débit utile. Au cours de la dernière décennie, de nouvelles approches en égalisation aveugle ont été proposées qui prennent en compte l'ensemble de la distribution des données. L'objectif de cette thèse est de proposer de nouvelles techniques d'égalisation, basées sur l'ajustement de densité de probabilité par méthodes à noyaux, plus performantes que celles existantes en termes de vitesse de convergence et d'erreur résiduelle. On a proposé une nouvelle structure d'égaliseur satisfaisant à ces exigences et dont on a démontré la convergence de l'erreur quadratique en sortie vers celle de l'égaliseur non aveugle du minimum d'erreur quadratique moyenne (MMSE). Par ailleurs, en vue de répondre aux nouveaux défis liés à la construction de systèmes intelligents et capables de s'adapter aux conditions de transmission, on s'est également intéressé à l'étude des techniques de classification automatique de modulation (CAM). Ces techniques sont utiles notamment pour les systèmes de radio cognitive où le récepteur ne dispose ni de la connaissance du canal ni de celle de la modulation émise. Nous avons ainsi proposé de nouvelles approches pour la classification automatique des modulations MAQ (Modulation d'Amplitude en Quadrature) et MDP (Modulation par Déplacement de Phase).

La reconnaissance de gestes humains est l'un des nombreux défis posés dans le domaine de la vision par les ordinateurs et dans le domaine des interactions humains-machines. Cette problématique qui a gagné en attention au cours des dernières décennies, faisant suite aux nouveaux développements technologiques (caméra 3D, capteurs EEG et EMG, etc.) et nouveaux résultats scientifiques obtenus dans les communautés du traitement du signal et de l'apprentissage automatique, entre autres. C'est un sujet qui soulève plusieurs problématiques : l’acquisition et le prétraitement des données et la détection/reconnaissance (classification) des mouvements. Dans le cadre de ce stage, nous avons comparé différents modèles de Markov cachés (HMM) dont un modèle expérimental avec fonction de densité non paramétrique, nous avons également comparé les résultats de ce modèle avec ceux obtenus via un autre type de classifieur (SVM).

In automatic control, obtaining a model is always the cornerstone of the synthesis procedures such as controller design, fault detection or prediction... This thesis deals with the identification of a class of complex systems, hybrid dynamical systems. These systems involve the interaction of continuous and discrete behaviors. The goal is to build a model from experimental measurements of the system inputs and outputs. A new approach for the identification of linear hybrid systems based on the geometric properties of hybrid systems in the parameter space is proposed. A new algorithm is then proposed to recover the sparsest solutions of underdetermined systems of linear equations. This allows us to improve an identification approach based on the error sparsification. In addition, new approaches based on kernel models are proposed for the identification of nonlinear hybrid systems and piecewise smooth systems., En automatique, l'obtention d'un modèle du système est la pierre angulaire des procédures comme la synthèse d'une commande, la détection des défaillances, la prédiction... Cette thèse traite de l'identification d'une classe de systèmes complexes, les systèmes dynamiques hybrides. Ces systèmes impliquent l'interaction de comportements continus et discrets. Le but est de construire un modèle à partir de mesures expérimentales d'entrée et de sortie. Une nouvelle approche pour l'identification de systèmes hybrides linéaires basée sur les propriétés géométriques des systèmes hybrides dans l'espace des paramètres est proposée. Un nouvel algorithme est ensuite proposé pour le calcul de la solution la plus parcimonieuse (ou creuse) de systèmes d'équations linéaires sous-déterminés. Celui-ci permet d'améliorer une approche d'identification basée sur l'optimisation de la parcimonie du vecteur d'erreur. De plus, de nouvelles approches, basées sur des modèles à noyaux, sont proposées pour l'identification de systèmes hybrides non linéaires et de systèmes lisses par morceaux.

National audience; Dans cet article, nous étudions des techniques d'égalisation aveugle basées sur des critères en théorie de l'information. Elles s'appuient sur l'estimation de la fonction de densité de probabilité (pdf) des données transmises. Notre travail est basé sur des études antérieures où la méthode de la fenêtre de Parzen a été utilisée pour estimer la pdf à la sortie de l'égaliseur. L'égaliseur est obtenu en minimisant la distance entre cette pdf égalisée et une distribution cible. En vue de réduire la complexité de l'algorithme, nous proposons une implémentation à constellation réduite de l'égaliseur adaptatif. Nous montrons un gain de complexité et une amélioration des performances par rapport à des approches similaires dans la littérature.

The aim of this thesis is to develop tools for predicting interactions between proteins that can be applied to the human proteins forming a network with the CFTR protein. This protein, when defective, is involved in cystic fibrosis. The development of in silico prediction methods can be useful for biologists to suggest new interaction targets and to better explain the proteins' functions in the network. We propose a new method to solve the link prediction problem. To benefit from the information of unlabeled data, we place ourselves in the semi-supervised learning framework. Link prediction is addressed as an output kernel learning task, referred as Output Kernel Regression. An output kernel is assumed to encode the proximities of nodes in the target graph and the goal is to approximate this kernel by using appropriate input features. Using the kernel trick in the output space allows one to reduce the problem of learning from pairs to learning a single variable function with output values in a Hilbert space. By choosing candidates for regression functions in a reproducing kernel Hilbert space with operator valued kernels, we develop tools for regularization as for scalar-valued functions. We establish representer theorems in the supervised and semi-supervised cases and use them to define new regression models for different cost functions, called IOKR-ridge and IOKR-margin. We first tested the developed approach on transductive link prediction using artificial data, benchmark data as well as a protein-protein interaction network of the yeast S. Cerevisiae and we obtained very good results. Then we applied it to the prediction of protein interactions in a network built around the CFTR protein.; L'objectif de cette thèse est de développer des outils de prédiction d'interactions entre protéines qui puissent être appliqués en particulier chez l'homme, sur les protéines qui constituent un réseau avec la protéine CFTR. Cette protéine, lorsqu'elle est défectueuse, est impliquée dans la mucoviscidose. Le développement de méthodes de prédiction in silico peut s'avérer utile pour suggérer aux biologistes de nouvelles cibles d'interaction et pour mieux expliquer les fonctions des protéines présentes dans ce réseau. Nous proposons une nouvelle méthode pour le problème de la prédiction de liens dans un réseau. Afin de bénéficier de l'information des données non étiquetées, nous nous plaçons dans le cadre de l'apprentissage semi-supervisé. Nous abordons ce problème de prédiction comme une tâche d'apprentissage d'un noyau de sortie, appelée régression à noyau de sortie. Un noyau de sortie est supposé coder les proximités existantes entre les noeuds du graphe et l'objectif est d'approcher ce noyau à partir de descriptions appropriées en entrée. L'utilisation de l'astuce du noyau dans l'ensemble de sortie permet de réduire le problème d'apprentissage à partir de paires à un problème d'apprentissage d'une fonction d'une seule variable à valeurs dans un espace de Hilbert. En choisissant les fonctions candidates pour la régression dans un espace de Hilbert à noyau reproduisant à valeur opérateur, nous développons, comme dans le cas de fonctions à valeurs scalaires, des outils de régularisation. Nous établissons en particulier des théorèmes de représentation dans le cas supervisé et dans le cas semi-supervisé, que nous utilisons ensuite pour définir de nouveaux modèles de régression pour différentes fonctions de coût, appelés IOKR-ridge et IOKR-margin. Nous avons d'abord testé l'approche développée sur des données artificielles, des problèmes test ainsi que sur un réseau d'interaction protéine-protéine chez la levure S. Cerevisiae et obtenu de très bons résultats. Puis nous l'avons appliquée à la prédiction d'interactions entre protéines dans le cas d'un réseau construit autour de la protéine CFTR.

International audience

National audience; Nous abordons le problème de la prédiction de liens comme une tâche d'apprentissage d'un noyau de sortie par régression à sortie noyau semi-supervisée. En se plaçant dans le cadre de la théorie des espaces de Hilbert à noyau autoreproduisant à valeurs opérateurs pour des fonctions à valeurs vectorielles, nous établissons un nouveau théorème de représentation dédié à la régression semi-supervisée pour un critère des moindres carrés pénalisé. Nous choisissons ensuite un noyau à valeur opérateur défini à partir d'un noyau d'entrée à valeurs scalaires puis nous construisons un espace de Hilbert avec ce noyau comme noyau autoreproduisant. Nous appliquons ensuite le théorème de représentation. La minimisation des moindres carrés pénalisés dans ce cadre conduit à une solution analytique comme dans le cas de la régression ridge qui est donc ici étendue. Nous étudions la pertinence de cette nouvelle approche semi-supervisée dans le cadre de la prédiction de lien transductive. Des jeux de données artificiels étayent notre étude puis deux applications réelles sont traitées en utilisant un très faible pourcentage de données étiquetées.

L'astuce du noyau est une célèbre approche qui permet de transformer implicitement une méthode linéaire en une non-linéaire en remplaçant les produits scalaires par une fonction noyau. Cependant, peu d'algorithmes de quantification vectorielle en ont bénéficié. En effet, ils impliquent habituellement de calculer des transformations linéaires (par exemple le déplacement d'un prototype), ce qui ne permet pas l'application directe de cette astuce. Cet article introduit une méthodologie générale, consistant à travailler dans une approximation de l'espace de redescription et permettant de combiner les méthodes à noyaux aux algorithmes de quantification vectorielle. En conséquence, l'astuce du noyau peut être appliquée à tout type d'algorithme de quantification vectorielle, et plus généralement à tout algorithme impliquant au plus des transformations linéaires.

National audience; Recently, there has been a lot of interest around multi-task learning (MTL) problem with the constraints that tasks should share common features. Such a problem can be addressed through a regularization framework where the regularizer induces a joint-sparsity pattern between task decision functions. We follow this principled framework but instead we focus on lp − l2 (with p ≤ 1) mixed-norms as sparsity-inducing penalties. After having shown that the l1 − l2 MTL problem is a general case of Multiple Kernel Learning (MKL), we adapted the available efficient tools of solving MKL to the sparse MTL problem. Then, for the more general case when p < 1, the use of a DC program provides an iterative scheme solving at each iteration a weighted 1 − 2 sparse MTL problem.

Experimental designs are tools which can dramatically reduce the number of simulations required by time-consuming computer codes. Because we don't know the true relation between the response and inputs, designs should allow one to fit a variety of models and should provide information about all portions of the experimental region. One strategy for selecting the values of the inputs at which to observe the response is to choose these values so they are spread evenly throughout the experimental region, according to "space-filling designs". In this article, we suggest a new method based on comparing the empirical distribution of the points in a design to the uniform distribution with the Kullback-Leibler information. The considered approach consists in estimating this difference or, reciprocally, the Shannon entropy. The entropy is estimated by a Monte Carlo method where the density function is replaced by its kernel density estimator or by using the nearest neighbor distances

Machine Learning is a modern and actively developing field of computer science, devoted to extracting and estimating dependencies from empirical data. It combines such fields as statistics, optimization theory and artificial intelligence. In practical tasks, the general aim of Machine Learning is to construct algorithms able to generalize and predict in previously unseen situations based on some set of examples. Given some finite information, Machine Learning provides ways to exract knowledge, describe, explain and predict from data. Kernel Methods are one of the most successful branches of Machine Learning. They allow applying linear algorithms with well-founded properties such as generalization ability, to non-linear real-life problems. Support Vector Machine is a well-known example of a kernel method, which has found a wide range of applications in data analysis nowadays. In many practical applications, some additional prior knowledge is often available. This can be the knowledge about the data domain, invariant transformations, inner geometrical structures in data, some properties of the underlying process, etc. If used smartly, this information can provide significant improvement to any data processing algorithm. Thus, it is important to develop methods for incorporating prior knowledge into data-dependent models. The main objective of this thesis is to investigate approaches towards learning with kernel methods using prior knowledge. Invariant learning with kernel methods is considered in more details. In the first part of the thesis, kernels are developed which incorporate prior knowledge on invariant transformations. They apply when the desired transformation produce an object around every example, assuming that all points in the given object share the same class. Different types of objects, including hard geometrical objects and distributions are considered. These kernels were then applied for images classification with Support Vector Machines. Next, algorithms which specifically include prior knowledge are considered. An algorithm which linearly classifies distributions by their domain was developed. It is constructed such that it allows to apply kernels to solve non-linear tasks. Thus, it combines the discriminative power of support vector machines and the well-developed framework of generative models. It can be applied to a number of real-life tasks which include data represented as distributions. In the last part of the thesis, the use of unlabelled data as a source of prior knowledge is considered. The technique of modelling the unlabelled data with a graph is taken as a baseline from semi-supervised manifold learning. For classification problems, we use this apporach for building graph models of invariant manifolds. For regression problems, we use unlabelled data to take into account the inner geometry of the input space. To conclude, in this thesis we developed a number of approaches for incorporating some prior knowledge into kernel methods. We proposed invariant kernels for existing algorithms, developed new algorithms and adapted a technique taken from semi-supervised learning for invariant learning. In all these cases, links with related state-of-the-art approaches were investigated. Several illustrative experiments were carried out on real data on optical character recognition, face image classification, brain-computer interfaces, and a number of benchmark and synthetic datasets.

La recherche thérapeutique a de plus en plus recours à des techniques de modélisation, dites de criblage virtuel, visant à corréler la structure d'une molécule avec ses propriétés biologiques. En particulier, l'utilisation de modèles prédictifs quantifiant la toxicité d'une molécule ou son activité vis à vis d'une cible thérapeutique, permet de réduire de manière considérable le temps et les coûts nécessaires à la mise au point de nouveaux médicaments. Nous nous proposons d'aborder ce problème dans le cadre des méthodes à noyaux, qui permettent de construire de tels modèles de manière efficace dès lors que l'on dispose d'une fonction noyau mesurant la similarité des objets que l'on considère. Plus particulièrement, l'objet de cette thèse est de définir de telles fonctions noyaux entre structures bi- et tri-dimensionnelles de molécules. D'un point de vue méthodologique, ce problème se traduit respectivement comme celui de comparer des graphes représentant les liaisons covalentes des molécules, ou des ensembles d'atomes dans l'espace. Plusieurs approches sont envisagées sur la base de l'extraction et la comparaison de divers motifs structuraux qui permettent d'encoder les groupes fonctionnels des molécules à différents niveaux de résolution. Les validations expérimentales suggèrent que cette méthodologie est une alternative prometteuse aux approches classiques en criblage virtuel.

Kernel methods refer to a new family of data analysis tools which may be used in standardized learning contexts, such as classification or regression. Such tools are grounded on an \textit{a priori} similarity measure between the objects to be handled, which have been named ``kernels'' in the statistical learning and functional analysis literature. The simplicity of kernel methods comes from the fact that, given a learning task, such methods only require the definition of a kernel to compare the objects to yield practical results. The problem of selecting the right kernel for a task is nonetheless tricky, notably when the objects have complex structures. We propose in this work various families of generic kernels for composite objects, such as strings, graphs or images. The kernels that we obtain are tailored to compare clouds of points, histograms or more generally positive measures. Our approach is mainly motivated by algebraic considerations on the sets of interests, which is why we make frequent use of the theory of harmonic functions on semigroups in this work. The theoretical justification for such kernels is further grounded on the use of reproducing kernel Hilbert spaces, in which the measures are embedded, along with elements of convex analysis and descriptors of the measures used in statistics and information theory, such as variance and entropy. By mapping any structured object to a cloud of components, \eg taking a string and turning it into a cloud or a histogram of substrings, we apply these kernels on composite objects coupled with discriminative methods, such as the support vector machine, to address classification problems encountered in bioinformatics or image analysis. We extend this framework in the end of the thesis to propose a different viewpoint where objects are no longer seen as clouds of points but rather as nested clouds, where each cloud is labelled according to a set of events endowed with a hierarchy. We show how to benefit from such a description to apply a multiresolution comparison scheme between the objects., Les méthodes à noyaux désignent une famille récente d'outils d'analyse de données, pouvant être utilisés dans une grande variété de tâches classiques comme la classification ou la régression. Ces outils s'appuient principalement sur le choix a priori d'une fonction de similarité entre paires d'objets traités, communément appelée "noyau'' en apprentissage statistique et analyse fonctionnelle. Ces méthodes ont récemment gagné en popularité auprès des praticiens par leur simplicité d'utilisation et leur performance. Le choix d'un noyau adapté à la tâche traitée demeure néanmoins un problème épineux dans la pratique, et nous proposons dans cette thèse plusieurs noyaux génériques pour manipuler des objets structurés, tels que les séquences, les graphes ou les images. L'essentiel de notre contribution repose sur la proposition et l'étude de différents noyaux pour nuages de points ou histogrammes, et plus généralement de noyaux sur mesures positives. Ces approches sont principalement axées sur l'utilisation de propriétés algébriques des ensembles contenant les objets considérés, et nous faisons ainsi appel pour une large part à la théorie des fonctions harmoniques sur semigroupes. Nous utilisons également la théorie des espaces de Hilbert à noyau reproduisant dans lesquels sont plongées ces mesures, des éléments d'analyse convexe ainsi que plusieurs descripteurs de ces mesures utilisés en statistiques ou en théorie de l'information, comme leur variance ou leur entropie. En considérant tout objet structuré comme un ensemble de composants, à l'image d'une séquence transformée en un ensemble de sous-séquences ou d'images en ensembles de pixels, nous utilisons ces noyaux sur des données issues principalement de la bioinformatique et de l'analyse d'images, en les couplant notamment avec des méthodes discriminantes comme les machines à vecteurs de support. Nous terminons ce mémoire sur une extension de ce cadre, en considérons non plus chaque objet comme un seul nuage de point, mais plutôt comme une suite de nuages emboîtés selon un ensemble d'évènements hierarchisés, et aboutissons à travers cette approche à une famille de noyaux de multirésolution sur objets structurés.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Kernel methods have recently been introduced to solve Natural Language Processing and Text Mining problems. Kernels define a generalised similarity measure between objects of arbitrary structure, with three interesting properties, namely the ability to incorporate prior knowledge about the problem, the implicit mapping of the data into a new feature space, which allows for very richer representation and where problem solving is easier, and finally the independence of learning algorithms from the dimension of this new feature space (—the Kernel trick“). These properties, coupled with robust learning algorithms (for classification, clustering, dimension reduction, filtering, ...) provide some remarkable results in Text Mining tasks, such as document categorization, concept clustering, word sense disambiguation, information extraction, relationship extraction and automatic multilingual lexicon extraction., Les méthodes à noyaux connaissent depuis peu une utilisation intensive dans le domaine du traitement automatique du langage et en particulier pour la résolution de tâches en fouille de données textuelles. Les Noyaux définissent une mesure de similarité généralisée entre objects de structure arbitraire, avec trois propriétés intéressantes : la faculté d‘incorporer de la conaissance a priori sur le domaine, la projection implicite des données dans un espace où la représentation est plus riche et la résolution du problème plus aisée, la (relative) indépendance des algorithmes d‘apprentissage par rapport à la dimension de ce nouvel espace. Ces propriétés, couplées avec des algorithmes d‘apprentissage robuste œ pour des tâches telles que le classement, la classfication, la réduction de dimension, le filtrage, ... œ sont à la base de résultats remarquables pour des tâches de Fouille de données textuelles, telles que la catégorisation et la classification de documents et de concepts, la désambiguisation sémantique et structurelle, l‘extraction d‘informations et de relations entre entités, l‘extraction automatique de lexiques multilingues

Colloque avec actes et comité de lecture. internationale.; International audience; In Slow Feature Analysis (\cite{Wiskott02}), it has been demonstrated that high-order invariant properties can be extracted by projecting inputs into a nonlinear space and computing the slowest changing features in this space; this has been proposed as a simple general model for learning nonlinear invariances in the visual system. However, this method is highly constrained by the curse of dimensionality which limits it to simple theoretical simulations. This paper demonstrates that by using a different but closely-related objective function for extracting slowly varying features (\cite{Stone95a,Stone01}), and then exploiting the kernel trick, this curse can be avoided. Using this new method we show that both the complex cell properties of translation invariance and disparity coding can be learnt simultaneously from natural images when complex cells are driven by simple cells also learnt from the image.

De nombreuses techniques d'apprentissage numérique appliquées au traitement de données textuelles utilisent une représentation du texte en "sac de mot". Ce codage, qui a l'avantage de la simplicité, n'utilise que les fréquences d'apparition des mots dans les documents et perd toute information liée à l'ordre des éléments (ordre des mots, structure en paragraphes ou sections, etc). Depuis une petite dizaine d'années, une nouvelle famille d'algorithme d'apprentissage, basée sur la notion de noyaux, fait l'objet d'intenses recherches. Ces noyaux permettent de définir des mesures de similarité utilisables dans de nombreux algorithmes d'apprentissage statistique (de l'analyse discriminante de Fisher aux machines à vecteur de support). Récemment, l'utilisation de noyaux spécifiques pour le traitement de données textuelles structurées a commencé à faire l'objet de recherches. Dans le cadre de la sous-tâche 3.12 du projet InfoM@gic, le LIPN a décidé de travailler sur l'application de ces méthodes à noyau au traitement de données textuelles structurées. Ce rapport intermédiaire présente un bref état de l'art dans ce domaine. Nous passons en revue les principaux types de noyaux proposés ces dernières années pour le traitement des séquences et plus généralement des données structurées (arbres, graphes).