Recommended reading An Introduction to HMMs and Bayesian Networks Z Ghahramani Int Journal of Pattern Recognition and AI 15 1 9 42 2001 Especially Section 4 EM for HMMs a k a The Baum Welch Algorithm Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 12th 2006 1 Learning HMMs from fully observable data is easy X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Learn 3 distributions 2 Learning HMMs from fully observable data is easy X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Learn 3 distributions What if O is observed but X is hidden 3 Log likelihood for HMMs when X is hidden Marginal likelihood O is observed X is missing For simplicity of notation training data consists of only one sequence If there were m sequences 4 Computing Log likelihood for HMMs when X is hidden X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 5 Computing Log likelihood for HMMs when X is hidden variable elimination X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Can compute efficiently with variable elimination 6 EM for HMMs when X is hidden X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 E step Use inference forwards backwards algorithm M step Recompute parameters with weighted data 7 E step X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 E step computes probability of hidden vars x given o Will correspond to inference use forward backward algorithm 8 The M step X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Maximization step Use expected counts instead of counts If learning requires Count x o Use EQ t 1 Count x o 9 Decomposition of likelihood revisited X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Likelihood optimization decomposes 10 Starting state probability P X1 Using expected counts P X1 a X1 a 11 12 Transition probability P Xt Xt 1 Using expected counts P Xt a Xt 1 b Xt a Xt 1 b 13 Observation probability P Ot Xt Using expected counts P Ot a Xt b Ot a Xt b 14 E step revisited X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 E step computes probability of hidden vars x given o Must compute Q xt a o marginal probability of each position Q xt 1 a xt b o joint distribution between pairs of positions 15 The forwards backwards algorithm X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Initialization For i 2 to n Generate a forwards factor by eliminating Xi 1 Initialization For i n 1 to 1 Generate a backwards factor by eliminating Xi 1 i probability is 16 E step revisited X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 E step computes probability of hidden vars x given o Must compute Q xt a o marginal probability of each position Just forwards backwards Q xt 1 a xt b o joint distribution between pairs of positions Homework 17 What can you do with EM for HMMs 1 Clustering sequences X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Independent clustering Sequence clustering 18 What can you do with EM for HMMs 2 Exploiting unlabeled data X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 Labeling data is hard work save graduate student time by using both labeled and unlabeled data Labeled data X brace O Unlabeled data X O 19 Exploiting unlabeled data in clustering A few data points are labeled x o Most points are unlabeled o In the E step of EM If i th point is unlabeled compute Q X oi as usual If i th point is labeled set Q X x oi 1 and Q X x oi 0 M step as usual 20 21 20 Newsgroups data advantage of adding unlabeled data 22 20 Newsgroups data Effect of additional unlabeled data 23 Exploiting unlabeled data in HMMs X1 a z X2 a z X3 a z X4 a z X5 a z O1 O2 O3 O4 O5 A few data points are labeled x o Most points are unlabeled o In the E step of EM If i th point is unlabeled compute Q X oi as usual If i th point is labeled set Q X x oi 1 and Q X x oi 0 M step as usual Speed up by remembering counts for labeled data 24 What you need to know Baum Welch EM for HMMs E step Inference using forwards backwards M step Use weighted counts Exploiting unlabeled data Some unlabeled data can help classification Small change to EM algorithm In E step only use inference for unlabeled data 25 Acknowledgements Experiments combining labeled and unlabeled data provided by Tom Mitchell 26 EM for Bayes Nets Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 12th 2006 27 Data likelihood for BNs Flu Allergy Sinus Given structure log likelihood of fully observed data Nose Headache 28 Marginal likelihood Flu Allergy Sinus What if S is hidden Nose Headache 29 Log likelihood for BNs with hidden data Flu Marginal likelihood O is observed H is hidden Allergy Sinus Nose Headache 30 E step for BNs Flu Allergy Sinus Nose Headache E step computes probability of hidden vars h given o Corresponds to inference in BN 31 Flu The M step for BNs Allergy Sinus Nose Headache Maximization step Use expected counts instead of counts If learning requires Count h o Use EQ t 1 Count h o 32 Flu M step for each CPT Allergy Sinus Nose Headache M step decomposes per CPT Standard MLE M step uses expected counts 33 Flu Computing expected counts Allergy Sinus Nose Headache M step requires expected counts For a set of vars A must compute ExCount A a Some of A in example j will be observed denote by AO aO j Some of A will be hidden denote by AH Use inference E step computes expected counts ExCount t 1 AO aO j AH aH P AH aH AO aO j t 34 Data need not be hidden in the same way Flu Allergy Sinus Nose Headache When data is fully observed A data point is When data is partially observed A data point is But unobserved variables can be different for different data points e g Same framework just change definition of expected counts ExCount t 1 …
View Full Document
Unlocking...