Hidden Markov Models Sargur N. Srihari [email protected] Machine Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.html HMM Topics1. What is an HMM?Graphical Model of HMMHMM Viewed as Mixture2. State-Space Representation Transition ProbabilitiesConditional ProbabilitiesInitial Variable Probabilities Emission Probabilities p(xn|zn)3. HMM ParametersJoint Distribution over Latent and Observed variables4. Generative View of HMMLeft-to-Right HMMLeft-to-Right Applied Generatively to Digits5. Determining HMM ParametersComputational issues for Parameters EM for MLE in HMMExpansion of QDetail of g and xExpansion of Q E-StepM-StepM-step for Gaussian emissionM-Step for Multinomial Observed6. Forward-Backward AlgorithmDerivation of Forward-BackwardConditional independence BConditional independence CConditional independence DConditional independence EConditional independence FConditional independence GConditional independence HEvaluation of g(zn)Introducing a and bRecursion Relation for a Forward Recursion for EvaluationRecursion Relation for bBackward Recursion for M step EquationsEvaluation of Quantities x(zn-1,zn)Summary of EM to train HMMSummary of EM to train HMMValues for p(xn|zn)7(a) Sequence Length: Using Multiple Short Sequences7(b). Predictive Distribution7(c). Sum-Product and HMM Deriving alpha-beta from Sum-Product7(d). Scaling Factors7(e). The Viterbi AlgorithmViterbi Algorithm for HMMDeriving Viterbi from Max-SumOther Topics on Sequential DataMachine Learning: CSE 574 Machine Learning: CSE 574 00Hidden Markov Models Sargur N. Srihari [email protected] Machine Learning Course: http://www.cedar.buffalo.edu/~srihari/CSE574/index.htmlMachine Learning: CSE 574 Machine Learning: CSE 574 11HMM Topics1. What is an HMM?2. State-space Representation3. HMM Parameters4. Generative View of HMM5. Determining HMM Parameters Using EM6. Forward-Backward or α−β algorithm7. HMM Implementation Issues:a) Length of Sequenceb) Predictive Distributionc) Sum-Product Algorithmd) Scaling Factorse) Viterbi AlgorithmMachine Learning: CSE 574 Machine Learning: CSE 574 221. What is an HMM?• Ubiquitous tool for modeling time series data• Used in• Almost all speech recognition systems• Computational molecular biology• Group amino acid sequences into proteins• Handwritten word recognition• It is a tool for representing probability distributions over sequences of observations• HMM gets its name from two defining properties:• Observation xt at time t was generated by some process whose state zt is hidden from the observer• Assumes that state at zt is dependent only on state zt-1 and independent of all prior states (First order)• Example: z are phoneme sequencesx are acoustic observationsMachine Learning: CSE 574 Machine Learning: CSE 574 33Graphical Model of HMM• Has the graphical model shown below and latent variables are discrete• Joint distribution has the form:)|()|()(),..,,..(121111 nnNnNnnnnNzxpzzpzpzzxxp∏∏==−⎥⎦⎤⎢⎣⎡=Machine Learning: CSE 574 Machine Learning: CSE 574 44HMM Viewed as Mixture• A single time slice corresponds to a mixture distribution with component densities p(x|z)• Each state of discrete variable z represents a different component • An extension of mixture model• Choice of mixture component depends on choice of mixture component for previous distribution• Latent variables are multinomial variables zn• That describe component responsible for generating xn• Can use one-of-K coding schemeMachine Learning: CSE 574 Machine Learning: CSE 574 552. State-Space Representation • Probability distribution of zn depends on state of previous latent variable zn-1 through probability distribution p(zn |zn-1 )• One-of K coding• Since latent variables are K- dimensional binary vectorsAjk =p(znk =1|zn-1,j =1)Σk Ajk =1• These are known as Transition Probabilities• K(K-1) independent parametersk 1 2 . Kznk0 1 . 01 2 …. K12… AjkKA A matrixmatrixj 1 2 . Kzn-1,j1 0 . 0State State of of zznnState State of of zznn--11zn-1zznnMachine Learning: CSE 574 Machine Learning: CSE 574 66Transition Probabilitieszn =1zn1 =1zn2 =0zn3 =0zn =2zn1 =0zn2 =1zn3 =0zn =3zn1 =0zn2 =0zn3 =1zn-1 =1zn-1,1 =1zn-1,2 =0zn-1,3 =0A11A12A13zn-1 =2zn-1,1 =0zn-1,2 =1zn-1,3 =0A21A22A23zn-3 = 3zn-1,1 =0zn-1,2 =0zn-1,3 =1A31A32A33State Transition Diagram•• Not a graphical modelsince nodes are not separate variables but states of a single variable• Here K=3K=3AA1111 +A+A1212 +A+A1313 =1=1Example with 3-state latent variableMachine Learning: CSE 574 Machine Learning: CSE 574 77Conditional Probabilities• Transition probabilities Ajk represent state-to-state probabilities for each variable• Conditional probabilities are variable-to-variable probabilities• can be written in terms of transition probabilities as• Note that exponent zn-1,j zn,k is a product that evaluates to 0 or 1• Hence the overall product will evaluate to a single Ajk for each setting of values of zn and zn-1• E.g., zn-1 =2 and zn =3 will result in only zn-1,2 =1 and zn,3 =1. Thus p(zn =3|zn-1 =2)=A23• A is a global HMM parameter∏∏==−−=KkKjzzjknnknjnAAp111,,1),z|z(Machine Learning: CSE 574 Machine Learning: CSE 574 88Initial Variable Probabilities• Initial latent node z1 is a special case without parent node • Represented by vector of probabilities π with elements πk =p(z1k =1) so that• Note that πis an HMM parameter • representing probabilities of each state for the first variable1 where)|z(k11,1=Σ=∏=kKkzkkpπππMachine Learning: CSE 574 Machine Learning: CSE 574 99• State transition diagram unfolded over time• Representation of latent variable states• Each column corresponds to one of latent variables znLattice or Trellis DiagramMachine Learning: CSE 574 Machine Learning: CSE 574 1010Emission Probabilities p(xn |zn )• We have so far only specified p(zn |zn-1 ) by means of transition probabilities• Need to specify probabilities p(xn |zn ,φ) to complete the model, where φare parameters• These can be continuous or discrete• Because xn is observed and zn is discrete p(xn |zn ,φ) consists of a table of K numbers corresponding to K states of zn• Analogous to class-conditional probabilities• Can be represented as1(x | z , ) (x | )nkKznn nkkppϕϕ==∏Machine Learning: CSE 574 Machine Learning: CSE 574 11113. HMM Parameters• We have defined three types of HMM parameters: θ= (π, A,φ)1.