Adaptive estimation of HMM transition probabilities

This paper presents new schemes for recursive estimation of the state transition probabilities for hidden Markov models (HMMs) via extended least squares (ELS) and recursive state prediction error (RSPE) methods. Local convergence analysis for the proposed RSPE algorithm is shown using the ordinary differential equation (ODE) approach developed for the more familiar recursive output prediction error (RPE) methods. The presented scheme converges and is relatively well conditioned compared with the previously proposed RPE scheme for estimating the transition probabilities that perform poorly in low noise. The ELS algorithm presented is computationally of order N², which is less than the computational effort of order N⁴ required to implement the RSPE (and previous RPE) scheme, where N is the number of Markov states. Building on earlier work, an algorithm for simultaneous estimation of the state output mappings and the state transition probabilities that requires less computational effort than earlier schemes is also presented and discussed. Implementation aspects of the proposed algorithms are discussed, and simulation studies are presented to illustrate the convergence and convergence rates     

Online Bayesian estimation of transition probabilities for Markovian jump systems

Markovian jump systems (MJSs) evolve in a jump-wise manner by switching among simpler models, according to a finite Markov chain, whose parameters are commonly assumed known. This paper addresses the problem of state estimation of MJS with unknown transition probability matrix (TPM) of the embedded Markov chain governing the jumps. Under the assumption of a time-invariant but random TPM, an approximate recursion for the TPMs posterior probability density function (PDF) within the Bayesian framework is obtained. Based on this recursion, four algorithms for online minimum mean-square error (MMSE) estimation of the TPM are derived. The first algorithm (for the case of a two-state Markov chain) computes the MMSE estimate exactly, if the likelihood of the TPM is linear in the transition probabilities. Its computational load is, however, increasing with the data length. To limit the computational cost, three alternative algorithms are further developed based on different approximation techniques-truncation of high order moments, quasi-Bayesian approximation, and numerical integration, respectively. The proposed TPM estimation is naturally incorporable into a typical online Bayesian estimation scheme for MJS [e.g., generalized pseudo-Bayesian (GPB) or interacting multiple model (IMM)]. Thus, adaptive versions of MJS state estimators with unknown TPM are provided. Simulation results of TPM-adaptive IMM algorithms for a system with failures and maneuvering target tracking are presented.     

Particle filters for state estimation of jump Markov linear systems

Jump Markov linear systems (JMLS) are linear systems whose parameters evolve with time according to a finite state Markov chain. In this paper, our aim is to recursively compute optimal state estimates for this class of systems. We present efficient simulation-based algorithms called particle filters to solve the optimal filtering problem as well as the optimal fixed-lag smoothing problem. Our algorithms combine sequential importance sampling, a selection scheme, and Markov chain Monte Carlo methods. They use several variance reduction methods to make the most of the statistical structure of JMLS. Computer simulations are carried out to evaluate the performance of the proposed algorithms. The problems of on-line deconvolution of impulsive processes and of tracking a maneuvering target are considered. It is shown that our algorithms outperform the current methods     

Adaptive error coding using channel prediction

In this paper, we construct a finite-state Markov chain model for a Rayleigh fading channel by partitioning the range of the received signal envelope into K intervals. Using a simulation of the classic two-ray Rayleigh fading model, a Markov transition probability matrix is obtained. Using this matrix to predict the channel state, we introduce an adaptive forward error correction (FEC) coding scheme. Simulation results are presented to show that the adaptive FEC coding scheme significantly improves the performance of a wireless communication system.     

On-line estimation of hidden Markov model parameters based on theKullback-Leibler information measure

Sequential or online hidden Markov model (HMM) signal processing schemes are derived, and their performance is illustrated by simulation. The online algorithms are sequential expectation maximization (EM) schemes and are derived by using stochastic approximations to maximize the Kullback-Leibler information measure. The schemes can be implemented either as filters or fixed-lag or sawtooth-lag smoothers. They yield estimates of the HMM parameters including transition probabilities, Markov state levels, and noise variance. In contrast to the offline EM algorithm (Baum-Welch scheme), which uses the fixed-interval forward-backward scheme, the online schemes have significantly reduced memory requirements and improved convergence, and they can estimate HMM parameters that vary slowly with time or undergo infrequent jump changes. Similar techniques are used to derive online schemes for extracting finite-state Markov chains imbedded in a mixture of white Gaussian noise (WGN) and deterministic signals of known functional form with unknown parameters     

An MCMC sampling approach to estimation of nonstationary hiddenMarkov models

Hidden Markov models (HMMs) represent a very important tool for analysis of signals and systems. In the past two decades, HMMs have attracted the attention of various research communities, including the ones in statistics, engineering, and mathematics. Their extensive use in signal processing and, in particular, speech processing is well documented. A major weakness of conventional HMMs is their inflexibility in modeling state durations. This weakness can be avoided by adopting a more complicated class of HMMs known as nonstationary HMMs. We analyze nonstationary HMMs whose state transition probabilities are functions of time that indirectly model state durations by a given probability mass function and whose observation spaces are discrete. The objective of our work is to estimate all the unknowns of a nonstationary HMM, which include its parameters and the state sequence. To that end, we construct a Markov chain Monte Carlo (MCMC) sampling scheme, where sampling from all the posterior probability distributions is very easy. The proposed MCMC sampling scheme has been tested in extensive computer simulations on finite discrete-valued observed data, and some of the simulation results are presented     

Robust Fault Detection of Uncertain Time-Delay Markovian Jump Systems with Different System Modes

In this paper, a robust fault detection filter (RFDF)design scheme is presented for uncertain nonlinear Markovian jump systems with mixed delays. By using a observer-based fault detection filter as residual generator, the RFDF design is formulated as an H _∞-filtering problem. Particularly, two different Markov processes are considered for modeling the randomness of system matrix and the state delay; meanwhile, the corresponding two kinds of transition rate matrices are assumed to be incompletely accessible, that is, the one with partially unknown entries and the other with polytopic uncertainties. By using a new convex polyhedron technique, some new sufficient conditions are established in terms of delay-dependent linear matrix inequalities (LMIs) to synthesize the residual generation scheme. Finally, a numerical example is given to illustrate the effectiveness of the proposed techniques.     

Blind identification of multiuser nonlinear channels using tensor decomposition and precoding

This paper presents two blind identification methods for nonlinear memoryless channels in multiuser communication systems. These methods are based on the parallel factor (PARAFAC) decomposition of a tensor composed of channel output covariances. Such a decomposition is possible owing to a new precoding scheme developed for phase-shift keying (PSK) signals modeled as Markov chains. Some conditions on the transition probability matrices (TPM) of the Markov chains are established to introduce temporal correlation and satisfy statistical correlation constraints inducing the PARAFAC decomposition of the considered tensor. The proposed blind channel estimation algorithms are evaluated by means of computer simulations.     

基于马尔科夫链的灰狼优化算法收敛性研究

针对灰狼优化算法（Grey Wolf Optimization,GWO）在收敛性研究上的不足,首先,通过定义灰狼群状态转移序列,建立了GWO算法的马尔科夫（Markov）链模型,通过分析Markov链的性质,证明它是有限齐次 Markov链;其次,通过分析灰狼群状态序列最终转移状态,结合随机搜索算法的收敛准则,验证了GWO算法的全局收敛性;最后,对典型测试函数、偏移函数及旋转函数进行仿真实验,并与多种群体智能算法进行对比分析.实验结果表明,GWO算法具有全局收敛性强、计算耗时短和寻优精度高等优势.     

异构网络中多无线电多信道环境下信道状态预测算法研究

该文针对异构网络环境未知性的特点,基于部分可测马尔科夫(POMDP)模型,结合认知无线电频谱侦测技术,提出了一种新的多无线电多信道环境下信道状态预测算法。该算法通过对信道状态历史信息的分析,推导出信道信念状态(belief state)的初始分布和转移概率,并以此选择出具有最佳回报的信道以供接入,从而达到提高信道利用率的目的。仿真结果表明算法性能要优于传统算法。     

Lightweight opportunistic routing forwarding strategy based on Markov chain

A lightweight opportunistic routing forwarding strategy (MOR) was proposed based on Markov chain.In the scheme,the execute process of network was divided into a plurality of equal time period,and the random encounter state of node in each time period was represented by activity degree.The state sequence of a plurality of continuous time period constitutes a discrete Markov chain.The activity degree of encounter node was estimated by Markov model to predict its state of future time period,which can enhance the accuracy of activity degree estimation.Then,the method of comprehensive evaluating forwarding utility was designed based on the activity degree of node and the average encounter interval.MOR used the utility of node for making a routing forwarding decision.Each node only maintained a state of last time period and a state transition probability matrix,and a vector recording the average encounter interval of nodes.So,the routing forwarding decision algorithm was simple and efficient,low time and space complexity.Furthermore,the method was proposed to set optimal number of the message copy based on multiple factors,which can effectively balance the utilization of network resources.Results show that compared with existing algorithms,MOR algorithm can effectively increase the delivery ratio and reduce the delivery delay,and lower routing overhead ratio.     

Probabilistic algorithms for blind adaptive multiuser detection

Two probabilistic adaptive algorithms for jointly detecting active users in a DS-CDMA system are reported. The first one, which is based on the theory of hidden Markov models (HMMs) and the Baum-Welch (1070) algorithm, is proposed within the CDMA scenario and compared with the second one, which is a previously developed Viterbi-based algorithm. Both techniques are completely blind in the sense that no knowledge of the signatures, channel state information, or training sequences is required for any user. Once convergence has been achieved, an estimate of the signature of each user convolved with its physical channel response (CR) and estimated data sequences are provided. This CR estimate can be used to switch to any decision-directed (DD) adaptation scheme. Performance of the algorithms is verified via simulations as well as on experimental data obtained in an underwater acoustics (UWA) environment. In both cases, performance is found to be highly satisfactory, showing the near-far resistance of the analyzed algorithms     

Multiuser Detection Using Hidden Markov Model

Many existing multiuser detection algorithms assume that the user sequences are independent and identically distributed (i.i.d.). These algorithms, however, may not be efficient when the user sequences sent to a multiuser system are time correlated due to signal processing procedures such as channel coding. In this paper, we assume that the user sequences are time correlated and can be modeled as first-order, finite-state Markov chains. The proposed algorithm applies the decision feedback framework in which a linear filter based on the maximum target likelihood (MTL) criterion is derived to remove the interferences. A hidden Markov model (HMM) estimator is applied to the output of the MTL filter to estimate the user data, noise variance, and state transition probabilities. The estimated user data in turn are applied to update the parameters of the MTL filter. By exploiting the transmission of training symbols, the proposed algorithm requires neither knowledge of the user codes nor the timing information. Simulation results show the performance improvement of the proposed algorithm by exploiting the time-correlated redundancy of the Markov sources.     

一种改进的图像拼接检测算法

通过对图像拼接技术特点的分析,提出一种基于图像纹理特征分析和马尔科夫模型的改进的拼接图像检测算法。该算法计算图像DCT域上的马尔科夫转移概率矩阵,同时对图像进行纹理分析,得到两类特征共178维。为评估该检测算法的性能,提出了一个具体实现方案,提取了图片数据集的特征,使用支持向量机（Support Vector Machine,SVM）对特征数据进行训练与分类。实验表明,该方法取得了较好的分类效果。     

Hidden Markov model state estimation with randomly delayedobservations

This paper considers state estimation for a discrete-time hidden Markov model (HMM) when the observations are delayed by a random time. The delay process is itself modeled as a finite state Markov chain that allows an augmented state HMM to model the overall system. State estimation algorithms for the resulting HMM are then presented, and their performance is studied in simulations. The motivation for the model stems from the situation when distributed sensors transmit measurements over a connectionless packet switched communications network     

Modeling End-to-End Wireless Lossy Channels: A Finite-State Markov Approach

In this paper, we present a model for wireless losses in packet transmission data networks. The model provides information about the wireless channel status that can be used in congestion control schemes. A Finite State Markov Channel (FSMC) approach is implemented to model the wireless slow fading for different modulation schemes. The arrival process statistics of the packet traces determine the channel state transition probabilities, where the statistics of both error-free and erroneous bursts are captured. Later, we establish SNR partitioning scheme that uses the transition probabilities as a basis for the state margins. The crossover probability associated with each state is calculated accordingly. We also propose an end-to-end approach to loss discrimination based on the channel state estimation at the receiver. Finally, we present a scheme for finding the channel optimal number of states as a function of the SNR. The presented FSMC approach does not restrict the state transitions to the adjacent states, nor does impose constant state duration as compared to some literature studies. We validate our model by experimental packet traces. Our simulation results show the feasibility of building a fading channel model for better wireless-loss awareness.     

Minimization of mealy finite state machines via internal state merging

The problem of minimizing Mealy finite state machines (FSMs) arises when digital devices based on programmable logic integrated circuits are synthesized. A distinctive feature of the approach proposed is that merging of two states is used and an FSM is represented as a transition list. The conditions used to merge states, the functioning identity and the FSM’s behavior determinacy, are presented. Situations leading to wait state formation caused by state merging are discussed. The algorithms for minimizing the internal states, transition paths, and input variable of FSMs are described. The features of application of the method proposed are discussed.     

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     

Iterative algorithms for state estimation of jump Markov linearsystems

Jump Markov linear systems (JMLSs) are linear systems whose parameters evolve with time according to a finite state Markov chain. Given a set of observations, our aim is to estimate the states of the finite state Markov chain and the continuous (in space) states of the linear system. In this paper, we present original deterministic and stochastic iterative algorithms for optimal state estimation of JMLSs. The first stochastic algorithm yields minimum mean square error (MMSE) estimates of the finite state space Markov chain and of the continuous state of the JMLS. A deterministic and a stochastic algorithm are given to obtain the marginal maximum a posteriori (MMAP) sequence estimate of the finite state Markov chain. Finally, a deterministic and a stochastic algorithm are derived to obtain the MMAP sequence estimate of the continuous state of the JMLS. Computer simulations are carried out to evaluate the performance of the proposed algorithms. The problem of deconvolution of Bernoulli-Gaussian (BG) processes and the problem of tracking a maneuvering target are addressed     

Binary image steganalysis based on pixel mesh Markov transition matrix

Binary image stego systems have already been well developed, which raises the requirement of a steganalytic method that detects these stego systems reliably. In this paper, a steganalytic method based on the pixel mesh Markov transition matrix (PMMTM) is presented to detect binary image steganography in the spatial domain. The proposed scheme measures the embedding distortion on the texture consistency. Further, the dependence among texture structures is organized as the Markov transition of pixel meshes. The final dimensionality-reduced feature set is formed by shrinking the obtained PMMTM according to its detection performance on the embedding simulators, which are developed to simulate practical stego systems. In the end, experimental results are reported, demonstrating that the proposed approach can effectively and reliably detect state-of-the-art binary image stego systems.