Expectation maximization algorithms for MAP estimation of jumpMarkov linear systems

In a jump Markov linear system, the state matrix, observation matrix, and the noise covariance matrices evolve according to the realization of a finite state Markov chain. Given a realization of the observation process, the aim is to estimate the state of the Markov chain assuming known model parameters. Computing conditional mean estimates is infeasible as it involves a cost that grows exponentially with the number of observations. We present three expectation maximization (EM) algorithms for state estimation to compute maximum a posteriori (MAP) state sequence estimates [which are also known as Bayesian maximum likelihood state sequence estimates (MLSEs)]. The first EM algorithm yields the MAP estimate for the entire sequence of the finite state Markov chain. The second EM algorithm yields the MAP estimate of the (continuous) state of the jump linear system. The third EM algorithm computes the joint MAP estimate of the finite and continuous states. The three EM algorithms optimally combine a hidden Markov model (HMM) estimator and a Kalman smoother (KS) in three different ways to compute the desired MAP state sequence estimates. Unlike the conditional mean state estimates, which require computational cost exponential in the data length, the proposed iterative schemes are linear in the data length     

Performance of the maximum likelihood constant frequency estimatorfor frequency tracking

The performance of maximum likelihood (ML) estimators for an important frequency estimation problem is considered when the signal model assumptions are not valid. The motivation for this problem is to understand the robustness of the hidden Markov model-maximum likelihood (HMM-ML) tandem frequency estimator, where the signal is divided into time blocks, and the frequency in each time block is estimated using the ML approach under the assumption that the signal has a constant frequency in each time block. In order to analyze the sensitivity of ML estimators to the model assumptions, the mean frequency of a discrete complex tone that has a time-varying (ramp) frequency is estimated under the incorrect assumption that it has a constant frequency. In particular, the behavior of the threshold region with respect to different chirp rates is analyzed, and a simple rule is given. The mean squared error above the threshold region is shown to be constant even at very high SNR levels. These results are supported by simulations     

Throughput analysis of IEEE 802.15.4 beacon-enabled MAC protocol in the presence of hidden nodes

The presence of hidden nodes degrades the performance of wireless networks due to an excessive amount of data frame collisions. The IEEE 802.15.4 medium access control (MAC) protocol, which is widely used in current wireless sensor networks, does not provide any hidden node avoidance mechanisms and consequently could lead to severe performance degradation in networks with hidden nodes. This paper presents a simple technique based on discrete-time Markov chain analysis to approximate the throughput of IEEE 802.15.4 MAC protocol in the presence of hidden nodes. Using different network configurations, we validate the applicability of the proposed analysis for generic star-topology networks. Based on the analysis, the effects of network size, topology, frame length and frame arrival rate on the throughput of the system are investigated.     

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 .     

针对时间序列多步预测的聚类隐马尔科夫模型

时间序列的预测在现今社会各个领域中有着广泛的应用.本文针对时间序列趋势预测中的多步预测问题,提出了基于聚类的隐马尔科夫模型,利用隐马尔科夫模型中的隐状态来表示产生时间序列数据时的系统内部状态,实现对多步时间序列的预测.针对时间序列聚类中的距离计算问题,提出结合时间序列时间性和相似性的聚类算法,并给出了迭代精化基于聚类的隐马尔科夫模型的方法.实验表明,本文提出的方法在时间序列多步预测中精度较高.     

Modeling burst channels using partitioned Fritchman's Markov models

Discrete models based on functions of Markov chains (also referred to as hidden Markov models or finite-state channel (FSC) models) have been used to characterize the error process in communication channels with memory. One important property of these models is that the probability of any observed sequence can be expressed as a linear combination of the probability of a finite set of sequences of finite length, the so-called basis sequences. In this paper, we express the parameters of a class of FSC models as a simple function of the probability of the basis sequences. Based on this approach, we propose a new method for the parameterization of the Fritchman (1967) channel with single-error state as well as the interesting cases of Fritchman channels with more than one error state and the Gilbert-Elliott channel ((GEC) nonrenewal models). To illustrate the method, FSC models for the nonfrequency-selective Rician fading channel are presented. The number of states and the probability of state transitions are estimated for a given set of fading parameters     

Multiresolution image classification by hierarchical modeling withtwo-dimensional hidden Markov models

This paper treats a multiresolution hidden Markov model for classifying images. Each image is represented by feature vectors at several resolutions, which are statistically dependent as modeled by the underlying state process, a multiscale Markov mesh. Unknowns in the model are estimated by maximum likelihood, in particular by employing the expectation-maximization algorithm. An image is classified by finding the optimal set of states with maximum a posteriori probability. States are then mapped into classes. The multiresolution model enables multiscale information about context to be incorporated into classification. Suboptimal algorithms based on the model provide progressive classification that is much faster than the algorithm based on single-resolution hidden Markov models     

用于噪声鲁棒语音识别的声学模型及解码策略

提出了一种平行子状态隐马尔可夫模型用作噪声鲁棒语音识别的声学模型。该模型融合了纯净语音和背景噪声信息,模型的每个状态包含平行关系的子状态。在此基础上,提出了两种用于平行子状态隐马尔可夫模型的识别解码策略——子状态最大似然解码和联合转移子状态最大似然解码。实验结果表明,声学模型及其解码策略在各种噪声下取得了良好鲁棒识别效果。     

A Stochastic Approach for Blind Estimation of Multiple Co-Channel Signals Received at an Antenna Array

A stochastic maximum likelihood approach for blind estimation of co-channel signals received at an antenna array is proposed in this letter. A hidden Markov model formulation of the problem is introduced and the Baum-Welch algorithm for the associated stochastic maximum likelihood estimation procedure is modified. The performance of the proposed algorithm based on the evaluation of approximate Cramer-Rao bounds is studied. Finally, some simulation results are presented.     

Minimum error rate training for PHMM-based text recognition

Discriminative training is studied to improve the performance of our pseudo two-dimensional (2-D) hidden Markov model (PHMM) based text recognition system. The aim of this discriminative training is to adjust model parameters to directly minimize the classification error rate. Experimental results have shown great reduction in recognition error rate even for PHMMs already well-trained using conventional maximum likelihood (ML) approaches.     

Improved image decoding over noisy channels using minimummean-squared estimation and a Markov mesh

Joint source-channel (JSC) decoding based on residual source redundancy is a technique for providing channel robustness to quantized data. Previous work assumed a model equivalent to viewing the encoder/noisy channel tandem as a discrete hidden Markov model (HMM) with transmitted indices the hidden states. We generalize this HMM-based (1-D) approach for images, using the more powerful hidden Markov mesh random field (HMMRF) model. While previous state estimation methods for HMMRFs base estimates on only a causal subset of the observed data, our new method uses both causal and anticausal subsets. For JSC-based image decoding, the new method provides significant benefits over several competing techniques.     

Blind equalization of dispersive fast fading Ricean channels via the EMV algorithm

A blind maximum likelihood equalization method is proposed for frequency selective fast fading Ricean channels. This method employs the expectation-maximization Viterbi algorithm (EMVA) developed in for blind channel estimation and signal detection. Since the Viterbi algorithm (VA) is used to execute the E-phase of an expectation-maximization (EM) iteration, it requires that the observed sequence can be modelled as a finite-state hidden Markov process. We develop a hidden Markov model for frequency selective fast fading Ricean channels, so that the observed process can be viewed as the noisy output of a finite state machine (FSM), to which the VA is applicable. The EMVA is then employed to obtain a blind maximum likelihood estimate of the specular part of the channel and, for one special case, of a noise parameter measuring the total power of the additive and multiplicative channel noise components. Simulation results are presented which show that the EMVA achieves an accurate estimate of the channel specular part and has an error rate performance close to that of the maximum likelihood detector based on true parameters for the given FSM model.     

Estimating parameters of multiple wideband polynomial-phase sourcesin sensor arrays

We consider the problem of estimating the parameters of multiple wideband polynomial-phase signal (PPS) sources in sensor arrays. A new maximum likelihood (ML) direction-of-arrival (DOA) estimator is introduced, and the exact Cramer-Rao bound (CRB) is derived for the general case of multiple constant-amplitude polynomial-phase sources. Since the proposed exact ML estimator is computationally intensive, an approximate solution is proposed, originating from the analysis of the log-likelihood (LL) function in the single chirp signal case. As a result, a new form of spatio-temporal matched filter (referred to as the chirp beamformer) is derived, which is applicable to "well-separated" sources that have distinct time-frequency or/and spatial signatures. This beamforming approach requires solving a three-dimensional (3-D) optimization problem and, therefore, enjoys essentially simpler implementation than that entailed by the exact ML. Simulation results are presented, illustrating the performance of the estimators and validating our theoretical CRB analysis     

Gain-adapted hidden Markov models for recognition of clean andnoisy speech

In applying hidden Markov modeling for recognition of speech signals, the matching of the energy contour of the signal to the energy contour of the model for that signal is normally achieved by appropriate normalization of each vector of the signal prior to both training and recognition. This approach, however, is not applicable when only noisy signals are available for recognition. A unified approach is developed for gain adaptation in recognition of clean and noisy signals. In this approach, hidden Markov models (HMMs) for gain-normalized clean signals are designed using maximum-likelihood (ML) estimates of the gain contours of the clean training sequences. The models are combined with ML estimates of the gain contours of the clean test signals, obtained from the given clean or noisy signals, in performing recognition using the maximum a posteriori decision rule. The gain-adapted training and recognition algorithms are developed for HMMs with Gaussian subsources using the expectation-minimization (EM) approach     

基于二阶隐马尔可夫模型的文本信息抽取

隐马尔可夫模型是文本信息抽取的重要方法之一.在一阶隐马尔可夫模型中,假设状态转移概率和观察值输出概率仅依赖于模型当前的状态,一定程度降低了信息抽取的精确度.而二阶隐马尔可夫模型合理地考虑了概率和模型历史状态的关联性,对错误信息有更强的识别能力.提出了基于二阶隐马尔可夫模型的文本信息抽取算法;分析了二阶隐马尔可夫模型在文本信息抽取中的有效性;仿真实验表明,新的算法比基于一阶隐马尔可夫模型的算法具有更高的抽取精确度.     

Blind equalization of IIR channels using hidden Markov models andextended least squares

In this paper, we present a blind equalization algorithm for noisy IIR channels when the channel input is a finite state Markov chain. The algorithm yields estimates of the IIR channel coefficients, channel noise variance, transition probabilities, and state of the Markov chain. Unlike the optimal maximum likelihood estimator which is computationally infeasible since the computing cost increases exponentially with data length, our algorithm is computationally inexpensive. Our algorithm is based on combining a recursive hidden Markov model (HMM) estimator with a relaxed SPR (strictly positive real) extended least squares (ELS) scheme. In simulation studies we show that the algorithm yields satisfactory estimates even in low SNR. We also compare the performance of our scheme with a truncated FIR scheme and the constant modulus algorithm (CMA) which is currently a popular algorithm in blind equalization     

An integrated hybrid neural network and hidden Markov modelclassifier for sonar signals

We present here an integrated hybrid hidden Markov model and neural network (HMM/NN) classifier that combines the time normalization property of the HMM classifier with the superior discriminative ability of the neural net (NN). In the proposed classifier, a left-to-right HMM module is used first to segment the observation sequence of every exemplar into a fixed number of states. Subsequently, all the frames belonging to the same state are replaced by one average frame. Thus, every exemplar, irrespective of its time-state variation, is transformed into a fixed number of frames, i.e., a static pattern. The multilayer perceptron (MLP) neural net is then used as the classifier for these time-normalized exemplars. Some experimental results using sonar biologic signals are presented to demonstrate the superiority of the hybrid integrated classifier     

Fast evaluation of the likelihood of an HMM: ion channel currentswith filtering and colored noise

Hidden Markov models (HMMs) have been used in the study of single-channel recordings of ion channel currents for restoration of idealized signals from noisy recordings and for estimation of kinetic parameters. A key to their effectiveness from a computational point of view is that the number of operations to evaluate the likelihood, posterior probabilities and the most likely state sequence is proportional to the product of the square of the dimension of the state space and the length of the series. However, when the state space is quite large, computations can become infeasible. This can happen when the record has been lowpass filtered and when the noise is colored. In this paper, we present an approximate method that can provide very substantial reductions in computational cost at the expense of only a very small error. We describe the method and illustrate through examples the gains that can be made in evaluating the likelihood     

Maximum likelihood coordinate registration for over-the-horizonradar

Over-the-horizon radar exploits the refractive and multipath nature of high-frequency propagation through the ionosphere to achieve wide-area surveillance. The coordinate registration process converts the group delays and azimuths (i.e., slant coordinates) from a set of multipath target returns to an estimate of its location (i.e., ground coordinates). This is performed by associating the target returns with ray modes determined using a computational electromagnetic propagation model. Not surprisingly, errors in the estimates of down-range ionosphere parameters can seriously degrade the accuracy of the target location estimate. The coordinate registration method presented is designed to achieve improved accuracy by employing a statistical model for uncertainties in the ionosphere. Modeling down-range ionospheric parameters as random variables with known statistics facilitates maximum likelihood (ML) target location estimation, which is more robust to errors in the measured ionospheric conditions. The statistics of down-range ionospheric parameters can be determined using current and historical soundings of the ionosphere. ML target localization consists of determining the most likely target ground coordinates over an ensemble of ionospheric conditions consistent with the data. For greater computational efficiency, the likelihood function is approximated by a hidden Markov model (HMM) for the probability of a sequence of observed slant coordinates given a hypothesized target location. The parameters of the HMM are determined via Monte Carlo execution of a ray tracing propagation model for random realizations of the ionosphere. A simulation study performed using a random ionospheric model derived from ionogram measurements made at Wallops Island suggests that the ML method can potentially achieve average absolute miss distances as much as five times better than a conventional coordinate registration technique