News from the World of Hidden Markov Models

by László Gerencsér

In the area of Hidden Markov Models (HMM), successful research with a wide range of applications has been performed at SZTAKI by the Stochastic Systems Research Group. Much of the progress is due to recent advances made in the mathematical technology relevant to the analysis of HMMs.

Hidden Markov Models or HMMs have become a basic tool for modeling stochastic systems with a wide range of applications in such diverse areas as speech recognition, telecommunication, radar, nanotechnology, data mining, econometrics and financial mathematics. Spatial HMM processes have also been widely used in biology (DNA sequencing, modeling the spatial structure of proteins, molecular imaging) and astronomy. This research area is a central theme for ERNSI, the European Research Network for Systems Identification, and for the ERCIM Working Group in Control and Systems.

A Hidden Markov Model is characterized by an unseen state process - often a finite state Markov process - and an observation or read-out process - a random function of the state. The read-outs are conditionally independent and identically distributed given the state sequence. HMMs are special stochastic systems in which the transition from state to state, and state to read-out, can be decoupled. An important example is a quantized Gaussian ARMA-process, which arises in microrobotics and mobile communication. Another important example is a Gaussian dynamic mixture.

The estimation of the unseen state of a Hidden Markov Model is a basic problem in applications. It requires the estimation of the unknown dynamics of the HMM. A variety of new techniques have been developed in the last decade, with research focused on the analysis HMMs with finite state space and continuous read-outs.

The key partners of SZTAKI in this area have been IRISA/INRIA, Rennes (Francois LeGland), CNR ISIB (formerly LADSEB), Padova (Lorenzo Finesso), CWI (Jan van Schuppen), and ENST (Ecole Nationale Supérieure des Télécommunications, Olivier Cappé). The French-Hungarian collaboration was supported by the Balaton project.

The Stochastic Systems Research Group of SZTAKI launched a PhD project for the statistical analysis of HMMs in 2002 that successfully ended with the defense of Gábor Molnár-Sáska in 2006. The purpose of this research was to extend the scope of a powerful technique used in the analysis of linear stochastic systems. In particular, we have adapted a technique based on the concept of mixing that has been used successfully for a wide range of statistical problems in linear stochastic systems. A major advance stemming from the project was the extension of the constructions used in linear theory to a class of HMMs. A key step in this extension is the use of a smart weak-realization of an HMM via a non-linear state-space system. A weak realization produces an HMM with statistical characteristics identical to those of the original HMM.

The successful adaptation of mixing techniques has led to a number of powerful results, such as the accurate analysis of performance degradation of adaptive predictors for HMMs, and a lower bound for the performance of adaptive predictors. These results play a key role in the theory of stochastic complexity and change point detection. The efficiency of a Hinkley detector to a binary HMM is shown in the Figure, where the sudden increase of the detector indicates a change around 100, the actual change-point. Another application of the novel techniques is the analysis of Gaussian dynamic mixtures with state-dependent covariances. The Hungarian collaborators in this project were György Michaletzky (Eötvös Loránd University, Budapest) and Gábor Tusnády (Alfréd Rényi Institute of Mathematics, Budapest).

HMMs are widely used in modeling stochastic volatility processes in connection with financial time-series, a well-known special model being the celebrated GARCH model. A PhD project related to the statistical analysis of GARCH models was started by the group in 2003, and continues to progress. The major achievement of this project is the successful adaptation of the theory of Benveniste, Metivier and Priouret to this problem.

Real-time change point detection of a binary HMM using a Hinkley detector.

Another application of the technology, developed in connection with HMMs, is vision-based tracking. This was the subject of another PhD program launched by the Machine Learning Research Group of SZTAKI, lead by Csaba Szepesvári, with whom we closely collaborate. In this application the posterior density over the state space is typically multi-modal. The preferred method is to use particle filters, which can yield very accurate approximations of the posterior. A surprising and counter-intuitive property of particle filters is that their performance quickly degrades as the level of observation noise decreases to zero. They proposed an algorithm called local importance sampling, which overcomes the above-mentioned efficiency problem, and outperforms its competitors in a standard tracking problem. Further applications in data mining are described in ERCIM News No. 63, October 2005 (http://www.ercim.eu/publication/Ercim_News/enw63/szepesvari.html).

The current research interests of the group include the analysis of Markovian switching systems, where the read-outs are not static and the unseen states instead control a dynamic system. In addition, a project looking at applications in molecular biology is running in collaboration with the University of Dallas, Southwestern Medical School.
Furthermore, a French-Hungarian collaborative effort began in 2006, with Elisabeth Gassiat, Université Paris-Sud being the French principal investigator. This is supported by the Balaton project.

Please contact:
László Gerencsér, SZTAKI, Hungary
Tel: +36 1 279 6138
E-mail: gerencsersztaki.hu