Machine learning lecture 19 Tommi S Jaakkola MIT CSAIL tommi csail mit edu Topics Hidden markov models Viterbi algorithm examples alignment Graphical models representation examples Tommi Jaakkola MIT CSAIL 2 HMM problems There are several problems we have to solve 1 How do we evaluate the probability of an observation sequence x1 xn forward backward algorithm 2 How do we adapt the parameters of the HMM to better account for the observations the EM algorithm 3 How do we uncover the most likely hidden state sequence corresponding to the observations dynamic programming Viterbi algorithm Tommi Jaakkola MIT CSAIL 3 Max probabilities 1 2 s1 s2 s3 x1 x2 x3 We can recover the most likely hidden state sequence corresponding to a sequence of observations by evaluating the following max probabilities t i max P x1 xt s1 st 1 st i s1 st 1 Tommi Jaakkola MIT CSAIL 4 Viterbi algorithm 1 2 s1 s2 s3 x1 x2 x3 1 1 P x1 s1 1 1 2 P x1 s1 2 Tommi Jaakkola MIT CSAIL 5 Viterbi algorithm 1 2 s1 s2 s3 x1 x2 x3 1 1 P x1 s1 1 1 2 P x1 s1 2 1 1 P 1 Px x1 1 Tommi Jaakkola MIT CSAIL 6 Viterbi algorithm 1 2 s1 s2 s3 x1 x2 x3 1 1 P x1 s1 1 1 2 P x1 s1 2 1 1 P 1 Px x1 1 1 2 P 2 Px x1 2 Tommi Jaakkola MIT CSAIL 7 Viterbi algorithm 1 2 s1 s2 s3 x1 x2 x3 2 1 maxs1 P x1 x2 s1 s2 1 2 2 maxs1 P x1 x2 s1 s2 2 2 1 max 1 1 P1 1 1 1 2 P1 1 2 Px x2 1 Tommi Jaakkola MIT CSAIL 8 Viterbi algorithm 1 2 s1 s2 s3 x1 x2 x3 2 1 maxs1 P x1 x2 s1 s2 1 2 2 maxs1 P x1 x2 s1 s2 2 2 1 max 1 1 P1 1 1 1 2 P1 1 2 Px x2 1 2 2 max 1 1 P1 2 1 1 2 P1 2 2 Px x2 2 Tommi Jaakkola MIT CSAIL 9 Viterbi algorithm 1 2 t i s1 s2 s3 x1 x2 x3 max P x1 xt s1 st 1 st i s1 st 1 We get the following recursive equation for calculating the max probabilities 1 i P i Px x1 i t i max t 1 j P1 i j Px xt i j Tommi Jaakkola MIT CSAIL 10 Viterbi algorithm back tracking 1 2 s1 s2 s3 x1 x2 x3 We can recover the most likely state sequence by working backwards s n argmax n i i st argmax t j P1 s t 1 j j Tommi Jaakkola MIT CSAIL 11 Viterbi algorithm properties 1 2 s1 s2 s3 x1 x2 x3 The most likely path has the property that any partial path is also optimal If s t i then s 1 s t is also the most likely state sequence forced to end up in st i at time t given only x1 xt Tommi Jaakkola MIT CSAIL 12 Viterbi algorithm example Same example as in the EM case 3 states Gaussian outputs 4 4 3 3 2 2 1 1 0 0 1 1 2 0 20 40 60 80 100 after 0 iterations 120 2 0 20 40 60 80 100 120 after 7 iterations The most likely hidden state sequence s 0 s n need not agree with the most likely states derived from the posterior marginals t i Tommi Jaakkola MIT CSAIL 13 Example cont d 4 4 3 3 2 2 1 1 0 0 1 1 2 0 20 40 60 final Tommi Jaakkola MIT CSAIL 80 100 120 2 0 20 40 60 80 100 120 ML model no observations 14 Linear HMMs alignment Proteins GVAALGAKVLAQIGVAVSHLGDEGKMVAQMKAVGVRHKGYGNKHIKAQYFEPLGASLLSAMEHRIG A Linear HMM model for protein sequences d Begin 1 d 2 d 3 d 50 i 1 i 2 i 3 i 50 m m m m 1 2 3 50 End GVAALGAKVLAQIGVAVSHLGDegkMVAQMKAVGVRHKgygNK HIKAQYFEPLGASLLSAMEHRIG Tommi Jaakkola MIT CSAIL 15 Linear HMMs multiple alignment d Begin 1 d 2 d 3 d 50 i 1 i 2 i 3 i 50 m m m m 1 2 3 50 End VKGHGKKVADALTNAVAHVDD MPNALSALSDLHA HKLRVDPV NFKLLSHCLLVTLAAHLP KVKAHGKKVLGAFSDGLAHLDN LKGTFATLSELHC DKLHVDPE NFRLLGNVLVCVLAHHFG DLKKHGVTVLTALGAILKKKGH HEAELKPLAQSHA TK HKIPIkYLEFISEAIIHVLHSRHP PFETHANRIVGFFSKIIGELPN IEADVNTFVASHK PR GVTHD QLNNFRAGFVSYMKAH DVRWHAERIINAVNDAVASMDDtek MSMKLRDLSGKHA KSFQVDPQ YFKVLAAVIADTVAA ELQAHAGKVFKLVYEAAIQLQVtgvvvTDATLKNLGSVHV SK GVADA HFPVVKEAILKTIKEVVG GVAALGAKVLAQIGVAVSHLGDegk MVAQMKAVGVRHKgygNK HIKAQ YFEPLGASLLSAMEHRIG Tommi Jaakkola MIT CSAIL 16 Topics Hidden markov models Viterbi algorithm examples alignment Graphical models representation examples Tommi Jaakkola MIT CSAIL 17 What is a good representation Properties of good representations 1 Explicit 2 Modular 3 Permits efficient computation 4 etc Tommi Jaakkola MIT CSAIL 18 Representation explicit Representation in terms of variables and dependencies a graphical model s1 s2 s3 s4 Representation in terms of state transitions transition diagram P s2 s1 P s3 s2 Tommi Jaakkola MIT CSAIL P s1 s1 s2 s3 19 Representation modular We can easily add remove components of the model Markov model s1 s2 s3 s4 s1 s2 s3 s4 x1 x2 x3 x4 Hidden Markov model Tommi Jaakkola MIT CSAIL 20 Representation efficient computation 1 2 s1 s2 s3 x1 x2 x3 Forward backward probabilities EM algorithm Max probabilities viterbi Tommi Jaakkola MIT CSAIL 21 Graphical models examples Factorial Hidden Markov models linguistic features acoustic observations a k a directed graphs Bayesian networks Tommi Jaakkola MIT CSAIL 22 Graphical models examples Factor graphs and codes information theory y1 y2 y3 y4 y5 x1 Bits x2 x3 x5 x4 parity checks Tommi Jaakkola MIT CSAIL 23 Graphical models examples Lattice models Ising model physics s1 s2 a k a Markov random field Tommi Jaakkola MIT CSAIL 24 Graphical models examples Plates and relations information retrieval biology etc topics class words M Tommi Jaakkola MIT CSAIL N This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled 25 Graphical models y1 x1 Bits y2 y3 y4 x3 x2 y5 x5 x4 linguistic features parity checks s1 s2 acoustic observations topics class words M N Graph semantics graph separation properties independence Association with probability distributions independence family of distributions Inference and estimation graph structure efficient computation Tommi Jaakkola MIT CSAIL 26