Diagnostic tools for evaluating and updating hidden Markov models

In this paper we consider two related problems in hidden Markov models (HMMs). One, how the various parameters of an HMM actually contribute to predictions of state sequences and spatio-temporal pattern recognition. Two, how the HMM parameters (and associated HMM topology) can be updated to improve performance. These issues are examined in the context of four different experimental settings from pure simulations to observed data. Results clearly demonstrate the benefits of applying some critical tests on the model parameters before using it as a predictor or spatio-temporal pattern recognition technique.     

Robot introspection through learned hidden Markov models

In this paper we describe a machine learning approach for acquiring a model of a robot behaviour from raw sensor data. We are interested in automating the acquisition of behavioural models to provide a robot with an introspective capability. We assume that the behaviour of a robot in achieving a task can be modelled as a finite stochastic state transition system.Beginning with data recorded by a robot in the execution of a task, we use unsupervised learning techniques to estimate a hidden Markov model (HMM) that can be used both for predicting and explaining the behaviour of the robot in subsequent executions of the task. We demonstrate that it is feasible to automate the entire process of learning a high quality HMM from the data recorded by the robot during execution of its task.The learned HMM can be used both for monitoring and controlling the behaviour of the robot. The ultimate purpose of our work is to learn models for the full set of tasks associated with a given problem domain, and to integrate these models with a generative task planner. We want to show that these models can be used successfully in controlling the execution of a plan. However, this paper does not develop the planning and control aspects of our work, focussing instead on the learning methodology and the evaluation of a learned model. The essential property of the models we seek to construct is that the most probable trajectory through a model, given the observations made by the robot, accurately diagnoses, or explains, the behaviour that the robot actually performed when making these observations. In the work reported here we consider a navigation task. We explain the learning process, the experimental setup and the structure of the resulting learned behavioural models. We then evaluate the extent to which explanations proposed by the learned models accord with a human observer's interpretation of the behaviour exhibited by the robot in its execution of the task.     

Measure change estimates for hidden Markov models

Using a change of measure, the finite state observation process of a Markov chain is transformed into a sequence of independent random variables. By computing unnormalized conditional estimates under the new measure, simple, recursive formulate are obtained.     

A modified hidden Markov model

This paper considers two discrete time, finite state processes X$X$ and Y$Y$. In the usual hidden Markov model X$X$ modulates the values of Y$Y$. However, the values of Y$Y$ are then i.i.d. given X$X$. In this paper a new model is considered where the Markov chain X$X$ modulates the transition probabilities of the second, observed chain Y$Y$. This more realistically can represent problems arising in DNA sequencing. Algorithms for all related filters, smoothers and parameter estimations are derived. Versions of the Viterbi algorithms are obtained.     

Risk-sensitive filtering and smoothing for hidden Markov models

In this paper, we address the problem of risk-sensitive filtering and smoothing for discrete-time Hidden Markov Models (HMM) with finite-discrete states. The objective of risk-sensitive filtering is to minimise the expectation of the exponential of the squared estimation error weighted by a risk-sensitive parameter. We use the so-called Reference Probability Method in solving this problem. We achieve finite-dimensional linear recursions in the information state, and thereby the state estimate that minimises the risk-sensitive cost index. Also, fixed-interval smoothing results are derived. We show that L₂ or risk-neutral filtering for HMMs can be extracted as a limiting case of the risk-sensitive filtering problem when the risk-sensitive parameter approaches zero.     

A comparative evaluation of neural networks and hidden Markov models for monitoring turning tool wear

Condition monitoring of machine tool inserts is important for increasing the reliability and quality of machining operations. Various methods have been proposed for effective tool condition monitoring (TCM), and currently it is generally accepted that the indirect sensor-based approach is the best practical solution to reliable TCM. Furthermore, in recent years, neural networks (NNs) have been shown to model successfully, the complex relationships between input feature sets of sensor signals and tool wear data. NNs have several properties that make them ideal for effectively handling noisy and even incomplete data sets. There are several NN paradigms which can be combined to model static and dynamic systems. Another powerful method of modeling noisy dynamic systems is by using hidden Markov models (HMMs), which are commonly employed in modern speech-recognition systems. The use of HMMs for TCM was recently proposed in the literature. Though the results of these studies were quite promising, no comparative results of competing methods such as NNs are currently available. This paper is aimed at presenting a comparative evaluation of the performance of NNs and HMMs for a TCM application. The methods are employed on exactly the same data sets obtained from an industrial turning operation. The advantages and disadvantages of both methods are described, which will assist the condition-monitoring community to choose a modeling method for other applications.     

Masquerade detection using profile hidden Markov models

In this paper, we consider the problem of masquerade detection, based on user-issued UNIX commands. We present a novel detection technique based on profile hidden Markov models (PHMMs). For comparison purposes, we implement an existing modeling technique based on hidden Markov models (HMMs). We compare these approaches and show that, in general, our PHMM technique is competitive with HMMs. However, the standard test data set lacks positional information. We conjecture that such positional information would give our PHMM a significant advantage over HMM-based detection. To lend credence to this conjecture, we generate a simulated data set that includes positional information. Based on this simulated data, experimental results show that our PHMM-based approach outperforms other techniques when limited training data is available.     

Myocardial infarction classification with multi-lead ECG using hidden Markov models and Gaussian mixture models

This study presented a new diagnosis system for myocardial infarction classification by converting multi-lead ECG data into a density model for increasing accuracy and flexibility of diseases detection. In contrast to the traditional approaches, a hybrid system with HMMs and GMMs was employed for data classification. A hybrid approach using multi-leads, i.e., lead-V1, V2, V3 and V4 for myocardial infarction were developed and HMMs were used not only to find the ECG segmentations but also to calculate the log-likelihood value which was treated as statistical feature data of each heartbeat's ECG complex. The 4-dimension feature vector extracted by HMMs was clustered by GMMs with different numbers of distribution (disease and normal data). SVMs classifier was also examined for comparison with our system in experimental result. There were total 1129 samples of heartbeats from clinical data, including 582 data with myocardial infarction and 547 normal data. The sensitivity of this diagnosis system achieved 85.71%, specificity achieved 79.82% and accuracy achieved 82.50% statistically.     

Efficient backward decoding of high-order hidden Markov models

The forward-backward search (FBS) algorithm [S. Austin, R. Schwartz, P. Placeway, The forward-backward search algorithm, in: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1991, pp. 697-700] has resulted in increases in speed of up to 40 in expensive time-synchronous beam searches in hidden Markov model (HMM) based speech recognition [R. Schwartz, S. Austin, Efficient, high-performance algorithms for N-best search, in: Proceedings of the Workshop on Speech and Natural Language, 1990, pp. 6-11; L. Nguyen, R. Schwartz, F. Kubala, P. Placeway, Search algorithms for software-only real-time recognition with very large vocabularies, in: Proceedings of the Workshop on Human Language Technology, 1993, pp. 91-95; A. Sixtus, S. Ortmanns, High-quality word graphs using forward-backward pruning, in: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1999, pp. 593-596]. This is typically achieved by using a simplified forward search to decrease computation in the following detailed backward search. FBS implicitly assumes that forward and backward searches of HMMs are computationally equivalent. In this paper we present experimental results, obtained on the CallFriend database, that show that this assumption is incorrect for conventional high-order HMMs. Therefore, any improvement in computational efficiency that is gained by using conventional low-order HMMs in the simplified backward search of FBS is lost.This problem is solved by presenting a new definition of HMMs termed a right-context HMM, which is equivalent to conventional HMMs. We show that the computational expense of backward Viterbi-beam decoding right-context HMMs is similar to that of forward decoding conventional HMMs. Though not the subject of this paper, this allows us to more efficiently decode high-order HMMs, by capitalising on the improvements in computational efficiency that is obtained by using the FBS algorithm.     

Similarity-based classification of sequences using hidden Markov models

Hidden Markov models (HMM) are a widely used tool for sequence modelling. In the sequence classification case, the standard approach consists of training one HMM for each class and then using a standard Bayesian classification rule. In this paper, we introduce a novel classification scheme for sequences based on HMMs, which is obtained by extending the recently proposed similarity-based classification paradigm to HMM-based classification. In this approach, each object is described by the vector of its similarities with respect to a predetermined set of other objects, where these similarities are supported by HMMs. A central problem is the high dimensionality of resulting space, and, to deal with it, three alternatives are investigated. Synthetic and real experiments show that the similarity-based approach outperforms standard HMM classification schemes.     

Modeling and recognition of cursive words with hidden Markov models

In this paper, a new method for modeling and recognizing cursive words with hidden Markov models (HMM) is presented. In the proposed method, a sequence of thin fixed-width vertical frames are extracted from the image, capturing the local features of the handwriting. By quantizing the feature vectors of each frame, the input word image is represented as a Markov chain of discrete symbols. A handwritten word is regarded as a sequence of characters and optional ligatures. Hence, the ligatures are also explicitly modeled. With this view, an interconnection network of character and ligature HMMs is constructed to model words of indefinite length. This model can ideally describe any form of handwritten words, including discretely spaced words, pure cursive words and unconstrained words of mixed styles. Experiments have been conducted with a standard database to evaluate the performance of the overall scheme. The performance of various search strategies based on the forward and backward score has been compared. Experiments on the use of a preclassifier based on global features show that this approach may be useful for even large-vocabulary recognition tasks.     

Handwritten word-spotting using hidden Markov models and universal vocabularies

Handwritten word-spotting is traditionally viewed as an image matching task between one or multiple query word-images and a set of candidate word-images in a database. This is a typical instance of the query-by-example paradigm. In this article, we introduce a statistical framework for the word-spotting problem which employs hidden Markov models (HMMs) to model keywords and a Gaussian mixture model (GMM) for score normalization. We explore the use of two types of HMMs for the word modeling part: continuous HMMs (C-HMMs) and semi-continuous HMMs (SC-HMMs), i.e. HMMs with a shared set of Gaussians. We show on a challenging multi-writer corpus that the proposed statistical framework is always superior to a traditional matching system which uses dynamic time warping (DTW) for word-image distance computation. A very important finding is that the SC-HMM is superior when labeled training data is scarce—as low as one sample per keyword—thanks to the prior information which can be incorporated in the shared set of Gaussians.     

The likelihood ratio test for hidden Markov models in two-sample problems

The asymptotic distribution of the likelihood ratio test statistic in two-sample testing problems for hidden Markov models is derived when allowing for unequal sample sizes as well as for different families of state-dependent distributions. In both cases under regularity conditions the limit distribution is a standard χ²-distribution, and in particular does not depend on the ratio of the distinct sample sizes. In a simulation study, the finite sample properties are investigated, and the methodology is illustrated in an application to modeling the movement of Drosophila larvae.     

Perception-based hidden Markov models: a theoretical framework for data mining and knowledge discovery

 The combination of objective measurements and human perceptions using hidden Markov models with particular reference to sequential data mining and knowledge discovery is presented in this paper. Both human preferences and statistical analysis are utilized for verification and identification of hypotheses as well as detection of hidden patterns. As another theoretical view, this work attempts to formalize the complementarity of the computational theories of hidden Markov models and perceptions for providing solutions associated with the manipulation of the internet.     

Almost sure convergence rates for system identification using binary,quantized, and regular sensors

This paper presents almost sure convergence rates for system identification under binary, quantized, and regular sensors. To accommodate practical model complexity constraints, the system under consideration is represented by a modeled part together with an unknown-but-bounded unmodeled dynamics. Under uncorrelated noise sequences, identification errors with different sensor types are studied and tight error bounds are obtained without information or constraints on noise moment conditions. The results are then extended to correlated noise sequences whose remote past and distant future are asymptotically independent. In both cases, almost sure error bounds of the laws of iterated logarithms type are derived.