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
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
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
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
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
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
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
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
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
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
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
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 AlgorithmAarti SinghSlides courtesy: Eric Xing, Carlos GuetrinMachine Learning 10-701/15-781Oct 27, 2010K-means Recap …S:What is K-means optimizing?=K-means algorithmK-means algorithm:(1)Exactly first step – assign each point to the nearest cluster centerK-means algorithmK-means algorithm:(2)Solution: average of points in cluster iExactly second step (re-center)K-means algorithmK-means algorithm: (coordinate descent on F)(1)(2)Expectation stepMaximization stepToday, we will see a generalization of this approach:EM algorithm• K-means – hard assignment: each object belongs to only one cluster• Mixture modeling– soft assignment: probability that an object belongs to a clusterGenerative approach7Partitioning AlgorithmsGaussian Mixture ModelMixture of K Gaussians distributions: (Multi-modal distribution)• There are k components• Component i has an associated mean vector mim1m2m3Mixture of K Gaussians distributions: (Multi-modal distribution)• There are k components• Component i has an associated mean vector mim1m2m3m1m2m3• Each component generates data from a Gaussian with mean mi and covariance matrixs2IEach data point is generated according to the following recipe: Gaussian Mixture ModelMixture of K Gaussians distributions: (Multi-modal distribution)• There are k components• Component i has an associated mean vector mim2m2• Each component generates data from a Gaussian with mean mi and covariance matrixs2IEach data point is generated according to the following recipe: 1) Pick a component at random: Choose component i with probability P(y=i)Gaussian Mixture ModelMixture of K Gaussians distributions: (Multi-modal distribution)• There are k components• Component i has an associated mean vector mim2• Each component generates data from a Gaussian with mean mi and covariance matrixs2IEach 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)m2xGaussian Mixture ModelMixture of K Gaussians distributions: (Multi-modal distribution)m1m2m3m1m2m3p(x|y=i) ~ N(mi, s2I)p(x) = S p(x|y=i) P(y=i)iMixtureproportionMixturecomponentMixturecomponentGaussian Mixture ModelRecall: Gaussian Bayes ClassifierMixture of K Gaussians distributions: (Multi-modal distribution)m1m2m3m1m2m3Gaussian Bayes Classifier:)x|jy(P)x|iy(Plog==xwT=“Linear Decision boundary” – Recall that second-order terms cancel out)jy(P)jy|x(p)iy(P)iy|x(plog=====p(x|y=i) ~ N(mi, s2I)Depends on m1,m2, .. ,mK, s2, P(y=1),…, P(Y=k)MLE for GMMMaximum Likelihood Estimate (MLE)m2m3m1argmax j=1P(yj,xj)But we don’t know yj’s!!!Maximize marginal likelihood:argmax jP(xj) = argmax ji=1P(yj=i,xj)= argmax jiP(yj=i)p(xj|yj=i)= argmax ji=1P(yj=i)m1,m2, .. ,mK,s2, P(y=1),…, P(Y=k)KK2221expijxmsKmK-means and GMM“Linear” Decision BoundariesAssume data comes from a mixture of K Gaussians distributions with same varianceHard assignment:P(yj= i) = 1 if i = C(n)= 0 otherwiseSame as K-means!!!argmax jP(xj) m1,m2, .. ,mK,s2, P(y=1), …, P(y=k)=mjjCjx12)(minargmm1, .. ,mKC(1), …, C(m)Maximize marginal likelihood:(One) bad case for K-means• Clusters may not be linearly separable• Clusters may overlap• Some clusters may be “wider” than othersGeneral GMMGMM – Gaussian Mixture Model (Multi-modal distribution)m1m2m3m1m2m3• There are k components• Component i has an associated mean vector mi• Each component generates data from a Gaussian with mean mi and covariance matrixSiEach 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)General GMMGMM – Gaussian Mixture Model (Multi-modal distribution)m1m2m3m1m2m3p(x|y=i) ~ N(mi, Si)p(x) = S p(x|y=i) P(y=i)iMixtureproportionMixturecomponentGeneral GMMGMM – Gaussian Mixture Model (Multi-modal distribution)m1m2m3m1m2m3p(x|y=i) ~ N(mi, Si)Gaussian Bayes Classifier:)x|jy(P)x|iy(Plog==xwWxxTT=“Quadratic Decision boundary” – second-order terms don’t cancel out)jy(P)jy|x(p)iy(P)iy|x(plog=====Depend on m1,m2, .. ,mK, S1, S2, .. , SK,P(y=1),…, P(Y=k)General GMMMaximize marginal likelihood:argmax jP(xj) = argmax ji=1P(yj=i,xj)= argmax ji=1P(yj=i)p(xj|yj=i)KK====mjkiijiTijixxiyP11)()(21exp)det(1)(maxargmmSoft assignment: P(yj=i) = P(y=i) 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. Non-linear non-analytically solvable μi* Use gradient descent: Doable, but often slowExpectation-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 inferenceM-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.kExpectation-Maximization (EM)A simple case:We have unlabeled data x1x2… xmWe know there are k classesWe know P(y=1), P(y=2) P(y=3) … P(y=K)We don’t know μ1μ2.. μkWe know common variance s2We can write P( data | μ1…. μk) ( )( )( )( )( )===========mjkiijmjkiijmjkjkmiyxiyiyxxxx1122111111P21exp P ,p...p......pmsmmmmmIndependent dataMarginalize over classExpectation (E) stepIf we know m1,…,mk  easily compute prob. point xjbelongs to class y=i( )( )iyPx21exp...,xiyP2ij2k1j=msmm=simply evaluate gaussian and normalizeFor each point xj, j = 1, …, mEquivalent to assigning clusters to each data point in K-meansMaximization (M) stepIf we know prob. point xjbelongs to class y=i MLE for miis weighted averageimagine multiple copies of each xj, each with weight P(y=i|xj): mi = P y = i xj( )j=1mxjP y = i xj( )j=1mEquivalent to updating cluster centers in K-meansEM for spherical, same variance GMMsE-stepCompute “expected” classes of all datapoints for each classM-stepCompute Max. like μ given our


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 2 2 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?