Expectation Maximization Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 9th 2007 2005 2007 Carlos Guestrin Gaussian Bayes Classifier Reminder P y i x j p x j y i P y i p x j T 1 1 1 P y i x j exp x j i i x j i P y i m 2 1 2 2 2 i 2005 2007 Carlos Guestrin Next back to Density Estimation What if we want to do density estimation with multimodal or clumpy data 2005 2007 Carlos Guestrin Marginal likelihood for general case P y i x j T 1 1 1 exp x x j i i j i P y i m 2 1 2 2 2 i Marginal likelihood m m k P x j 1 j P x j y i j 1 i 1 T 1 1 1 exp x j i i x j i P y i m 2 1 2 2 2 i j 1 i 1 m k 2005 2007 Carlos Guestrin Duda Hart s Example 2 Graph of log P x1 x2 x25 1 2 against 1 and 2 1 Max likelihood 1 2 13 2 1 668 Local minimum but very close to global at 1 2 085 2 1 257 corresponds to switching y1 with y2 2005 2007 Carlos Guestrin Finding the max likelihood 1 2 k We can compute P data 1 2 k How do we find the i s which give max likelihood The normal max likelihood trick Set log Prob 0 i and solve for i s Here you get non linear non analytically solvable equations Use gradient descent Slow but doable Use a much faster cuter and recently very popular method 2005 2007 Carlos Guestrin Expectation Maximalization 2005 2007 Carlos Guestrin The E M Algorithm R U TO E D We ll get back to unsupervised learning soon But now we ll look at an even simpler case with hidden information The EM algorithm Can do trivial things such as the contents of the next few slides An excellent way of doing our unsupervised learning problem as we ll see Many many other uses including learning BNs with hidden data 2005 2007 Carlos Guestrin Silly Example Let events be grades in a class w1 Gets an A P A w2 Gets a B P B w3 Gets a C P C 2 w4 Gets a D P D 3 Note 0 1 6 Assume we want to estimate from data In a given class there were a A s b B s c C s d D s What s the maximum likelihood estimate of given a b c d 2005 2007 Carlos Guestrin Trivial Statistics P A P B P C 2 P D 3 P a b c d K a b 2 c 3 d log P a b c d log K alog blog clog 2 dlog 3 FOR MAX LIKE SET LogP 0 LogP b 2c 3d 0 2 1 2 3 b c Gives max like 6 b c d So if class got Max like A B C D 14 6 9 10 1 10 2005 2007 Carlos Guestrin in Bor e u r t ut b g Same Problem with Hidden Information REMEMBER Someone tells us that Number of High grades A s B s h Number of C s c Number of D s d What is the max like estimate of now 2005 2007 Carlos Guestrin P A P B P C 2 P D 3 Same Problem with Hidden Information Someone tells us that Number of High grades A s B s h Number of C s c Number of D s d REMEMBER P A P B P C 2 P D 3 What is the max like estimate of now We can answer this question circularly EXPECTATION If we know the value of we could compute the expected value of a and b 1 2 h a b h Since the ratio a b should be the same as the ratio 1 1 2 2 MAXIMIZATION If we know the expected values of a and b we could compute the maximum likelihood value of 2005 2007 Carlos Guestrin b c 6 b c d E M for our Trivial Problem REMEMBER P A P B We begin with a guess for We iterate between EXPECTATION and MAXIMALIZATION to improve our estimates of and a and b Define t the estimate of on the t th iteration b t the estimate of b on t th iteration 0 initial guess b t t 1 t h t b 1 t 2 b t c 6 b t c d E step M step max like est of given b t Continue iterating until converged Good news Converging to local optimum is assured Bad news I said local optimum 2005 2007 Carlos Guestrin P C 2 P D 3 E M Convergence Convergence proof based on fact that Prob data must increase or remain same between each iteration NOT OBVIOUS But it can never exceed 1 OBVIOUS So it must therefore converge OBVIOUS In our example suppose we had h 20 c 10 d 10 0 0 t t Convergence is generally linear error decreases by a constant factor each time step 2005 2007 Carlos Guestrin b t 0 0 0 1 0 0833 2 857 2 0 0937 3 158 3 0 0947 3 185 4 0 0948 3 187 5 0 0948 3 187 6 0 0948 3 187 Back to Unsupervised Learning of GMMs a simple case A simple case We have unlabeled data x1 x2 xm We know there are k classes We know P y1 P y2 P y3 P yk We don t know 1 2 k We can write P data 1 k p x1 x m 1 k m p x j 1 k j 1 m k p x j i P y i j 1 i 1 m k j 1 i 1 1 2 exp 2 x j i P y i 2 2005 2007 Carlos Guestrin EM for simple case of GMMs The E step If we know 1 k easily compute prob point xj belongs to class y i 1 2 p y i x j 1 k exp 2 x j i P y i 2 2005 2007 Carlos Guestrin EM for simple case of GMMs The M step If we know prob point xj belongs to class y i MLE for i is weighted average imagine k copies of each xj each with weight P y i xj m P y i x x j i j j 1 m P y i x j j 1 2005 2007 Carlos Guestrin E M for GMMs E step Compute expected classes of all datapoints for each class 1 2 p y i x j 1 k exp 2 x j i P y i 2 Just evaluate a Gaussian at xj M step Compute Max like given our data s class membership distributions m P y i x x j i j j 1 m …
View Full Document
Unlocking...