No description available.

No description available.

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

Lorsqu’une grandeur d’intérêt ne peut être directement mesurée, il est fréquent de procéder à l’observation d’autres quantités qui lui sont liées par des lois physiques. Ces quantités peuvent contenir de l’information sur la grandeur d’intérêt si l’on sait résoudre le problème inverse, souvent mal posé, et inférer la valeur. L’inférence bayésienne constitue un outil statistique puissant pour l’inversion, qui requiert le calcul d’intégrales en grande dimension. Les méthodes Monte Carlo séquentielles (SMC), aussi dénommées méthodes particulaires, sont une classe de méthodes Monte Carlo permettant d’échantillonner selon une séquence de densités de probabilité de dimension croissante. Il existe de nombreuses applications, que ce soit en filtrage, en optimisation globale ou en simulation d’évènement rare. Les travaux ont porté notamment sur l’extension des méthodes SMC dans un contexte dynamique où le système, régi par un processus de Markov caché, est aussi déterminé par des paramètres statiques que l’on cherche à estimer. En estimation bayésienne séquentielle, la détermination de paramètres fixes provoque des difficultés particulières : un tel processus est non-ergodique, le système n’oubliant pas ses conditions initiales. Il est montré comment il est possible de surmonter ces difficultés dans une application de poursuite et identification de formes géométriques par caméra numérique CCD. Des étapes d’échantillonnage MCMC (Chaîne de Markov Monte Carlo) sont introduites pour diversifier les échantillons sans altérer la distribution a posteriori. Pour une autre application de contrôle de matériau, qui cette fois « hors ligne » mêle paramètres statiques et dynamiques, on a proposé une approche originale. Elle consiste en un algorithme PMMH (Particle Marginal Metropolis-Hastings) intégrant des traitements SMC Rao-Blackwellisés, basés sur des filtres de Kalman d’ensemble en interaction.D’autres travaux en traitement de l’information ont été menés, que ce soit en filtrage particulaire pour la poursuite d’un véhicule en phase de rentrée atmosphérique, en imagerie radar 3D par régularisation parcimonieuse ou en recalage d’image par information mutuelle. / When a quantity of interest is not directly observed, it is usual to observe other quantities that are linked by physical laws. They can provide information about the quantity of interest if it is able to solve the inverse problem, often ill posed, and infer the value. Bayesian inference is a powerful tool for inversion that requires the computation of high dimensional integrals. Sequential Monte Carlo (SMC) methods, a.k.a. interacting particles methods, are a type of Monte Carlo methods that are able to sample from a sequence of probability densities of growing dimension. They are many applications, for instance in filtering, in global optimization or rare event simulation.The work has focused in particular on the extension of SMC methods in a dynamic context where the system, governed by a hidden Markov process, is also determined by static parameters that we seek to estimate. In sequential Bayesian estimation, the determination of fixed parameters causes particular difficulties: such a process is non-ergodic, the system not forgetting its initial conditions. It is shown how it is possible to overcome these difficulties in an application of tracking and identification of geometric shapes by CCD digital camera. Markov Monte Carlo Chain (MCMC) sampling steps are introduced to diversify the samples without altering the posterior distribution. For another material control application, which mixes static and dynamic parameters, we proposed an original offline approach. It consists of a Particle Marginal Metropolis-Hastings (PMMH) algorithm that integrates Rao-Blackwellized SMC, based on a bank of interacting Ensemble Kalman filters.Other information processing works has been conducted: particle filtering for atmospheric reentry vehicle tracking, 3D radar imaging by sparse regularization and image registration by mutual information.

Il y a de nouveaux défis dans l'administration et dans la conception des systèmes pour optimiser la gestion des ressources des applications basées en nuage Cloud Computing. Certaines applications demandent des performances rigoureuses (par exemple, par rapport aux retards et aux limites de la gigue), tandis que d'autres applications présentent des charges de travail en rafale (volatiles). Cette thèse propose un framework inspiré dans un modèle épidémique (et basé sur des Chaînes de Markov à Temps Continu), qui peut reproduire la volatilité de la charge de travail, à savoir les effets de buzz (quand il y a une augmentation soudaine de la popularité d'un contenu) d'un système de Vidéo à la Demande (VoD). Deux méthodes d'estimation (basés sur des heuristiques et des Chaînes de Markov Monte Carlo - MCMC) ont été également proposées dans ce travail, de façon à ajuster le modèle selon les comportements de la charge de travail. Les paramètres du modèle obtenus à partir des procédures d'étalonnage révèlent des propriétés intéressantes du modèle. Basé sur des simulations numériques, la précision des deux procédures a été analysée, en montrant que les deux présentent des performances raisonnables. Toutefois, la méthode MCMC dépasse la performance de l'approche heuristique. Cette thèse compare également le modèle proposé avec d'autres modèles existants, tout en examinant la qualité de l'ajustement de certaines propriétés statistiques sur des traces réelles de la charge de travail. Finalement, ce travail propose une approche probabiliste de provisionnement des ressources, basée sur le Principe de Grandes Déviations (LDP). LDP caractérise statistiquement les effets de buzz, qui causent de la volatilité extrême de la charge de travail. Cette analyse exploite les informations obtenues en utilisant le LPD du système VoD pour la définition des politiques de gestion des ressources. Ces politiques peuvent être intéressantes pour toutes les acteurs dans le nouveau contexte de l'informatique en nuage. / There are some new challenges in system administration and design to optimize the resource management for a cloud based application. Some applications demand stringent performance requirements (e.g. delay and jitter bounds), while some applications exhibit bursty (volatile) workloads. This thesis proposes an epidemic model inspired (and continuous time Markov Chain based) framework, which can reproduce workload volatility namely the "buzz effects" (when there is a sudden increase of a content popularity) of a Video on Demand (VoD) system. Two estimation procedures (heuristic and a Markov Chain Monte Carlo (MCMC) based approach) have also been proposed in this work to calibrate the model against workload traces. Obtained model parameters from the calibration procedures reveal some interesting property of the model. Based on numerical simulations, precisions of both procedures have been analyzed, which show that both of them perform reasonably. However, the MCMC procedure outperforms the heuristic approach. This thesis also compares the proposed model with other existing models examining the goodness-of-fit of some statistical properties of real workload traces. Finally this work suggests a probabilistic resource provisioning approach based on a Large Deviation Principle (LDP). LDP statistically characterizes the buzz effects that causeextreme workload volatility. This analysis exploits the information obtained using the LDP of the VoD system for defining resource management policies. These policies may be of some interest to all stakeholders in the emerging context of cloud networking.

Les algorithmes MCMC sont difficiles à mettre à l'échelle, car ils doivent balayer l'ensemble des données à chaque itération, ce qui interdit leurs applications dans de grands paramètres de données. En gros, tous les algorithmes MCMC évolutifs peuvent être divisés en deux catégories: les méthodes de partage et de conquête et les méthodes de sous-échantillonnage. Le but de ce projet est de réduire le temps de calcul induit par des fonctions complexes ou à grande efficacité. / MCMC algorithms are difficult to scale, since they need to sweep over the whole data set at each iteration, which prohibits their applications in big data settings. Roughly speaking, all scalable MCMC algorithms can be divided into two categories: divide-and-conquer methods and subsampling methods. The aim of this project is to reduce the computing time induced by complex or largelikelihood functions.

La technique des répliques est une technique formidable prenant ses origines de la physique statistique, comme un moyen de calculer l'espérance du logarithme de la constante de normalisation d'une distribution de probabilité à haute dimension. Dans le jargon de physique, cette quantité est connue sous le nom de l’énergie libre, et toutes sortes de quantités utiles, telle que l’entropie, peuvent être obtenue de là par des dérivées. Cependant, ceci est un problème NP-difficile, qu’une bonne partie de statistique computationelle essaye de résoudre, et qui apparaît partout; de la théorie des codes, à la statistique en hautes dimensions, en passant par les problèmes de satisfaction de contraintes. Dans chaque cas, la méthode des répliques, et son extension par (Parisi et al., 1987), se sont prouvées fortes utiles pour illuminer quelques aspects concernant la corrélation des variables de la distribution de Gibbs et la nature fortement nonconvexe de son logarithme negatif. Algorithmiquement, il existe deux principales méthodologies adressant la difficulté de calcul que pose la constante de normalisation: a). Le point de vue statique: dans cette approche, on reformule le problème en tant que graphe dont les nœuds correspondent aux variables individuelles de la distribution de Gibbs, et dont les arêtes reflètent les dépendances entre celles-ci. Quand le graphe en question est localement un arbre, les procédures de message-passing sont garanties d’approximer arbitrairement bien les probabilités marginales de la distribution de Gibbs et de manière équivalente d'approximer la constante de normalisation. Les prédictions de la physique concernant la disparition des corrélations à longues portées se traduise donc, par le fait que le graphe soit localement un arbre, ainsi permettant l’utilisation des algorithmes locaux de passage de messages. Ceci va être le sujet du chapitre 4. b). Le point de vue dynamique: dans une direction orthogonale, on peut contourner le problème que pose le calcul de la constante de normalisation, en définissant une chaîne de Markov le long de laquelle, l’échantillonnage converge à celui selon la distribution de Gibbs, tel qu’après un certain nombre d’itérations (sous le nom de temps de relaxation), les échantillons sont garanties d’être approximativement générés selon elle. Afin de discuter des conditions dans lesquelles chacune de ces approches échoue, il est très utile d’être familier avec la méthode de replica symmetry breaking de Parisi. Cependant, les calculs nécessaires sont assez compliqués, et requièrent des notions qui sont typiquemment étrangères à ceux sans un entrainement en physique statistique. Ce mémoire a principalement deux objectifs : i) de fournir une introduction a la théorie des répliques, ses prédictions, et ses conséquences algorithmiques pour les problèmes de satisfaction de constraintes, et ii) de donner un survol des méthodes les plus récentes adressant la transition de phase, prédite par la méthode des répliques, dans le cas du problème k−SAT, à partir du point de vu statique et dynamique, et finir en proposant un nouvel algorithme qui prend en considération la transition de phase en question. / The replica trick is a powerful analytic technique originating from statistical physics as an attempt to compute the expectation of the logarithm of the normalization constant of a high dimensional probability distribution known as the Gibbs measure. In physics jargon this quantity is known as the free energy, and all kinds of useful quantities, such as the entropy, can be obtained from it using simple derivatives. The computation of this normalization constant is however an NP-hard problem that a large part of computational statistics attempts to deal with, and which shows up everywhere from coding theory, to high dimensional statistics, compressed sensing, protein folding analysis and constraint satisfaction problems. In each of these cases, the replica trick, and its extension by (Parisi et al., 1987), have proven incredibly successful at shedding light on keys aspects relating to the correlation structure of the Gibbs measure and the highly non-convex nature of − log(the Gibbs measure()). Algorithmic speaking, there exists two main methodologies addressing the intractability of the normalization constant: a) Statics: in this approach, one casts the system as a graphical model whose vertices represent individual variables, and whose edges reflect the dependencies between them. When the underlying graph is locally tree-like, local messagepassing procedures are guaranteed to yield near-exact marginal probabilities or equivalently compute Z. The physics predictions of vanishing long range correlation in the Gibbs measure, then translate into the associated graph being locally tree-like, hence permitting the use message passing procedures. This will be the focus of chapter 4. b) Dynamics: in an orthogonal direction, we can altogether bypass the issue of computing the normalization constant, by defining a Markov chain along which sampling converges to the Gibbs measure, such that after a number of iterations known as the relaxation-time, samples are guaranteed to be approximately sampled according to the Gibbs measure. To get into the conditions in which each of the two approaches is likely to fail (strong long range correlation, high energy barriers, etc..), it is very helpful to be familiar with the so-called replica symmetry breaking picture of Parisi. The computations involved are however quite involved, and come with a number of prescriptions and prerequisite notions (s.a. large deviation principles, saddle-point approximations) that are typically foreign to those without a statistical physics background. The purpose of this thesis is then twofold: i) to provide a self-contained introduction to replica theory, its predictions, and its algorithmic implications for constraint satisfaction problems, and ii) to give an account of state of the art methods in addressing the predicted phase transitions in the case of k−SAT, from both the statics and dynamics points of view, and propose a new algorithm takes takes these into consideration.