Training approach for hidden Markov models

The authors propose a new training approach based on maximum model distance (MMD) for HMMs. MMD uses the entire training set to estimate the parameters of each HMM, while the traditional maximum likelihood (ML) only uses those data labelled for the model. Experimental results showed that significant error reduction can be achieved through the proposed approach. In addition, the relationship between MMD and corrective training was discussed, and we have proved that the corrective training is a special case of the MMD approach     

Reduced-complexity estimation for large-scale hidden Markov models

In this paper, we address the problem of reduced-complexity estimation of general large-scale hidden Markov models (HMMs) with underlying nearly completely decomposable discrete-time Markov chains and finite-state outputs. An algorithm is presented that computes O(/spl epsi/) (where /spl epsi/ is the related weak coupling parameter) approximations to the aggregate and full-order filtered estimates with substantial computational savings. These savings are shown to be quite large when the chains have blocks with small individual dimensions. Some simulation studies are presented to demonstrate the performance of the algorithm.     

Recursive algorithms for estimation of hidden Markov models andautoregressive models with Markov regime

This paper is concerned with recursive algorithms for the estimation of hidden Markov models (HMMs) and autoregressive (AR) models under the Markov regime. Convergence and rate of convergence results are derived. Acceleration of convergence by averaging of the iterates and the observations are treated. Finally, constant step-size tracking algorithms are presented and examined     

An approach to cardiac arrhythmia analysis using hidden Markov models

This paper describes a new approach to ECG arrhythmia analysis based on "hidden Markov modeling" (HMM), a technique successfully used since the mid-1970's to model speech waveforms for automatic speech recognition. Many ventricular arrhythmias can be classified by detecting and analyzing QRS complexes and determining R-R intervals. Classification of supraventricular arrhythmias, however, often requires detection of the P wave in addition to the QRS complex. The hidden Markov modeling approach combines structural and statistical knowledge of the ECG signal in a single parametric model. Model parameters are estimated from training data using an iterative, maximum likelihood reestimation algorithm. Initial results suggest that this approach may provide improved supraventricular arrhythmia analysis through accurate representation of the entire beat including the P wave.     

Optimal error exponents in hidden Markov models order estimation

We consider the estimation of the number of hidden states (the order) of a discrete-time finite-alphabet hidden Markov model (HMM). The estimators we investigate are related to code-based order estimators: penalized maximum-likelihood (ML) estimators and penalized versions of the mixture estimator introduced by Liu and Narayan (1994). We prove strong consistency of those estimators without assuming any a priori upper bound on the order and smaller penalties than previous works. We prove a version of Stein's lemma for HMM order estimation and derive an upper bound on underestimation exponents. Then we prove that this upper bound can be achieved by the penalized ML estimator and by the penalized mixture estimator. The proof of the latter result gets around the elusive nature of the ML in HMM by resorting to large-deviation techniques for empirical processes. Finally, we prove that for any consistent HMM order estimator, for most HMM, the overestimation exponent is .     

A new approach to designing computationally efficient interpolatedFIR filters

More efficient use of multipliers in FIR filters can be achieved at the expense of a slight increase in delay by designing sparse filter structures. We have developed a new, relatively simple approach to designing sparse cascaded filters, also described in the literature as interpolated FIR filters. Our method is heuristic in nature, but gives surprisingly good results without requiring iterative design or investigation of a large number of alternative parameterizations. The design uses the efficient and widely available Remez exchange algorithm along with some routines that we have written for Matlab. Although the resulting designs are not optimal in a minimax-error sense, they have reduced RMS error, which may be attractive for some applications. We give design examples, and study the effects of coefficient quantization     

Application of extreme value theory to level estimation innonlinearly distorted hidden Markov models

This paper is concerned with the application of extreme value theory (EVT) to the state level estimation problem for discrete-time, finite-state Markov chains hidden in additive colored noise and subjected to unknown nonlinear distortion. If the nonlinear distortion affects only those observations with small magnitudes or those that lie outside a finite interval, we show that the level estimation problem can be reduced to a curve fitting problem with a unique global minimum. Compared with optimum maximum likelihood estimation algorithms, the developed level estimation algorithms are computationally inexpensive and are not affected by the unknown nonlinearity as long as the extreme values of observations are not distorted. This work has been motivated by unknown deadzone and saturation nonlinearities introduced by sensors in data measurement systems. We illustrate the effectiveness of the new EVT-based level estimation algorithms with computer simulations     

A stochastic method for Bayesian estimation of hidden Markov random field models with application to a color model.

We propose a new stochastic algorithm for computing useful Bayesian estimators of hidden Markov random field (HMRF) models that we call exploration/selection/estimation (ESE) procedure. The algorithm is based on an optimization algorithm of O. Fran?ois, called the exploration/selection (E/S) algorithm. The novelty consists of using the a posteriori distribution of the HMRF, as exploration distribution in the E/S algorithm. The ESE procedure computes the estimation of the likelihood parameters and the optimal number of region classes, according to global constraints, as well as the segmentation of the image. In our formulation, the total number of region classes is fixed, but classes are allowed or disallowed dynamically. This framework replaces the mechanism of the split-and-merge of regions that can be used in the context of image segmentation. The procedure is applied to the estimation of a HMRF color model for images, whose likelihood is based on multivariate distributions, with each component following a Beta distribution. Meanwhile, a method for computing the maximum likelihood estimators of Beta distributions is presented. Experimental results performed on 100 natural images are reported. We also include a proof of convergence of the E/S algorithm in the case of nonsymmetric exploration graphs.     

On a computationally efficient approach to boron-interstitial clustering

The physical concepts developed to describe the transient activation of boron during post-implantation annealing are based on the concurrent formation of complexes comprising boron atoms and self-interstitials. A complete implementation into TCAD software leads to a high number of equations to be solved which is often inadmissible for multi-dimensional simulations. In this work, a minimum number of such complexes is taken into considerations. We show that such a model is nevertheless able to reproduce profile shape and dopant activation for a large variety of implant and annealing conditions.     

Improved hidden Markov models in the wavelet-domain

Wavelet-domain hidden Markov models (HMMs), in particular the hidden Markov tree (HMT) model, have been introduced and applied to signal and image processing, e.g., signal denoising. We develop a simple initialization scheme for the efficient HMT model training and then propose a new four-state HMT model called HMT-2. We find that the new initialization scheme fits the HMT-2 model well. Experimental results show that the performance of signal denoising using the HMT-2 model is often improved over the two-state HMT model developed by Crouse et al. (see ibid., vol.46, p.886-902, 1998)     

A computationally efficient multivariate maximum-entropy density estimation (MEDE) technique

Density estimation is the process of taking a set of multivariate data and finding an estimate for the probability density function (pdf) that produced it. One approach for obtaining an accurate estimate of the true density f(x) is to use the polynomial-moment method with Boltzmann-Shannon entropy. Although rigorous mathematically, the method is difficult to implement in practice because the solution involves a large set of simultaneous nonlinear integral equations, one for each moment or joint moment constraint. Solutions available in the literature are generally not easily applicable to multivariate data, nor computationally efficient. In this paper, we take the functional form that was developed in this problem and apply pointwise estimates of the pdf as constraints. These pointwise estimates are transformed into basis coefficients for a set of Legendre polynomials. The procedure is mathematically similar to the multidimensional Fourier transform, although with different basis functions. We apply this technique, called the maximum-entropy density estimation (MEDE) technique, to a series of multivariate datasets.     

Hybrid approach to speech recognition using hidden Markov modelsand Markov chains

The paper presents a hybrid of a hidden Markov model and a Markov chain model for speech recognition. In this hybrid, the hidden Markov model is concerned with the time-varying property of spectral features, while the Markov chain accounts for the interdependence of spectral features. The log-likelihood scores of the two models, with respect to a given utterance, are combined by a postprocessor to yield a combined log-likelihood score for word classification. Experiments on speaker-independent and multispeaker isolated English alphabet recognition show that the hybrid outperformed both the hidden Markov model and the Markov chain model in terms of recognition     

Image segmentation using hidden Markov Gauss mixture models.

Image segmentation is an important tool in image processing and can serve as an efficient front end to sophisticated algorithms and thereby simplify subsequent processing. We develop a multiclass image segmentation method using hidden Markov Gauss mixture models (HMGMMs) and provide examples of segmentation of aerial images and textures. HMGMMs incorporate supervised learning, fitting the observation probability distribution given each class by a Gauss mixture estimated using vector quantization with a minimum discrimination information (MDI) distortion. We formulate the image segmentation problem using a maximum a posteriori criteria and find the hidden states that maximize the posterior density given the observation. We estimate both the hidden Markov parameter and hidden states using a stochastic expectation-maximization algorithm. Our results demonstrate that HMGMM provides better classification in terms of Bayes risk and spatial homogeneity of the classified objects than do several popular methods, including classification and regression trees, learning vector quantization, causal hidden Markov models (HMMs), and multiresolution HMMs. The computational load of HMGMM is similar to that of the causal HMM.     

Frequency tracking of atrial fibrillation using hidden Markov models.

A hidden Markov model (HMM) is employed to improve noise robustness when tracking the dominant frequency of atrial fibrillation (AF) in the electrocardiogram (ECG). Following QRST cancellation, a sequence of observed frequency states is obtained from the residual ECG, using the short-time Fourier transform. Based on the observed state sequence, the Viterbi algorithm retrieves the optimal state sequence by exploiting the state transition matrix, incorporating knowledge on AF characteristics, and the observation matrix, incorporating knowledge of the frequency estimation method and signal-to-noise ratio (SNR). The tracking method is evaluated with simulated AF signals to which noise, obtained from ECG recordings, has been added at different SNRs. The results show that the use of HMM improves performance considerably by reducing the rms error associated with frequency tracking: at 4-dB SNR, the rms error drops from 0.2 to 0.04 Hz.     

Joint turbo decoding and estimation of hidden Markov sources

We describe a joint source-channel scheme for modifying a turbo decoder in order to exploit the statistical characteristics of hidden Markov sources. The basic idea is to treat the trellis describing the hidden Markov source as another constituent decoder which exchanges information with the other constituent decoder blocks. The source block uses as extrinsic information the probability of the input bits that is provided by the constituent decoder blocks. On the other hand, it produces a new estimation of such a probability which will be used as extrinsic information by the constituent turbo decoders. The proposed joint source-channel decoding technique leads to significantly improved performance relative to systems in which source statistics are not exploited and avoids the need to perform any explicit source coding prior to transmission. Lack of a priori knowledge of the source parameters does not degrade the performance of the system, since these parameters can be jointly estimated with turbo decoding     

Combining hidden Markov source models and parallel concatenatedcodes

We present here a framework for modifying a decoder for parallel concatenated codes to incorporate a general hidden Markov source model. This allows the receiver to utilize the statistical characteristics of the source during the decoding process, and leads to significantly improved performance relative to systems in which source statistics are not exploited. One of the constituent decoders makes use of a modified trellis which jointly describes the source and the encoder. The number of states in this modified trellis is the product of the number of states in the hidden Markov source and the number of states in the encoder     

On the first order equalization of hidden Markov models

The article exploits some properties of the “first order equalization” technique, used to increase the recognition performance of speech. It shows that if the eigenvalues of the covariance matrix of observations are restricted, then a solution exists for this problem, although it may not be unique,     

Object trajectory-based activity classification and recognition using hidden Markov models.

Motion trajectories provide rich spatiotemporal information about an object's activity. This paper presents novel classification algorithms for recognizing object activity using object motion trajectory. In the proposed classification system, trajectories are segmented at points of change in curvature, and the subtrajectories are represented by their principal component analysis (PCA) coefficients. We first present a framework to robustly estimate the multivariate probability density function based on PCA coefficients of the subtrajectories using Gaussian mixture models (GMMs). We show that GMM-based modeling alone cannot capture the temporal relations and ordering between underlying entities. To address this issue, we use hidden Markov models (HMMs) with a data-driven design in terms of number of states and topology (e.g., left-right versus ergodic). Experiments using a database of over 5700 complex trajectories (obtained from UCI-KDD data archives and Columbia University Multimedia Group) subdivided into 85 different classes demonstrate the superiority of our proposed HMM-based scheme using PCA coefficients of subtrajectories in comparison with other techniques in the literature.     

Infinite hidden Markov models for unusual-event detection in video.

We address the problem of unusual-event detection in a video sequence. Invariant subspace analysis (ISA) is used to extract features from the video, and the time-evolving properties of these features are modeled via an infinite hidden Markov model (iHMM), which is trained using "normal"/"typical" video. The iHMM retains a full posterior density function on all model parameters, including the number of underlying HMM states. Anomalies (unusual events) are detected subsequently if a low likelihood is observed when associated sequential features are submitted to the trained iHMM. A hierarchical Dirichlet process framework is employed in the formulation of the iHMM. The evaluation of posterior distributions for the iHMM is achieved in two ways: via Markov chain Monte Carlo and using a variational Bayes formulation. Comparisons are made to modeling based on conventional maximum-likelihood-based HMMs, as well as to Dirichlet-process-based Gaussian-mixture models.