Letteratura scientifica selezionata sul tema "Hidden semi-Markov chains"

Being one of the fastest growing fields of engineering, wireless has gained the attention of researchers and commercial businesses all over the world. Extensive research is underway to improve the performance of existing systems and to introduce cutting edge wireless technologies that can make high speed wireless communications possible. The first part of this dissertation deals with discrete channel models that are used for simulating error traces produced by wireless channels. Most of the time, wireless channels have memory and we rely on discrete time Markov models to simulate them. The primary advantage of using these models is rapid experimentation and prototyping. Efficient estimation of the parameters of a Markov model (including its number of states) is important to reproducing and/or forecasting channel statistics accurately. Although the parameter estimation of Markov processes has been studied extensively, its order estimation problem has been addressed only recently. In this report, we investigate the existing order estimation techniques for Markov chains and hidden Markov models. Performance comparison with semi-hidden Markov models is also discussed. Error source modeling in slow and fast fading conditions is also considered in great detail. Cognitive Radio is an emerging technology in wireless communications that can improve the utilization of radio spectrum by incorporating some intelligence in its design. It can adapt with the environment and can change its particular transmission or reception parameters to execute its tasks without interfering with the licensed users. One problem that CR network usually faces is the difficulty in detecting and classifying its low power signal that is present in the environment. Most of the time traditional energy detection techniques fail to detect these signals because of their low SNRs. In the second part of this thesis, we address this problem by using higher order statistics of incoming signals and classifying them by using the pattern recognition capabilities of HMMs combined with cased-based learning approach. This dissertation also deals with dynamic spectrum allocation in cognitive radio using HMMs. CR networks that are capable of using frequency bands assigned to licensed users, apart from utilizing unlicensed bands such as UNII radio band or ISM band, are also called Licensed Band Cognitive Radios. In our novel work, the dynamic spectrum management or dynamic frequency allocation is performed by the help of HMM predictions. This work is based on the idea that if Markov models can accurately model spectrum usage patterns of different licensed users, then it should also correctly predict the spectrum holes and use these frequencies for its data transmission. Simulations have shown that HMMs prediction results are quite accurate and can help in avoiding CR interference with the primary licensed users and vice versa. At the same time, this helps in sending its data over these channels more reliably.
Ph. D.

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

Le contexte de la thèse est celui du quantified-self, un mouvement né en Californie qui consiste à mieux se connaître en mesurant les données relatives à son corps et à ses activités. Les travaux de recherche ont consisté à développer des algorithmes d'analyse des signaux d'un capteur IMU (\textit{Inertial Measurement Unit}) placé sur la jambe pour reconnaître différentes activités de mouvement telles que la marche, la course, la montée d’escalier.... Ces activités sont reconnaissables grâce à la forme des signaux d'accélération et de vitesse angulaire du capteur, tous triaxiaux, pendant le mouvement des jambes lors du cycle de marche. Pour résoudre ce problème de reconnaissance, les travaux de thèse ont permis la construction d'un modèle de chaîne de Markov cachée particulier, appelé chaîne triplet semi-Markov, qui combine un modèle semi-Markov et un modèle de mélange gaussien dans un modèle de Markov triplet. Ce nouveau modèle est adapté à la fois à la nature du cycle de marche et à l'enchaînement des activités que l’on peut réaliser dans la vie quotidienne. Pour adapter les paramètres du modèle aux différences de morphologie et de comportement humain, nous avons développé des algorithmes d'estimation des paramètres en ligne et hors ligne.Pour établir les performances d'apprentissage et de classification des algorithmes, nous avons mené des expériences sur la base d'enregistrements recueillis pendant la thèse et d'un ensemble de données publiques. Les résultats sont systématiquement comparés aux algorithmes de reconnaissance actuels
The thesis context is that of the quantified self, a movement born in California that consists in getting to know oneself better by measuring data relating to one’s body and activities. The research work consisted in developing algorithms for analyzing signals from an IMU (Inertial Measurement Unit) sensor placed on the leg to recognize different movement activities such as walking, running, stair climbing... These activities are recognizable by the shape of the sensor’s acceleration and angular velocity signals, both tri-axial, during leg movement and gait cycle.To address the recognition problem, the thesis work resulted in the construction of a particular hidden Markov chain, called semi-triplet Markov chain, which combines a semi-Markov model and a Gaussian mixture model in a triplet Markov model. This model is both adapted to the nature of the gait cycle, and to the sequence of activities as it can be carried out in daily life. To adapt the model parameters to the differences in human morphology and behavior, we have developed algorithms for estimating parameters both off-line and on-line.To establish the classification and learning performance of the algorithms, we conducted experiments on the basis of recordings collected during the thesis and on public dataset. The results are systematically compared with state-of-the-art algorithms

Le premier chapitre présente les axes principaux de recherche ainsi que les problèmes traités dans cette thèse. Plus précisément, il expose une synthèse sur le sujet, en y donnant les propriétés essentielles pour la bonne compréhension de cette étude, accompagnée des références bibliographiques les plus importantes. Il présente également les motivations de ce travail en précisant les contributions originales dans ce domaine. Le deuxième chapitre est composé d’une recherche originale sur l’estimation du risque sismique, dans la zone du nord de la mer Egée (Grèce), en faisant usage de la théorie des processus semi-markoviens à temps continue. Il propose des estimateurs des mesures importantes qui caractérisent les processus semi-markoviens, et fournit une modélisation dela prévision de l’instant de réalisation d’un séisme fort ainsi que la probabilité et la grandeur qui lui sont associées. Les chapitres 3 et 4 comprennent une première tentative de modélisation du processus de génération des séismes au moyen de l’application d’un temps discret des modèles cachés markoviens et semi-markoviens, respectivement. Une méthode d’estimation non paramétrique est appliquée, qui permet de révéler des caractéristiques fondamentales du processus de génération des séismes, difficiles à détecter autrement. Des quantités importantes concernant les niveaux des tensions sont estimées au moyen des modèles proposés. Le chapitre 5 décrit les résultats originaux du présent travail à la théorie des processus stochastiques, c’est- à-dire l’étude et l’estimation du « Intensité du temps d’entrée en temps discret (DTIHT) » pour la première fois dans des chaînes semi-markoviennes et des chaînes de renouvellement markoviennes cachées. Une relation est proposée pour le calcul du DTIHT et un nouvel estimateur est présenté dans chacun de ces cas. De plus, les propriétés asymptotiques des estimateurs proposés sont obtenues, à savoir, la convergence et la normalité asymptotique. Le chapitre 6 procède ensuite à une étude de comparaison entre le modèle markovien caché et le modèle semi-markovien caché dans un milieu markovien et semi-markovien en vue de rechercher d’éventuelles différences dans leur comportement stochastique, déterminé à partir de la matrice de transition de la chaîne de Markov (modèle markovien caché) et de la matrice de transition de la chaîne de Markov immergée (modèle semi-markovien caché). Les résultats originaux concernent le cas général où les distributions sont considérées comme distributions des temps de séjour ainsi que le cas particulier des modèles qui sont applique´s dans les chapitres précédents où les temps de séjour sont estimés de manière non-paramétrique. L’importance de ces différences est spécifiée à l’aide du calcul de la valeur moyenne et de la variance du nombre de sauts de la chaîne de Markov (modèle markovien caché) ou de la chaîne de Markov immergée (modèle semi-markovien caché) pour arriver dans un état donné, pour la première fois. Enfin, le chapitre 7 donne des conclusions générales en soulignant les points les plus marquants et des perspectives pour développements futurs
The first chapter describes the definition of the subject under study, the current state of science in this area and the objectives. In the second chapter, continuous-time semi-Markov models are studied and applied in order to contribute to seismic hazard assessment in Northern Aegean Sea (Greece). Expressions for different important indicators of the semi- Markov process are obtained, providing forecasting results about the time, the space and the magnitude of the ensuing strong earthquake. Chapters 3 and 4 describe a first attempt to model earthquake occurrence by means of discrete-time hidden Markov models (HMMs) and hidden semi-Markov models (HSMMs), respectively. A nonparametric estimation method is followed by means of which, insights into features of the earthquake process are provided which are hard to detect otherwise. Important indicators concerning the levels of the stress field are estimated by means of the suggested HMM and HSMM. Chapter 5 includes our main contribution to the theory of stochastic processes, the investigation and the estimation of the discrete-time intensity of the hitting time (DTIHT) for the first time referring to semi-Markov chains (SMCs) and hidden Markov renewal chains (HMRCs). A simple formula is presented for the evaluation of the DTIHT along with its statistical estimator for both SMCs and HMRCs. In addition, the asymptotic properties of the estimators are proved, including strong consistency and asymptotic normality. In chapter 6, a comparison between HMMs and HSMMs in a Markov and a semi-Markov framework is given in order to highlight possible differences in their stochastic behavior partially governed by their transition probability matrices. Basic results are presented in the general case where specific distributions are assumed for sojourn times as well as in the special case concerning the models applied in the previous chapters, where the sojourn time distributions are estimated non-parametrically. The impact of the differences is observed through the calculation of the mean value and the variance of the number of steps that the Markov chain (HMM case) and the EMC (HSMM case) need to make for visiting for the first time a particular state. Finally, Chapter 7 presents concluding remarks, perspectives and future work

This chapter provides an introduction to large deviation theory. It begins with an overview of the motivatio n for the problem under study, focusing on probability distributions and how to construct an empirical distribution. It then considers the notion of a lower semi-continuous function and that of a lower semi-continuous relaxation before discussing the large deviation property for i.i.d. samples. In particular, it describes Sanov's theorem for a finite alphabet and proceeds by analyzing large deviation property for Markov chains, taking into account stationary distributions, entropy and relative entropy rates, the rate function for doubleton frequencies, and the rate function for singleton frequencies.

Trajectory-User Linking (TUL) is an essential task in Geo-tagged social media (GTSM) applications, enabling personalized Point of Interest (POI) recommendation and activity identification. Existing works on mining mobility patterns often model trajectories using Markov Chains (MC) or recurrent neural networks (RNN) -- either assuming independence between non-adjacent locations or following a shallow generation process. However, most of them ignore the fact that human trajectories are often sparse, high-dimensional and may contain embedded hierarchical structures. We tackle the TUL problem with a semi-supervised learning framework, called TULVAE (TUL via Variational AutoEncoder), which learns the human mobility in a neural generative architecture with stochastic latent variables that span hidden states in RNN. TULVAE alleviates the data sparsity problem by leveraging large-scale unlabeled data and represents the hierarchical and structural semantics of trajectories with high-dimensional latent variables. Our experiments demonstrate that TULVAE improves efficiency and linking performance in real GTSM datasets, in comparison to existing methods.