Dans cette thèse, nous nous intéressons à l'estimation de paramètres dans les chaînes de Markov cachées. Nous considérons tout d'abord le problème de l'estimation en ligne (sans sauvegarde des observations) au sens du maximum de vraisemblance. Nous proposons une nouvelle méthode basée sur l'algorithme Expectation Maximization appelée Block Online Expectation Maximization (BOEM). Cet algorithme est défini pour des chaînes de Markov cachées à espace d'état et espace d'observations généraux. Dans le cas d'espaces d'états généraux, l'algorithme BOEM requiert l'introduction de méthodes de Monte Carlo séquentielles pour approcher des espérances sous des lois de lissage. La convergence de l'algorithme nécessite alors un contrôle de la norme Lp de l'erreur d'approximation Monte Carlo explicite en le nombre d'observations et de particules. Une seconde partie de cette thèse se consacre à l'obtention de tels contrôles pour plusieurs méthodes de Monte Carlo séquentielles. Nous étudions enfin des applications de l'algorithme BOEM à des problèmes de cartographie et de localisation simultanées. La dernière partie de cette thèse est relative à l'estimation non paramétrique dans les chaînes de Markov cachées. Le problème considéré est abordé dans un cadre précis. Nous supposons que (Xk) est une marche aléatoire dont la loi des incréments est connue à un facteur d'échelle a près. Nous supposons que, pour tout k, Yk est une observation de f(Xk) dans un bruit additif gaussien, où f est une fonction que nous cherchons à estimer. Nous établissons l'identifiabilité du modèle statistique et nous proposons une estimation de f et de a à partir de la vraisemblance par paires des observations. / This document is dedicated to inference problems in hidden Markov models. The first part is devoted to an online maximum likelihood estimation procedure which does not store the observations. We propose a new Expectation Maximization based method called the Block Online Expectation Maximization (BOEM) algorithm. This algorithm solves the online estimation problem for general hidden Markov models. In complex situations, it requires the introduction of Sequential Monte Carlo methods to approximate several expectations under the fixed interval smoothing distributions. The convergence of the algorithm is shown under the assumption that the Lp mean error due to the Monte Carlo approximation can be controlled explicitly in the number of observations and in the number of particles. Therefore, a second part of the document establishes such controls for several Sequential Monte Carlo algorithms. This BOEM algorithm is then used to solve the simultaneous localization and mapping problem in different frameworks. Finally, the last part of this thesis is dedicated to nonparametric estimation in hidden Markov models. It is assumed that the Markov chain (Xk) is a random walk lying in a compact set with increment distribution known up to a scaling factor a. At each time step k, Yk is a noisy observations of f(Xk) where f is an unknown function. We establish the identifiability of the statistical model and we propose estimators of f and a based on the pairwise likelihood of the observations.

We address the problem of learning discrete hidden Markov models from very long sequences of observations. Incremental versions of the Baum-Welch algorithm that approximate the beta-values used in the backward procedure are commonly used for this problem since their memory complexity is independent of the sequence length. However, traditional approaches have two main disadvantages: the approximation of the beta-values deviates far from the real values, and the learning algorithm requires previous knowledge of the topology of the model. This dissertation describes a new incremental Baum-Welch algorithm with a novel backward procedure that improves the approximation of the â-values based on a one-step lookahead in the training sequence and investigates heuristics to prune unnecessary states from an initial complex model. Two new approaches for pruning, greedy and controlled, are introduced and a novel method for identification of ill-conditioned models is presented. Incremental learning of multiple independent observations is also investigated. We justify the new approaches analytically and report empirical results that show they converge faster than the traditional Baum-Welch algorithm using fewer computer resources. Furthermore, we demonstrate that the new learning algorithms converge faster than the previous incremental approaches and can be used to perform online learning of high-quality models useful for classification tasks. Finally, this dissertation explores the use of the new algorithms for anomaly detection in computer systems, that improve our previous research work on detectors based on hidden Markov models integrated into real-world monitoring systems of high-performance computers.

No description available.

No description available.

No description available.

This thesis describes the implementation of a speaker dependent connected-digit recognizer using continuous Hidden Markov Modeling (HMM). The speech recognition system was implemented using MATLAB and on the ADSP-2181, a digital signal processor manufactured by Analog Devices. Linear predictive coding (LPC) analysis was first performed on a speech signal to model the characteristics of the vocal tract filter. A 7 state continuous HMM with 4 mixture density components was used to model each digit. The Viterbi reestimation method was primarily used in the training phase to obtain the parameters of the HMM. Viterbi decoding was used for the recognition phase. The system was first implemented as an isolated word recognizer. Recognition rates exceeding 99% were obtained on both the MATLAB and the ADSP-2181 implementations. For continuous word recognition, several algorithms were implemented and compared. Using MATLAB, recognition rates exceeding 90% were obtained. In addition, the algorithms were implemented on the ADSP-2181 yielding recognition rates comparable to the MATLAB implementation. / Master of Science

Cognitive radio is a growing field in communications which allows a radio to automatically configure its transmission or reception properties in order to reduce interference, provide better quality of service, or allow for more users in a given spectrum. Such processes require several complex features that are currently being utilized in cognitive radio. Two such features, spectrum sensing and identification, have been implemented in numerous ways, however, they generally suffer from high computational complexity. Additionally, Hidden Markov Models (HMMs) are a widely used mathematical modeling tool used in various fields of engineering and sciences. In electrical and computer engineering, it is used in several areas, including speech recognition, handwriting recognition, artificial intelligence, queuing theory, and are used to model fading in communication channels. The research presented in this thesis proposes a new approach to spectrum identification using a parallel implementation of Hidden Markov Models. Algorithms involving HMMs are usually implemented in the traditional serial manner, which have prohibitively long runtimes. In this work, we study their use in parallel implementations and compare our approach to traditional serial implementations. Timing and power measurements are taken and used to show that the parallel implementation can achieve well over 100Ã speedup in certain situations. To demonstrate the utility of this new parallel algorithm using graphics processing units (GPUs), a new method for signal identification is proposed for both serial and parallel implementations using HMMs. The method achieved high recognition at -10 dB Eb/N0. HMMs can benefit from parallel implementation in certain circumstances, specifically, in models that have many states or when multiple models are used in conjunction. / Master of Science

Specific emitter identification is a technology used to uniquely identify a class of wireless devices, and in some cases a single device. Minute differences in the implementation of a wireless communication standard from one device manufacturer to another make it possi- ble to extract a wireless "fingerprint" from the transmitted signal. These differences may stem from imperfect radio frequency (RF) components such as filters and power amplifiers. However, the problem of identifying a wireless device through analysis of these key signal characteristics presents several difficulties from an algorithmic perspective. Given that the differences in these features can be extremely subtle, in general a high signal to noise ratio (SNR) is necessary for a sufficient probability of correct detection. If a sufficiently high SNR is not guaranteed, then some from of identification algorithm which operates well in low SNR conditions must be used. Cyclostationary analysis offers a method of specific emitter iden- tification through analysis of second order spectral correlation features which can perform well at relatively low SNRs. The eigenvector/eigenvalue decomposition (EVD) is capable of separating principal components from uncorrelated gaussian noise. This work proposes a technique of specific emitter identification which utilizes the principal components of the EVD of the spectral correlation function which has been arranged into a square matrix. An analysis of this EVD-based SEI technique is presented herein, and some limitations are identified. Analysis is constrained to orthogonal frequency division multiplexing (OFDM) using the IEEE 802.16 specification (used for WiMAX) as a guideline for a variety of pilot arrangements. / Master of Science

Estimation of the number of hidden states is challenging in hidden Markov models. Motivated by the analysis of a specific type of cell adhesion experiments, a new frame-work based on hidden Markov model and double penalized order selection is proposed. The order selection procedure is shown to be consistent in estimating the number of states. A modified Expectation-Maximization algorithm is introduced to efficiently estimate parameters in the model. Simulations show that the proposed framework outperforms existing methods. Applications of the proposed methodology to real data demonstrate the accuracy of estimating receptor-ligand bond lifetimes and waiting times which are essential in kinetic parameter estimation. The second part of the thesis is concerned with prediction of a deterministic response function y at some untried sites given values of y at a chosen set of design sites. The intended application is to computer experiments in which y is the output from a computer simulation and each design site represents a particular configuration of the input variables. A Bayesian version of the cubic spline method commonly used in numerical analysis is proposed, in which the random function that represents prior uncertainty about y is taken to be a specific stationary Gaussian process. An MCMC procedure is given for updating the prior given the observed y values. Simulation examples and a real data application are given to compare the performance of the Bayesian cubic spline with that of two existing methods.

The performance of automatic speech recognition systems often degrades in adverse conditions where there is a mismatch between training and testing conditions. This is true for most modern systems which employ Hidden Markov Models (HMMs) to decode speech utterances. One strategy is to map the distorted features back to clean speech features that correspond well to the features used for training of HMMs. This can be achieved by treating the noisy speech as the distorted version of the clean speech of interest. Under this framework, we can track and consequently extract the underlying clean speech from the noisy signal and use this derived signal to perform utterance recognition. Particle filter is a versatile tracking technique that can be used where often conventional techniques such as Kalman filter fall short. We propose a particle filters based algorithm to compensate the corrupted features according to an additive noise model incorporating both the statistics from clean speech HMMs and observed background noise to map noisy features back to clean speech features. Instead of using specific knowledge at the model and state levels from HMMs which is hard to estimate, we pool model states into clusters as side information. Since each cluster encompasses more statistics when compared to the original HMM states, there is a higher possibility that the newly formed probability density function at the cluster level can cover the underlying speech variation to generate appropriate particle filter samples for feature compensation. Additionally, a dynamic joint tracking framework to monitor the clean speech signal and noise simultaneously is also introduced to obtain good noise statistics. In this approach, the information available from clean speech tracking can be effectively used for noise estimation. The availability of dynamic noise information can enhance the robustness of the algorithm in case of large fluctuations in noise parameters within an utterance. Testing the proposed PF-based compensation scheme on the Aurora 2 connected digit recognition task, we achieve an error reduction of 12.15% from the best multi-condition trained models using this integrated PF-HMM framework to estimate the cluster-based HMM state sequence information. Finally, we extended the PFC framework and evaluated it on a large-vocabulary recognition task, and showed that PFC works well for large-vocabulary systems also.