Letteratura scientifica selezionata sul tema "Chaînes de semi-Markov cachées"

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.

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

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.

Les chaînes de Markov cachées (HMC) sont très utilisées pour la segmentation bayésienne non supervisée de données discrètes. Elles sont particulièrement robustes et, malgré leur simplicité, elles sont suffisamment efficaces dans de nombreuses situations. En particulier pour la segmentation d'image, malgré leur nature unidimensionnelle, elles sont capables, grâce à une transformation des images bidimensionnelles en séquences monodimensionnelles avec le balayage de Peano (PS), de produire des résultats satisfaisants. Cependant, dans certains cas, on peut préférer des modèles plus complexes tels que les champs de Markov cachées (HMF) malgré leur plus grande complexité en temps, pour leurs meilleurs résultats. De plus, les modèles de Markov cachés (les chaînes aussi bien que les champs) ont été étendus aux modèles de Markov couples et triplets, qui peuvent être intéressant dans des cas plus complexes. Par exemple, lorsque le temps de séjour n'est pas géométrique, les chaînes de semi-Markov cachées (HSMC) ont tendance à être plus performantes que les HMC, and on peut dire de même pour les chaînes de Markov évidentielles cachées (HEMC) dans le cas de données non-stationnaires. Dans cette thèse, nous proposons dans un premier lieu une nouvelle chaîne de Markov triplet (TMC), qui étend simultanément les HSMC et les HEMC. Basée sur les chaînes de Markov triplets cachées (HTMC), la nouvelle chaîne de semi-Markov évidentielle cachée (HESMC) peut être utilisée de manière non supervisée, les paramètres étant estimés avec l'algorithme Expectation-Maximization (EM). Nous validons l'intérêt d'un tel modèle grâce à des expériences sur des données synthétiques. Nous nous intéressons ensuite au problème de l'unidimensionnalité des HMC avec PS dans le cadre de la segmentation d'image, en construisant le balayage de Peano contextuel (CPS). Il consiste à associer à chaque indexe dans le HMC obtenu à partir du PS, deux observations sur les pixels qui sont voisins du pixel en question dans l'image considérée, mais qui ne sont pas voisins dans la HMC. On obtient donc trois observations pour chaque point du balayage de Peano, ce qui induit une nouvelle chaîne de Markov conditionnelle (CMC) avec une structure plus complexe, mais dont la loi a posteriori est toujours markovienne. Ainsi, nous pouvons appliquer la méthode classique d'estimation des paramètres : l'algorithme Stochastic Expectation-Maximization (SEM), ainsi qu'étudier la segmentation non supervisée obtenue avec l'estimateur du mode des marginales a posteriori (MPM). Les segmentations supervisées et non supervisées par MPM, basées sur la CMC avec CPS, sont comparés aux HMC avec PS et aux HMF à travers des expériences sur des images synthétiques. Elles améliorent de manière significative les premières, et peuvent même être compétitives avec ces derniers. Finalement, nous étendons les CMC-CPS aux chaînes de Markov couples conditionnelles (CPMC) et à deux chaînes de Markov triplets particulières : les chaînes de Markov évidentielles conditionnelles (CEMC) et les chaînes de semi-Markov conditionnelles (CSMC). Pour chacune de ces extensions, nous montrons qu'elles peuvent améliorer de manière notable leur contrepartie non conditionnelle, ainsi que les CMC-CPS, et peuvent même être compétitives avec les HMF. Par ailleurs, elles permettent de mieux utiliser la généralité du triplet markovien dans le cadre de la segmentation d'image, en contournant les problèmes de temps de calcul considérables qui apparaissent lorsque l'on passe des champs de Markov cachés aux triplets
Hidden Markov chains (HMC) are widely used in unsupervised Bayesian hidden discrete data restoration. They are very robust and, in spite of their simplicity, they are sufficiently efficient in many situations. In particular for image segmentation, despite their mono-dimensional nature, they are able, through a transformation of the bi-dimensional images into mono-dimensional sequences with Peano scan (PS), to give satisfying results. However, sometimes, more complex models such as hidden Markov fields (HMF) may be preferred in spite of their increased time complexity, for their better results. Moreover, hidden Markov models (the chains as well as the fields) have been extended to pairwise and triplet Markov models, which can be of interest in more complex situations. For example, when sojourn time in hidden states is not geometrical, hidden semi-Markov (HSMC) chains tend to perform better than HMC, and such is also the case for hidden evidential Markov chains (HEMC) when data are non-stationary. In this thesis, we first propose a new triplet Markov chain (TMC), which simultaneously extends HSMC and HEMC. Based on hidden triplet Markov chains (HTMC), the new hidden evidential semi-Markov chain (HESMC) model can be used in unsupervised framework, parameters being estimated with Expectation-Maximization (EM) algorithm. We validate its interest through some experiments on synthetic data. Then we address the problem of mono-dimensionality of the HMC with PS model in image segmentation by introducing the “contextual” Peano scan (CPS). It consists in associating to each index in the HMC obtained from PS, two observations on pixels which are neighbors of the pixel considered in the image, but are not its neighbors in the HMC. This gives three observations on each point of the Peano scan, which leads to a new conditional Markov chain (CMC) with a more complex structure, but whose posterior law is still Markovian. Therefore, we can apply the usual parameter estimation method: Stochastic Expectation-Maximization (SEM), as well as study unsupervised segmentation Marginal Posterior Mode (MPM) so obtained. The CMC with CPS based supervised and unsupervised MPM are compared to the classic scan based HMC-PS and the HMF through experiments on artificial images. They improve notably the former, and can even compete with the latter. Finally, we extend the CMC-CPS to Pairwise Conditional Markov (CPMC) chains and two particular triplet conditional Markov chain: evidential conditional Markov chains (CEMC) and conditional semi-Markov chains (CSMC). For each of these extensions, we show through experiments on artificial images that these models can improve notably their non conditional counterpart, as well as the CMC with CPS, and can even compete with the HMF. Beside they allow the generality of markovian triplets to better play its part in image segmentation, while avoiding the substantial time complexity of triplet Markov fields

La restauration statistique non-supervisée de signaux admet d'innombrables applications dans les domaines les plus divers comme économie, santé, traitement du signal, ... Un des problèmes de base, qui est au coeur de cette thèse, est d'estimer une séquence cachée (Xn)1:N à partir d'une séquence observée (Yn)1:N. Ces séquences sont considérées comme réalisations, respectivement, des processus (Xn)1:N et (Yn)1:N. Plusieurs techniques ont été développées pour résoudre ce problème. Le modèle parmi le plus répandu pour le traiter est le modèle dit "modèle de Markov caché" (MMC). Plusieurs extensions de ces modèles ont été proposées depuis 2000. Dans les modèles de Markov couples (MMCouples), le couple (X, Y) est markovien, ce qui implique que p(x|y) est également markovienne (alors que p(x) ne l'est plus nécessairement), ce qui permet les mêmes traitements que dans les MMC. Plus récemment (2002) les MMCouples ont été étendus aux "modèles de Markov triplet" (MMT), dans lesquels on introduit un processus auxiliaire U et suppose que le triplet T = (X, U, Y) est markovien. Là encore il est possible, dans un cadre plus général que celui des MMCouples, d'effectuer des traitements avec une complexité raisonnable. L'objectif de cette thèse est de proposer des nouvelles modélisations faisant partie des MMT et d'étudier leur pertinence et leur intérêt. Nous proposons deux types de nouveautés: (i) Lorsque la chaîne cachée est discrète et lorsque le couple (X, Y) n'est pas stationnaire, avec un nombre fini de "sauts" aléatoires dans les paramètres, l'utilisation récente des MMT dans lesquels les sauts sont modélisés par un processus discret U a donné des résultats très convaincants (Lanchantin, 2006). Notre première idée est d'utiliser cette démarche avec un processus U continu, qui modéliserait des non-stationnarités "continues" de(X, Y). Nous proposons des chaînes et des champs triplets et présentons quelques expériences. Les résultats obtenus dans la modélisation de la non-stationnarité continue semblent moins intéressants que dans le cas discret. Cependant, les nouveaux modèles peuvent présenter d'autres intérêts; en particulier, ils semblent plus efficaces que les modèles "chaînes de Markov cachées" classiques lorsque le bruit est corrélé; (ii) Soit un MMT T = (X, U, Y) tel que X et Y sont continu et U est discret fini. Nous sommes en présence du problème de filtrage, ou du lissage, avec des sauts aléatoires. Dans les modélisations classiques le couple caché (X, U) est markovien mais le couple (U, Y) ne l'est pas, ce qui est à l'origine de l'impossibilité des calculs exacts avec une complexité linéaire en temps. Il est alors nécessaire de faire appel à diverses méthodes approximatives, dont celles utilisant le filtrage particulaire sont parmi les plus utilisées. Dans des modèles MMT récents le couple caché (X, U) n'est pas nécessairement markovien, mais le couple (U, Y) l'est, ce qui permet des traitements exacts avec une complexité raisonnable (Pieczynski 2009). Notre deuxième idée est d'étendre ces derniers modèles aux triplets T = (X, U, Y) dans lesquels les couples (U, Y) sont "partiellement" de Markov. Un tel couple (U, Y) n'est pas de Markov mais U est de Markov conditionnellement àY. Nous obtenons un modèle T = (X, U, Y) plus général, qui n'est plus de Markov, dans lequel le filtrage et le lissage exacts sont possibles avec une complexité linéaire en temps. Quelques premières simulations montrent l'intérêt des nouvelles modélisations en lissage en présence des sauts.

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

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.