La caractérisation des tremblements de terre est un domaine de recherche primordial en sismologie, où l'objectif final est de fournir des estimations précises d'attributs de la source sismique. Dans ce domaine, certaines questions émergent, par exemple : quand un tremblement de terre s’est-il produit? quelle était sa taille? ou quelle était son évolution dans le temps et l'espace? On pourrait se poser d'autres questions plus complexes comme: pourquoi le tremblement s'est produit? quand sera le prochain dans une certaine région? Afin de répondre aux premières questions, une représentation physique du phénomène est nécessaire. La construction de ce modèle est l'objectif scientifique de ce travail doctoral qui est réalisé dans le cadre de la modélisation cinématique. Pour effectuer cette caractérisation, les modèles cinématiques de la source sismique sont un des outils utilisés par les sismologues. Il s’agit de comprendre la source sismique comme une dislocation en propagation sur la géométrie d’une faille active. Les modèles de sources cinématiques sont une représentation physique de l’histoire temporelle et spatiale d’une telle rupture en propagation. Cette modélisation est dite approche cinématique car les histoires de la rupture inférées par ce type de technique sont obtenues sans tenir compte des forces qui causent l'origine du séisme.Dans cette thèse, je présente une nouvelle méthode d'inversion cinématique capable d'assimiler, hiérarchiquement en temps, les traces de données à travers des fenêtres de temps évolutives. Cette formulation relie la fonction de taux de glissement et les sismogrammes observés, en préservant la positivité de cette fonction et la causalité quand on parcourt l'espace de modèles. Cette approche, profite de la structure creuse de l’histoire spatio-temporelle de la rupture sismique ainsi que de la causalité entre la rupture et chaque enregistrement différé par l'opérateur. Cet opérateur de propagation des ondes connu, est différent pour chaque station. Cette formulation progressive, à la fois sur l’espace de données et sur l’espace de modèle, requiert des hypothèses modérées sur les fonctions de taux de glissement attendues, ainsi que des stratégies de préconditionnement sur le gradient local estimé pour chaque paramètre du taux de glissement. Ces hypothèses sont basées sur de simples modèles physiques de rupture attendus. Les applications réussies de cette méthode aux cas synthétiques (Source Inversion Validation Exercise project) et aux données réelles du séisme de Kumamoto 2016 (Mw=7.0), ont permis d’illustrer les avantages de cette approche alternative d’une inversion cinématique linéaire de la source sismique.L’objectif sous-jacent de cette nouvelle formulation sera la quantification des incertitudes d’un tel modèle. Afin de mettre en évidence les propriétés clés prises en compte dans cette approche linéaire, dans ce travail, j'explore l'application de la stratégie bayésienne connue comme Hamiltonian Monte Carlo (HMC). Cette méthode semble être l’une des possibles stratégies qui peut être appliquée à ce problème linéaire sur-paramétré. Les résultats montrent qu’elle est compatible avec la stratégie linéaire dans le domaine temporel présentée ici. Grâce à une estimation efficace du gradient local de la fonction coût, on peut explorer rapidement l'espace de grande dimension des solutions possibles, tandis que la linéarité est préservée. Dans ce travail, j'explore la performance de la stratégie HMC traitant des cas synthétiques simples, afin de permettre une meilleure compréhension de tous les concepts et ajustements nécessaires pour une exploration correcte de l'espace de modèles probables. Les résultats de cette investigation préliminaire sont encourageants et ouvrent une nouvelle façon d'aborder le problème de la modélisation de la reconstruction cinématique de la source sismique, ainsi, que de l’évaluation des incertitudes associées. / The earthquake characterization is a fundamental research field in seismology, which final goal is to provide accurate estimations of earthquake attributes. In this study field, various questions may rise such as the following ones: when and where did an earthquake happen? How large was it? What is its evolution in space and time? In addition, more challenging questions can be addressed such as the following ones: why did it occur? What is the next one in a given area? In order to progress in the first list of questions, a physical description, or model, of the event is necessary. The investigation of such model (or image) is the scientific topic I investigate during my PhD in the framework of kinematic source models. Understanding the seismic source as a propagating dislocation that occurs across a given geometry of an active fault, the kinematic source models are the physical representations of the time and space history of such rupture propagation. Such physical representation is said to be a kinematic approach because the inferred rupture histories are obtained without taking into account the forces that might cause the origin of the dislocation.In this PhD dissertation, I present a new hierarchical time kinematic source inversion method able to assimilate data traces through evolutive time windows. A linear time-domain formulation relates the slip-rate function and seismograms, preserving the positivity of this function and the causality when spanning the model space: taking benefit of the time-space sparsity of the rupture model evolution is as essential as considering the causality between rupture and each record delayed by the known propagator operator different for each station. This progressive approach, both on the data space and on the model space, does require mild assumptions on prior slip-rate functions or preconditioning strategies on the slip-rate local gradient estimations. These assumptions are based on simple physical expected rupture models. Successful applications of this method to a well-known benchmark (Source Inversion Validation Exercise 1) and to the recorded data of the 2016 Kumamoto mainshock (Mw=7.0) illustrate the advantages of this alternative approach of a linear kinematic source inversion.The underlying target of this new formulation will be the future uncertainty quantification of such model reconstruction. In order to achieve this goal, as well as to highlight key properties considered in this linear time-domain approach, I explore the Hamiltonian Monte Carlo (HMC) stochastic Bayesian framework, which appears to be one of the possible and very promising strategies that can be applied to this stabilized over-parametrized optimization of a linear forward problem to assess the uncertainties on kinematic source inversions. The HMC technique shows to be compatible with the linear time-domain strategy here presented. This technique, thanks to an efficient estimation of the local gradient of the misfit function, appears to be able to rapidly explore the high-dimensional space of probable solutions, while the linearity between unknowns and observables is preserved. In this work, I investigate the performance of the HMC strategy dealing with simple synthetic cases with almost perfect illumination, in order to provide a better understanding of all the concepts and required tunning to achieve a correct exploration of the model space. The results from this preliminary investigation are promising and open a new way of tackling the kinematic source reconstruction problem and the assessment of the associated uncertainties.

Le volume de données disponibles est en perpétuelle expansion. Il est primordial de fournir des méthodes efficaces et robustes permettant d'en extraire des informations pertinentes. Nous nous focalisons sur des données pouvant être représentées sous la forme de nuages de points dans un certain espace muni d'une métrique, e.g. l'espace Euclidien R^d, générées selon une certaine distribution. Parmi les questions naturelles que l'on peut se poser lorsque l'on a accès à des données, trois d'entre elles sont abordées dans cette thèse. La première concerne la comparaison de deux ensembles de points. Comment décider si deux nuages de points sont issus de formes ou de distributions similaires ? Nous construisons un test statistique permettant de décider si deux nuages de points sont issus de distributions égales (modulo un certain type de transformations e.g. symétries, translations, rotations...). La seconde question concerne la décomposition d'un ensemble de points en plusieurs groupes. Étant donné un nuage de points, comment faire des groupes pertinents ? Souvent, cela consiste à choisir un système de k représentants et à associer chaque point au représentant qui lui est le plus proche, en un sens à définir. Nous développons des méthodes adaptées à des données échantillonnées selon certains mélanges de k distributions, en présence de données aberrantes. Enfin, lorsque les données n'ont pas naturellement une structure en k groupes, par exemple, lorsqu'elles sont échantillonnées à proximité d'une sous-variété de R^d, une question plus pertinente est de construire un système de k représentants, avec k grand, à partir duquel on puisse retrouver la sous-variété. Cette troisième question recouvre le problème de la quantification d'une part, et le problème de l'approximation de la distance à un ensemble d'autre part. Pour ce faire, nous introduisons et étudions une variante de la méthode des k-moyennes adaptée à la présence de données aberrantes dans le contexte de la quantification. Les réponses que nous apportons à ces trois questions dans cette thèse sont de deux types, théoriques et algorithmiques. Les méthodes proposées reposent sur des objets continus construits à partir de distributions et de sous-mesures. Des études statistiques permettent de mesurer la proximité entre les objets empiriques et les objets continus correspondants. Ces méthodes sont faciles à implémenter en pratique lorsque des nuages de points sont à disposition. L'outil principal utilisé dans cette thèse est la fonction distance à la mesure, introduite à l'origine pour adapter les méthodes d'analyse topologique des données à des nuages de points corrompus par des données aberrantes / It is primordial to establish effective and robust methods to extract pertinent information from datasets. We focus on datasets that can be represented as point clouds in some metric space, e.g. Euclidean space R^d; and that are generated according to some distribution. Of the natural questions that may arise when one has access to data, three are addressed in this thesis. The first question concerns the comparison of two sets of points. How to decide whether two datasets have been generated according to similar distributions? We build a statistical test allowing to one to decide whether two point clouds have been generated from distributions that are equal (up to some rigid transformation e.g. symmetry, translation, rotation...).The second question is about the decomposition of a set of points into clusters. Given a point cloud, how does one make relevant clusters? Often, it consists of selecting a set of k representatives, and associating every point to its closest representative (in some sense to be defined). We develop methods suited to data sampled according to some mixture of k distributions, possibly with outliers. Finally, when the data can not be grouped naturally into $k$ clusters, e.g. when they are generated in a close neighborhood of some sub-manifold in R^d, a more relevant question is the following. How to build a system of $k$ representatives, with k large, from which it is possible to recover the sub-manifold? This last question is related to the problems of quantization and compact set inference. To address it, we introduce and study a modification of the $k$-means method adapted to the presence of outliers, in the context of quantization. The answers we bring in this thesis are of two types, theoretical and algorithmic. The methods we develop are based on continuous objects built from distributions and sub-measures. Statistical studies allow us to measure the proximity between the empirical objects and the continuous ones. These methods are easy to implement in practice, when samples of points are available. The main tool in this thesis is the function distance-to-measure, which was originally introduced to make topological data analysis work in the presence of outliers.

Cette thèse regroupe des contributions méthodologiques à l'analyse statistique des données issues des technologies de séquençage du transcriptome (RNA-seq). Les difficultés de modélisation des données de comptage RNA-seq sont liées à leur caractère discret et au faible nombre d'échantillons disponibles, limité par le coût financier du séquençage. Une première partie de travaux de cette thèse porte sur la classification à l'aide de modèle de mélange. L'objectif de la classification est la détection de modules de gènes co-exprimés. Un choix naturel de modélisation des données RNA-seq est un modèle de mélange de lois de Poisson. Mais des transformations simples des données permettent de se ramener à un modèle de mélange de lois gaussiennes. Nous proposons de comparer, pour chaque jeu de données RNA-seq, les différentes modélisations à l'aide d'un critère objectif permettant de sélectionner la modélisation la plus adaptée aux données. Par ailleurs, nous présentons un critère de sélection de modèle prenant en compte des informations biologiques externes sur les gènes. Ce critère facilite l'obtention de classes biologiquement interprétables. Il n'est pas spécifique aux données RNA-seq. Il est utile à toute analyse de co-expression à l'aide de modèles de mélange visant à enrichir les bases de données d'annotations fonctionnelles des gènes. Une seconde partie de travaux de cette thèse porte sur l'inférence de réseau à l'aide d'un modèle graphique. L'objectif de l'inférence de réseau est la détection des relations de dépendance entre les niveaux d'expression des gènes. Nous proposons un modèle d'inférence de réseau basé sur des lois de Poisson, prenant en compte le caractère discret et la grande variabilité inter-échantillons des données RNA-seq. Cependant, les méthodes d'inférence de réseau nécessitent un nombre d'échantillons élevé.Dans le cadre du modèle graphique gaussien, modèle concurrent au précédent, nous présentons une approche non-asymptotique pour sélectionner des sous-ensembles de gènes pertinents, en décomposant la matrice variance en blocs diagonaux. Cette méthode n'est pas spécifique aux données RNA-seq et permet de réduire la dimension de tout problème d'inférence de réseau basé sur le modèle graphique gaussien. / This thesis gathers methodologicals contributions to the statistical analysis of next-generation high-throughput transcriptome sequencing data (RNA-seq). RNA-seq data are discrete and the number of samples sequenced is usually small due to the cost of the technology. These two points are the main statistical challenges for modelling RNA-seq data.The first part of the thesis is dedicated to the co-expression analysis of RNA-seq data using model-based clustering. A natural model for discrete RNA-seq data is a Poisson mixture model. However, a Gaussian mixture model in conjunction with a simple transformation applied to the data is a reasonable alternative. We propose to compare the two alternatives using a data-driven criterion to select the model that best fits each dataset. In addition, we present a model selection criterion to take into account external gene annotations. This model selection criterion is not specific to RNA-seq data. It is useful in any co-expression analysis using model-based clustering designed to enrich functional annotation databases.The second part of the thesis is dedicated to network inference using graphical models. The aim of network inference is to detect relationships among genes based on their expression. We propose a network inference model based on a Poisson distribution taking into account the discrete nature and high inter sample variability of RNA-seq data. However, network inference methods require a large number of samples. For Gaussian graphical models, we propose a non-asymptotic approach to detect relevant subsets of genes based on a block-diagonale decomposition of the covariance matrix. This method is not specific to RNA-seq data and reduces the dimension of any network inference problem based on the Gaussian graphical model.

Les modèles de croissance de plantes peuvent être utilisés afin de prédire des quantités d’intérêt ou évaluer la variabilité génotypique au sein d’une population de plantes ; ce double usage est mis en évidence au sein de ce travail. Trois modèles de plantes sont ainsi considérés (LNAS pour la betterave et le blé, GreenLab pour Arabidopsis thaliana) au sein du cadre mathématique des modèles à espace d’états généraux.Une nouvelle plate-forme de calcul générique pour la modélisation et l’inférence statistique (ADJUSTIN’) a été développée en Julia, permettant la simulation des modèles de croissance de plantes considérés ainsi que l’utilisation de techniques d’estimation de pointe telles que les méthodes de Monte Carlo par chaînes de Markov ou de Monte Carlo séquentielles.L’inférence statistique au sein des modèles de croissance de plantes étant de première importance pour des applications concrètes telles que la prédiction de rendement, les méthodes d’estimation de paramètres et d’états au sein de modèles à espaces d’états et dans un cadre bayésien furent tout d’abord étudiées, et plusieurs cas d’étude pour les plantes considérées sont analysés pour le cas d’une plante individuelle.La caractérisation de la variabilité au sein d’une population de plantes est envisagée à travers les distributions des paramètres de population au sein de modèles hiérarchiques bayésiens. Cette approche requérant l’acquisition de nombreuses données pour chaque individu, un algorithme de segmentation-suivi pour l’analyse d’images d’Arabidopsis thaliana, obtenues grâce au Phénoscope, une plate-forme de phénotypage à haut rendement de l’INRA Versailles, est proposé.Finalement, l’intérêt de l’utilisation des modèles hiérarchiques bayésiens pour la mise en évidence de la variabilité au sein d’une population de plantes est discutée. D’abord par l’étude de différents scénarios sur des données simulées, et enfin en utilisant les données expérimentales obtenues à partir de l’analyse d’images pour une population d’Arabidopsis thaliana comprenant 48 individus. / Plant growth models can be used in order to predict quantities of interest or assess the genotypic variability of a population of plants; this dual use is emphasized throughout this work.Three plant growth models are therefore considered (LNAS for sugar beet and wheat, GreenLab for Arabidopsis thaliana) within the mathematical framework of general state space models.A new generic computing platform for modelling and statistical inference (ADJUSTIN’) has been developed in Julia, allowing to simulate the plant growth models considered as well as the use of state-of-the-art estimation techniques such as Markov chain Monte Carlo and sequential Monte Carlo methods.Statistical inference within plant growth models is of primary importance for concrete applications such as yield prediction, parameter and state estimation methods within general state-space models in a Bayesian framework were first studied and several case studies for the plants considered are then investigated in the case of an individual plant.The characterization of the variability of a population of plants is envisioned through the distributions of parameters using Bayesian hierarchical models. This approach requiring the acquisition of numerous data for each individual, a segmentation-tracking algorithm for the analysis of images of Arabidopsis thaliana, obtained thanks to the Phenoscope, a high-throughput phenotyping platform of INRA Versailles, is proposed.Finally, the interest of using Bayesian hierarchical models to evidence the variability of a population of plants is discussed. First through the study of different scenarios on simulated data, and then by using the experimental data acquired via image analysis for the population of Arabidopsis thaliana comprising 48 individuals.

Cette thèse présente de nouvelles méthodes pour l'application de la prédiction structurée en vision numérique et en imagerie médicale.Nos nouvelles contributions suivent quatre axes majeurs.La première partie de cette thèse étudie le problème d'inférence d'ordre supérieur.Nous présentons une nouvelle famille de problèmes de minimisation d'énergie discrète, l'étiquetage parcimonieux, encourageant la parcimonie des étiquettes.C'est une extension naturelle des problèmes connus d'étiquetage de métriques aux potentiels d'ordre élevé.Nous proposons par ailleurs une généralisation du modèle Pn-Potts, le modèle Pn-Potts hiérarchique.Enfin, nous proposons un algorithme parallélisable à proposition de mouvements avec de fortes bornes multiplicatives pour l'optimisation du modèle Pn-Potts hiérarchique et l'étiquetage parcimonieux.La seconde partie de cette thèse explore le problème de classement en utilisant de l'information d'ordre élevé.Nous introduisons deux cadres différents pour l'incorporation d'information d'ordre élevé dans le problème de classement.Le premier modèle, que nous nommons SVM binaire d'ordre supérieur (HOB-SVM), optimise une borne supérieure convexe sur l'erreur 0-1 pondérée tout en incorporant de l'information d'ordre supérieur en utilisant un vecteur de charactéristiques jointes.Le classement renvoyé par HOB-SVM est obtenu en ordonnant les exemples selon la différence entre la max-marginales de l'affectation d'un exemple à la classe associée et la max-marginale de son affectation à la classe complémentaire.Le second modèle, appelé AP-SVM d'ordre supérieur (HOAP-SVM), s'inspire d'AP-SVM et de notre premier modèle, HOB-SVM.Le modèle correspond à une optimisation d'une borne supérieure sur la précision moyenne, à l'instar d'AP-SVM, qu'il généralise en permettant également l'incorporation d'information d'ordre supérieur.Nous montrons comment un optimum local du problème d'apprentissage de HOAP-SVM peut être déterminé efficacement grâce à la procédure concave-convexe.En utilisant des jeux de données standards, nous montrons empiriquement que HOAP-SVM surpasse les modèles de référence en utilisant efficacement l'information d'ordre supérieur tout en optimisant directement la fonction d'erreur appropriée.Dans la troisième partie, nous proposons un nouvel algorithme, SSVM-RP, pour obtenir un chemin de régularisation epsilon-optimal pour les SVM structurés.Nous présentons également des variantes intuitives de l'algorithme Frank-Wolfe pour l'optimisation accélérée de SSVM-RP.De surcroît, nous proposons une approche systématique d'optimisation des SSVM avec des contraintes additionnelles de boîte en utilisant BCFW et ses variantes.Enfin, nous proposons un algorithme de chemin de régularisation pour SSVM avec des contraintes additionnelles de positivité/negativité.Dans la quatrième et dernière partie de la thèse, en appendice, nous montrons comment le cadre de l'apprentissage semi-supervisé des SVM à variables latentes peut être employé pour apprendre les paramètres d'un problème complexe de recalage déformable.Nous proposons un nouvel algorithme discriminatif semi-supervisé pour apprendre des métriques de recalage spécifiques au contexte comme une combinaison linéaire des métriques conventionnelles.Selon l'application, les métriques traditionnelles sont seulement partiellement sensibles aux propriétés anatomiques des tissus.Dans ce travail, nous cherchons à déterminer des métriques spécifiques à l'anatomie et aux tissus, par agrégation linéaire de métriques connues.Nous proposons un algorithme d'apprentissage semi-supervisé pour estimer ces paramètres conditionnellement aux classes sémantiques des données, en utilisant un jeu de données faiblement annoté.Nous démontrons l'efficacité de notre approche sur trois jeux de données particulièrement difficiles dans le domaine de l'imagerie médicale, variables en terme de structures anatomiques et de modalités d'imagerie. / This thesis develops novel methods to enable the use of structured prediction in computer vision and medical imaging. Specifically, our contributions are four fold. First, we propose a new family of high-order potentials that encourage parsimony in the labeling, and enable its use by designing an accurate graph cuts based algorithm to minimize the corresponding energy function. Second, we show how the average precision SVM formulation can be extended to incorporate high-order information for ranking. Third, we propose a novel regularization path algorithm for structured SVM. Fourth, we show how the weakly supervised framework of latent SVM can be employed to learn the parameters for the challenging deformable registration problem.In more detail, the first part of the thesis investigates the high-order inference problem. Specifically, we present a novel family of discrete energy minimization problems, which we call parsimonious labeling. It is a natural generalization of the well known metric labeling problems for high-order potentials. In addition to this, we propose a generalization of the Pn-Potts model, which we call Hierarchical Pn-Potts model. In the end, we propose parallelizable move making algorithms with very strong multiplicative bounds for the optimization of the hierarchical Pn-Potts model and the parsimonious labeling.Second part of the thesis investigates the ranking problem while using high-order information. Specifically, we introduce two alternate frameworks to incorporate high-order information for the ranking tasks. The first framework, which we call high-order binary SVM (HOB-SVM), optimizes a convex upperbound on weighted 0-1 loss while incorporating high-order information using joint feature map. The rank list for the HOB-SVM is obtained by sorting samples using max-marginals based scores. The second framework, which we call high-order AP-SVM (HOAP-SVM), takes its inspiration from AP-SVM and HOB-SVM (our first framework). Similar to AP-SVM, it optimizes upper bound on average precision. However, unlike AP-SVM and similar to HOB-SVM, it can also encode high-order information. The main disadvantage of HOAP-SVM is that estimating its parameters requires solving a difference-of-convex program. We show how a local optimum of the HOAP-SVM learning problem can be computed efficiently by the concave-convex procedure. Using standard datasets, we empirically demonstrate that HOAP-SVM outperforms the baselines by effectively utilizing high-order information while optimizing the correct loss function.In the third part of the thesis, we propose a new algorithm SSVM-RP to obtain epsilon-optimal regularization path of structured SVM. We also propose intuitive variants of the Block-Coordinate Frank-Wolfe algorithm (BCFW) for the faster optimization of the SSVM-RP algorithm. In addition to this, we propose a principled approach to optimize the SSVM with additional box constraints using BCFW and its variants. In the end, we propose regularization path algorithm for SSVM with additional positivity/negativity constraints.In the fourth and the last part of the thesis (Appendix), we propose a novel weakly supervised discriminative algorithm for learning context specific registration metrics as a linear combination of conventional metrics. Conventional metrics can cope partially - depending on the clinical context - with tissue anatomical properties. In this work we seek to determine anatomy/tissue specific metrics as a context-specific aggregation/linear combination of known metrics. We propose a weakly supervised learning algorithm for estimating these parameters conditionally to the data semantic classes, using a weak training dataset. We show the efficacy of our approach on three highly challenging datasets in the field of medical imaging, which vary in terms of anatomical structures and image modalities.

Les relaxations en problème d’optimisation linéaire jouent un rôle central en inférence du maximum a posteriori (map) dans les champs aléatoires de Markov discrets. Nous étudions ici les avantages offerts par les méthodes de Newton pour résoudre efficacement le problème dual (au sens de Lagrange) d’une reformulation lisse du problème. Nous comparons ces dernières aux méthodes de premier ordre, à la fois en terme de vitesse de convergence et de robustesse au mauvais conditionnement du problème. Nous exposons donc un cadre général pour l’apprentissage non-supervisé basé sur le transport optimal et les régularisations parcimonieuses. Nous exhibons notamment une approche prometteuse pour résoudre le problème de la préimage dans l’acp à noyau. Du point de vue de l’optimisation, nous décrivons le calcul du gradient d’une version lisse de la norme p de Schatten et comment cette dernière peut être utilisée dans un schéma de majoration-minimisation. / Numerical optimization and machine learning have had a fruitful relationship, from the perspective of both theory and application. In this thesis, we present an application oriented take on some inference and learning problems. Linear programming relaxations are central to maximum a posteriori (MAP) inference in discrete Markov Random Fields (MRFs). Especially, inference in higher-order MRFs presents challenges in terms of efficiency, scalability and solution quality. In this thesis, we study the benefit of using Newton methods to efficiently optimize the Lagrangian dual of a smooth version of the problem. We investigate their ability to achieve superior convergence behavior and to better handle the ill-conditioned nature of the formulation, as compared to first order methods. We show that it is indeed possible to obtain an efficient trust region Newton method, which uses the true Hessian, for a broad range of MAP inference problems. Given the specific opportunities and challenges in the MAP inference formulation, we present details concerning (i) efficient computation of the Hessian and Hessian-vector products, (ii) a strategy to damp the Newton step that aids efficient and correct optimization, (iii) steps to improve the efficiency of the conjugate gradient method through a truncation rule and a pre-conditioner. We also demonstrate through numerical experiments how a quasi-Newton method could be a good choice for MAP inference in large graphs. MAP inference based on a smooth formulation, could greatly benefit from efficient sum-product computation, which is required for computing the gradient and the Hessian. We show a way to perform sum-product computation for trees with sparse clique potentials. This result could be readily used by other algorithms, also. We show results demonstrating the usefulness of our approach using higher-order MRFs. Then, we discuss potential research topics regarding tightening the LP relaxation and parallel algorithms for MAP inference.Unsupervised learning is an important topic in machine learning and it could potentially help high dimensional problems like inference in graphical models. We show a general framework for unsupervised learning based on optimal transport and sparse regularization. Optimal transport presents interesting challenges from an optimization point of view with its simplex constraints on the rows and columns of the transport plan. We show one way to formulate efficient optimization problems inspired by optimal transport. This could be done by imposing only one set of the simplex constraints and by imposing structure on the transport plan through sparse regularization. We show how unsupervised learning algorithms like exemplar clustering, center based clustering and kernel PCA could fit into this framework based on different forms of regularization. We especially demonstrate a promising approach to address the pre-image problem in kernel PCA. Several methods have been proposed over the years, which generally assume certain types of kernels or have too many hyper-parameters or make restrictive approximations of the underlying geometry. We present a more general method, with only one hyper-parameter to tune and with some interesting geometric properties. From an optimization point of view, we show how to compute the gradient of a smooth version of the Schatten p-norm and how it can be used within a majorization-minimization scheme. Finally, we present results from our various experiments.

Cette thèse présente nos contributions àl’inférence et l’apprentissage des modèles graphiquesen vision artificielle. Tout d’abord, nous proposons unenouvelle classe d’algorithmes de décomposition pour résoudrele problème d’appariement de graphes et d’hypergraphes,s’appuyant sur l’algorithme des directionsalternées (ADMM) non convexe. Ces algorithmes sontefficaces en terme de calcul et sont hautement parallélisables.En outre, ils sont également très générauxet peuvent être appliqués à des fonctionnelles d’énergiearbitraires ainsi qu’à des contraintes de correspondancearbitraires. Les expériences montrent qu’ils surpassentles méthodes de pointe existantes sur des benchmarkspopulaires. Ensuite, nous proposons une relaxationcontinue non convexe pour le problème d’estimationdu maximum a posteriori (MAP) dans les champsaléatoires de Markov (MRFs). Nous démontrons quecette relaxation est serrée, c’est-à-dire qu’elle est équivalenteau problème original. Cela nous permet d’appliquerdes méthodes d’optimisation continue pour résoudrele problème initial discret sans perte de précisionaprès arrondissement. Nous étudions deux méthodes degradient populaires, et proposons en outre une solutionplus efficace utilisant l’ADMM non convexe. Les expériencessur plusieurs problèmes réels démontrent quenotre algorithme prend l’avantage sur ceux de pointe,dans différentes configurations. Finalement, nous proposonsune méthode d’apprentissage des paramètres deces modèles graphiques avec des données d’entraînement,basée sur l’ADMM non convexe. Cette méthodeconsiste à visualiser les itérations de l’ADMM commeune séquence d’opérations différenciables, ce qui permetde calculer efficacement le gradient de la perted’apprentissage par rapport aux paramètres du modèle.L’apprentissage peut alors utiliser une descente de gradientstochastique. Nous obtenons donc un frameworkunifié pour l’inférence et l’apprentissage avec l’ADMMnon-convexe. Grâce à sa flexibilité, ce framework permetégalement d’entraîner conjointement de-bout-en-boutun modèle graphique avec un autre modèle, telqu’un réseau de neurones, combinant ainsi les avantagesdes deux. Nous présentons des expériences sur un jeude données de segmentation sémantique populaire, démontrantl’efficacité de notre méthode. / This thesis presents our contributions toinference and learning of graph-based models in computervision. First, we propose a novel class of decompositionalgorithms for solving graph and hypergraphmatching based on the nonconvex alternating directionmethod of multipliers (ADMM). These algorithms arecomputationally efficient and highly parallelizable. Furthermore,they are also very general and can be appliedto arbitrary energy functions as well as arbitraryassignment constraints. Experiments show that theyoutperform existing state-of-the-art methods on popularbenchmarks. Second, we propose a nonconvex continuousrelaxation of maximum a posteriori (MAP) inferencein discrete Markov random fields (MRFs). Weshow that this relaxation is tight for arbitrary MRFs.This allows us to apply continuous optimization techniquesto solve the original discrete problem withoutloss in accuracy after rounding. We study two populargradient-based methods, and further propose a more effectivesolution using nonconvex ADMM. Experimentson different real-world problems demonstrate that theproposed ADMM compares favorably with state-of-theartalgorithms in different settings. Finally, we proposea method for learning the parameters of these graphbasedmodels from training data, based on nonconvexADMM. This method consists of viewing ADMM iterationsas a sequence of differentiable operations, whichallows efficient computation of the gradient of the trainingloss with respect to the model parameters, enablingefficient training using stochastic gradient descent. Atthe end we obtain a unified framework for inference andlearning with nonconvex ADMM. Thanks to its flexibility,this framework also allows training jointly endto-end a graph-based model with another model suchas a neural network, thus combining the strengths ofboth. We present experiments on a popular semanticsegmentation dataset, demonstrating the effectivenessof our method.

La partie principale de cette thèse s'intéresse à développer les aspects théoriques et algorithmiques pour trois procédures statistiques distinctes. Le premier problème abordé est la complétion de matrices binaires. Nous proposons un estimateur basé sur une approximation variationnelle pseudo-bayésienne en utilisant une fonction de perte différente de celles utilisées auparavant. Nous pouvons calculer des bornes non asymptotiques sur le risque intégré. L'estimateur proposé est beaucoup plus rapide à calculer qu'une estimation de type MCMC et nous montrons sur des exemples qu'il est efficace en pratique. Le deuxième problème abordé est l'étude des propriétés théoriques du minimiseur du risque empirique pénalisé pour des fonctions de perte lipschitziennes. Nous pouvons ensuite appliquer les résultats principaux sur la régression logistique avec la pénalisation SLOPE ainsi que sur la complétion de matrice. Le troisième chapitre développe une approximation de type Expectation-Propagation quand la vraisemblance n'est pas explicite. On utilise alors l'approximation ABC dans un second temps. Cette procédure peut s'appliquer à beaucoup de modèles et est beaucoup plus précise et rapide. Elle est appliquée à titre d'exemple sur un modèle d'extrêmes spatiaux. / The main part of this thesis aims at studying the theoretical and algorithmic aspects of three distinct statistical procedures. The first problem is the binary matrix completion. We propose an estimator based on a variational approximation of a pseudo-Bayesian estimator. We use a different loss function of the ones used in the literature. We are able to compute non asymptotic risk bounds. It is much faster to compute the estimator than a MCMC method and we show on examples that it is efficient in practice. In a second part we study the theoretical properties of the regularized empirical risk minimizer for Lipschitz loss functions. We are therefore able to apply it on the logistic regression with the SLOPE regularization and on the matrix completion as well. The third chapter develops an Expectation-Propagation approximation when the likelihood is not explicit. We then use an ABC approximation in a second stage. This procedure may be applied to many models and is more precise and faster than the classic ABC approximation. It is used in a spatial extremes model.

Motivée par les récentes avancées dans l'analyse théorique des performances des algorithmes d'apprentissage automatisé, cette thèse s'intéresse à l'analyse de performances et à l'amélioration de la classification nonsupervisée de données et graphes en grande dimension. Spécifiquement, dans la première grande partie de cette thèse, en s'appuyant sur des outils avancés de la théorie des grandes matrices aléatoires, nous analysons les performances de méthodes spectrales sur des modèles de graphes réalistes et denses ainsi que sur des données en grandes dimensions en étudiant notamment les valeurs propres et vecteurs propres des matrices d'affinités de ces données. De nouvelles méthodes améliorées sont proposées sur la base de cette analyse théorique et démontrent à travers de nombreuses simulations que leurs performances sont meilleures comparées aux méthodes de l'état de l'art. Dans la seconde partie de la thèse, nous proposons un nouvel algorithme pour la détection de communautés hétérogènes entre plusieurs couches d'un graphe à plusieurs types d'interaction. Une approche bayésienne variationnelle est utilisée pour approximer la distribution apostériori des variables latentes du modèle. Toutes les méthodes proposées dans cette thèse sont utilisées sur des bases de données synthétiques et sur des données réelles et présentent de meilleures performances en comparaison aux approches standard de classification dans les contextes susmentionnés. / Spurred by recent advances on the theoretical analysis of the performances of the data-driven machine learning algorithms, this thesis tackles the performance analysis and improvement of high dimensional data and graph clustering. Specifically, in the first bigger part of the thesis, using advanced tools from random matrix theory, the performance analysis of spectral methods on dense realistic graph models and on high dimensional kernel random matrices is performed through the study of the eigenvalues and eigenvectors of the similarity matrices characterizing those data. New improved methods are proposed and are shown to outperform state-of-the-art approaches. In a second part, a new algorithm is proposed for the detection of heterogeneous communities from multi-layer graphs using variational Bayes approaches to approximate the posterior distribution of the sought variables. The proposed methods are successfully applied to synthetic benchmarks as well as real-world datasets and are shown to outperform standard approaches to clustering in those specific contexts.

Streptococcus pneumoniae est une bactérie cocci gram positif commensale de la flore oropharyngée qui colonise le rhinopharynx de l’Homme et dont près de 100 sérotypes sont connus. Les nourrissons et les jeunes enfants représentent son réservoir principal. Le pneumocoque peut être à l’origine d’infections graves, telles que la méningite, les bactériémies et la pneumonie, et moins graves mais plus courantes comme la sinusite et l’otite moyenne aiguë. Deux vaccins anti-pneumococciques conjugués ont été introduits en France : le PCV7 (couvrant contre 7 sérotypes) en 2003 et le PCV13 (couvrant contre 6 sérotypes supplémentaires) en 2010. L’objectif général de ce travail de thèse est d’évaluer l’impact des politiques vaccinales sur les infections invasives à pneumocoque en France, en s’intéressant principalement aux évolutions temporelles et géographiques des plus graves : les méningites à pneumocoque (MP). Un premier travail a étudié les dynamiques temporelles des MP sur la période 2001–2014 afin d’identifier l’impact de l’introduction des vaccins conjugués. Des techniques statistiques de modélisations adaptées aux séries temporelles ont été utilisées. Les résultats de ce travail retrouvent des effets rapportés dans la littérature : une réduction des MP à sérotypes vaccinaux mais aussi une augmentation des MP dues aux sérotypes non inclus dans le vaccin (phénomène de « remplacement sérotypique »).Par conséquent, le premier bénéfice, à l’échelle de la population générale, de l’introduction de cette vaccination a été observé seulement onze ans après l’introduction du PCV7, et principalement suite à l’introduction du PCV13 en 2010, avec une diminution de 25% du nombre de MP en 2014. La composante géographique a ensuite été prise en compte afin d’étudier le rôle de la de couverture vaccinale dans la variabilité des MP annuelles entre les départements sur la période 2001-2016. Les résultats confirment l’efficacité des deux formulations du vaccin sur les MP dues aux sérotypes vaccinaux et suggèrent une certaine homogénéité de cet effet entre les différents départements. Inversement, le remplacement sérotypique a été confirmé mais uniquement suite à l’introduction de la première formulation du vaccin et ces effets présentent une répartition géographique hétérogène et variable. La variabilité de la couverture vaccinale entre les départements n’explique pas celle observée dans le nombre de MP, ce qui suggère l’intervention d’autres facteurs tel que la densité géographique. Enfin, une modélisation dynamique, permettant de prendre en compte des aspects fondamentaux des dynamiques de transmission et d’infection du pneumocoque non intégrés dans les méthodes de modélisation statique, a été proposée afin de prédire l’impact de différentes stratégies de vaccination pour les adultes de 65 ans et plus et ainsi évaluer leur rapport coût-utilité. / Streptococcus pneumoniae is a Gram-positive commensal bacterium of the oropharyngeal flora usually colonizing human’s rhino pharynx, of which almost 100 serotypes are known. Infants and young children constitute its main reservoir. Pneumococcus may cause serious infections, such as meningitis, bacteremia and pneumonia, or less serious but more common such as sinusitis and acute otitis media (AOM). Two conjugate pneumococcal vaccines have been introduced in France: PCV7 (covering 7 serotypes) in 2003 and PCV13 (covering 6 additional serotypes) in 2010. The overall objective of this thesis is to assess the impact of vaccination policy on invasive pneumococcal diseases in France, by focusing on temporal and geographical trends of the most serious of them: pneumococcal meningitis (PM). An initial study of PMs temporal dynamics over the 2011-2014 period assessed the impact of conjugate vaccines’ introduction. Statistical modeling techniques were used for time series analysis. The results confirm the effects found in literature: a reduction of vaccine serotypes PMs but at the same time an increase of PMs, due to non-vaccine serotypes (effect of “serotype replacement”). Therefore, the first benefit of vaccine introduction at population scale has been observed no less than 11 years after PCV7 introduction, and then principally after PCV13 was introduced in 2010, with a 25% decrease in PMs in 2014. The geographic component was then implemented to analyze the role of vaccine coverage in annual PM variability between geographic units over the 2001-2016 period. Results confirm the effectiveness of both vaccine compositions on vaccine serotypes PMs and suggest homogeneity of this effect among geographic units. Conversely the serotype replacement has been confirmed only after the first vaccine composition was introduced and presents a variable and heterogeneous geographical repartition. Variability in vaccine coverage among geographic units doesn’t explain the differences in PMs, which could suggest the role of others factors such as demographic density. Finally, a dynamic modeling capable of taking into consideration fundamental aspects of pneumococcus transmission and infection mechanisms not integrated in static modeling has been proposed in order to predict the impacts of different vaccination strategies for 65+ adults and therefore assess their cost-utility ratios.