Evolving the structure of hidden Markov models

A genetic algorithm (GA) is proposed for finding the structure of hidden Markov Models (HMMs) used for biological sequence analysis. The GA is designed to preserve biologically meaningful building blocks. The search through the space of HMM structures is combined with optimization of the emission and transition probabilities using the classic Baum-Welch algorithm. The system is tested on the problem of finding the promoter and coding region of C. jejuni. The resulting HMM has a superior discrimination ability to a handcrafted model that has been published in the literature.     

Mining free-structured information based on hidden Markov models

The potentials of hidden Markov models (HMM) in mining free-structured information are investigated in this study. The samples under test are relating to C4ISR information derived from the contents of ‘Forecast International’, which is a web-based database containing free-structured archive of forecast reports about aerospace systems, weapon systems, and military industries. This study focuses on three C4ISR relating target terms, namely, ‘Company’, ‘System types’, and ‘cost’, for information mining analysis. The experiments are performed in two stages. In the first stage, each HMM being built is exclusively serving for one target term information extraction so as to test the HMM fundamental information extraction capability. While in the second stage, the experiment is then extended to resolve a more complex, multiple term extraction issue. The results reveal that, by using HMMs as a basis, the accuracies can all achieve more than 80% for single target term extraction, and 76% in average for multi-term extraction case.     

Controlling eye movements with hidden Markov models

Advances in technology and in active vision research allow and encourage sequential visual information acquisition. Hidden Markov models (HMMs) can represent probabilistic sequences and probabilistic graph structures: here we explore their use in controlling the acquisition of visual information. We include a brief tutorial with two examples: (1) use input sequences to derive an aspect graph and (2) similarly derive a finite state machine for control of visual processing.The first main topic is the use of HMMs in both their learning and generative modes, and their augmentation to allow inputs sensed during generation to modify the generated outputs temporarily or permanently. We propose these augmented HMMs as a theory of adaptive skill acquisition and generation. The second main topic builds on the first: the augmented HMMs can be used for knowledge fusion. We give an example, the what-where-AHMM, which creates a hybrid skill from separate skills based on object location and object identity. Insofar as low-level skills can be learned from the output of high-level cognitive processes, AHMMs can provide a link between high-level and low-level vision.     

Speech recognition with continuous-parameter hidden Markov models

The acoustic modeling problem in automatic speech recognition is examined from an information-theoretic point of view. This problem is to design a speech-recognition system which can extract from the speech waveform as much information as possible about the corresponding word sequence. The information extraction process is broken down into two steps: a signal-processing step which converts a speech waveform into a sequence of information-bearing acoustic feature vectors, and a step which models such a sequence. We are primarily concerned with the use of hidden Markov models to model sequences of feature vectors which lie in a continuous space. We explore the trade-off between packing information into such sequences and being able to model them accurately. The difficulty of developing accurate models of continuous-parameter sequences is addressed by investigating a method of parameter estimation which is designed to cope with inaccurate modeling assumptions.     

Denoising and recognition using hidden Markov models with observation distributions modeled by hidden Markov trees

Hidden Markov models have been found very useful for a wide range of applications in machine learning and pattern recognition. The wavelet transform has emerged as a new tool for signal and image analysis. Learning models for wavelet coefficients have been mainly based on fixed-length sequences, but real applications often require to model variable-length, very long or real-time sequences. In this paper, we propose a new learning architecture for sequences analyzed on short-term basis, but not assuming stationarity within each frame. Long-term dependencies will be modeled with a hidden Markov model which, in each internal state, will deal with the local dynamics in the wavelet domain, using a hidden Markov tree. The training algorithms for all the parameters in the composite model are developed using the expectation-maximization framework. This novel learning architecture could be useful for a wide range of applications. We detail two experiments with artificial and real data: model-based denoising and speech recognition. Denoising results indicate that the proposed model and learning algorithm are more effective than previous approaches based on isolated hidden Markov trees. In the case of the ‘Doppler’ benchmark sequence, with 1024 samples and additive white noise, the new method reduced the mean squared error from 1.0 to 0.0842. The proposed methods for feature extraction, modeling and learning, increased the phoneme recognition rates in 28.13%, with better convergence than models based on Gaussian mixtures.     

Ergodicity of hidden Markov models

In this paper we study ergodic properties of hidden Markov models with a generalized observation structure. In particular sufficient conditions for the existence of a unique invariant measure for the pair filter-observation are given. Furthermore, necessary and sufficient conditions for the existence of a unique invariant measure of the triple state-observation-filter are provided in terms of asymptotic stability in probability of incorrectly initialized filters. We also study the asymptotic properties of the filter and of the state estimator based on the observations as well as on the knowledge of the initial state. Their connection with minimal and maximal invariant measures is also studied. Work partially supported by grants MIUR-PRIN 2001, PBZ KBN 016/P03/99 and IMPAN-BC Centre of Excellence     

Training hidden Markov models with multiple observations-acombinatorial method

Hidden Markov models (HMM) are stochastic models capable of statistical learning and classification. They have been applied in speech recognition and handwriting recognition because of their great adaptability and versatility in handling sequential signals. On the other hand, as these models have a complex structure and also because the involved data sets usually contain uncertainty, it is difficult to analyze the multiple observation training problem without certain assumptions. For many years researchers have used the training equations of Levinson (1983) in speech and handwriting applications, simply assuming that all observations are independent of each other. This paper presents a formal treatment of HMM multiple observation training without imposing the above assumption. In this treatment, the multiple observation probability is expressed as a combination of individual observation probabilities without losing generality. This combinatorial method gives one more freedom in making different dependence-independence assumptions. By generalizing Baum's auxiliary function into this framework and building up an associated objective function using the Lagrange multiplier method, it is proven that the derived training equations guarantee the maximization of the objective function. Furthermore, we show that Levinson's training equations can be easily derived as a special case in this treatment     

Private predictions on hidden Markov models

Hidden Markov models (HMMs) are widely used in practice to make predictions. They are becoming increasingly popular models as part of prediction systems in finance, marketing, bio-informatics, speech recognition, signal processing, and so on. However, traditional HMMs do not allow people and model owners to generate predictions without disclosing their private information to each other. To address the increasing needs for privacy, this work identifies and studies the private prediction problem; it is demonstrated with the following scenario: Bob has a private HMM, while Alice has a private input; and she wants to use Bob’s model to make a prediction based on her input. However, Alice does not want to disclose her private input to Bob, while Bob wants to prevent Alice from deriving information about his model. How can Alice and Bob perform HMMs-based predictions without violating their privacy? We propose privacy-preserving protocols to produce predictions on HMMs without greatly exposing Bob’s and Alice’s privacy. We then analyze our schemes in terms of accuracy, privacy, and performance. Since they are conflicting goals, due to privacy concerns, it is expected that accuracy or performance might degrade. However, our schemes make it possible for Bob and Alice to produce the same predictions efficiently while preserving their privacy.     

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.     

Audio/visual mapping with cross-modal hidden Markov models

The audio/visual mapping problem of speech-driven facial animation has intrigued researchers for years. Recent research efforts have demonstrated that hidden Markov model (HMM) techniques, which have been applied successfully to the problem of speech recognition, could achieve a similar level of success in audio/visual mapping problems. A number of HMM-based methods have been proposed and shown to be effective by the respective designers, but it is yet unclear how these techniques compare to each other on a common test bed. In this paper, we quantitatively compare three recently proposed cross-modal HMM methods, namely the remapping HMM (R-HMM), the least-mean-squared HMM (LMS-HMM), and HMM inversion (HMMI). The objective of our comparison is not only to highlight the merits and demerits of different mapping designs, but also to study the optimality of the acoustic representation and HMM structure for the purpose of speech-driven facial animation. This paper presents a brief overview of these models, followed by an analysis of their mapping capabilities on a synthetic dataset. An empirical comparison on an experimental audio-visual dataset consisting of 75 TIMIT sentences is finally presented. Our results show that HMMI provides the best performance, both on synthetic and experimental audio-visual data.     

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.     

Profile hidden Markov models and metamorphic virus detection

Metamorphic computer viruses “mutate” by changing their internal structure and, consequently, different instances of the same virus may not exhibit a common signature. With the advent of construction kits, it is easy to generate metamorphic strains of a given virus. In contrast to standard hidden Markov models (HMMs), profile hidden Markov models (PHMMs) explicitly account for positional information. In principle, this positional information could yield stronger models for virus detection. However, there are many practical difficulties that arise when using PHMMs, as compared to standard HMMs. PHMMs are widely used in bioinformatics. For example, PHMMs are the most effective tool yet developed for finding family related DNA sequences. In this paper, we consider the utility of PHMMs for detecting metamorphic virus variants generated from virus construction kits. PHMMs are generated for each construction kit under consideration and the resulting models are used to score virus and non-virus files. Our results are encouraging, but several problems must be resolved for the technique to be truly practical.     

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.     

Fire detection based on hidden Markov models

In this paper, a novel method of real-time fire detection based on HMMs is presented. First, we present an analysis of fire characteristics that provides evidence supporting the use of HMMs to detect fire; second, we propose an algorithm for detecting candidate fire pixels that entails the detection of moving pixels, fire-color inspection, and pixels clustering. The main contribution of this paper is the establishment and application of a hidden Markov fire model by combining the state transition between fire and non-fire with fire motion information to reduce data redundancy. The final decision is based on this model which includes training and application; the training provides parameters for the HMM application. The experimental results show that the method provides both a high detection rate and a low false alarm rate. Furthermore, real-time detection has been effectively realized via the learned parameters of the HMM, since the most time-consuming components such as HMM training are performed off-line.     

Asymptotical statistics of misspecified hidden Markov models

This paper deals with the problem of modeling data generated by an ergodic stochastic process as the output of a hidden Markov model (HMM). More specifically, we consider the problem of fitting a parametric family of HMM with continuous output to an ergodic stochastic process with continuous values, which does not necessarily belong to the family. In this context, we derive the main asymptotic results: almost sure consistency of the maximum likelihood estimator, asymptotic normality of the estimation error and the exact rates of almost sure convergence.     

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.     

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.     

Parametric hidden Markov models for gesture recognition

A method for the representation, recognition, and interpretation of parameterized gesture is presented. By parameterized gesture we mean gestures that exhibit a systematic spatial variation; one example is a point gesture where the relevant parameter is the two-dimensional direction. Our approach is to extend the standard hidden Markov model method of gesture recognition by including a global parametric variation in the output probabilities of the HMM states. Using a linear model of dependence, we formulate an expectation-maximization (EM) method for training the parametric HMM. During testing, a similar EM algorithm simultaneously maximizes the output likelihood of the PHMM for the given sequence and estimates the quantifying parameters. Using visually derived and directly measured three-dimensional hand position measurements as input, we present results that demonstrate the recognition superiority of the PHMM over standard HMM techniques, as well as greater robustness in parameter estimation with respect to noise in the input features. Finally, we extend the PHMM to handle arbitrary smooth (nonlinear) dependencies. The nonlinear formulation requires the use of a generalized expectation-maximization (GEM) algorithm for both training and the simultaneous recognition of the gesture and estimation of the value of the parameter. We present results on a pointing gesture, where the nonlinear approach permits the natural spherical coordinate parameterization of pointing direction     

Texture classification using noncausal hidden Markov models

This paper addresses the problem of using noncausal hidden Markov models (HMMs) for texture classification. In noncausal models, the state of each pixel may be dependent on its neighbors in all directions. New algorithms are given to learn the parameters of a noncausal HMM of a texture and to classify it into one of several learned categories. Texture classification results using these algorithms are provided