Academic literature on the topic 'Simulation par chaînes de Markov'

Cette thèse propose l'étude et l'application des méthodes de simulation Monte Carlo par chaînes de Markov (MCMC) pour résoudre des problèmes d'estimation en traitement du signal. Les hyptohèses a priori sur les signaux et/ou les modèles de transfert peuvent être prises en compte en utilisant une approche Bayésienne, menant aux estimateurs classiques de type moyenne a posteriori et maximum a posteriori dont le calcul est généralement difficile. Des techniques d'estimation Monte Carlo sont ainsi considérées et implantées par des schémas de simulation par chaînes de Markov. Dans un premier temps, des problèmes d'estimation pour des modèles de séparation de sources sont considérés. Le cas des communications numériques est spécifiquement abordé en étudiant la séparation de signaux sources issus de modulations PSK. Une méthode de séparation fondée sur l'algorithme d'échantillonnage de Gibbs est proposée et illustrée par des simulations numériques. L'algorithme permet de séparer des mélanges sous-déterminés et peut en outre être modifié afin de résoudre d'autres problèmes associés à ce modèle : estimation du nombre d'état des constellations des signaux sources, estimation du nombre de signaux sources. Dans un second temps, un problème d'égalisation est abordé dans le cadre de communications satellitaires. L'approche Bayésienne et son implantation par une méthode d'estimation Monte Carlo permettent de prendre en compte de manière explicite la non-linéarité du système d'amplification à bord du satellite. Une méthode de simulation séquentielle de type filtrage particulaire est ainsi proposée pour égaliser la chaîne de transmission complète de manière aveugle et robuste<br>This thesis proposes to study and apply Markov chain Monte-Carlo (MCMC) simulation methods for solving estimation problems arising in the field of signal processing. Prior hypothesis on signals and/or on transfert function models can be taken into account thanks to a Bayesian approach leading to classical estimators, posterior mean and maximum a posteriori for instance, whose computation is generally difficult. Monte-Carlo estimation techniques are thus considered and implemented with Markov chain simulation schemes. In a first step, estimation problems dealing with source separation models are considered. The case of digital communications is specifically focused on with the study of source signals associated to PSK modulations. A separation method based on the Gibbs sampling algorithm is proposed and illustrated with numerical experiments. The algorithm makes it possible to separate underdetermined mixtures and can be modified in order to solve other problems associated to this model: estimation of the number of state for the constellations of source signals, estimation of the number of the source signals. In a second step, an equalisation problem is tackled in the context of satellite communications. The Bayesian approach and its implementation through a Monte-Carlo estimation technique make it possible to take into account explicitely the nonlinearity of the amplification stage in the satellite. A sequential simulation method based on particle filtering is then proposed for equalising blindly and robustly the complete transmission chain

L'objet de cette thèse est d'établir un cadre d'analyse des données recueillies sur les véhicules en vue de les mettre en correspondance avec des comportements. Pour cela, nous avons défini le modèle Semi-Markovien caché pondéré pour modéliser les signaux issus des capteurs et établi des résultats théoriques sur les modèles de régressions multi-phasiques dans le cas linéaire et nonlinéaire. Puis, nous avons établi une méthodologie d'analyse de l'activité basée sur un apprentissage semi-automatique, et structurée par les résultats des modèles cognitifs du conducteur. Pour valider cette méthodologie, nous avons effectué une expérimentation où furent enregistrées 1209 séquences de conduite. Ces données nous ont permis d'implémenter des modèles de Markov cachées décrivant l'évolution des capteurs associés à des situations de conduite caractérisées par l'objectif, l'infrastructure perçue par le conducteur et la vitesse initiale. Les modèles générés nous permettent dès lors de catégoriser, avec un taux satisfaisant, à quelle situation ou à quel groupe de situation appartient une séquence inconnue. Par ailleurs, nous illustrons l'utilité des modèles markoviens conjugués aux modèles multi-phasiques pour la recherche automatique de situation dans un ensemble de données. Mot clés libres: modèle Semi-Markovien cachés pondéré, modèles multi-phasiques, apprentissage semi-automatique, catégorisation du comportement du conducteur, analyse de l'activité de conduite analyse hiérarchique

Les matériaux granulaires sont omniprésents, ils se trouvent aussi bien dans la nature que dans quelques applications industrielles. Parmi les applications industrielles utilisant les matériaux granulaires, on cite le mélange des poudres dans les industries agro-alimentaires, chimiques, métallurgiques et pharmaceutiques. La caractérisation et l'étude du comportement de ces matériaux sont nécessaires pour la compréhension de plusieurs phénomènes naturels comme le mouvement des dunes et les avalanches de neige, et de processus industriels tel que l'écoulement et le mélange des grains dans un mélangeur. Le comportement varié des matériaux granulaires les rend inclassables parmi les trois états de la matière : solide, liquide et gazeux. Ceci a fait dire qu'il s'agit d'un ``quatrième état'' de la matière, situé entre solide et liquide. L'objectif de ce travail est de concevoir et de mettre en oeuvre des méthodes efficaces d'éléments discrets pour la simulation et l'analyse des processus de mélange et de ségrégation des particules ellipsoïdales dans des mélangeurs culbutants industriels tels que le mélangeur à cerceaux. Dans la DEM l'étape la plus critique en terme de temps CPU est celle de la détection et de résolution de contact. Donc pour que la DEM soit efficace il faut optimiser cette étape. On se propose de combiner le modèle du potentiel géométrique et la condition algébrique de contact entre deux ellipsoïdes proposée par Wang et al., pour l'élaboration d'un algorithme efficace de détection de contact externe entre particules ellipsoïdales. Puis de de prouver un résultat théorique et d'élaborer un algorithme pour le contact interne. D'autre part, le couplage DEM-chaîne de Markov permet de diminuer très sensiblement le temps de simulation en déterminant la matrice de transition à partir d'une simulation à courte durée puis en calculant l'état du système à l'aide du modèle de chaîne de Markov. En effet, en utilisant la théorie des matrices strictement positives et en se basant sur le théorème de Perron-Frobenius on peut approximer le nombre de transitions nécessaires pour la convergence vers un état donné.

Cette thèse porte sur le problème de l'échantillonnage en grande dimension et est basée sur l'algorithme de Langevin non ajusté (ULA).Dans une première partie, nous proposons deux extensions d'ULA et fournissons des garanties de convergence précises pour ces algorithmes. ULA n'est pas applicable lorsque la distribution cible est à support compact; grâce à une régularisation de Moreau Yosida, il est néanmoins possible d'échantillonner à partir d'une distribution suffisamment proche de la distribution cible. ULA diverge lorsque les queues de la distribution cible sont trop fines; en renormalisant correctement le gradient, cette difficulté peut être surmontée.Dans une deuxième partie, nous donnons deux applications d'ULA. Nous fournissons un algorithme pour estimer les constantes de normalisation de densités log concaves à partir d'une suite de distributions dont la variance augmente graduellement. En comparant ULA avec la diffusion de Langevin, nous développons une nouvelle méthode de variables de contrôle basée sur la variance asymptotique de la diffusion de Langevin.Dans une troisième partie, nous analysons Stochastic Gradient Langevin Dynamics (SGLD), qui diffère de ULA seulement dans l'estimation stochastique du gradient. Nous montrons que SGLD, appliqué avec des paramètres habituels, peut être très éloigné de la distribution cible. Cependant, avec une technique appropriée de réduction de variance, son coût calcul peut être bien inférieur à celui d'ULA pour une précision similaire<br>This thesis focuses on the problem of sampling in high dimension and is based on the unadjusted Langevin algorithm (ULA).In a first part, we suggest two extensions of ULA and provide precise convergence guarantees for these algorithms. ULA is not feasible when the target distribution is compactly supported; thanks to a Moreau Yosida regularization, it is nevertheless possible to sample from a probability distribution close enough to the distribution of interest. ULA diverges when the tails of the target distribution are too thin; by taming appropriately the gradient, this difficulty can be overcome.In a second part, we give two applications of ULA. We provide an algorithm to estimate normalizing constants of log concave densities based on a sequence of distributions with increasing variance. By comparison of ULA with the Langevin diffusion, we develop a new control variates methodology based on the asymptotic variance of the Langevin diffusion.In a third part, we analyze Stochastic Gradient Langevin Dynamics (SGLD), which differs from ULA only in the stochastic estimation of the gradient. We show that SGLD, applied with usual parameters, may be very far from the target distribution. However, with an appropriate variance reduction technique, its computational cost can be much lower than ULA for the same accuracy

Le nombre des personnes âgées ne cesse d’augmenter dans le monde d’où l’enjeu de les aider à continuer de vivre chez eux et de vieillir en bonne santé. Cette thèse s’inscrit dans cette problématique de santé publique et propose la détection du changement de comportement de la personne en se basant sur l’enregistrement des activités au domicile par des capteurs de profondeur à bas coût qui garantissent l’anonymat et qui fonctionnent de façon autonome de jour comme de nuit. Après une étude initiale associant la classification des images par des approches de machine learning, une méthode basée sur les réseaux de neurones profonds ResNet-18 a été proposée pour la détection de la chute et la détection des postures. Cette approche a donné des résultats satisfaisants avec une précision globale de 93,44% et une sensibilité globale de 93.24%. La détection des postures permet de suivre les changements de comportement qui sont synonymes de la perte de la routine. Deux stratégies ont été déployées pour le suivi du maintien de la routine. La première examine la succession des activités dans la journée en établissant une distance d’édition ou une déformation dynamique de la journée, l’autre consiste à classer la journée en routine et non-routine en associant des approches supervisées (k-moyennes et k-modes), non supervisées (Random Forest) ou les connaissances a priori sur la journée routine de la personne. Ces stratégies ont été évaluées à la fois sur des données réelles enregistrées en EHPAD chez deux personnes fragiles et à la fois sur des données simulées créés pour combler le manque de données réelles. Elles ont montré la possibilité de détecter différents scénarios de changement de comportement (brusque, progressif, récurrent) et prouvent que les capteurs de profondeur peuvent être utilisés en EHPAD ou dans l’habitat d’une personne âgée<br>The number of elderly people in the world is constantly increasing, hence the challenge of helping them to continue to live at home and ageing in good health. This PhD takes part in this public health issue and proposes the detection of the person behavior change based on the recording of activities in the home by low-cost depth sensors that guarantee anonymity and that operate autonomously day and night. After an initial study combining image classification by machine learning approaches, a method based on Resnet-18 deep neural networks was proposed for fall and posture position detection. This approach gave good results with a global accuracy of 93.44% and a global sensitivity of 93.24%. The detection of postures makes possible to follow the state of the person and in particular the behavior changes which are assumed to be the routine loss. Two strategies were deployed to monitor the routine. The first one examines the succession of activities in the day by computing an edit distance or a dynamic deformation of the day, the other one consists in classifying the day into routine and non-routine by combining supervised (k-means and k-modes), unsupervised (Random Forest) or a priori knowledge about the person's routine. These strategies were evaluated both on real data recorded in EHPAD in two frail people and on simulated data created to fill the lack of real data. They have shown the possibility to detect different behavioral change scenarios (abrupt, progressive, recurrent) and prove that depth sensors can be used in EHPAD or in the home of an elderly person

Les systèmes pair-à-pair à grande échelle ont été proposés comme un moyen fiable d'assurer un stockage de données à faible coût. Pour assurer la pérennité des données sur une période très longue, ces systèmes codent les données des utilisateurs comme un ensemble de fragments redondants qui sont distribués entre différents pairs du réseau. Un mécanisme de réparation est nécessaire pour faire face au comportement dynamique et non fiable des pairs. Ce mécanisme reconstruit en permanence les fragments de redondance manquants. Le système dépend de nombreux paramètres de configuration qui doivent être bien réglés, comme le facteur de redondance, sa politique de placement et la fréquence de réparation des données. Ces paramètres affectent la quantité de ressources, telles que la bande passante et l'espace de stockage, nécessaires pour obtenir un niveau souhaité de fiabilité, c'est-à-dire, une certaine probabilité de perdre des données. Cette thèse vise à fournir des outils permettant d'analyser et de prédire la performance de systèmes de stockage de données à grande échelle en général. Nous avons utilisé ces outils pour analyser l'impact de différents choix de conception du système sur différentes mesures de performance. Par exemple, la consommation de bande passante, l'espace de stockage et la probabilité de perdre des données, doivent être aussi faibles que possible. Différentes techniques sont étudiées et appliquées. Tout d'abord, nous décrivons un modèle simple par chaîne de Markov qui exploit la dynamique d'un système de stockage sous l'effet de défaillance des pairs et de réparation de données. Puis nous établissons des formules mathématiques closes qui donnent de bonnes approximations du modèle. Ces formules nous permettent de comprendre les interactions entre les paramètres du système. En effet, un mécanisme de réparation paresseux (lazy repair) est étudié et nous décrivons comment régler les paramètres du système pour obtenir une utilisation efficace de la bande passante. Nous confirmons en comparant à des simulations que ce modèle donne des approximations correctes du comportement moyen du système, mais ne parvient pas à capturer ses importantes variations au fil du temps. Nous proposons ensuite un nouveau modèle stochastique basé sur une approximation fluide pour saisir les écarts par rapport au comportement moyen. Ces variations qui sont généralement négligées par les travaux antérieurs, sont très im- portants pour faire une bonne estimation des ressources nécessaires au système. De plus, nous étudions plusieurs autres aspects d'un système de stockage distribué: nous utilisons un modèle de files d'attente pour calculer le temps de réparation pour un système avec bande passante limitée; nous étudions un système de codage hybride: en mixant les codes d'éffacement avec la simple réplication des données; enfin, nous étudions l'impact des différentes façons de distribuer des fragments de données entre les pairs, i.e., les stratégies des placements.

Les méthodes de Monte Carlo (MC) sont des méthodes probabilistes basées sur l'utilisation des nombres aléatoires dans des simulations répétées afin d'estimer un paramètre. Leurs analogues déterministes sont appelées méthodes Quasi-Monte Carlo (QMC). Leur principe consiste à remplacer les points pseudo-aléatoires par des points quasi-aléatoires déterministes (ou points à discrépance faible). Dans cette thèse, nous proposons et analysons des algorithmes du type QMC pour la simulation des chaînes de Markov multidimensionnelles. Après avoir rappelé le principe et les propriétés des méthodes MC et QMC, nous introduisons quelques modèles financiers simples, qui serviront dans la suite pour tester l'efficacité des algorithmes proposés. Nous détaillons particulièrement des modèles où l'on connait la solution exacte, afin de pouvoir vérifier dans la suite la validité des méthodes d'approximation, et comparer leur efficacité. Dans un premier temps, nous nous intéressons à la simulation des chaînes de Markov à espace d'états discret de dimension S. Nous proposons un schéma itératif QMC permettant l'approximation de la distribution de la chaîne à tout instant. Ce schéma utilise une suite (T,S+1) en base B pour les transitions. De plus, il faut ordonner les copies de la chaine suivant leurs composantes successives à chaque itération. Nous étudions la convergence du schéma en faisant des hypothèses sur la matrice de transition. Nous validons l'étude théorique par des expériences numériques issues de la finance. Les résultats obtenus permettent d'affirmer que le nouvel algorithme est plus efficace que le schéma MC traditionnel. Nous nous intéressons ensuite à la simulation des chaînes de Markov à espace d'états multidimensionnel continu. Nous proposons un schéma QMC d'approximation de la distribution de la chaîne à tout instant. Il utilise le même algorithme de tri des états simulés que dans le cas discret. Nous étudions la convergence de l'algorithme dans le cas unidimensionnel puis multidimensionnel en faisant des hypothèses supplémentaires sur les transitions. Nous illustrons la convergence de l'algorithme par des expériences numériques; leurs résultats montrent que l'approche QMC converge plus rapidement que la technique Monte Carlo. Dans la dernière partie, nous considérons le problème de l'équation de diffusion dans un milieu hétérogène. Nous utilisons une méthode de marche aléatoire en faisant une correction des pas Gaussiens. Nous mettons au point une variante QMC de cette méthode, en adaptant les idées utilisées pour la simulation des chaines de Markov. Nous testons l'efficacité de l'algorithme en dimensions 1, 2 et 3 sur un problème de diffusion d'ions calcium dans un milieu biologique. Dans toutes les expériences, les résultats des calculs QMC sont de meilleure qualité que ceux des simulations MC. Finalement, nous faisons un bilan du travail effectué et nous proposons quelques perspectives pour des travaux futurs<br>Monte Carlo (MC) methods are probabilistic methods based on the use of random numbers in repeated simulations to estimate some parameter. Their deterministic versions are called Quasi-Monte Carlo (QMC) methods. The idea is to replace pseudo-random points by deterministic quasi-random points (also known as low-discrepancy point sets or sequences). In this work, we propose and analyze QMC-based algorithms for the simulation of multidimensional Markov chains. The quasi-random points we use are (T,S)-sequences in base B. After recalling the principles of MC and QMC methods and their main properties, we introduce some plain financial models, to serve in the following as numerical examples to test the convergence of the proposed schemes. We focus on problems where the exact solution is known, in order to be able to compute the error and to compare the efficiency of the various schemes In a first part, we consider discrete-time Markov chains with S-dimensional state spaces. We propose an iterative QMC scheme for approximating the distribution of the chain at any time. The scheme uses a (T,S+1)-sequence in base b for the transitions. Additionally, one needs to re-order the copies of the chain according to their successive components at each time-step. We study the convergence of the scheme by making some assumptions on the transition matrix. We assess the accuracy of the QMC algorithm through financial examples. The results show that the new technique is more efficient than the traditional MC approach. Then, we propose a QMC algorithm for the simulation of Markov chains with multidimensional continuous state spaces. The method uses the same re-ordering step as in the discrete setting. We provide convergence results in the case of one dimensional chains and then in the case of multidimensional chains, by making additional assumptions. We illustrate the convergence of the algorithm through numerical experiments. The results show that the new method converges faster than the MC algorithm. In the last part, we consider the problem of the diffusion equation in a spatially nonhomogeneous medium. We use a random walk algorithm, in conjunction with a correction of the Gaussian Steplength. We write a QMC variant of the algorithm, by adapting the principles seen for the simulation of the Markov chains. We test the method in dimensions 1, 2 and 3 on a problem involving the diffusion of calcium ions in a biological medium. In all the simulations, the results of QMC computations show a strong improvement over MC outcomes. Finally, we give some perspectives and directions for future work

Bien qu’il ne soit pas pratique d’étudier la population dans de nombreux domaines et applications, l’échantillonnage est une méthode nécessaire permettant d’inférer l’information.Cette thèse est consacrée au développement des algorithmes d’échantillonnage probabiliste pour déduire l’ensemble de la population lorsqu’elle est trop grande ou impossible à obtenir.Les techniques Monte Carlo par chaîne de markov (MCMC) sont l’un des outils les plus importants pour l’échantillonnage à partir de distributions de probabilités surtout lorsque ces distributions ont des constantes de normalisation difficiles à évaluer.Le travail de cette thèse s’intéresse principalement aux techniques d’échantillonnage pour les graphes. Deux méthodes pour échantillonner des sous-arbres uniformes à partir de graphes en utilisant les algorithmes de Metropolis-Hastings sont présentées dans le chapitre 2. Les méthodes proposées visent à échantillonner les arbres selon une distribution à partir d’un graphe où les sommets sont marqués. L’efficacité de ces méthodes est prouvée mathématiquement. De plus, des études de simulation ont été menées et ont confirmé les résultats théoriques de convergence vers la distribution d’équilibre.En continuant à travailler sur l’échantillonnage des graphes, une méthode est présentée au chapitre 3 pour échantillonner des ensembles de sommets similaires dans un graphe arbitraire non orienté en utilisant les propriétés des processus des points permanents PPP. Notre algorithme d’échantillonnage des ensembles de k sommets est conçu pour surmonter le problème de la complexité de calcul lors du calcul du permanent par échantillonnage d’une distribution conjointe dont la distribution marginale est un kPPP.Enfin, dans le chapitre 4, nous utilisons les définitions des méthodes MCMC et de la vitesse de convergence pour estimer la bande passante du noyau utilisée pour la classification dans l’apprentissage machine supervisé. Une méthode simple et rapide appelée KBER est présentée pour estimer la bande passante du noyau de la fonction de base radiale RBF en utilisant la courbure moyenne de Ricci de graphes<br>While it is impractical to study the population in many domains and applications, sampling is a necessary method allows to infer information. This thesis is dedicated to develop probability sampling algorithms to infer the whole population when it is too large or impossible to be obtained. Markov chain Monte Carlo (MCMC) techniques are one of the most important tools for sampling from probability distributions especially when these distributions haveintractable normalization constants.The work of this thesis is mainly interested in graph sampling techniques. Two methods in chapter 2 are presented to sample uniform subtrees from graphs using Metropolis-Hastings algorithms. The proposed methods aim to sample trees according to a distribution from a graph where the vertices are labelled. The efficiency of these methods is proved mathematically. Additionally, simulation studies were conducted and confirmed the theoretical convergence results to the equilibrium distribution.Continuing to the work on graph sampling, a method is presented in chapter 3 to sample sets of similar vertices in an arbitrary undirected graph using the properties of the Permanental Point processes PPP. Our algorithm to sample sets of k vertices is designed to overcome the problem of computational complexity when computing the permanent by sampling a joint distribution whose marginal distribution is a kPPP.Finally in chapter 4, we use the definitions of the MCMC methods and convergence speed to estimate the kernel bandwidth used for classification in supervised Machine learning. A simple and fast method called KBER is presented to estimate the bandwidth of the Radial basis function RBF kernel using the average Ricci curvature of graphs