Academic literature on the topic 'Semi-chaînes de Markov cachées'

It was recently proved by Jelenković and Radovanović (2004) that the least-recently-used (LRU) caching policy, in the presence of semi-Markov-modulated requests that have a generalized Zipf's law popularity distribution, is asymptotically insensitive to the correlation in the request process. However, since the previous result is asymptotic, it remains unclear how small the cache size can become while still retaining the preceding insensitivity property. In this paper, assuming that requests are generated by a nearly completely decomposable Markov-modulated process, we characterize the critical cache size below which the dependency of requests dominates the cache performance. This critical cache size is small relative to the dynamics of the modulating process, and in fact is sublinear with respect to the sojourn times of the modulated chain that determines the dependence structure.

It was recently proved by Jelenković and Radovanović (2004) that the least-recently-used (LRU) caching policy, in the presence of semi-Markov-modulated requests that have a generalized Zipf's law popularity distribution, is asymptotically insensitive to the correlation in the request process. However, since the previous result is asymptotic, it remains unclear how small the cache size can become while still retaining the preceding insensitivity property. In this paper, assuming that requests are generated by a nearly completely decomposable Markov-modulated process, we characterize the critical cache size below which the dependency of requests dominates the cache performance. This critical cache size is small relative to the dynamics of the modulating process, and in fact is sublinear with respect to the sojourn times of the modulated chain that determines the dependence structure.

Dans la première partie de ma thèse je me suis intéressé au modèle semi-markovien à temps discret et à l'estimation non-paramétrique associée. Les résultats obtenus sont appliqués pour déduire des estimateurs de la fiabilité des systèmes et des mesures associées. Les propriétés asymptotiques des estimateurs sont étudiées. Un exemple illustre le calcul pratique des mesures de la fiabilité. La deuxième partie de ma thèse est consacrée à l'estimation des modèles semi-markoviens cachés. Les propriétés asymptotiques des estimateurs sont étudiées et un algorithme EM pour obtenir les estimateurs est proposé. Une application en génétique pour l'estimation des îlots CpG dans une séquence d'ADN illustre l'intérêt de nos recherches
The first part of my thesis concerns the discrete time semi-Markov models and the associated nonparametric estimation. The obtained results are used for deriving estimators of the systems reliability and of the associated measures. The asymptotic properties of the estimators are studied. An example illustrates how to practically compute the reliability indicators. The second part of my thesis is devoted to the estimation of hidden semi-Markov models. The asymptotic properties of the estimators are studied and an EM algorithm is proposed. An application in genetics for detecting the CpG islands in a DNA sequence shows the interest of our researches

Dans cette thèse, on considère une chaîne de Markov $(X_i)$ à espace d'états continu que l'on suppose récurrente positive et stationnaire. L'objectif est d'estimer la densité de transition $\Pi$ définie par $\Pi(x,y)dy=P(X_{i+1}\in dy|X_i=x)$. On utilise la sélection de modèles pour construire des estimateurs adaptatifs. On se place dans le cadre minimax sur $L^2$ et l'on s'intéresse aux vitesses de convergence obtenues lorsque la densité de transition est supposée régulière. Le risque intégré de nos estimateurs est majoré grâce au contrôle de processus empiriques par une inégalité de concentration de Talagrand. Dans une première partie, on suppose que la chaîne est directement observée. Deux estimateurs différents sont présentés, l'un par quotient, l'autre minimisant un contraste moindres carrés et prenant également en compte l'anisotropie du problème. Dans une deuxième partie, on aborde le cas d'observations bruitées $Y_1,\dots, Y_{n+1}$ où $Y_i=X_i+\varepsilon_i$ avec $(\varepsilon_i)$ un bruit indépendant de la chaîne $(X_i)$. On généralise à ce cas les deux estimateurs précédents. Des simulations illustrent les performances des estimateurs.

Le problème de la restauration est rencontré dans domaines très variés notamment en traitement de signal et de l'image. Il correspond à la récupération des données originales à partir de données observées. Dans le cas de données multidimensionnelles, la résolution de ce problème peut se faire par différentes approches selon la nature des données, l'opérateur de transformation et la présence ou non de bruit. Dans ce travail, nous avons traité ce problème, d'une part, dans le cas des données discrètes en présence de bruit. Dans ce cas, le problème de restauration est analogue à celui de la segmentation. Nous avons alors exploité les modélisations dites chaînes de Markov couples et triplets qui généralisent les chaînes de Markov cachées. L'intérêt de ces modèles réside en la possibilité de généraliser la méthode de calcul de la probabilité à posteriori, ce qui permet une segmentation bayésienne. Nous avons considéré ces méthodes pour des observations bi-dimensionnelles et nous avons appliqué les algorithmes pour une séparation sur des documents issus de manuscrits scannés dans lesquels les textes des deux faces d'une feuille se mélangeaient. D'autre part, nous avons attaqué le problème de la restauration dans un contexte de séparation aveugle de sources. Une méthode classique en séparation aveugle de sources, connue sous l'appellation "Analyse en Composantes Indépendantes" (ACI), nécessite l'hypothèse d'indépendance statistique des sources. Dans des situations réelles, cette hypothèse n'est pas toujours vérifiée. Par conséquent, nous avons étudié une extension du modèle ACI dans le cas où les sources peuvent être statistiquement dépendantes. Pour ce faire, nous avons introduit un processus latent qui gouverne la dépendance et/ou l'indépendance des sources. Le modèle que nous proposons combine un modèle de mélange linéaire instantané tel que celui donné par ACI et un modèle probabiliste sur les sources avec variables cachées. Dans ce cadre, nous montrons comment la technique d'Estimation Conditionnelle Itérative permet d'affaiblir l'hypothèse usuelle d'indépendance en une hypothèse d'indépendance conditionnelle

Le problème de la restauration est rencontré dans domaines très variés notamment en traitement de signal et de l'image. Il correspond à la récupération des données originales à partir de données observées. Dans le cas de données multidimensionnelles, la résolution de ce problème peut se faire par différentes approches selon la nature des données, l'opérateur de transformation et la présence ou non de bruit. Dans ce travail, nous avons traité ce problème, d'une part, dans le cas des données discrètes en présence de bruit. Dans ce cas, le problème de restauration est analogue à celui de la segmentation. Nous avons alors exploité les modélisations dites chaînes de Markov couples et triplets qui généralisent les chaînes de Markov cachées. L'intérêt de ces modèles réside en la possibilité de généraliser la méthode de calcul de la probabilité à posteriori, ce qui permet une segmentation bayésienne. Nous avons considéré ces méthodes pour des observations bi-dimensionnelles et nous avons appliqué les algorithmes pour une séparation sur des documents issus de manuscrits scannés dans lesquels les textes des deux faces d'une feuille se mélangeaient. D'autre part, nous avons attaqué le problème de la restauration dans un contexte de séparation aveugle de sources. Une méthode classique en séparation aveugle de sources, connue sous l'appellation "Analyse en Composantes Indépendantes" (ACI), nécessite l'hypothèse d'indépendance statistique des sources. Dans des situations réelles, cette hypothèse n'est pas toujours vérifiée. Par conséquent, nous avons étudié une extension du modèle ACI dans le cas où les sources peuvent être statistiquement dépendantes. Pour ce faire, nous avons introduit un processus latent qui gouverne la dépendance et/ou l'indépendance des sources. Le modèle que nous proposons combine un modèle de mélange linéaire instantané tel que celui donné par ACI et un modèle probabiliste sur les sources avec variables cachées. Dans ce cadre, nous montrons comment la technique d'Estimation Conditionnelle Itérative permet d'affaiblir l'hypothèse usuelle d'indépendance en une hypothèse d'indépendance conditionnelle
The restoration problem is usually encountered in various domains and in particular in signal and image processing. It consists in retrieving original data from a set of observed ones. For multidimensional data, the problem can be solved using different approaches depending on the data structure, the transformation system and the noise. In this work, we have first tackled the problem in the case of discrete data and noisy model. In this context, the problem is similar to a segmentation problem. We have exploited Pairwise and Triplet Markov chain models, which generalize Hidden Markov chain models. The interest of these models consist in the possibility to generalize the computation procedure of the posterior probability, allowing one to perform bayesian segmentation. We have considered these methods for two-dimensional signals and we have applied the algorithms to retrieve of old hand-written document which have been scanned and are subject to show through effect. In the second part of this work, we have considered the restoration problem as a blind source separation problem. The well-known "Independent Component Analysis" (ICA) method requires the assumption that the sources be statistically independent. In practice, this condition is not always verified. Consequently, we have studied an extension of the ICA model in the case where the sources are not necessarily independent. We have introduced a latent process which controls the dependence and/or independence of the sources. The model that we propose combines a linear instantaneous mixing model similar to the one of ICA model and a probabilistic model on the sources with hidden variables. In this context, we show how the usual independence assumption can be weakened using the technique of Iterative Conditional Estimation to a conditional independence assumption

Les raies de fréquences éventuellement présentes sur la représentation temps fréquence appelée lofar-gramme permettent à un opérateur sonar de classifier, voire de trajectographier partiellement, les sources d'intérêts. Pour la trajectographie, les raies de fréquences constantes mais décalées par effet Doppler sont utilisées. Pour la classification, c'est l'instabilité des raies fréquentielles qui est source d'information. Dans cette thèse, nous nous sommes intéressés à l'extraction de pistes fréquentielles instables (estimation des pistes présentes dans l'image). Les problèmes fondamentaux de l'extraction sont la méconnaissance du nombre de pistes présentes, de leurs instants d'apparition et de disparition, de leurs rapports signal sur bruit respectifs et la gestion du croisement de pistes. Nous adoptons une approche basée sur une modélisation par chaînes de Markov : chaque piste fréquentielle est supposée suivre une marche aléatoire; l'espace d'état est défini par l'ensemble des canaux fréquentiels de l'analyse spectrale et par un ensemble discret et fini de pentes associées à chaque piste. Le lofargrarnme fournit les mesures. Dans le cas mono¬piste, nous proposons une solution basée sur la version "normalisée" des algorithmes issus do la littérature des chaînes de Markov cachées (Hidden Markov Models) : algorithme de Viterbi (VA), algorithme Forward (F) et Forward-Backward (FB). Dans le cas multi-pistes. Nous avons développé un nouvel algorithme FB "normalisé" dans lequel chaque probabilité est conditionnée par l'événement exclusif suivant : deux pistes fréquentielles ne peuvent être dans le même état simultanément. L'algorithme travaille en deux étapes : 1) les lignes sont extraites du début jusqu'à la fin du lofargrarnme ; 2) les instants de début et de fin de chaque piste sont estimés. Lorsque ces deux dates sont égales, la piste est éliminée. Avec cette stratégie, le nombre de pistes fréquentielles doit être a priori surestimé. Des essais sur des données synthétiques et sur des données réelles ont été menés à bien pour valider nos algorithmes en utilisation opérationnelle
The frequency vs. Time image called lofargram in any passive sonar system is the key of the downstream information processing : the operator will investigate on this representation in order to classify the tar¬gets of interest and/or to track the targets that have generated them by the so-called Target Motion Analysis (TMA). Both need to use frequency lines. For TMA, constant but Doppler-shifted frequencies are necessary. Conversely, for classification, the fluctuations of frequency help the discrimination between targets. In this thesis, we are concerned by unstable frequency line tracker (FLT). The role of such a tracker is to estimate frequency lines. The fundamental problems of FLT come from the unknown num¬ber of lines, their dates of birth and death, their respective SNR's and the case of crossing lines. We propose a method based on Markov Chain modeling : each frequency line is assumed to follow a random walk; the state space is the lofargram frequency cell set vs. A discrete and finite set of slopes. The data are composed by each lofargram line. When one unique line is present, we propose a scaled version of algorithms encountered in Hidden Markov Models (HMM) literature : Viterbi algorithm (VA), Forward (F), Forward-Backward (FB). In case of several frequency lines, we derive a new scaled FB algorithm in which each probability is conditioned by the exclusive event : two lines cannot be simultaneously in the same spot. The algorithm works in two passes : first, the lines are extracted from the beginning to the end of the lofargram; then, we estimate the dates of birth and death of each of them. When those dates are equal, the line is discarded. Therefore, the number of lines must be a priori overestimated. Trials on synthetic but also real data have been conducted and allow us to conclude that this algorithm performs very correctly (in a operational sense)

L'objectif de cette thèse est de proposer différents modèles généralisant le modèle classique des chaînes de Markov cachées à bruit indépendant couramment utilisé en inférence bayésienne de signaux. Les diverses extensions de ce modèle visent à l'enrichir et à prendre en compte différentes propriétés du signal, comme le caractère non gaussien du bruit, ou la nature semi-markovienne du signal caché. Dans un problème d'inférence bayésienne, nous disposons de deux processus aléatoires X et Y , on observe la réalisation y de Y et nous estimons la réalisation cachée x de X. Le lien existant entre les deux processus est modélisé par la distribution de probabilité p(x, y). Dans le modèle classique des chaînes de Markov cachées à bruit indépendant, la distribution p(x) est celle d'une chaîne de Markov et la distribution p(y|x) est celle de marginales indépendantes conditionnellement à x. Bien que ce modèle puisse être utilisé dans de nombreuses applications, il ne parvient pas à modéliser toutes les situations de dépendance. Le premier modèle que nous proposons est de type “chaînes de Markov triplet”, on considère ainsi un troisième processus U tel que le triplet (X, U, Y ) soit une chaîne de Markov. Dans le modèle proposé, ce processus auxiliaire modélise la semi-markovianité de X ; on parvient ainsi à prendre en compte la non markovianité éventuelle du processus caché. Dans un deuxième modèle, nous considérons des observations à dépendance longue et nous proposons un algorithme d'estimation original des paramètres de ce modèle. Nous étudions par ailleurs différents modèles prenant en compte simultanément la semi-markovianité des données cachées, la dépendance longue dans les observations ou la non stationnarité des données cachées. Enfin, la nature non nécessairement gaussienne du bruit est prise en compte via l'introduction des copules. L'intérêt des différents modèles proposés est également validé au travers d'expérimentations. Dans la dernière partie de cette thèse, nous étudions également comment la segmentation obtenue par une méthode bayésienne peut être utilisée dans la détection de cibles dans le signal radar. Le détecteur original que nous implémentons utilise la différence de statistiques entre un signal recu et les signaux recus de son voisinage. Le détecteur ainsi implémenté s'avère donner de meilleurs résultats en présence de fort bruit que le détecteur habituellement utilisé en traitement radar.

Depuis leur création, les codes graphiques constituent un outil d'identification automatique largement exploité en industrie. Cependant, les performances de lecture sont limitées par un flou optique et un flou de mouvement. L'objectif de la thèse est l'optimisation de lecture des codes 1D et 2D en exploitant des modèles de Markov cachés simples et doubles, et des méthodes d'estimation aveugles. En premier lieu, le système de lecture de codes graphiques est modélisé par une chaîne de Markov cachée, et des nouveaux algorithmes pour l'estimation du canal et la détection des symboles sont développés. Ils tiennent compte de la non stationnarité de la chaîne de Markov. De plus une méthode d'estimation de la taille du flou et de sa forme est proposée. La méthode utilise des critères de sélection permettant de choisir le modèle de dégradation le plus adéquat. Enfin nous traitons le problème de complexité qui est particulièrement important dans le cas d'un canal à mémoire longue. La solution proposée consiste à modéliser le canal à mémoire longue par une chaîne de Markov double. Sur la base de ce modèle, des algorithmes offrant un rapport optimisé performance-complexité sont présentés
Since its birth, the technology of barcode is well investigated for automatic identification. When reading, a barcode can be degraded by a blur , caused by a bad focalisation and/ or a camera movement. The goal of this thesis is the optimisation of the receiver of 1D and 2D barcode from hidden and double Markov model and blind statistical estimation approaches. The first phase of our work consists of modelling the original image and the observed one using Hidden Markov model. Then, new algorithms for joint blur estimation and symbol detection are proposed, which take into account the non-stationarity of the hidden Markov process. Moreover, a method to select the most relevant model of the blur is proposed, based on model selection criterion. The method is also used to estimate the blur length. Finally, a new algorithm based on the double Markov chain is proposed to deal with digital communication through a long memory channel. Estimation of such channel is not possible using the classical detection algorithms based on the maximum likelihood due to the prohibitive complexity. New algorithm giving good trade off between complexity and performance is provided

Trois domaines d'application des modèles de chaînes de Markov cachées (HMM) pour l'interprétation des génomes bactériens ont été abordés dans cette thèse sous l'angle de l'utilisation d'approches d'estimation non supervisée. Tout d'abord, l'utilisation d'une méthode de segmentation des séquences d'ADN en régions de composition homogène a permis l'identification de transferts génétiques horizontaux chez Bacillus subtilis ainsi que d'autres niveaux d'hétérogénéités liés aux propriétés biologiques des gènes. Ensuite, un logiciel de prédiction de gènes a été développé. Une attention particulière a été portée à la recherche de très petits gènes. Une trentaine de gènes de taille inférieure à 50 acides aminés a ainsi été ajoutée à la vingtaine de petits gènes connus biologiquement chez B. Subtilis. Enfin, un algorithme de Monte-Carlo par chaîne de Markov (MCMC) est proposé pour la sélection bayésienne de modèles adaptés aux motifs des sites de fixation de l'ARN polymérase
Considering the use of self-training approaches, we developed in this thesis three domains in which we applied HMM for the bacterial genome interpretation. First, a segmentation method of DNA sequences into regions of homogeneous composition enables us to identify horizontal gene transfers on the Bacillus subtilis chromosome and also others heterogeneities levels linked to biological properties of genes. Next we developed a gene prediction software and we especially focused on small genes research. Around 30 genes smaller than 50 amino acids have been added to about 20 small genes previously biologically identified on B. Subtilis. Then we proposed a MCMC algorithm for Bayesian model selection in the context of RNA polymerase binding sites modeling

La premiere partie de cette these est consacree a l'etude du critere odq (order determination quantity) intervenant dans le probleme du choix des ordres d'un processus arma vectoriel stable. La deuxieme partie est consacree a l'etude statistique des chaines de markov cachees (cmc). Nous generalisons l'etude statistique des cmc a espace fini d'etats de baum et petrie au cas non stationnaire. Nous proposons d'autre part un algorithme d'estimation des parametres d'une cmc a espace d'etats quelconque base sur la methode du recuit simule dont nous montrons la convergence p. S. En loi. Nous donnons aussi un principe de grandes deviations pour des moyennes empiriques de fonctions de cmc, que nous relions au probleme de l'estimation des parametres d'une cmc par la methode du recuit simule classique. Nous concluons ce travail par l'estimation des parametres du modele mo-m1 du gene du virus hiv, au moyen de notre algorithme.

La persistance des populations de plantes à fleur repose sur la colonisation et la dormance, cette dernière étant difficile à estimer car la banque de graines est rarement observée. Nous présentons une modélisation par chaînes de Markov cachées couplées qui représente explicitement ces deux processus. Nous l’illustrons sur l’estimation des paramètres clés de la dynamique des plantes adventices.