### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 275 Class Note for CS 59000 with Professor Qi at Purdue

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Department

This 34 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 19 views.

## Similar to Course at Purdue

## Reviews for 275 Class Note for CS 59000 with Professor Qi at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

CS 59000 Statistical Machine learning Lecture 23 Yuan Aura j PUMME C3 Hum 18 200 Outline Review of max sum algorithm K means clustering K medoids Mixture of Gaussians Vector quantization Expectation maximization EM Alternative view of EM The MaxSum Algorithm 1 Objective an efficient algorithm for finding i the value XmaX that maximises p x ii the value ofpxmaX In general maximum marginals joint maximum argmaxpvy 1 argmaxpa 0 1 3 The MaxSum Algorithm 2 Maximizing over a chain max product 31 32 N71 cN maxpx max maxpx x 561 10M HEX 39 39Dgax 1251313502 39 39 wN 1NN 1N N max HEX 10120517362 quotIginN 1NN 1N The MaxSum Algorithm 4 Max Product gt Max Sum For numerical reasons use In maxpx maxlnpx Again use distributive law maxa b a C a maXb C The MaxSum Algorithm 5 Initialization leaf nodes Mat gtfm O Mf mCE 1nf Recursion Mf ixw max Infmx1xM Z Majmafxm mEnefsc gba argmax 1nfxx11M Z ux7r19fxm 111M mEnefs Z Usz gt1 l nef 7 52 l K 3 The MaxSum Algorithm 6 Termination root node pmax mgxl Z Mfs mx xmax argmax Z Mfg gt433 a sEnen Kmeans Clustering Goal Given data set xxN in Ddimensional Euclidean space Partition into K clusters which is given One ofK coding Indicator variable rnk a 01 where k 1K Describes which ofK clusters data point x is assigned to Cost Function Sum of squared errors NK JZZrnkilxn uklr n1 k1 Goal is to find values for rnk and the uk so as to minimize J Can be done by iterative procedure Each iteration has two steps Successive optimization wrt rnk and W Two Stage Updates First choose initial values for pk First phase minimize Jwrt rnk keeping pk fixed Second phase minimize Jwrt pk keeping rnk fixed Optimizing Cluster Assignment NA Because J 221Ligtltnill2 11 Ifl is a linear function of rnk this optimization is performed easily closed form solution Terms involving different n are independent Therefore can optimize for each n separately Choosing rnk to be 1 for whichever value of k gives minimum value of llxnukll3 ThUS I ifk argmin ll x uj l2 IIIr 0 otherwise Interpretation Assign xquot to cluster whose mean is closest Optimizing Cluster Centers Hold rnk fixed Objective function JIkilx mr is a quadratic function of uk Minimized by setting derivative wrt W to zero Thus 22nix u0 quot Zrnkxn 1 Which is solved to give k z Equaltonoof d Interpretation foogissfesisllfgne Set uk to mean of all data points xn assigned to cluster k Example of KMeans Clustering I4 Stochastic Online Clustering Instead of batch processing entire data set Apply RobbinsMonro procedure To finding roots of the regression function given by the derivative of J wrt pk M 1 777 Xi 13 where 77 is a learning rate parameter made to decrease monotonically as more samples are observed Kmedoids Algorithm Euclidean distance has limitations Inappropriate for categorical labels Cluster means are nonrobust to outliers Use more general dissimilarity measure vxx and distortion measure N N K JZZZIl7kxn7 k 111 kl Which gives the k medoids algorithm VKMeans and Vector Quantization I 2 A 3 Iquot 10 Original image IJ39k Codebook vectors for lossy data compression Limitations of Kmeans Every data point is assigned uniquely to one and only one cluster A point may be equidistant from two cluster centers A probabilistic approach will have a soft assignment of data points reflecting the level of uncertainty Mixture of Gaussians Mixture of Gaussians K W Z mmxiuk 2k 61 Introduce latent variables X 92k 1 2 Wk Marginal distribution K pltxgt Zpltzgtpltxzgt EmaNewly at 61 Conditional Probability PM 1Xl2k 1 7 319 1X K 1pxzj 1 33921 WICNXIHICJ 53k K ZWjNltxluj 23 33921 Responsibility that component k takes for explaining the observation Maximum Likelihood Maximize the log likelihood function N K 1npX7ru2 Zln 7T1 NltXnluk2k 171 n 1 Graphical representation of a Gaussian mixture model for a set of N iid data points xn with corresponding latent points Zn where n 17 7N 7quot An easy solution Discussion Severe Overfitting by Maximum Likelihood i PM I When a cluster has only data point its variance goes to O Iden ab hy For any given maximum likelihood solution a K component mixture will have a total of K equivalent solutions corresponding to the K ways of assigning K sets of parameters to K components Why If we flip the labels of the components we will have an equivalent model Difficulty for parameter interpretation irrelevant for density estimation Maximum Likelihood Conditions 1 Setting the derivatives of 1npXi7Tu 2 to zero O iv WkNXTZ Hk7 2k 21307 1 2339 WjNXTl Il ja 23 7an 1 N W Wan Wm N Maximum Likelihood Conditions 2 Setting the derivative of 1npXl7nui 2 to zero EA Z 7Z39rlk7xn Mktgtltxn 711 Maximum Likelihood Conditions 3 Lagrange function K lnpXi7r u E A 77k 1 191 Setting its derivative to zero and use the normalization constraint we obtain 2 T N Expectation Maximization for Mixture Gaussians Although the previous conditions do not provide closed form conditions we can use them to construct iterative updates E step Compute responsibilitieswzlnk M step Compute new mean kw variance 2k and mixing coefficients m Loop over E and M steps until the log likelihood 1npXluE7t stops to increase h 1 a 2 O O quot quot as 7 U 2 O a 2 2 O b 2 C 2 2 L20 C 0 L39 0 5 0 I 2 t 2 5 2 5 2 0 d 7 7 0 e 2 2 D f EM on the Old Faithful cata set General EM Algorithm Given a joint distribution pX ZiB over observed variables X and latent vari ables Z governed by parameters 9 the goal is to maximize the likelihood func tion with respect to 6 1 Choose an initial setting for the parameters 60 2 E step Evaluate pZX 001d 3 M step Evaluate t9116W given by Huew argmax QM 001d 0 Where 90 60 EMZIX 001dgt1npX7 Zl0 7 4 Check for convergence of either the log likelihood or the parameter values If the convergence criterion is not satis ed then let 001d anew and return to step 2 EM as Lower Bounding Methods Goal maximize pXi9 ZpXZi9 Z 19X Zi0 Define q0 EZ qZ1n qZ Z pZiX 9 Lower Bound MM is a functional of the distribution 12 Since KLqP 2 0 and 11119ltXl9gt Q79KLQHP MM is a lower bound ofthe log likelihood function InpXl9 Illustration of Lower Bound Lower Bound Perspective of EM Expectation Step Maximizing the functional lower bound q6 over the distribution qltZ Maximization Step Maximizing the lower bound over the parameters 6 Illustration of EM Updates 111X 6 Old 6 new

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.