Trang 1
CS 229 – Machine Learning https://stanford.edu/~shervine 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 We note c(i) the cluster of data point i and μ the center of cluster j. {x(1),...,x(m)}. j r Algorithm – After randomly initializing the cluster centroids μ ,μ ,...,μ ∈ Rn, the k-means 1 2 k r Jensen’s inequality – Let f be a convex function and X a random variable. We have the algorithm repeats the following step until convergence: following inequality: ∑m 1 x(i) E[f(X)] > f(E[X]) {c(i)=j} c(i) = arg min||x(i) − μ ||2 and μ = i=1 j j ∑m j Expectation-Maximization 1 (i) {c =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(μ ,Σ ) μ ∈ Rn, φ ∈ Rk j j j Factor analysis N(0,I) N(μ + Λz,ψ) μ ∈ Rn j r Algorithm – The Expectation-Maximization (EM) algorithm gives an efficient method at r Distortion function – In order to see if the algorithm converges, we look at the distortion estimating the parameter θ through maximum likelihood estimation by repeatedly constructing function defined as follows: a lower-bound on the likelihood (E-step) and optimizing that lower bound (M-step) as follows: ∑m J(c,μ) = ||x(i) − μ ||2 • E-step: Evaluate the posterior probability Q (z(i)) that each data point x(i) came from c(i) i a particular cluster z(i) as follows: i=1 Q (z(i)) = P(z(i)|x(i);θ) Hierarchical clustering i r Algorithm – It is a clustering algorithm with an agglomerative hierarchical approach that • M-step: Use the posterior probabilities Q (z(i)) as cluster specific weights on data points build nested clusters in a successive manner. i x(i) to separately re-estimate each cluster model as follows: r Types – There are different sorts of hierarchical clustering algorithms that aims at optimizing different objective functions, which is summed up in the table below: ∑ˆ ( ) Ward linkage Average linkage Complete linkage P(x(i),z(i);θ) θ = argmax Q (z(i)) log dz(i) i i Q (z(i)) Minimize within cluster Minimize average distance Minimize maximum distance θ z(i) i distance between cluster pairs of between cluster pairs i Stanford University 1 Fall 2018
Trang 2
CS 229 – Machine Learning https://stanford.edu/~shervine Clustering assessment metrics 1 ∑m • Step 2: Compute Σ = x(i)x(i)T ∈ Rn×n, which is symmetric with real eigenvalues. m In an unsupervised learning setting, it is often hard to assess the performance of a model since i=1 we don’t have the ground truth labels as was the case in the supervised learning setting. • Step 3: Compute u , ..., u ∈ Rn the k orthogonal principal eigenvectors of Σ, i.e. the r Silhouette coefficient – By noting a and b the mean distance between a sample and all 1 k other points in the same class, and between a sample and all other points in the next nearest orthogonal eigenvectors of the k largest eigenvalues. cluster, the silhouette coefficient s for a single sample is defined as follows: • Step 4: Project the data on span (u ,...,u ). This procedure maximizes the variance R 1 k b − a among all k-dimensional spaces. s = max(a,b) r Calinski-Harabaz index – By noting k the number of clusters, Bk and Wk the between and within-clustering dispersion matrices respectively defined as ∑k ∑m B = n (μ − μ)(μ − μ)T , W = (x(i) − μ )(x(i) − μ )T k c(i) c(i) c(i) k c(i) c(i) j=1 i=1 the Calinski-Harabaz index s(k) indicates how well a clustering model defines its clusters, such that the higher the score, the more dense and well separated the clusters are. It is defined as follows: Independent component analysis Tr(Bk) N − k It is a technique meant to find the underlying generating sources. s(k) = × Tr(Wk) k − 1 r Assumptions – We assume that our data x has been generated by the n-dimensional source vector s = (s1,...,sn), where si are independent random variables, via a mixing and non-singular matrix A as follows: Principal component analysis x = As It is a dimension reduction technique that finds the variance maximizing directions onto which The goal is to find the unmixing matrix W = A−1 by an update rule. to project the data. r Bell and Sejnowski ICA algorithm – This algorithm finds the unmixing matrix W by r Eigenvalue, eigenvector – Given a matrix A ∈ Rn×n, λ is said to be an eigenvalue of A if following the steps below: there exists a vector z ∈ Rn\{0}, called eigenvector, such that we have: • Write the probability of x = As = W−1s as: Az = λz ∏ n p(x) = p (wT x)·|W| s i r Spectral theorem – Let A ∈ Rn×n. If A is symmetric, then A is diagonalizable by a real i=1 orthogonal matrix U ∈ Rn×n. By noting Λ = diag(λ ,...,λ ), we have: 1 n • Write the log likelihood given our training data {x(i), i ∈ [[1,m]]} and by noting g the ∃Λ diagonal, A = UΛUT sigmoid function as: ( ( ) ) Remark: the eigenvector associated with the largest eigenvalue is called principal eigenvector of ∑m ∑n matrix A. l(W) = log g′(wT x(i)) + log |W| j r Algorithm – The Principal Component Analysis (PCA) procedure is a dimension reduction i=1 j=1 technique that projects the data on k dimensions by maximizing the variance of the data as follows: Therefore, the stochastic gradient ascent learning rule is such that for each training example x(i), we update W as follows: • Step 1: Normalize the data to have a mean of 0 and standard deviation of 1. 1 − 2g(wT x(i)) 1 1 − 2g(wT x(i)) W ←− W + α 2 x(i)T + (WT )−1 x(i) − μ ∑m ∑m .. (i) j j 1 (i) 2 1 (i) 2 . x ← where μj = x and σj = (x − μj) T (i) j σ m j m j 1 − 2g(w x ) j n i=1 i=1 Stanford University 2 Fall 2018
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!