https://stanford.edu/~shervine CS 229 – Machine Learning VIP Cheatsheet: Unsupervised Learning Afshine Amidi and Shervine Amidi August 12, 2018 Introduction to Unsupervised Learning k-means clustering r Motivation – The goal of unsupervised learning is to find hidden patterns in unlabeled data {x(1) ,...,x(m) }. We note c(i) the cluster of data point i and µj the center of cluster j. r Algorithm – After randomly initializing the cluster centroids µ1 ,µ2 ,...,µk ∈ Rn , the k-means algorithm repeats the following step until convergence: r Jensen’s inequality – Let f be a convex function and X a random variable. We have the following inequality: m X E[f (X)] ⩾ f (E[X]) c(i) = arg min||x(i) − µj ||2 and µj = j 1{c(i) =j} x(i) i=1 m X Expectation-Maximization 1{c(i) =j} i=1 r Latent variables – Latent variables are hidden/unobserved variables that make estimation problems difficult, and are often denoted z. Here are the most common settings where there are latent variables: Setting Latent variable z x|z Comments Mixture of k Gaussians Multinomial(φ) N (µj ,Σj ) µj ∈ Rn , φ ∈ Rk Factor analysis N (0,I) N (µ + Λz,ψ) µj ∈ Rn r Algorithm – The Expectation-Maximization (EM) algorithm gives an efficient method at estimating the parameter θ through maximum likelihood estimation by repeatedly constructing a lower-bound on the likelihood (E-step) and optimizing that lower bound (M-step) as follows: r Distortion function – In order to see if the algorithm converges, we look at the distortion function defined as follows: J(c,µ) = E-step: Evaluate the posterior probability Qi (z (i) ) that each data point x(i) came from a particular cluster z (i) as follows: Hierarchical clustering r Algorithm – It is a clustering algorithm with an agglomerative hierarchical approach that build nested clusters in a successive manner. M-step: Use the posterior probabilities Qi (z (i) ) as cluster specific weights on data points x(i) to separately re-estimate eac