La constante de normalisation des champs de Markov se présente sous la forme d'une intégrale hautement multidimensionnelle et ne peut être calculée par des méthodes analytiques ou numériques standard. Cela constitue une difficulté majeure pour l'estimation des paramètres ou la sélection de modèle. Pour approcher la loi a posteriori des paramètres lorsque le champ de Markov est observé, nous remplaçons la vraisemblance par une vraisemblance composite, c'est à dire un produit de lois marginales ou conditionnelles du modèle, peu coûteuses à calculer. Nous proposons une correction de la vraisemblance composite basée sur une modification de la courbure au maximum afin de ne pas sous-estimer la variance de la loi a posteriori. Ensuite, nous proposons de choisir entre différents modèles de champs de Markov cachés avec des méthodes bayésiennes approchées (ABC, Approximate Bayesian Computation), qui comparent les données observées à de nombreuses simulations de Monte-Carlo au travers de statistiques résumées. Afin de pallier l'absence de statistiques exhaustives pour ce choix de modèle, des statistiques résumées basées sur les composantes connexes des graphes de dépendance des modèles en compétition sont introduites. Leur efficacité est étudiée à l'aide d'un taux d'erreur conditionnel original mesurant la puissance locale de ces statistiques à discriminer les modèles. Nous montrons alors que nous pouvons diminuer sensiblement le nombre de simulations requises tout en améliorant la qualité de décision, et utilisons cette erreur locale pour construire une procédure ABC qui adapte le vecteur de statistiques résumés aux données observées. Enfin, pour contourner le calcul impossible de la vraisemblance dans le critère BIC (Bayesian Information Criterion) de choix de modèle, nous étendons les approches champs moyens en substituant la vraisemblance par des produits de distributions de vecteurs aléatoires, à savoir des blocs du champ. Le critère BLIC (Block Likelihood Information Criterion), que nous en déduisons, permet de répondre à des questions de choix de modèle plus large que les méthodes ABC, en particulier le choix conjoint de la structure de dépendance et du nombre d'états latents. Nous étudions donc les performances de BLIC dans une optique de segmentation d'images. / Due to the Markovian dependence structure, the normalizing constant of Markov random fields cannot be computed with standard analytical or numerical methods. This forms a central issue in terms of parameter inference or model selection as the computation of the likelihood is an integral part of the procedure. When the Markov random field is directly observed, we propose to estimate the posterior distribution of model parameters by replacing the likelihood with a composite likelihood, that is a product of marginal or conditional distributions of the model easy to compute. Our first contribution is to correct the posterior distribution resulting from using a misspecified likelihood function by modifying the curvature at the mode in order to avoid overly precise posterior parameters.In a second part we suggest to perform model selection between hidden Markov random fields with approximate Bayesian computation (ABC) algorithms that compare the observed data and many Monte-Carlo simulations through summary statistics. To make up for the absence of sufficient statistics with regard to this model choice, we introduce summary statistics based on the connected components of the dependency graph of each model in competition. We assess their efficiency using a novel conditional misclassification rate that evaluates their local power to discriminate between models. We set up an efficient procedure that reduces the computational cost while improving the quality of decision and using this local error rate we build up an ABC procedure that adapts the summary statistics to the observed data.In a last part, in order to circumvent the computation of the intractable likelihood in the Bayesian Information Criterion (BIC), we extend the mean field approaches by replacing the likelihood with a product of distributions of random vectors, namely blocks of the lattice. On that basis, we derive BLIC (Block Likelihood Information Criterion) that answers model choice questions of a wider scope than ABC, such as the joint selection of the dependency structure and the number of latent states. We study the performances of BLIC in terms of image segmentation.

This thesis considers the problem of performing inference on undirected graphical models with continuous state spaces. These models represent conditional independence structures that can appear in the context of Bayesian Machine Learning. In the thesis, we focus on computational methods and applications. The aim of the thesis is to demonstrate that the factorisation structure corresponding to the conditional independence structure present in high-dimensional models can be exploited to decrease the computational complexity of inference algorithms. First, we consider the smoothing problem on Hidden Markov Models (HMMs) and discuss novel algorithms that have sub-quadratic computational complexity in the number of particles used. We show they perform on par with existing state-of-the-art algorithms with a quadratic complexity. Further, a novel class of rejection free samplers for graphical models known as the Local Bouncy Particle Sampler (LBPS) is explored and applied on a very large instance of the Probabilistic Matrix Factorisation (PMF) problem. We show the method performs slightly better than Hamiltonian Monte Carlo methods (HMC). It is also the first such practical application of the method to a statistical model with hundreds of thousands of dimensions. In a second part of the thesis, we consider approximate Bayesian inference methods and in particular the Expectation Propagation (EP) algorithm. We show it can be applied as the backbone of a novel distributed Bayesian inference mechanism. Further, we discuss novel variants of the EP algorithms and show that a specific type of update mechanism, analogous to the mirror descent algorithm outperforms all existing variants and is robust to Monte Carlo noise. Lastly, we show that EP can be used to help the Particle Belief Propagation (PBP) algorithm in order to form cheap and adaptive proposals and significantly outperform classical PBP.

Este projeto de doutorado apresenta uma nova abordagem MAP-MRF para a classificação contextual de imagens multiespectrais utilizando combinação de modelos de Campos Aleatórios Markovianos definidos em sistemas de ordens superiores. A modelagem estatística para o problema de classificação segue o paradigma Bayesiano, com a definição de um modelo Markoviano para os dados observados (Gaussian Markov Random Field multiespectral) e outro modelo para representar o conhecimento a priori (Potts). Nesse cenário, o parâmetro β do modelo de Potts atua como um parâmetro de regularização, tendo papel fundamental no compromisso entre as observações e o conhecimento a priori, de modo que seu correto ajuste é necessário para a obtenção de bons resultados. A introdução de sistemas de vizinhança de ordens superiores requer a definição de novos métodos para a estimação dos parâmetros dos modelos Markovianos. Uma das contribuições desse trabalho é justamente propor novas equações de pseudo-verossimilhança para a estimação desses parâmetros no modelo de Potts em sistemas de segunda e terceira ordens. Apesar da abordagem por máxima pseudo-verossimilhança ser amplamente utilizada e conhecida na literatura de campos aleatórios, pouco se conhece acerca da acurácia dessa estimação. Foram derivadas aproximações para a variância assintótica dos estimadores propostos, caracterizando-os completamente no caso limite, com o intuito de realizar inferências e análises quantitativas sobre os parâmetros dos modelos Markovianos. A partir da definição dos modelos e do conhecimento dos parâmetros, o próximo estágio é a classificação das imagens multiespectrais. A solução para esse problema de inferência Bayesiana é dada pelo critério de estimação MAP, onde a solução ótima é determinada maximizando a probabilidade a posteriori, o que define um problema de otimização. Como não há solução analítica para esse problema no caso de prioris Markovianas, algoritmos iterativos de otimização combinatória foram empregados para aproximar a solução ótima. Nesse trabalho, adotam-se três métodos sub-ótimos: Iterated Conditional Modes, Maximizer of the Posterior Marginals e Game Strategy Approach. Porém, é demonstrado na literatura que tais métodos convergem para máximos locais e não globais, pois são altamente dependentes de sua condição inicial. Isto motivou o desenvolvimento de uma nova abordagem para combinação de classificadores contextuais, que utiliza múltiplas inicializações simultâneas providas por diferentes classificadores estatísticos pontuais. A metodologia proposta define um framework MAP-MRF bastante robusto para solução de problemas inversos, pois permite a utilização e a integração de diferentes condições iniciais em aplicações como classificação, filtragem e restauração de imagens. Como medidas quantitativas de desempenho, são adotados o coeficiente Kappa de Cohen e o coeficiente Tau de Kendall para verificar a concordância entre as saídas dos classificadores e a verdade terrestre (amostras pré-rotuladas). Resultados obtidos mostram que a inclusão de sistemas de vizinhança de ordens superiores é de fato capaz de melhorar significativamente não apenas o desempenho da classificação como também a estimação dos parâmetros dos modelos Markovianos, reduzindo tanto o erro de estimação quanto a variância assintótica. Além disso, a combinação de classificadores contextuais através da utilização de múltiplas inicializações simultâneas melhora significativamente o desempenho da classificação se comparada com a abordagem tradicional com apenas uma inicialização. / This work presents a novel MAP-MRF approach for multispectral image contextual classification by combining higher-order Markov Random Field models. The statistical modeling follows the Bayesian paradigm, with the definition of a multispectral Gaussian Markov Random Field model for the observations and a Potts MRF model to represent the a priori knowledge. In this scenario, the Potts MRF model parameter (β) plays the role of a regularization parameter by controlling the tradeoff between the likelihood and the prior knowledge, in a way that a suitable tunning for this parameter is required for a good performance in contextual classification. The introduction of higher-order MRF models requires the specification of novel parameter estimation methods. One of the contributions of this work is the definition of novel pseudo-likelihood equations for the estimation of these MRF parameters in second and third order neighborhood systems. Despite its widely usage in practical MRF applications, little is known about the accuracy of maximum pseudo-likelihood approach. Approximations for the asymptotic variance of the proposed MPL estimators were derived, completely characterizing their behavior in the limiting case, allowing statistical inference and quantitative analysis. From the statistical modeling and having the model parameters estimated, the next step is the multispectral image classification. The solution for this Bayesian inference problem is given by the MAP criterion, where the optimal solution is obtained by maximizing the a posteriori distribution, defining an optimization problem. As there is no analytical solution for this problem in case of Markovian priors, combinatorial optimization algorithms are required to approximate the optimal solution. In this work, we use three suboptimal methods: Iterated Conditional Modes, Maximizer of the Posterior Marginals and Game Strategy Approach, a variant approach based on non-cooperative game theory. However, it has been shown that these methods converge to local maxima solutions, since they are extremelly dependent on the initial condition. This fact motivated the development of a novel approach for combination of contextual classifiers, by making use of multiple initializations at the same time, where each one of these initial conditions is provided by different pointwise pattern classifiers. The proposed methodology defines a robust MAP-MRF framework for the solution of general inverse problems since it allows the use and integration of several initial conditions in a variety of applications as image classification, denoising and restoration. To evaluate the performance of the classification results, two statistical measures are used to verify the agreement between the classifiers output and the ground truth: Cohens Kappa and Kendalls Tau coefficient. The obtained results show that the use of higher-order neighborhood systems is capable of significantly improve not only the classification performance, but also the MRF parameter estimation by reducing both the estimation error and the asymptotic variance. Additionally, the combination of contextual classifiers through the use of multiple initializations also improves the classificatoin performance, when compared to the traditional single initialization approach.

In this thesis we propose to use a penalized maximum conditional likelihood criterion to estimate the graph of a general discrete Markov random field. We prove the almost sure convergence of the estimator of the graph in the case of a finite or countable infinite set of variables. Our method requires minimal assumptions on the probability distribution and contrary to other approaches in the literature, the usual positivity condition is not needed. We present several examples with a finite set of vertices and study the performance of the estimator on simulated data from theses examples. We also introduce an empirical procedure based on k-fold cross validation to select the best value of the constant in the estimators definition and show the application of this method in two real datasets. / Nesta tese propomos um critério de máxima verossimilhança penalizada para estimar o grafo de dependência condicional de um campo aleatório Markoviano discreto. Provamos a convergência quase certa do estimador do grafo no caso de um conjunto finito ou infinito enumerável de variáveis. Nosso método requer condições mínimas na distribuição de probabilidade e contrariamente a outras abordagens da literatura, a condição usual de positividade não é necessária. Introduzimos alguns exemplos com um conjunto finito de vértices e estudamos o desempenho do estimador em dados simulados desses exemplos. Também propomos um procedimento empírico baseado no método de validação cruzada para selecionar o melhor valor da constante na definição do estimador, e mostramos a aplicação deste procedimento em dois conjuntos de dados reais.

Estruturas do tipo linha/curva (line-like, curve-like), alongadas e ramificadas são comumente encontradas nos ecossistemas que conhecemos. Na biomedicina e na biociências, por exemplo, diversas aplicações podem ser observadas. Justamente por este motivo, extrair este tipo de estrutura em imagens é um constante desafio em problemas de análise de imagens. Porém, diversas dificuldades estão envolvidas neste processo. Normalmente as características espectrais e espaciais destas estruturas podem ser muito complexas e variáveis. Especificamente as mais \"finas\" são muito frágeis a qualquer tipo de processamento realizado na imagem e torna-se muito fácil a perda de informações importantes. Outro problema bastante comum é a ausência de parte das estruturas, seja por motivo de pouca resolução, ou por problemas de aquisição, ou por casos de oclusão. Este trabalho tem por objetivo explorar, descrever e desenvolver técnicas de detecção/segmentação de estruturas finas e ramificadas. Diferentes métodos são utilizados de forma combinada, buscando uma melhor representação topológica e perceptual das estruturas e, assim, melhores resultados. Grafos são usados para a representação das estruturas. Esta estrutura de dados vem sendo utilizada com sucesso na literatura na resolução de diversos problemas em processamento e análise de imagens. Devido à fragilidade do tipo de estrutura explorado, além das técnicas de processamento de imagens, princípios de visão computacional são usados. Busca-se, desta forma, obter um melhor \"entendimento perceptual\" destas estruturas na imagem. Esta informação perceptual e informações contextuais das estruturas são utilizadas em um modelo de campos aleatórios de Markov, buscando o resultado final da detecção através de um processo de otimização. Finalmente, também propomos o uso combinado de diferentes modalidades de imagens simultaneamente. Um software é resultado da implementação do arcabouço desenvolvido e o mesmo é utilizado em duas aplicações para avaliar a abordagem proposta: extração de estradas em imagens de satélite e extração de raízes em imagens de perfis de solo. Resultados do uso da abordagem proposta na extração de estradas em imagens de satélite mostram um melhor desempenho em comparação com método existente na literatura. Além disso, a técnica de fusão proposta apresenta melhora significativa de acordo com os resultados apresentados. Resultados inéditos e promissores são apresentados na extração de raízes de plantas. / Line- curve-like, elongated and ramified structures are commonly found inside many known ecosystems. In biomedicine and biosciences, for instance, different applications can be observed. Therefore, the process to extract this kind of structure is a constant challenge in image analysus problems. However, various difficulties are involved in this process. Their spectral and spatial characteristics are usually very complex and variable. Considering specifically the thinner ones, they are very \"fragile\" to any kind of process applied to the image, and then, it becomes easy the loss of crucial data. Another very common problem is the absence of part of the structures, either because of low image resolution and image acquisition problems or because of occlusion problems. This work aims to explore, describe and develop techniques for detection/segmentation of thin and ramified structures. Different methods are used in a combined way, aiming to reach a better topological and perceptual representation of the structures and, therefore, better results. Graphs are used to represent the structures. This data structure has been successfully used in the literature for the development of solutions for many image processing and analysis problems. Because of the fragility of the kind of structures we are dealing with, some computer vision principles are used besides usual image processing techniques. In doing so, we search for a better \"perceptual understanding\" of these structures in the image. This perceptual information along with contextual information about the structures are used in a Markov random field, searching for a final detection through an optimization process. Lastly, we propose the combined use of different image modalities simultaneously. A software is produced from the implementation of the developed framework and it is used in two application in order to evaluate the proposed approach: extraction of road networks from satellite images and extraction of plant roots from soil profile images. Results using the proposed approach for the extraction of road networks show a better performance if compared with an existent method from the literature. Besides that, the proposed fusion technique presents a meaningful improvement according to the presented results. Original and promising results are presented for the extraction of plant roots from soil profile images.

En France, les chutes constituent la première cause de mortalité chez les plus de 75 ans, et la seconde chez les plus de 65 ans. On estime qu'elle engendre un coût de 1 à 2 milliards d'euros par an pour la société. L'enjeu humain et socio-économique est colossal, sachant que le risque de chute est multiplié par 20 après une première chute, que le risque de décès est multiplié par 4 dans l'année qui suit une chute, que les chutes concernent 30% des personnes de plus de 65 ans et 50% des personnes de plus de 85 ans, et que l'on estime que d'ici 2050, plus de 30% de la population sera âgée de plus de 65 ans. Cette thèse propose un dispositif de détection de présence au sol se basant sur l'analyse de cartes de profondeurs acquises en temps réel, ainsi qu'une amélioration du dispositif proposé utilisant également un capteur thermique. Les cartes de profondeurs et les images thermiques nous permettent de nous affranchir des conditions d'illumination de la scène observée, et garantissent l'anonymat des personnes qui évoluent dans le champ de vision du dispositif. Cette thèse propose également différentes méthodes de détection du plan du sol dans une carte de profondeurs, le plan du sol constituant une référence géométrique nécessaire au dispositif proposé. Une enquête psychosociale a été réalisée, qui nous a permis d'évaluer l'acceptabilité a priori dudit dispositif. Cette enquête a démontré sa bonne acceptabilité, et a fourni des préconisations quant aux points d'amélioration et aux écueils à éviter. Enfin, une méthode de suivi d'objets dans une carte de profondeurs est proposée, un objectif à plus long terme consistant à mesurer l'activité des individus observés. / In France, fall is the first death cause for people aged 75 and more, and the second death cause for people aged 65 and more. It is considered that falls generate about 1 to 2 billion euros health costs per year. The human and social-economical issue is crucial, knowing that for the mentioned populations, fall risk is multiplied by 20 after a first fall; that the death risk is multiplied by 4 in the year following a fall; that per year, 30% of the people aged 65 and more and 50% of the people aged 85 and more are subject to falls; and that it is estimated that more than 30% of the French population whill be older than 65 years old by 2050. This thesis proposes a ground lying event detection device which bases on the real time analysis of depth maps, and also proposes an improvement of the device, which uses an additional thermal sensor. Depth maps and thermal images ensure the device is independent from textures and lighting conditions of the observed scenes, and guarantee that the device respects the privacy of those who pass into its field of view, since nobody can be recognized in such images. This thesis also proposes several methods to detect the ground plane in a depth map, the ground plane being a geometrical reference for the device. A psycho-social inquiry was conducted, and enabled the evaluation of the a priori acceptability of the proposed device. This inquiry demonstrated the good acceptability of the proposed device, and resulted in recommendations on points to be improved and on pitfalls to avoid. Last, a method to separate and track objects detected in a depth map is proposed, the measurement of the activity of observed individuals being a long term objective for the device.

La présente thèse propose des méthodes pour l'estimation du mouvement des organes d'un patient autravers de l'imagerie tomographique. Le but est la correction du mouvement spatio-temporel sur les imagesmédicales tomographiques. En tant que paradigme expérimental, nous considérons le problème de l'estimation dumouvement dans l'imagerie IRM de diffusion, une modalité d'imagerie sensible à la diffusion des molécules d'eaudans le corps. Le but de ces travaux de thèse est l'évaluation des patients atteints de lymphome, car l'eau diffusedifféremment dans les tissus biologiques sains et dans les lésions. L'effet de la diffusion de l'eau peut être mieuxreprésenté par une image paramétrique, grâce au coefficient de diffusion apparente (image à ADC), créé sur la based'une série d'images DWI du même patient (séquence d'images 3D), acquises au moment de la numérisation. Unetelle image paramétrique a la possibilité de devenir un biomarqueur d'imagerie d’IRM et de fournir aux médecinsdes informations complémentaires concernantl'image de FDG-PET qui est la méthode d'imagerie de base pour lelymphome et qui montre la quantité de glucose métabolisée.Nos principales contributions sont au nombre de trois. Tout d'abord, nous proposons une méthode de recalaged'image déformable en groupe spécialement conçue pour la correction de mouvement dans l’IRM de diffusion, carelle est guidée par un modèle physiologique décrivant le processus de diffusion qui se déroule lors de l'acquisitionde l'image. Notre méthode détermine une image à ADC de plus grande précision en termes de représentation dugradient de la diffusion des molécules d'eau par rapport à l` image correspondante obtenue par pratique couranteou par d'autres méthodes de recalage d'image non basé sur un modèle. Deuxièmement, nous montrons qu'enimposant des contraintes spatiales sur le calcul de l'image à ADC, les tumeurs de l'image peuvent être encore mieuxcaractérisées en les classant dans les différentes catégories liées à la maladie. Troisièmement, nous montronsqu'une corrélation entre DWI et FDG-PET doit exister en examinant la corrélation entre les caractéristiquesstatistiques extraites par l'image à ADC lisse découlant de notre méthode du recalage d’image déformable et lesscores de recommandation sur la malignité des lésions, donnés par des experts basés sur une évaluation des imagesFDG-PET correspondantes du patient. / This doctoral thesis develops methods to estimate patient's motion, voluntary and involuntary (organs'motion), in order to correct for motion in spatiotemporal tomographic medical images. As an experimentalparadigm we consider the problem of motion estimation in Diffusion-Weighted Magnetic Resonance Imaging (DWI),an imaging modality sensitive to the diffusion of water molecules in the body. DWI is used for the evaluation oflymphoma patients, since water diffuses differently in healthy tissues and in lesions. The effect of water diffusioncan be better depicted through a parametric map, the so-called apparent diffusion coefficient (ADC map), createdbased on a series of DW images of the same patient (3D image sequence), acquired in time during scanning. Such aparametric map has the potentiality to become an imaging biomarker in DWI and provide physicians withcomplementary information to current state-of-the-art FDG-PET imaging reflecting quantitatively glycosemetaboslism.Our contributions are three fold. First, we propose a group-wise deformable image registration methodespecially designed for motion correction in DWI, as it is guided by a physiological model describing the diffusionprocess taking place during image acquisition. Our method derives an ADC map of higher accuracy in terms ofdepicting the gradient of the water molecules' diffusion in comparison to the corresponding map derived bycommon practice or by other model-free group-wise image registration methods. Second, we show that by imposingspatial constraints on the computation of the ADC map, the tumours in the image can be even better characterized interms of classifying them into the different types of the disease. Third, we show that a correlation between DWI andFDG-PET should exist by examining the correlation between statistical features extracted by the smooth ADC mapderived by our deformable registration method, and recommendation scores on the malignancy of the lesions, givenby experts based on an evaluation of the corresponding FDG-PET images of the patient.

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.

L'un des modèles d'apprentissage non-supervisé générant le plus de recherche active est la machine de Boltzmann --- en particulier la machine de Boltzmann restreinte, ou RBM. Un aspect important de l'entraînement ainsi que l'exploitation d'un tel modèle est la prise d'échantillons. Deux développements récents, la divergence contrastive persistante rapide (FPCD) et le herding, visent à améliorer cet aspect, se concentrant principalement sur le processus d'apprentissage en tant que tel. Notamment, le herding renonce à obtenir un estimé précis des paramètres de la RBM, définissant plutôt une distribution par un système dynamique guidé par les exemples d'entraînement. Nous généralisons ces idées afin d'obtenir des algorithmes permettant d'exploiter la distribution de probabilités définie par une RBM pré-entraînée, par tirage d'échantillons qui en sont représentatifs, et ce sans que l'ensemble d'entraînement ne soit nécessaire. Nous présentons trois méthodes: la pénalisation d'échantillon (basée sur une intuition théorique) ainsi que la FPCD et le herding utilisant des statistiques constantes pour la phase positive. Ces méthodes définissent des systèmes dynamiques produisant des échantillons ayant les statistiques voulues et nous les évaluons à l'aide d'une méthode d'estimation de densité non-paramétrique. Nous montrons que ces méthodes mixent substantiellement mieux que la méthode conventionnelle, l'échantillonnage de Gibbs. / One of the most active topics of research in unsupervised learning is the Boltzmann machine --- particularly the Restricted Boltzmann Machine or RBM. In order to train, evaluate or exploit such models, one has to draw samples from it. Two recent algorithms, Fast Persistent Contrastive Divergence (FPCD) and Herding aim to improve sampling during training. In particular, herding gives up on obtaining a point estimate of the RBM's parameters, rather defining the model's distribution with a dynamical system guided by training samples. We generalize these ideas in order to obtain algorithms capable of exploiting the probability distribution defined by a pre-trained RBM, by sampling from it, without needing to make use of the training set. We present three methods: Sample Penalization, based on a theoretical argument as well as FPCD and Herding using constant statistics for their positive phases. These methods define dynamical systems producing samples with the right statistics and we evaluate them using non-parametric density estimation. We show that these methods mix substantially better than Gibbs sampling, which is the conventional sampling method used for RBMs.

L'expression des gènes dans une cellule a longtemps été observable uniquement à travers des quantités moyennes mesurées sur des populations. L'arrivée des techniques «single-cell» permet aujourd'hui d'observer des niveaux d'ARN et de protéines dans des cellules individuelles : il s'avère que même dans une population de génome identique, la variabilité entre les cellules est parfois très forte. En particulier, une description moyenne est clairement insuffisante étudier la différenciation cellulaire, c'est-à-dire la façon dont les cellules souches effectuent des choix de spécialisation. Dans cette thèse, on s'intéresse à l'émergence de tels choix à partir de réseaux de régulation sous-jacents entre les gènes, que l'on souhaiterait pouvoir inférer à partir de données. Le point de départ est la construction d'un modèle stochastique de réseaux de gènes capable de reproduire les observations à partir d'arguments physiques. Les gènes sont alors décrits comme un système de particules en interaction qui se trouve être un processus de Markov déterministe par morceaux, et l'on cherche à obtenir un modèle statistique à partir de sa loi invariante. Nous présentons deux approches : la première correspond à une approximation de champ assez populaire en physique, pour laquelle nous obtenons un résultat de concentration, et la deuxième se base sur un cas particulier que l'on sait résoudre explicitement, ce qui aboutit à un champ de Markov caché aux propriétés intéressantes / Gene expression in a cell has long been only observable through averaged quantities over cell populations. The recent development of single-cell transcriptomics has enabled gene expression to be measured in individual cells: it turns out that even in an isogenic population, the molecular variability can be very important. In particular, an averaged description is not sufficient to account for cell differentiation. In this thesis, we are interested in the emergence of such cell decision-making from underlying gene regulatory networks, which we would like to infer from data. The starting point is the construction of a stochastic gene network model that is able to explain the data using physical arguments. Genes are then seen as an interacting particle system that happens to be a piecewise-deterministic Markov process, and our aim is to derive a tractable statistical model from its stationary distribution. We present two approaches: the first one is a popular field approximation, for which we obtain a concentration result, and the second one is based on an analytically tractable particular case, which provides a hidden Markov random field with interesting properties