The Viterbi Algorithm for Models of Hidden Markov Processes with the Unknown Moment of Appearance of Parameter Jump

The methods of the theory of optimal nonlinear filtering of the Markov processes is used to develop the Viterbi algorithm for obtaining optimal estimates of a sequence of hidden states in the model of discrete-value Markov processes generalized to the case of jump-like changing parameters with an unknown time of the jump appearance. The results of numerical simulation of the algorithm performance are given. __________ Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Radiofizika, Vol. 48, No. 4, pp. 358–366, April 2005.     

Algorithm for Optimal Estimation of Appearance Times of Pulsed Signals in Discrete Time

Using the methods of optimal nonlinear Markov filtering, we obtain an algorithm for optimal mean-square estimation of appearance times of random pulsed variations in signal parameters against the background of white Gaussian noise in discrete time. Linear difference equations are used to describe signals, noise, and the observed processes. Equations of the algorithm permitting real-time calculations of the a posteriori variances and optimal estimations of pulse-appearance times are obtained in the approximation of Gaussian conditional probability densities. We present simulation results for algorithm operation in the particular problem of estimating the appearance times of two pulsed signals having the known shapes and observed against noise background.     

An optimal control approach to probabilistic Boolean networks

External control of some genes in a genetic regulatory network is useful for avoiding undesirable states associated with some diseases. For this purpose, a number of stochastic optimal control approaches have been proposed. Probabilistic Boolean networks (PBNs) as powerful tools for modeling gene regulatory systems have attracted considerable attention in systems biology. In this paper, we deal with a problem of optimal intervention in a PBN with the help of the theory of discrete time Markov decision process. Specifically, we first formulate a control model for a PBN as a first passage model for discrete time Markov decision processes and then find, using a value iteration algorithm, optimal effective treatments with the minimal expected first passage time over the space of all possible treatments. In order to demonstrate the feasibility of our approach, an example is also displayed.     

Adaptive Sampling of Large Deviations

We introduce and test an algorithm that adaptively estimates large deviation functions characterizing the fluctuations of additive functionals of Markov processes in the long-time limit. These functions play an important role for predicting the probability and pathways of rare events in stochastic processes, as well as for understanding the physics of nonequilibrium systems driven in steady states by external forces and reservoirs. The algorithm uses methods from risk-sensitive and feedback control to estimate from a single trajectory a new process, called the driven process, known to be efficient for importance sampling. Its advantages compared to other simulation techniques, such as splitting or cloning, are discussed and illustrated with simple equilibrium and nonequilibrium diffusion models.     

Algorithm for Detecting a Sequence of Pulsed Signals with Random Appearance Times

Using the methods of optimal nonlinear Markov filtering, we obtain an algorithm for optimal detection of a sequence of pulsed signals with random times of appearance against the background of white Gaussian noise in discrete time. Statistical characteristics of the synthesized algorithm are studied by computer simulation. The dependences of correct-detection probability on the signal-to-noise ratio and the intervals between pulses are obtained. It is shown that using the optimal nonlinear filtering methods we can improve the quality of detection of a sequence of pulsed signals compared with the methods based on the matched filtering of individual pulses in a packet.     

STUDY OF ALGORITHMS FOR ESTIMATING SIGNALS WITH A PULSED-DISTURBANCE FLOW

Using the methods of the Markov theory of optimal nonlinear filtering, we derive equations of the algorithm for estimating random signals described by linear difference equations in discrete time in the case of a pulsed-disturbance flow. Optimal estimates of signals are represented as the sum of auxiliary estimates allowing for the influence of pulsed disturbances spaced apart by a multiple number of pulses. The results of mathematical simulation are given and the algorithm structure is discussed.     

窄带语音带宽扩展算法研究

为了降低谱失真,提出了一种基于隐马尔科夫模型的窄带语音带宽扩展算法。首先,算法选取与宽带谱包络互信息大的参数构成特征矢量,并利用隐马尔可夫状态和过去观察特征矢量的联合先验概率估计条件后验概率。其次,以条件后验概率为基础,算法结合贝叶斯条件参数估计法和最小均方差准则估计宽带谱包络。针对宽带激励信号估计,基于信号高频和低频的谐波相关性,提出了一种中频激励扩展算法。实验结果表明,与传统的基于隐马尔可夫模型的带宽扩展算法相比,本文算法可降低0.187 dB的平均谱失真,将谱失真大于10 dB的语音帧减少了34.3%。      

Trans-dimensional geoacoustic inversion

This paper develops a general trans-dimensional Bayesian methodology for geoacoustic inversion. Trans-dimensional inverse problems are a generalization of fixed-dimensional inversion that includes the number and type of model parameters as unknowns in the problem. By extending the inversion state space to multiple subspaces of different dimensions, the posterior probability density quantifies the state of knowledge regarding inversion parameters, including effects due to limited knowledge about appropriate parametrization of the environment and error processes. The inversion is implemented here using a reversible-jump Markov chain Monte Carlo algorithm and the seabed is parametrized using a partition model. Unknown data errors are addressed by including a data-error model. Jumps between dimensions are implemented with a birth-death methodology that allows transitions between dimensions by adding or removing interfaces while maintaining detailed balance in the Markov chain. Trans-dimensional inversion results in an inherently parsimonious solution while partition modeling provides a naturally self-regularizing algorithm based on data information content, not on subjective regularization functions. Together, this results in environmental estimates that quantify appropriate seabed structure as supported by the data, allowing sharp discontinuities while approximating smooth transitions where needed. This approach applies generally to geoacoustic inversion and is illustrated here with seabed reflection-coefficient data.     

Optimal estimation of the parameters of a nonstationary random pulse train in discrete time

The problem of optimal estimation of the parameters of a nonstationary sequence of random pulses observed additively with the noise is considered with the step change in average pulse repetition rate taken into account. A recurrent algorithm is derived for optimal estimation of the pulse repetition rate and time of its jump in real time. The optimal assessment of the Bernoulli trial parameters is shown as an example. The results of computer simulation experiments are presented.Lobachevsky State University, Nizhny Novgorod. Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Radiofizika, Vol. 38, No. 7, pp. 678–694, July, 1995.     

Intrinsic irreversibility of Kolmogorov dynamical systems

We give the mathematical details and various extensions of the results stated in previous work of Courbage and Prigogine. “Intrinsic random systems” are deterministic and conservative dynamical systems for which we can associate two dissipative Markov processes through a one-to-one “change of representation”, the first leading to equilibrium for t→+∞ and the second for t→-∞. The microscopic formulation of the second principle of thermodynamics permits to lift the degeneracy by the exclusion of all states that do not approach equilibrium for t→+∞. The set of admitted initial conditions $\text{D}$⁺ is then characterized by a non-equilibrium entropy functional which is infinite for rejected initial states and takes finite values for admitted initial conditions. Thus, rejected initial states correspond to an infinite amount of information. To realize this selection rule we consider general probability measures on phase space that are not necessarily absolutely continuous and we extend the theory of transition to Markov processes to such measures. Owing to the non-invariance of $\text{D}$⁺ under the time inversion, the evolution of these states in the new representation can only be given by one of the two possible Markov processes.     

Optimal estimation of the time instant of occurrence of an impulse disturbance in a random signal in discrete time

Using the methods of the Markov theory of nonlinear filtering, the problem of optimal estimation in discrete time of the time instant of occurrence of a random impulse disturbance in a signal observed against a background of white noise has been solved. It is shown that the optimal estimate in the mean-square sense for the impulse occurrence can be represented as the sum of two conditional estimates calculated in current time with the help of a system of recurrent equations with a posteriori probability of the impulse occurrence and auxiliary probability densities. A simplified approximate estimation algorithm has been developed using a Gaussian approximation of the auxiliary probability densities.Nizhny Novgorod State University. Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Radiofizika, Vol. 36, No. 6, pp. 498–511, June, 1993.     

Narrowband speech wideband extension algorithm research

To reduce the spectral distortion,a Hidden Markov Model-based narrowband speech bandwidth extension algorithm is presented.Firstly,the parameters which have higher mutual information with wideband envelope were extracted to constitute the feature vector,and then a posterior probability was calculated via the joint probability of the partial observation feature vector sequence and the markov states.Secondly,based on the posterior probability,the wideband envelope was estimated using Bayesian parameter estimation method and minimum mean square error criteria.For estimation of wideband excitation signal,intermediate frequency extension algorithm is proposed based on the harmonic correlation between the low frequency and high frequency.The experimental results show that,compared with the traditional bandwidth extension algorithm based on Hidden Markov Model,the average spectral distortion is reduced by 0.187 dB and the number of speech frame with spectral distortion over10dB is decreased by 34.3%.     

Transition events fluctuations in jump markovian dynamics. A general approach to Šolc's problem

We introduce a new formalism for computing the moments of transition events for nonhomogeneous Markov jump processes. Our method is applied directly to the master equation and does not involve the use of diffusion approximation. The general theory is applied to produce exact expressions for means and dispersions. For time homogeneous Markov processes with a finite number of connected states we are able to prove that both means and dispersions asymptotically increase linearly in time.     

Parameter estimation for the piecewice-polynomial mean value trend of a stochastic time series

We consider the problem of mean value trend estimation for a stochastic time series in a mixture with noise. The trend is simulated as a polynomial function of time with parameters changing discontinuously at a random instant. The proposed solution of this problem is based on the optimal nonlinear filtering theory for pulsed Markovian processes. An algorithm for approximate estimation of piesewise-linear trend parameters is devised as an example. The results of numerical simulation of a synthesized algorithm are presented. Lobachevsky State University, Nizhny Novgorod, Russia. Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Radiofizika, Vol. 40, No. 11, pp. 1405–1415, November, 1997.     

模拟回火马尔可夫链蒙特卡罗全波形分析方法

针对传统的全波形分析方法不能快速自动处理全波形数据的缺点,提出了一种模拟回火马尔可夫链蒙特卡罗全波形分析法,用于求解全波形数据中的波峰数和峰值位置等参量.该方法采用Metropolis更新策略求解波峰数量和噪声两个参量,以达到快速求解的目的;而峰值位置和波峰幅值则采用改进的模拟回火策略求解,通过添加的主动干预回火步骤实现对参量更新过程的有效探测,以满足对速度或运算收敛性的要求.模拟回火马尔可夫链蒙特卡罗全波形分析方法以马尔可夫算法为基础,仍保持马氏链的收敛性,从而保证本方法具有良好的鲁棒性,实现对全波形数据的自动化处理.     

The Optimal Sink and the Best Source in a Markov Chain

It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e.g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance (“information”) that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc.     

EXTRACTION OF STRUCTURAL SYSTEM MATRICES FROM AN IDENTIFIED STATE-SPACE SYSTEM USING THE COMBINED MEASUREMENTS OF DVA

A time domain method for the extraction of the structural system matrices (mass, damping and stiffness matrices) from an identified state-space system is proposed in this paper using the combined measurements of displacement, velocity and acceleration (DVA) together with the input excitations. The method is based on the invariance of continuous-time Markov parameters. An explicit expression of the relationship between the continuous-time Markov parameters, the structural system matrices, and the influence matrices for output DVA as well as the input force has been derived. The determination of structural system matrices is also valid when only the displacement, velocity or acceleration responses are measured. In this paper, the equivalent state system matrices are obtained by an algorithm, which combines the eigensystem realization algorithm (ERA) and the autoregressive with exogeneous (ARX) model. The ARX model provides the necessary discrete-time Markov parameters from the measured input and output data, and then the equivalent state system matrices are identified from discrete-time Markov parameters by using the ERA. A lumped mass model with three degrees of freedom is employed to illustrate the accuracy and feasibility of the presented method.     

Optimal estimates of free energies from multistate nonequilibrium work data

We derive the optimal estimates of the free energies of an arbitrary number of thermodynamic states from nonequilibrium work measurements; the work data are collected from forward and reverse switching processes and obey a fluctuation theorem. The maximum likelihood formulation properly reweights all pathways contributing to a free energy difference and is directly applicable to simulations and experiments. We demonstrate dramatic gains in efficiency by combining the analysis with parallel tempering simulations for alchemical mutations of model amino acids.     

Optimal estimate of the parameters of a twice stochastic poisson stream of events with errors in measuring times the events occur

A problem of estimating the parameters of a twice stochastic Poisson stream of events is considered. Formulas are derived for calculating the a posteriori probability density function for vector-parameters of the stream which is the most complete characteristic of the parameters of the stream. An optimal algorithm for estimating the vector-parameters as the a posteriori mean and an algorithm for calculating the estimates with the use of approximate calculation formulas are suggested. Tomsk State University. Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Fizika, No. 4, pp. 19–27, April, 1999.     

Glauber Dynamics of the Random Energy Model

 We investigate the long-time behavior of the Glauber dynamics for the random energy model below the critical temperature. We give very precise estimates on the motion of the process to and between the states of extremal energies. We show that when disregarding time, the consecutive steps of the process on these states are governed by a Markov chain that jumps uniformly on all possible states. The mean times of these jumps are also computed very precisely and are seen to be asymptotically independent of the terminal point. A first indicator of aging is the observation that the mean time of arrival in the set of states that have waiting times of order T is itself of order T. The estimates proven in this paper will furnish crucial input for a follow-up paper where aging is analysed in full detail. Received: 9 October 2001 / Accepted: 17 October 2002 Published online: 28 February 2003 RID="*" ID="*" Work partially supported by the Swiss National Science Foundation under contract 21-65267.01 RID="⋆⋆" ID="⋆⋆" On leave from CPT-CNRS, Luminy, Case 907, 13288 Marseille Cedex 9, France. E-mail:veronique.gayrard@epfl.ch Communicated by M. Aizenman