Extensions of Hidden Markov Models Sargur N. Srihari [email protected] Machine Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.html HMM Extensions1. Sequence ClassificationDiscriminative HMM2. Autoregressive HMMAutoregressive with dependency 23. Input-output HMMSupervised Learning in HMM4. Factorial HMMExample of a path in factorial HMMOther Topics on Sequential DataMachine Learning: CSE 574 0Extensions of Hidden Markov Models Sargur N. Srihari [email protected] Machine Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.htmlMachine Learning: CSE 574 1HMM Extensions1. Sequence Classification Also called Discriminative HMM2. Autoregressive HMMHandling long-term dependencies3. Input-output HMMSupervised learning4. Factorial HMMMultiple chains of latent variablesMachine Learning: CSE 574 21. Sequence Classification• HMM as a generative model can give poor results not representative of the data• If goal is classification • better to estimate HMM parameters using discriminative rather than MLE approaches• We have training set of R observation sequences Xr , r = 1,..,R• Each sequence is labeled according to class m, m =1,..,M and mr is the label assigned to Xr• For each class we have a separate HMM with its own parameters θmMachine Learning: CSE 574 3Discriminative HMM• Optimize cross-entropy• Each term in summation is probability of class m being associated with sequence Xr• We wish to maximize joint probability of assigning correct class to each sequence• Using Bayes theorem this can be expressed in terms of sequence probabilities associated with HMMs• where p(m) is the prior probability of class m• Optimization of this cost function is more complex than for maximum likelihood• Requires that every sequence be evaluated under each model so as to compute the denominator• HMM discriminative methods are widely used in speech recognition1ln ( | X )Rrrrpm=∑11(|)()ln(|)()Rrr rMrrl llpX pmpX pmθθ==⎧⎫⎪⎪⎪⎪⎨⎬⎪⎪⎪⎪⎩⎭∑∑Machine Learning: CSE 574 42. Autoregressive HMM• HMM is poor in capturing long-term correlations between observed variables• Since they are mediated via first-order Markov chains• Distribution of xn depends on zn as well as on subset of previous observations• Extra links are added into HMMMachine Learning: CSE 574 5Autoregressive with dependency 2• Dependency on previous two observed variables as well as hidden state• Although graph is messy, it has a simple probabilistic structure• If we condition on zn(assume node is filled) then zn-1 and zn+1 are independent (because path is blocked)• Can use forward- backward recursion in E- step of EM algorithm • Minor modification of M stepMachine Learning: CSE 574 63. Input-output HMM• Sequence of observed variables u1 ,..,uN• Output variables are x1 ,..xN• Values of observed variables influence both latent and output variables• Extends HMM to domain of supervised learning for sequential dataMachine Learning: CSE 574 7Supervised Learning in HMM• Markov property still holds• Since there is only one path from zn-1 to zn+1 and this is head-to-tail with respect to the observed node zn• Allows formulation of computationally efficient learning algorithmnnnzzz |11 −+⊥Machine Learning: CSE 574 84. Factorial HMM• There are multiple independent chains of latent variables• Distribution of observed variable is conditioned on states of all corresponding latent variablesMachine Learning: CSE 574 9Example of a path in factorial HMM• It is head-to-head at observed nodes xn-1 and xn+1• It is head-to tail at unobserved nodes zn-1(2), zn(2) and zn+1(2)• Thus path is not blocked• Thus conditional independence property does not hold for individual latent chains of HMM• As a consequence there is no efficient exact E step for this model nnnzzz |11 −+⊥Machine Learning: CSE 574 10Other Topics on Sequential Data• Sequential Data and Markov Models:http://www.cedar.buffalo.edu/~srihari/CSE574/Chap11/Ch1 1.1-MarkovModels.pdf• Hidden Markov Models:http://www.cedar.buffalo.edu/~srihari/CSE574/Chap11/Ch1 1.2-HiddenMarkovModels.pdf• Linear Dynamical Systems:http://www.cedar.buffalo.edu/~srihari/CSE574/Chap11/Ch1 1.4-LinearDynamicalSystems.pdf• Conditional Random Fields:http://www.cedar.buffalo.edu/~srihari/CSE574/Chap11/Ch1