Hidden Markov Models (Vaseghi - Advanced Digital Signal Processing and Noise Reduction)

Advanced Digital Signal Processing and Noise Reduction, Second Edition.Saeed V. VaseghiCopyright © 2000 John Wiley & Sons LtdISBNs: 0-471-62692-9 (Hardback): 0-470-84162-1 (Electronic)5HELLOHIDDEN MARKOV MODELS5.15.25.35.45.55.65.75.8Statistical Models for Non-Stationary ProcessesHidden Markov ModelsTraining Hidden Markov ModelsDecoding of Signals Using Hidden Markov ModelsHMM-Based Estimation of Signals in NoiseSignal and Noise Model Combination and DecompositionHMM-Based Wiener FiltersSummaryHidden Markov models (HMMs) are used for the statistical modellingof non-stationary signal processes such as speech signals, imagesequences and time-varying noise.

An HMM models the timevariations (and/or the space variations) of the statistics of a random processwith a Markovian chain of state-dependent stationary subprocesses. AnHMM is essentially a Bayesian finite state process, with a Markovian priorfor modelling the transitions between the states, and a set of state probabilitydensity functions for modelling the random variations of the signal processwithin each state. This chapter begins with a brief introduction tocontinuous and finite state non-stationary models, before concentrating onthe theory and applications of hidden Markov models.

We study the variousHMM structures, the Baum–Welch method for the maximum-likelihoodtraining of the parameters of an HMM, and the use of HMMs and theViterbi decoding algorithm for the classification and decoding of anunlabelled observation signal sequence. Finally, applications of the HMMsfor the enhancement of noisy signals are considered.144Hidden Markov ModelsExcitationObservable processmodelSignalProcessparametersHidden state-controlmodelFigure 5.1 Illustration of a two-layered model of a non-stationary process.5.1 Statistical Models for Non-Stationary ProcessesA non-stationary process can be defined as one whose statistical parametersvary over time. Most “naturally generated” signals, such as audio signals,image signals, biomedical signals and seismic signals, are non-stationary, inthat the parameters of the systems that generate the signals, and theenvironments in which the signals propagate, change with time.A non-stationary process can be modelled as a double-layeredstochastic process, with a hidden process that controls the time variations ofthe statistics of an observable process, as illustrated in Figure 5.1.

Ingeneral, non-stationary processes can be classified into one of two broadcategories:(a) Continuously variable state processes.(b) Finite state processes.A continuously variable state process is defined as one whose underlyingstatistics vary continuously with time. Examples of this class of randomprocesses are audio signals such as speech and music, whose power andspectral composition vary continuously with time. A finite state process isone whose statistical characteristics can switch between a finite number ofstationary or non-stationary states. For example, impulsive noise is a binarystate process.

Continuously variable processes can be approximated by anappropriate finite state process.Figure 5.2(a) illustrates a non-stationary first-order autoregressive (AR)process. This process is modelled as the combination of a hidden stationaryAR model of the signal parameters, and an observable time-varying ARmodel of the signal. The hidden model controls the time variations of the145Statistical Models for Non-Stationary ProcessesSignal excitatione(m)x(m)Parameterexcitationε (m)a(m)βzz–1–1(a)e0 (m)H0 (z)x0 (m)Stochasticswitch s(m)x(m)e 1(m)H1 (z)x1 (m)(b)Figure 5.2 (a) A continuously variable state AR process.

(b) A binary-state ARprocess.parameters of the non-stationary AR model. For this model, the observationsignal equation and the parameter state equation can be expressed asx(m) = a(m)x(m − 1) + e(m)Observation equation(5.1)a(m) = β a(m − 1)+ε (m)Hidden state equation(5.2)where a(m) is the time-varying coefficient of the observable AR process andβ is the coefficient of the hidden state-control process.A simple example of a finite state non-stationary model is the binarystate autoregressive process illustrated in Figure 5.2(b), where at each timeinstant a random switch selects one of the two AR models for connection tothe output terminal. For this model, the output signal x(m) can be expressedasx ( m ) = s ( m ) x0 ( m ) + s ( m ) x1 ( m )(5.3)where the binary switch s(m) selects the state of the process at time m, ands (m) denotes the Boolean complement of s(m).146Hidden Markov ModelsPW =0.8 PB =0.2PW =0.6 PB =0.4State1State2Hidden state selector(a)0.60.80.2S2S1(b)0.4Figure 5.3 (a) Illustration of a two-layered random process.

(b) An HMM model ofthe process in (a).5.2 Hidden Markov ModelsA hidden Markov model (HMM) is a double-layered finite state process,with a hidden Markovian process that controls the selection of the states ofan observable process. As a simple illustration of a binary-state Markovianprocess, consider Figure 5.3, which shows two containers of differentmixtures of black and white balls. The probability of the black and the whiteballs in each container, denoted as PB and PW respectively, are as shownabove Figure 5.3. Assume that at successive time intervals a hiddenselection process selects one of the two containers to release a ball.

Theballs released are replaced so that the mixture density of the black and thewhite balls in each container remains unaffected. Each container can beconsidered as an underlying state of the output process. Now for an exampleassume that the hidden container-selection process is governed by thefollowing rule: at any time, if the output from the currently selected147Statistical Models for Non-Stationary Processescontainer is a white ball then the same container is selected to output thenext ball, otherwise the other container is selected. This is an example of aMarkovian process because the next state of the process depends on thecurrent state as shown in the binary state model of Figure 5.3(b).

Note thatin this example the observable outcome does not unambiguously indicatethe underlying hidden state, because both states are capable of releasingblack and white balls.In general, a hidden Markov model has N sates, with each state trainedto model a distinct segment of a signal process. A hidden Markov model canbe used to model a time-varying random process as a probabilisticMarkovian chain of N stationary, or quasi-stationary, elementary subprocesses. A general form of a three-state HMM is shown in Figure 5.4.This structure is known as an ergodic HMM. In the context of an HMM, theterm “ergodic” implies that there are no structural constraints for connectingany state to any other state.A more constrained form of an HMM is the left–right model of Figure5.5, so-called because the allowed state transitions are those from a left stateto a right state and the self-loop transitions.

The left–right constraint isuseful for the characterisation of temporal or sequential structures ofstochastic signals such as speech and musical signals, because time may bevisualised as having a direction from left to right.a11S1a 21a13a12a23a 31S2a 22S3a32a33Figure 5.4 A three-state ergodic HMM structure.148Hidden Markov Modelsa 22a 11S1S2a 13Spoken lettera 33a 44a 55S3S4S5a 24a 35"C"Figure 5.5 A 5-state left–right HMM speech model.5.2.1 A Physical Interpretation of Hidden Markov ModelsFor a physical interpretation of the use of HMMs in modelling a signalprocess, consider the illustration of Figure 5.5 which shows a left–rightHMM of a spoken letter “C”, phonetically transcribed as ‘s-iy’, togetherwith a plot of the speech signal waveform for “C”.

In general, there are twomain types of variation in speech and other stochastic signals: variations inthe spectral composition, and variations in the time-scale or the articulationrate. In a hidden Markov model, these variations are modelled by the stateobservation and the state transition probabilities. A useful way ofinterpreting and using HMMs is to consider each state of an HMM as amodel of a segment of a stochastic process.

For example, in Figure 5.5, stateS1 models the first segment of the spoken letter “C”, state S2 models thesecond segment, and so on. Each state must have a mechanism toaccommodate the random variations in different realisations of the segmentsthat it models. The state transition probabilities provide a mechanism for149Hidden Markov Modelsconnection of various states, and for the modelling the variations in theduration and time-scales of the signals in each state. For example if asegment of a speech utterance is elongated, owing, say, to slow articulation,then this can be accommodated by more self-loop transitions into the statethat models the segment.

Conversely, if a segment of a word is omitted,owing, say, to fast speaking, then the skip-next-state connectionaccommodates that situation. The state observation pdfs model theprobability distributions of the spectral composition of the signal segmentsassociated with each state.5.2.2 Hidden Markov Model as a Bayesian ModelA hidden Markov model M is a Bayesian structure with a Markovian statetransition probability and a state observation likelihood that can be either adiscrete pmf or a continuous pdf. The posterior pmf of a state sequence s ofa model M, given an observation sequence X, can be expressed using Bayes’rule as the product of a state prior pmf and an observation likelihoodfunction:PS | X,M (s X, M ) =1f X (X )PS |M (s M ) f X |S,M ( X s, M )(5.4)where the observation sequence X is modelled by a probability densityfunction PS|X,M(s|X,M).The posterior probability that an observation signal sequence X wasgenerated by the model M is summed over all likely state sequences, andmay also be weighted by the model prior PM (M ) :PM | X (M X ) =1PM (M )f X ( X ) PS |M (s M )∑Model prior sf | S,M ( X s, M )X(5.5)State prior Observation likelihoodThe Markovian state transition prior can be used to model the timevariations and the sequential dependence of most non-stationary processes.However, for many applications, such as speech recognition, the stateobservation likelihood has far more influence on the posterior probabilitythan the state transition prior.150Hidden Markov Models5.2.3 Parameters of a Hidden Markov ModelA hidden Markov model has the following parameters:Number of states N.

This is usually set to the total number of distinct, orelementary, stochastic events in a signal process. For example, inmodelling a binary-state process such as impulsive noise, N is set to 2,and in isolated-word speech modelling N is set between 5 to 10.State transition-probability matrix A={aij, i,j=1, ...

N}. This provides aMarkovian connection network between the states, and models thevariations in the duration of the signals associated with each state. Fora left–right HMM (see Figure 5.5), aij=0 for i>j, and hence thetransition matrix A is upper-triangular.State observation vectors {µi1, µi2, ..., µiM, i=1, ..., N}. For each state a setof M prototype vectors model the centroids of the signal spaceassociated with each state.State observation vector probability model. This can be either a discretemodel composed of the M prototype vectors and their associatedprobability mass function (pmf) P={Pij(·); i=1, ..., N, j=1, ... M}, or itmay be a continuous (usually Gaussian) pdf model F={fij(·); i=1, ...,N, j=1, ..., M}.Initial state probability vector π=[π1, π2, ..., πN].5.2.4 State Observation ModelsDepending on whether a signal process is discrete-valued or continuousvalued, the state observation model for the process can be either a discretevalued probability mass function (pmf), or a continuous-valued probabilitydensity function (pdf).