Sequential Data and Markov Models Sargur N. Srihari [email protected] Machine Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.html Sequential Data ExamplesMarkov Model – WeatherMarkov Model – Weather State DiagramSound Spectrogram of SpeechMarkov model for the production of spoken words Stationary vs Non-stationaryMaking a Sequence of DecisionsLatent VariablesHidden Markov ModelMarkov Model Assuming IndependenceMarkov ModelFirst Order Markov ModelMarkov Model – Sequence probabilitySecond Order Markov ModelMth Order Markov SourceIntroducing Latent VariablesConditional Independence with Latent VariablesJt Distribution with Latent VariablesTwo Models Described by GraphFurther Topics on Sequential Data0Sequential Data and Markov Models Sargur N. Srihari [email protected] Machine Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.html1• Often arise through measurement of time series–Snowfall measurements on successive days –Rainfall measurements on successive days–Daily values of currency exchange rate–Acoustic features at successive time frames in speech recognition–Nucleotide base pairs in a strand of DNA –Sequence of characters in an English sentence–Parts of speech of successive words10Sequential Data Examples2Markov Model – Weather• The weather of a day is observed as being one of the following:–State 1: Rainy–State 2: Cloudy–State 3: Sunny• Weather pattern of a locationTomorrowRain Cloudy SunnyTodayRain 0.3 0.3 0.4Cloudy 0.2 0.6 0.2Sunny 0.1 0.1 0.83Markov Model – Weather State Diagram0.80.10.10.30.30.40.60.20.24Sound Spectrogram of Speech• “Bayes Theorem”• Plot of the intensity of the spectral coefficients versus time index• Successive observations of speech spectrum highly correlated (Markov dependency)5• States represent phonemes• Production of word: “cat”• Represented by states/k/ /a/ /t/ • Transitions from • /k/ to /a/• /a/ to /t/• /t/ to a silent state• Although only correct cat sound is represented by model, perhaps other transitions can be introduced, • eg, /k/ followed by /t/10Markov model for the production of spoken words/t//a//k/Markov ModelMarkov Modelfor word for word ““catcat””6Stationary vs Non-stationary• Stationary: Data evolves over time but distribution remains same–e.g., dependence of current word over previous word remains constant• Non-stationary: Generative distribution itself changes over time7• Processes in time, states at time t are influenced by a state at time t-1• Wish to predict next value from previous values, e.g., financial forecasting• Impractical to consider general dependence of future dependence on all previous observations–Complexity grows without limit as number of observations increases• Markov models assume dependence on most recent observations10Making a Sequence of Decisions8Latent Variables• While Markov models are tractable they are severely limited• Introduction of latent variables provides a more general framework• Lead to state-space models• When latent variables are:–Discrete • they are called Hidden Markov models–Continuous • they are linear dynamical systems9Hidden Markov Model0.80.40.60.10.10.30.30.20.2Hidden0.60.30.10.50.30.20.80.20.0Observations are Observations are activities of friend activities of friend described over telephonedescribed over telephoneAlternatively from data:Alternatively from data:Day M TuW ThTempBarometer10Markov Model Assuming Independence• Simplest model: –Assume observations are independent –Graph without links• To predict whether it rains tomorrow is only based on relative frequency of rainy days • Ignores influence of whether it rained the previous day11Markov Model),..|(),..(1111 −=∏=nnNnNxxxpxxp• Most general Markov model for observations {xn }• Product rule to express joint distribution of sequence of observations12First Order Markov Model• Chain of observations {xn }• Joint distribution for a sequence of n variables• It can be verified (using product rule from above) that• If model is used to predict next observation, distribution of prediction will only depend on preceding observation and independent of earlier observations• Stationarity implies conditional distributions p(xn |xn-1 ) are all equal)|()..|(111 −−=nnnnxxpxxxp)|()(),..(1211 −=∏=nnNnNxxpxpxxp13Markov Model – Sequence probability• What is the probability that the weather for the next 7 days will be “S-S-R-R-S-C-S”?–Find the probability of O, given the model.O SSSSSSSS={,,,,,,,}3331132342332131131333332332131131333333231133310536.1)2.0()1.0()3.0()4.0()1.0()8.0()8.0(1)|()|()|()|()|()|()|()()|,,,,,,,()|(−×=⋅⋅⋅⋅⋅⋅⋅=⋅⋅⋅⋅⋅⋅⋅=⋅⋅⋅⋅⋅⋅⋅==aaaaaaaSSPSSPSSPSSPSSPSSPSSPSPModelSSSSSSSSPModelOPπ14Second Order Markov Model• Conditional distribution of observation xn depends on the values of two previous observations xn-1 and xn-2),|()|()(),..(2131211 −−=∏=nnnNnNxxxpxxpxpxxp• Each observation is influenced by previous two observations15Mth Order Markov Source• Conditional distribution for a particular variable depends on previous M variables• Pay a price for number of parameters• Discrete variable with K states–First order: p(xn |xn-1 ) needs K-1 parameters for each value of xn-1 for each of K states of xn giving K(K-1) parameters –Mth order will need KM-1(K-1) parameters16Introducing Latent Variables• Model for sequences not limited by Markov assumption of any order but with limited number of parameters• For each observation xn , introduce a latent variable zn• zn may be of different type or dimensionality to the observed variable• Latent variables form the Markov chain• Gives the “state-space model”ObservationsObservationsLatent variablesLatent variables17Conditional Independence with Latent Variables• Satisfies key assumption that• From d-separationWhen latent node zn is filled, the only path between zn-1 and zn+1 has a head-to-tail node that is blockednnnzzz |11 −+⊥18Jt Distribution with Latent VariablesObservationsObservationsLatent variablesLatent variables)|()|()(),..,,..(121111 nnNnNnnnnNzxpzzpzpzzxxp∏∏==−⎥⎦⎤⎢⎣⎡=• Joint distribution for this model • There is always a path between any xn and xm via latent variables which is never blocked• Thus predictive distribution p(xn+1 |x1 ,..,xn ) for observation xn+1 does not