An overview of Hidden Markov Models

Hidden Markov Models (HMM’s) are mathematical models of uncertain phenomena, well suited to describe complex dynamical behaviours. HMMs find applications in a variety of fields in the areas of digital signal processing, control, and pattern recognition. Popular as they have become, HMM’s still offer a wealth of challenging theoretical problems. HMM’s are an ongoing research topic in engineering, statistics, and probability. The simplest probabilistic models of uncertain phenomena are independent processes. The basic feature of these models is their lack of memory: the present value of the process is not influenced by its past or future values. Independent processes are adequate to represent the randomness of games of chance or other simple physical phenomena, but are of limited use in describing true dynamic behaviors. One step above independent processes, in the hierarchy of probabilistic models, one finds Markov chain (MC) models. The present value of a MC depends on a finite (bounded) number of its most recent past values. If their memory size is correctly adjusted, MC’s can be used to describe approximately phenomena with complex dynamical behaviour. Hidden Markov Models are at the top of this hierarchy. Roughly speaking, HMM’s are processes that can be represented as functions of MC’s with a finite number of states: if X(n) is a (finitely valued) MC and h(.) a given function, then Y(n) = h(X(n)) is an HMM. In a HMM Y(n), in general the transformation h(.) destroys the Markov property of the process X(n), and as a result the HMM process Y(n)=h(X(n)) can exhibit infinite memory. That explains why HMMs are so popular: they are very simple to describe, as functions of MCs, and at the same time they can capture complex dynamical behaviors thanks to their infinite memory. The most basic probabilistic question is the characterization of HMM’s. Is it possible to decide whether a process Y(t) is an HMM, knowing all of its finite dimensional distribution functions? The positive answer to this question was provided, independently, by Heller and by Furstenberg in the early sixties and later rederived, within the framework of System Theory, by Picci in 1976. Another probabilistic problem is the realization of HMM’s, i.e. given the probabilistic description of the HMM Y(n), construct the parameters X(t) and h(.), such that Y(n)=h(X(n)). This problem has very recently been generalized to the construction of an approximate realization where, given Y(n) one constructs h(.) and X(n) such that the information theoretical criterion D(Y(n)|| h(X(n)) (relative entropy) is minimized. Statistical inference problems for HMM’s have also been intensively studied since the early sixties, when Baum and his coworkers presented two related algorithms (the Forward-Backward and a form of what is today known as the EM algorithm) that helped solve the Maximum Likelihood parameter estimation problem in the case of finitely valued HMM’s.