DOC PREVIEW
CMU CS 10701 - EM Algorithm

This preview shows page 1-2-3-24-25-26-27-49-50-51 out of 51 pages.

Save
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

EM Algorithm Aarti Singh Slides courtesy Eric Xing Carlos Guetrin Machine Learning 10 701 15 781 Oct 27 2010 K means Recap S What is K means optimizing K means algorithm K means algorithm 1 Exactly first step assign each point to the nearest cluster center K means algorithm K means algorithm 2 Solution average of points in cluster i Exactly second step re center K means algorithm K means algorithm coordinate descent on F 1 Expectation step 2 Maximization step Today we will see a generalization of this approach EM algorithm Partitioning Algorithms K means hard assignment each object belongs to only one cluster Mixture modeling soft assignment probability that an object belongs to a cluster Generative approach 7 Gaussian Mixture Model Mixture of K Gaussians distributions Multi modal distribution There are k components Component i has an associated mean vector mi m2 m1 m3 Gaussian Mixture Model Mixture of K Gaussians distributions Multi modal distribution There are k components Component i has an associated mean vector mi Each component generates data from a Gaussian with mean mi and covariance matrix s2I Each data point is generated according to the following recipe m2 m1 m3 Gaussian Mixture Model Mixture of K Gaussians distributions Multi modal distribution There are k components Component i has an associated mean vector mi Each component generates data from a Gaussian with mean mi and covariance matrix s2I Each data point is generated according to the following recipe 1 Pick a component at random Choose component i with probability P y i m2 Gaussian Mixture Model Mixture of K Gaussians distributions Multi modal distribution There are k components Component i has an associated mean vector mi Each component generates data from a Gaussian with mean mi and covariance matrix s2I Each data point is generated according to the following recipe 1 Pick a component at random Choose component i with probability P y i 2 Datapoint x N mi s2I m2 x Gaussian Mixture Model Mixture of K Gaussians distributions Multi modal distribution p x y i N mi s2I p x S p x y i P y i i Mixture component Mixture proportion m2 m1 m3 Recall Gaussian Bayes Classifier Mixture of K Gaussians distributions Multi modal distribution p x y i N mi s2I Gaussian Bayes Classifier P y i x log P y j x p x y i P y i log p x y j P y j wTx m2 m1 m3 Depends on m1 m2 mK s2 P y 1 P Y k Linear Decision boundary Recall that second order terms cancel out MLE for GMM Maximum Likelihood Estimate MLE m argmax j 1 P yj xj m1 s2 m1 m2 mK m2 P y 1 P Y k m3 But we don t know yj s Maximize marginal likelihood K argmax j P xj argmax j i 1 P yj i xj K argmax j i P yj i p xj yj i 2 1 argmax j i 1P yj i exp 2 x j mi 2s K K means and GMM Linear Decision Boundaries Assume data comes from a mixture of K Gaussians distributions with same variance Hard assignment P yj i 1 0 if i C n otherwise Maximize marginal likelihood m argmax j P xj arg min x j mC j m1 m2 mK s2 P y 1 P y k m1 mK 2 j 1 C 1 C m Same as K means One bad case for K means Clusters may not be linearly separable Clusters may overlap Some clusters may be wider than others General GMM GMM Gaussian Mixture Model Multi modal distribution There are k components Component i has an associated mean vector mi Each component generates data from a Gaussian with mean mi and covariance matrix Si Each data point is generated according to the following recipe 1 Pick a component at random Choose component i with probability P y i 2 Datapoint x N mi Si m2 m1 m3 General GMM GMM Gaussian Mixture Model Multi modal distribution p x y i N mi Si p x S p x y i P y i i Mixture component Mixture proportion m2 m1 m3 General GMM GMM Gaussian Mixture Model Multi modal distribution p x y i N mi Si m2 Gaussian Bayes Classifier m1 P y i x log P y j x p x y i P y i log p x y j P y j x T Wx w T x m3 Depend on m1 m2 mK S1 S2 SK P y 1 P Y k Quadratic Decision boundary second order terms don t cancel out General GMM Maximize marginal likelihood K argmax j P xj argmax j i 1 P yj i xj K argmax j i 1 P yj i p xj yj i Soft assignment P yj i P y i 1 1 arg max P y i exp x j mi T i x j mi det i 2 j 1 i 1 m k How do we find the i s and P y i s which give max marginal likelihood Set log Prob 0 and solve for i s i Use gradient descent Non linear non analytically solvable Doable but often slow Expectation Maximization EM A general algorithm to deal with hidden data but we will study it in the context of unsupervised learning hidden labels first EM is an optimization strategy for objective functions that can be interpreted as likelihoods in the presence of missing data It is much simpler than gradient methods No need to choose step size EM is an Iterative algorithm with two linked steps E step fill in hidden values using inference M step apply standard MLE MAP method to completed data We will prove that this procedure monotonically improves the likelihood or leaves it unchanged Thus it always converges to a local optimum of the likelihood k Expectation Maximization EM A simple case We have unlabeled data x1 x2 xm We know there are k classes We know P y 1 P y 2 P y 3 P y K We don t know 1 2 k We know common variance s2 We can write P data 1 k p x1 xm m1 m k p x j m1 m k m Independent data j 1 p x j y i mi P y i m k Marginalize over class j 1 i 1 2 1 exp 2 x j mi P y i 2s j 1 i 1 m k Expectation E step If we know m1 mk easily compute prob point xj belongs to class y i For each point xj j 1 m 2 1 P y i x j m1 m k exp 2 x j mi P y i 2s simply evaluate gaussian and normalize Equivalent to assigning clusters to each data point in K means Maximization M step If we know prob point xj belongs to class y i MLE for mi is weighted average imagine multiple copies of each xj each with weight P y i xj m P y i x x j mi j j …


View Full Document

CMU CS 10701 - EM Algorithm

Documents in this Course
lecture

lecture

12 pages

lecture

lecture

17 pages

HMMs

HMMs

40 pages

lecture

lecture

15 pages

lecture

lecture

20 pages

Notes

Notes

10 pages

Notes

Notes

15 pages

Lecture

Lecture

22 pages

Lecture

Lecture

13 pages

Lecture

Lecture

24 pages

Lecture9

Lecture9

38 pages

lecture

lecture

26 pages

lecture

lecture

13 pages

Lecture

Lecture

5 pages

lecture

lecture

18 pages

lecture

lecture

22 pages

Boosting

Boosting

11 pages

lecture

lecture

16 pages

lecture

lecture

20 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

18 pages

Lecture

Lecture

13 pages

Exam

Exam

10 pages

Lecture

Lecture

27 pages

Lecture

Lecture

15 pages

Lecture

Lecture

24 pages

Lecture

Lecture

16 pages

Lecture

Lecture

23 pages

Lecture6

Lecture6

28 pages

Notes

Notes

34 pages

lecture

lecture

15 pages

Midterm

Midterm

11 pages

lecture

lecture

11 pages

lecture

lecture

23 pages

Boosting

Boosting

35 pages

Lecture

Lecture

49 pages

Lecture

Lecture

22 pages

Lecture

Lecture

16 pages

Lecture

Lecture

18 pages

Lecture

Lecture

35 pages

lecture

lecture

22 pages

lecture

lecture

24 pages

Midterm

Midterm

17 pages

exam

exam

15 pages

Lecture12

Lecture12

32 pages

lecture

lecture

19 pages

Lecture

Lecture

32 pages

boosting

boosting

11 pages

pca-mdps

pca-mdps

56 pages

bns

bns

45 pages

mdps

mdps

42 pages

svms

svms

10 pages

Notes

Notes

12 pages

lecture

lecture

42 pages

lecture

lecture

29 pages

lecture

lecture

15 pages

Lecture

Lecture

12 pages

Lecture

Lecture

24 pages

Lecture

Lecture

22 pages

Midterm

Midterm

5 pages

mdps-rl

mdps-rl

26 pages

Load more
Download EM Algorithm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view EM Algorithm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view EM Algorithm and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?