Sur l’apprentissage des paramètres pour les modèles Perturb-and-MAP

Probabilistic graphical models encode hidden dependencies between random variables for data modelling. Parameter estimation is a crucial and necessary part of handling such probabilistic models. These very general models have been used in plenty of fields such as computer vision, signal processing, natural language processing and many more. We mostly focused on log-supermodular models, which is a specific part of exponential family distributions, where the potential function is assumed to be the negative of a submodular function. This property will be very handy for maximum a posteriori and parameter learning estimations. Despite the apparent restriction of the models of interest, they cover a broad part of exponential families, since there are plenty of functions that are submodular, e.g., graph cuts, entropy and others. It is well known that a probabilistic treatment is challenging for most models, however we were able to tackle some of the challenges at least approximately.In this manuscript, we exploit perturb-and-MAP ideas for partition function approximation and thus efficient parameter learning. Moreover, the problem can be also interpreted as a structure learning task, where each estimated parameter or weight represents the importance of the corresponding term. We propose a way of approximating parameter estimation and inference for models where exact learning and inference is intractable in general case due to the partition function calculation complexity.The first part of the thesis is dedicated to theoretical guarantees. Given the log-supermodular models, we take advantage of the efficient minimization property related to submodularity. Introducing and comparing two existing upper bounds of the partition function, we are able to demonstrate their relation by proving a theoretical result. We introduce an approach for missing data as a natural subroutine of probabilistic modelling. It appears that we can apply a stochastic technique over the proposed perturb-and-map approximation approach and still maintain convergence while make it faster in practice.The second main contribution of this thesis is an efficient and scalable generalization of the parameter learning approach. In this section we develop new algorithms to perform parameter estimation for various loss functions, different levels of supervision and we also work on the scalability. In particular, working with mostly graph cuts, we were able to incorporate various acceleration techniques.As a third contribution we deal with the general problem of learning continuous signals. In this part, we focus on the sparse graphical models representations. We consider common sparsity-inducing regularizers as negative log-densities for the prior distribution. The proposed denoising techniques do not require choosing any precise regularizer in advance. To perform sparse representation learning, the signal processing community often uses symmetric penalties such as l1, but we propose to parameterize the penalty and learn the weight of each loss component from the data. This is feasible via an approach which is similar to what we proposed in the previous sections.For all aspects of the parameter estimation mentioned above we performed computational experiments to illustrate the ideas or compare with existing benchmarks, and demonstrate its performance in practice.Les modèles graphiques probabilistes codent des dépendances cachées entre des variables aléatoires pour la modélisation des données. L’estimation des paramètres est une partie cruciale et nécessaire du traitement de ces modèles probabilistes. Ces modèles très généraux ont été utilisés dans de nombreux domaines tels que la vision par ordinateur, le traitement du signal, le traitement du langage naturel et bien d’autres. Nous nous sommes surtout concentrés sur les modèles log-supermodulaires, qui constituent une partie spécifique des distributions de la famille exponentielle, où la fonction potentielle est supposée être l’opposée d’une fonction sous-modulaire. Cette propriété sera très pratique pour l’estimation par maximum a posteriori et l’apprentissage des paramètres. Malgré la restriction apparente des modèles d’intérêt, ils couvrent une grande partie des familles exponentielles, puisqu’il y a beaucoup de fonctions qui sont sous-modulaires, par exemple, les coupes dans de graphes, l’entropie et d’autres. Il est bien connu que le traitement probabiliste est un défi pour la plupart des modèles, mais nous avons été en mesure de relever certains de ces défis au moins approximativement.Dans ce manuscrit, nous exploitons les idées “perturb-and-MAP” pour l’approximation de la fonction de partition et donc un apprentissage efficace des paramètres. De plus, le problème peut être considéré comme une tâche d’apprentissage structuré, où chaque paramètre ou poids estimé représente l’importance du terme correspondant. Nous proposons une méthode d’estimation et d’inférence approchée des paramètres pour les modèles où l’apprentissage et l’inférence exacts sont insolubles dans le cas général en raison de la complexité du calcul des fonctions de partition.La première partie de la thèse est consacrée aux garanties théoriques. Étant donnés les modèles log-supermodulaires, nous tirons parti de la propriété de minimisation efficace liée à la sous-modularité. En introduisant et en comparant deux bornes supérieures existantes de la fonction de partition, nous sommes en mesure de démontrer leur relation en prouvant un résultat théorique. Nous introduisons une approche pour les données manquantes comme sous-routine naturelle de la modélisation probabiliste. Il semble que nous puissions appliquer une technique stochastique à l’approche d’approximation par perturbation tout en maintenant la convergence et la rendant plus rapide en pratique.La deuxième contribution principale de cette thèse est une généralisation efficace de l’approche de l’apprentissage paramétrique. Dans cette section, nous développons de nouveaux algorithmes pour effectuer l’estimation des paramètres pour diverses fonctions de perte, différents niveaux de supervision et travaillons sur l’efficacité à grande échelle. En particulier, en travaillant principalement avec des coupes de graphes, nous avons pu intégrer différentes techniques d’accélération.Comme troisième contribution, nous traitons d’un problème général d’apprentissage des signaux continus. Dans cette partie, nous nous concentrons sur les représentations de modèles graphiques parcimonieux. Nous traitons des penalités classiques en estimation parcimonieuse en les considérant comme l’opposée de la log-vraiseullante de la distribution a priori. Les techniques de débruitage proposées ne nécessitent pas de paramêtre de régularisation précis à l’avance. Pour effectuer l’apprentissage de la représentation parcimonieuse la communauté utilise souvent des pénalités symétriques comme la meme l1, mais nous proposons de paramétrer la perte et d’apprendre le poids de chaque composante de la pénalité à partir des données. C’est faisable avec l’approche sur laquelle nous avons travaillé auparavant.Pour tous les aspects de l’estimation des paramètres mentionnés ci-dessus, nous avons effectué des expériences pour illustrer l’idée ou la comparer aux algorithmes existants, et démontrer sa performance en pratique