Relative Entropy Rate Based Multiple Hidden Markov Model Approximation

This paper proposes a novel relative entropy rate (RER) based approach for multiple HMM (MHMM) approximation of a class of discrete-time uncertain processes. Under different uncertainty assumptions, the model design problem is posed either as a min-max optimisation problem or stochastic minimization problem on the RER between joint laws describing the state and output processes (rather than the more usual RER between output processes). A suitable filter is proposed for which performance results are established which bound conditional mean estimation performance and show that estimation performance improves as the RER is reduced. These filter consistency and convergence bounds are the first results characterizing multiple HMM approximation performance and suggest that joint RER concepts provide a useful model selection criteria. The proposed model design process and MHMM filter are demonstrated on an important image processing dim-target detection problem.     

二态隐马尔可夫过程熵率的逼近算法

基于熵率上下界收敛性,该文提出了一个算法以计算二态隐马尔可夫过程的熵率.该算法能以任意精度逼近熵率的理论值,且可计算最大偏差.算法的复杂度的对数和误差的对数为线性关系,因此其计算代价是可以接受的.该算法为计算一般隐马尔可夫模型的熵率提供了一种新途径.     

On the Entropy Rate of Hidden Markov Processes Observed Through Arbitrary Memoryless Channels

This paper studies the entropy rate of hidden Markov processes (HMPs) which are generated by observing a discrete-time binary homogeneous Markov chain through an arbitrary memoryless channel. A fixed-point functional equation is derived for the stationary distribution of an input symbol conditioned on all past observations. While the existence of a solution to the fixed-point functional equation is guaranteed by martingale theory, its uniqueness follows from the fact that the solution is the fixed point of a contraction mapping. The entropy or differential entropy rate of the HMP can then be obtained through computing the average entropy of each input symbol conditioned on past observations. In absence of an analytical solution to the fixed-point functional equation, a numerical method is proposed in which the fixed-point functional equation is first converted to a discrete linear system using uniform quantization and then solved efficiently. The accuracy of the computed entropy rate is shown to be proportional to the quantization interval. Unlike many other numerical methods, this numerical solution is not based on averaging over a sample path of the HMP.      

基于最大熵的隐马尔可夫模型文本信息抽取

文本信息抽取是处理海量文本的重要手段之一.最大熵模型提供了一种自然语言处理的方法.提出了一种基于最大熵的隐马尔可夫模型文本信息抽取算法.该算法结合最大熵模型在处理规则知识上的优势,以及隐马尔可夫模型在序列处理和统计学习上的技术基础,将每个观察文本单元所有特征的加权之和用来调整隐马尔可夫模型中的转移概率参数,实现文本信息抽取.实验结果表明,新的算法在精确度和召回率指标上比简单隐马尔可夫模型具有更好的性能.     

Hidden Markov processes

An overview of statistical and information-theoretic aspects of hidden Markov processes (HMPs) is presented. An HMP is a discrete-time finite-state homogeneous Markov chain observed through a discrete-time memoryless invariant channel. In recent years, the work of Baum and Petrie (1966) on finite-state finite-alphabet HMPs was expanded to HMPs with finite as well as continuous state spaces and a general alphabet. In particular, statistical properties and ergodic theorems for relative entropy densities of HMPs were developed. Consistency and asymptotic normality of the maximum-likelihood (ML) parameter estimator were proved under some mild conditions. Similar results were established for switching autoregressive processes. These processes generalize HMPs. New algorithms were developed for estimating the state, parameter, and order of an HMP, for universal coding and classification of HMPs, and for universal decoding of hidden Markov channels. These and other related topics are reviewed     

隐马尔可夫模型演化下的隐组查询

针对社会网络图中的隐组查询问题,提出了一种基于隐马尔科夫模型演化的方法。不同于传统方法,文中首先对“微观法则”提出了一些合理的假设,这些法则决定了在某时刻一个个体是否存在于一个特定群体。通过这些假设,可以得到社会个体和群体的动态演化。然后根据群体演化,找出长时间保持通信的群体作为潜在的隐组,再通过进一步分析,确保这些潜在的隐组以一个较高的概率成为理想的结果。为验证算法的有效性,文中分别对模拟和真实的数据进行了测试。     

Characterization of Ergodic Hidden Markov Sources

An algebraic criterion for the ergodicity of discrete random sources is presented. For finite-dimensional sources, which contain hidden Markov sources as a subclass, the criterion can be effectively computed. This result is obtained on the background of a novel, elementary theory of discrete random sources, which is based on linear spaces spanned by word functions, and linear operators on these spaces. An outline of basic elements of this theory is provided.     

Modeling iCAR via Multi-Dimensional Markov Chains

iCAR is a new wireless system architecture based on the integration of cellular and modern ad hoc relaying technologies. It addresses the congestion problem due to limited channel access in a cellular system and provides interoperability for heterogeneous networks. The iCAR system can efficiently balance traffic loads and share channel resource between cells by using ad hoc relaying stations (ARS) to relay traffic from one cell to another dynamically. Analyzing the performance of iCAR is nontrivial as the classic Erlang-B formula no longer applies when relaying is used. In this paper, we build multi-dimensional Markov chains to analyze the performance of the iCAR system in terms of the call blocking probability. In particular, we develop an approximate model as well as an accurate model. While it can be time-consuming and tedious to obtain the solutions of the accurate model, the approximate model yields analytical results that are close to the simulation results we obtained previously. Our results show that with a limited number of ARSs, the call blocking probability in a congested cell as well as the overall system can be reduced.     

Universal Filtering Via Hidden Markov Modeling

The problem of discrete universal filtering, in which the components of a discrete signal emitted by an unknown source and corrupted by a known discrete memoryless channel (DMC) are to be causally estimated, is considered. A family of filters are derived, and are shown to be universally asymptotically optimal in the sense of achieving the optimum filtering performance when the clean signal is stationary, ergodic, and satisfies an additional mild positivity condition. Our schemes are comprised of approximating the noisy signal using a hidden Markov process (HMP) via maximum-likelihood (ML) estimation, followed by the use of the forward recursions for HMP state estimation. It is shown that as the data length increases, and as the number of states in the HMP approximation increases, our family of filters attains the performance of the optimal distribution-dependent filter. An extension to the case of channels with memory is also established.     

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.     

Hidden Markov Models With Stick-Breaking Priors

The number of states in a hidden Markov model (HMM) is an important parameter that has a critical impact on the inferred model. Bayesian approaches to addressing this issue include the nonparametric hierarchical Dirichlet process, which does not extend to a variational Bayesian (VB) solution. We present a fully conjugate, Bayesian approach to determining the number of states in a HMM, which does have a variational solution. The infinite-state HMM presented here utilizes a stick-breaking construction for each row of the state transition matrix, which allows for a sparse utilization of the same subset of observation parameters by all states. In addition to our variational solution, we discuss retrospective and collapsed Gibbs sampling methods for MCMC inference. We demonstrate our model on a music recommendation problem containing 2250 pieces of music from the classical, jazz, and rock genres.     

Hidden Markov models for character recognition

A hierarchical system for character recognition with hidden Markov model knowledge sources which solve both the context sensitivity problem and the character instantiation problem is presented. The system achieves 97-99% accuracy using a two-level architecture and has been implemented using a systolic array, thus permitting real-time (1 ms per character) multifont and multisize printed character recognition as well as handwriting recognition.     

隐马尔可夫模型在生物信息学中的应用

结合DNA序列分析例子,介绍了HMMs与其的解码、估计、学习3个计算问题。综述了HMMs在生物信息学中的应用情况,同时对HMMs在生物信息学中可能的发展方向进行了展望。     

Hidden Markov modeling of flat fading channels

Hidden Markov models (HMMs) are a powerful tool for modeling stochastic random processes. They are general enough to model with high accuracy a large variety of processes and are relatively simple allowing us to compute analytically many important parameters of the process which are very difficult to calculate for other models (such as complex Gaussian processes). Another advantage of using HMMs is the existence of powerful algorithms for fitting them to experimental data and approximating other processes. In this paper, we demonstrate that communication channel fading can be accurately modeled by HMMs, and we find closed-form solutions for the probability distribution of fade duration and the number of level crossings     

Hidden Markov models for multiaspect target classification

This article presents a new approach for target identification, in which we fuse scattering data from multiple target-sensor orientations. The multiaspect data is processed via hidden Markov model (HMM) classifiers, buttressed by physics-based feature extraction. This approach explicitly accounts for the fact that the target-sensor orientation is generally unknown or “hidden”. Discrimination results are presented for measured scattering data     

Hidden Markov model for multidimensional wavefront tracking

In subsurface sensing, the estimation of the delays (wavefronts) of the backscattered wavefields is a very time-consuming, mostly manual task. We propose delay estimation by exploiting the continuity of the wavefronts modeled as a Markov chain. Each wavefront is a realization of Brownian motion with a correlation that depends on the distance between each source/receiver pair. Therefore, the delay profiles can be tracked with any known method by assuming that the ordered sequence of signals is described by a hidden Markov model (HMM). Linear array provides the most natural data-ordering, and in this case the tracking algorithms can preserve the target/tracker association. However, when measurements are multidimensional, the volume-slicing strategies, that are able to get a linear array of (virtually) ordered signals, select the measurements independently of the target. When different estimates along slices are merged mis-ties can occur easily. Since data-ordering is a main issue for irregularly positioned sources and receivers, we propose a region growing tracking technique that orders (for each specified target) the data while tracking. The ordering is based on the maximum a posteriori probability of detection. Experiments based on multidimensional measurements show that this region growing tracking algorithm based on HMM preserves the target/tracker association     

Music Analysis Using Hidden Markov Mixture Models

We develop a hidden Markov mixture model based on a Dirichlet process (DP) prior, for representation of the statistics of sequential data for which a single hidden Markov model (HMM) may not be sufficient. The DP prior has an intrinsic clustering property that encourages parameter sharing, and this naturally reveals the proper number of mixture components. The evaluation of posterior distributions for all model parameters is achieved in two ways: 1) via a rigorous Markov chain Monte Carlo method; and 2) approximately and efficiently via a variational Bayes formulation. Using DP HMM mixture models in a Bayesian setting, we propose a novel scheme for music analysis, highlighting the effectiveness of the DP HMM mixture model. Music is treated as a time-series data sequence and each music piece is represented as a mixture of HMMs. We approximate the similarity of two music pieces by computing the distance between the associated HMM mixtures. Experimental results are presented for synthesized sequential data and from classical music clips. Music similarities computed using DP HMM mixture modeling are compared to those computed from Gaussian mixture modeling, for which the mixture modeling is also performed using DP. The results show that the performance of DP HMM mixture modeling exceeds that of the DP Gaussian mixture modeling.     

基于HMM的系统可靠性建模研究

传统的系统可靠性分析需要检测系统中所有元件的故障状态，并不适用予系统的定期维护和保养检查。隐马尔可夫模型(HMM)是一种双重随机过程，能够解决随机不确定问题。通过对系统关键点的检测，经过复杂的网络运算综合得到系统状态的检测参数，给出了实现检测的相关网络模型以及相应的算法。     

语音识别隐马尔可夫模型的改进

由于在语音识别中被广泛应用的隐马尔可夫模型是一重马尔可夫模型，它不能充分地描述语音信号的时间相依性。虽然理论上可将ＨＭＭ扩展成多重马尔可夫模型，但由于所需运算量和存储量将成指数增长而使其难以应用。因此，本文提出一种新模型，它是由ＨＭＭ与一个能描述语音信号时间相依性的多维高斯密度函数相结合构成的。本文从理论上论证了新模型的合理性。对汉语不计声调的全部４０９个单音节的识别实验结果表明：新模型的识别率显     

Spectral Analysis of Functions of Markov Chains with Applications

This paper deals with the spectral analysis of digital processes obtained through memoryless functions of stationary Markov chains. Under the assumption that the Markov chain is ergodic, not necessarily acyclic, closed form formulas are derived for both the discrete part (spectral lines) and the continuous part of the spectral density. The results are applied at the output of a finite state sequential machine driven by a stationary Markov chain, which represents a general model of several situations of engineering interest. Finally, the theory is used to evaluate the spectrum of encoded and modulated digital signals.