1©2005-2007 Carlos Guestrin1EMMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityNovember 19th, 20072K-means1. Ask user how manyclusters they’d like.(e.g. k=5)2. Randomly guess kcluster Centerlocations3. Each datapoint findsout which Center it’sclosest to.4. Each Center findsthe centroid of thepoints it owns…5. …and jumps there6. …Repeat untilterminated!3K-means Randomly initialize k centers µ(0) = µ1(0),…, µk(0) Classify: Assign each point j∈{1,…m} to nearestcenter: Recenter: µi becomes centroid of its point: Equivalent to µi ← average of its points!4Does K-means converge??? Part 2 Optimize potential function: Fix C, optimize µ5Coordinate descent algorithms Want: mina minb F(a,b) Coordinate descent: fix a, minimize b fix b, minimize a repeat Converges!!! if F is bounded to a (often good) local optimum as we saw in applet (play with it!) K-means is a coordinate descent algorithm!6(One) bad case for k-means Clusters may overlap Some clusters may be“wider” than others7Gaussian Bayes ClassifierReminder)()()|()|(jjjpiyPiypiyPxxx====! P(y = i | xj) "1(2#)m / 2|| $i||1/ 2exp %12xj%µi( )T$i%1xj%µi( )& ' ( ) * + P(y = i)8Predicting wealth from age9Predicting wealth from age10Learning modelyear ,mpg ---> maker ! " =#21#12L#1m#12#22L#2mM M O M#1m#2mL#2m$ % & & & & ' ( ) ) ) )11General: O(m2)parameters ! " =#21#12L#1m#12#22L#2mM M O M#1m#2mL#2m$ % & & & & ' ( ) ) ) ) 12Aligned: O(m)parameters ! " =#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% & ' ' ' ' ' ' ' ( ) * * * * * * *13Aligned: O(m)parameters ! " =#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% & ' ' ' ' ' ' ' ( ) * * * * * * * 14Spherical: O(1)cov parameters ! " =#20 0 L 0 00#20 L 0 00 0#2L 0 0M M M O M M0 0 0 L#200 0 0 L 0#2$ % & & & & & & & ' ( ) ) ) ) ) ) )15Spherical: O(1)cov parameters ! " =#20 0 L 0 00#20 L 0 00 0#2L 0 0M M M O M M0 0 0 L#200 0 0 L 0#2$ % & & & & & & & ' ( ) ) ) ) ) ) ) 16Next… back to Density EstimationWhat if we want to do density estimation withmultimodal or clumpy data?17But we don’t see class labels!!! MLE: argmax ∏j P(yj,xj) But we don’t know yj’s!!! Maximize marginal likelihood: argmax ∏j P(xj) = argmax ∏j ∑i=1k P(yj=i,xj)18Special case: spherical Gaussiansand hard assignments If P(X|Y=i) is spherical, with same σ for all classes: If each xj belongs to one class C(j) (hard assignment), marginal likelihood: Same as K-means!!!! P(xj| y = i) " exp #12$2xj#µi2% & ' ( ) * ! P(xj, y = i)i=1k"j=1m#$ exp %12&2xj%µC ( j )2' ( ) * + , j=1m#! P(y = i | xj) "1(2#)m / 2|| $i||1/ 2exp %12xj%µi( )T$i%1xj%µi( )& ' ( ) * + P(y = i)19The GMM assumption• There are k components• Component i has an associatedmean vector µiµ1µ2µ320The GMM assumption• There are k components• Component i has an associatedmean vector µi• Each component generates datafrom a Gaussian with mean µi andcovariance matrix σ2IEach data point is generatedaccording to the following recipe:µ1µ2µ321The GMM assumption• There are k components• Component i has anassociated mean vector µi• Each component generatesdata from a Gaussian withmean µi and covariance matrixσ2IEach data point is generatedaccording to the followingrecipe:1. Pick a component at random:Choose component i withprobability P(y=i)µ222The GMM assumption• There are kcomponents• Component i has anassociated mean vector µi• Each component generatesdata from a Gaussian withmean µi and covariance matrixσ2IEach data point is generatedaccording to the followingrecipe:1. Pick a component at random:Choose component i withprobability P(y=i)2. Datapoint ~ N(µi, σ2I )µ2x23The General GMM assumptionµ1µ2µ3• There are kcomponents• Component i has anassociated mean vector µi• Each component generatesdata from a Gaussian withmean µi and covariance matrixΣiEach data point is generatedaccording to the followingrecipe:1. Pick a component at random:Choose component i withprobability P(y=i)2. Datapoint ~ N(µi, Σi )24Unsupervised Learning:not as hard as it looksand sometimes in betweenSometimes impossibleSometimes easyIN CASE YOU’REWONDERING WHATTHESE DIAGRAMSARE, THEY SHOW 2-dUNLABELED DATA (XVECTORS)DISTRIBUTED IN 2-dSPACE. THE TOPONE HAS THREEVERY CLEARGAUSSIAN CENTERS25Marginal likelihood for general case Marginal likelihood:! P(xj)j=1m"= P(xj, y = i)i=1k#j=1m"=1(2$)m / 2|| %i||1/ 2exp &12xj&µi( )T%i&1xj&µi( )' ( ) * + , P(y = i)i=1k#j=1m"! P(y = i | xj) "1(2#)m / 2|| $i||1/ 2exp %12xj%µi( )T$i%1xj%µi( )& ' ( ) * + P(y = i)26Special case 2: sphericalGaussians and soft assignments If P(X|Y=i) is spherical, with same σ for all classes: Uncertain about class of each xj (soft assignment), marginallikelihood:! P(xj| y = i) " exp #12$2xj#µi2% & ' ( ) * ! P(xj, y = i)i=1k"j=1m#$ exp %12&2xj%µi2' ( ) * + , P(y = i)i=1k"j=1m#27Unsupervised Learning:Mediumly Good NewsWe now have a procedure s.t. if you give me a guess at µ1, µ2 .. µk,I can tell you the prob of the unlabeled data given those µ‘s.Suppose x‘s are 1-dimensional.There are two classes; w1 and w2P(y1) = 1/3 P(y2) = 2/3 σ = 1 .There are 25 unlabeled datapointsx1 = 0.608x2 = -1.590x3 = 0.235x4 = 3.949 :x25 = -0.712(From Duda and Hart)28Duda & Hart’s ExampleWe can graph theprob. dist. functionof data given ourµ1 and µ2estimates.We can also graph thetrue function fromwhich the data wasrandomly generated.• They are close. Good.• The 2nd solution tries to put the “2/3” hump where the “1/3” hump should go,and vice versa.• In this example unsupervised is almost as good as supervised. If the x1 ..x25 are given the class which was used to learn them, then the results are(µ1=-2.176, µ2=1.684). Unsupervised got (µ1=-2.13, µ2=1.668).29Graph oflog P(x1, x2 .. x25 | µ1, µ2 )against µ1 (→) and µ2 (↑)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.Duda & Hart’s Exampleµ1µ230Finding the max likelihood µ1,µ2..µkWe 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 ∂ µiand solve for µi‘s.# Here you get non-linear non-analytically-solvable equations Use gradient descentOften slow but doable Use a much
View Full Document
Unlocking...