1©2005-2007 Carlos Guestrin1EM (cont.)Machine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityNovember 26th, 20072©2005-2007 Carlos GuestrinSilly ExampleLet 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 werea A’sb B’sc C’sd D’sWhat’s the maximum likelihood estimate of µ given a,b,c,d ?3©2005-2007 Carlos GuestrinTrivial StatisticsP(A) = ½ P(B) = µ P(C) = 2µ P(D) = ½-3µP( a,b,c,d | µ) = K(½)a(µ)b(2µ)c(½-3µ)dlog P( a,b,c,d | µ) = log K + alog ½ + blog µ + clog 2µ + dlog (½-3µ)! FOR MAX LIKE µ, SET "LogP"µ= 0"LogP"µ=bµ+2c2µ#3d1/2 # 3µ= 0Gives max like µ = b + c6 b + c + d( )So if class gotMax like µ=110109614DCBABoring, but true!4©2005-2007 Carlos GuestrinSame Problem with Hidden InformationSomeone tells us thatNumber of High grades (A’s + B’s) = hNumber of C’s = cNumber of D’s = dWhat is the max. like estimate of µ now?We can answer this question circularly:! µ = b + c6 b + c + d( )MAXIMIZATIONIf we know the expected values of a and bwe could compute the maximum likelihoodvalue of µREMEMBERP(A) = ½P(B) = µP(C) = 2µP(D) = ½-3µ! a =1212+µh b =µ12+µhEXPECTATIONIf we know the value of µ we could compute theexpected value of a and bSince the ratio a:b should be the same as the ratio ½ : µ5©2005-2007 Carlos GuestrinE.M. for our Trivial ProblemWe begin with a guess for µWe iterate between EXPECTATION and MAXIMALIZATION to improve our estimatesof µ and a and b.Define µ(t) the estimate of µ on the t’th iteration b(t) the estimate of b on t’th iterationREMEMBERP(A) = ½P(B) = µP(C) = 2µP(D) = ½-3µ! µ(0)= initial guessb(t )= µ(t )h12+µ(t )= " b |µ(t )[ ]µ(t +1)=b(t )+ c6 b(t )+ c + d( )= max like est. of µ given b(t )E-stepM-stepContinue iterating until converged.Good news: Converging to local optimum is assured.Bad news: I said “local” optimum.6©2005-2007 Carlos GuestrinE.M. Convergence Convergence proof based on fact that Prob(data | µ) must increase or remainsame between each iteration [NOT OBVIOUS] But it can never exceed 1 [OBVIOUS]So it must therefore converge [OBVIOUS]3.1870.094863.1870.094853.1870.094843.1850.094733.1580.093722.8570.08331000b(t)µ(t)tIn our example,suppose we hadh = 20c = 10d = 10 µ(0) = 0Convergence is generally linear: errordecreases by a constant factor each timestep.7©2005-2007 Carlos GuestrinBack to Unsupervised Learning ofGMMs – a simple caseA simple case:We have unlabeled data x1 x2 … xmWe know there are k classesWe know P(y1) P(y2) P(y3) … P(yk)We don’t know µ1 µ2 .. µkWe can write P( data | µ1…. µk)! = p x1...xmµ1...µk( )= p xjµ1...µk( )j=1m"= p xjµi( )P y = i( )i=1k#j=1m"$ exp %12&2xj%µi2' ( ) * + , P y = i( )i=1k#j=1m"8©2005-2007 Carlos GuestrinEM for simple case of GMMs: TheE-step If we know µ1,…,µk → easily compute prob.point xj belongs to class y=i! p y = i xj,µ1...µk( )"exp #12$2xj#µi2% & ' ( ) * P y = i( )9©2005-2007 Carlos GuestrinEM for simple case of GMMs: TheM-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):! µi = P y = i xj( )j=1m"xjP y = i xj( )j=1m"10©2005-2007 Carlos GuestrinE.M. for GMMsE-stepCompute “expected” classes of all datapoints for each classM-stepCompute Max. like µ given our data’s class membership distributionsJust evaluatea Gaussian atxj! p y = i xj,µ1...µk( )"exp #12$2xj#µi2% & ' ( ) * P y = i( )! µi = P y = i xj( )j=1m"xjP y = i xj( )j=1m"11©2005-2007 Carlos GuestrinE.M. Convergence This algorithm is REALLY USED. And in high dimensional state spaces, too.E.G. Vector Quantization for Speech Data• EM is coordinateascent on aninteresting potentialfunction• Coord. ascent forbounded pot. func. !convergence to alocal optimumguaranteed• See Neal & Hintonreading on classwebpage12©2005-2007 Carlos GuestrinE.M. for axis-aligned GMMsIterate. On the t’th iteration let our estimates beλt = { µ1(t), µ2(t) … µk(t), Σ1(t), Σ2(t) … Σk(t), p1(t), p2(t) … pk(t) }E-stepCompute “expected” classes of all datapoints for each class( ) ( ))()()(,p,Ptitijtitjxpxiy !"=µ#pi(t) is shorthand forestimate of P(y=i)on t’th iterationM-stepCompute Max. like µ given our data’s class membership distributions( )( )( )!!===+jtjjjtjtixiyxxiy"",P ,Pì1( )mxiypjtjti!==+",P)1(m = #recordsJust evaluatea Gaussian atxj ! " =#210 0 L 0 00#220 L 0 00 0#23L 0 0M M M O M M0 0 0 L#2m$100 0 0 L 0#2m% & ' ' ' ' ' ' ' ( ) * * * * * * * pi(t) is shorthand forestimate of P(y=i)on t’th iteration13©2005-2007 Carlos GuestrinE.M. for General GMMsIterate. On the t’th iteration let our estimates beλt = { µ1(t), µ2(t) … µk(t), Σ1(t), Σ2(t) … Σk(t), p1(t), p2(t) … pk(t) }E-stepCompute “expected” classes of all datapoints for each class( ) ( ))()()(,p,Ptitijtitjxpxiy !"=µ#pi(t) is shorthand forestimate of P(y=i)on t’th iterationM-stepCompute Max. like µ given our data’s class membership distributions( )( )( )!!===+jtjjjtjtixiyxxiy"",P ,Pì1( )( )( )[ ]( )[ ]( ) ,P ,P111!!=""==#+++jtjTtijtijjtjtixiyxxxiy$µµ$( )mxiypjtjti!==+",P)1(m = #recordsJust evaluatea Gaussian atxj14©2005-2007 Carlos GuestrinGaussian Mixture Example: Start15©2005-2007 Carlos GuestrinAfter first iteration16©2005-2007 Carlos GuestrinAfter 2nd iteration17©2005-2007 Carlos GuestrinAfter 3rd iteration18©2005-2007 Carlos GuestrinAfter 4th iteration19©2005-2007 Carlos GuestrinAfter 5th iteration20©2005-2007 Carlos GuestrinAfter 6th iteration21©2005-2007 Carlos GuestrinAfter 20th iteration22©2005-2007 Carlos GuestrinSome Bio Assay data23©2005-2007 Carlos GuestrinGMM clustering of the assay data24©2005-2007 Carlos GuestrinResultingDensityEstimator25©2005-2007 Carlos GuestrinThreeclasses ofassay(each learned withit’s own mixturemodel)26©2005-2007 Carlos GuestrinResultingBayesClassifier27©2005-2007 Carlos GuestrinResulting BayesClassifier, usingposteriorprobabilities toalert aboutambiguity andanomalousnessYellow meansanomalousCyan meansambiguous28©2005-2007 Carlos GuestrinAnnouncements Project: Poster session: NSH Atrium, Friday 11/30, 2-5pm Print your poster early!!! SCS facilities has a poster printer,
View Full Document
Unlocking...