CSI 436/536 Introduction To Machine Learning

CSI 436/536Introduction to Machine LearningMulti-model LLSE and k-means clusteringProfessor Siwei LyuComputer ScienceUniversity at Albany, State University of New York

Fitting multiple linear modelsation (EM) algorithm simultaneouslyrated from multiple parametric models.ure 2.3 arecollectionof datapoints we need to deal withIn amanypracticalproblems,of two linearmodelsof theatform:multiplemodelsthe same time to separate cooccurringattributing to observeddataa1 x(i) factorsb1 n1 (i)(2.21)a2 x(i) fittingb2 n2two(i), lines to the(2.22)data sets are a1 , b1 needand atothe systemof two lines a1, a2, b1, b2parameters2 , bfind2 , andoise n1 (i) and n2 (i).need to know the assignment ofeach point to line 1 or line 2rameters, then determining which data ch modelwould beonea simpleof knowingsolvematterthe otherint i, theismodelthatminimizeseasy, kbutsolvingthemthethe modelprediction:at thesame time is hard ak x(i) bk y(i)) ,(2.23)On the other hand, if we are told whichby which model, then estimating theFigure 2.3 Datafrom

Problem formulation & solution Overall objective functionnKαij,wj mini 1 j 1 αij(yi wjT xi)2, s.t. αij [0,1],K j 1αij 1Solution is a special case of the expectationmaximization (EM) algorithm1, Starting with initial values of αij K Iterate until convergence Update wj, for j 1, , K (E-step: fitting data toeach line)Update αij (M-step: figuring out the model of eachdata example belongs)

E-step Solving sub-problem with regards to each wjminwj n i 1αij(yi wjT xi)2 — this is a weighted LLSEDiagonal weight matrix W with Wii αij 0, and tosolveminw(y X T w)TW(y X T w)Solution w (y X T w)TW(y X T w) 2(XWX T w XWy) 0so XWX T w XWy w (XWX T ) 1XWy

M-step Solving sub-problem with regards to each αijminαij K j 1αij(yi wjT xi)2, s.t. αij [0,1],K j 1αij 1Define Lij (yi wjT xi)2, this reduces to a linearprogramming (LP) problem for each i, asminαij K j 1αij Lij, s.t. αij [0,1],K j 1αij 1We can solve this using LP solver, but this problemhas a simple solution

M-step Solving the M-step problemminαij K j 1αij Lij, s.t. αij [0,1],K j 1Lαij 1αThe constraint setαij [0,1],K j 1αij 1 is known as theprobability simplex L is a vector in the positive orthant, so optimal solutionis on the probability simplex Optimal solution can be obtained by Cauchy-ShwartzLijinequality αij K, which satisfies the constraint k 1 Lik

EM-LLSE algorithm Stands for expectationmaximization Set initial values of thetwo linear models Iterate untilconvergence occurs For each model tobe considered Compute errorsof each data point Update modelparameter withWeighted LLSEalgorithm

tion (EM)clustering problemation (EM) algorithm simultaneouslyrated from multiple parametric models. multi-modal linear LSE is a soft clustering problemure 2.3 area collection of data pointsof two linearmodels of the Membershiptoform:each model/cluster is in the form of aa1 x(i) b1“soft” n1 (i)weight(2.21)convert the problema2 x(i) Web2 cann2 (i),(2.22) to a hard clustering settinga “yes/no”s are a1 , b1 Membershipand a2 , b2 , andisthesystem binary questionoise n1 (i) and n2 (i).One data point can only belong to one clusterrameters, then determining which datach model would be a simple matter ofint i, the model k that minimizes thethe model prediction: ak x(i) bk y(i)) ,(2.23)On the other hand, if we are told whichby which model, then estimating the

Hard multi-modal LLSE Overall objective functionnKαij,wj mini 1 j 1αij(yi wjT xi)2, s.t. αij {0,1},K j 1αij 1 Note the difference is that the constraint changes froma continue interval [0,1] to a discrete binary set {0,1} The summation constraint determines that each datapoint is assigned to exactly one model solving this problem directly is NP-hard because Itinvolves enumerating all possible clusters We can solve it with the EM algorithm for anapproximate solution

EM algorithm for hard multi-modal LLSE Solving sub-problem with regards to each wjminwj n i 1αij(yi wjT xi)2 minwj Solving the M-step problemminαij K j 1nαij Lij, s.t. αij {0,1},i 1K1(xi,yi) modelj(yi wjT xi)2 j 1αij 1Solution is given by αij 1j arg mink LikIntuitively, data point i belongs to the model that givesthe minimum error

Clustering algorithm We can extend the multi-modal LLSE algorithm toclustering algorithms

k-means algorithm One of the most popular and simplest clusteringalgorithms, also known as Lloyd algorithm, or vectorquantization n d-dim data in matrix X C 2 clusters Ck, k 1, ,C cluster index set i Ck, then xi is in the kth cluster cluster membership indicatorcik no dual cluster membership cluster representatives µk1 i Ck0 i Ck

K-means algorithm Iterates between two steps Cluster assignment: update cluster membershipindicator Cluster representation: refine representative of eachcluster optimality: minimize representation errornCcik d( xi , µk )i 1 k 1 d is a distance metric, usually, assume euclidean normnCi 1 k 1cik xiµ k 2

Optimizing k-means solving this problem directly is NP-hard because Itinvolves enumerating all possible clustersn XCXmincik k xi µk k2cik , µk i 1 k 1solving by coordinate descent starting from initial guesses of µk, repeat until convergence fixing µk, find optimal cik - regrouping fixing cik, update µk - reassigningThis guarantees to converge [why?]

derivationregroupingmincikC XmXcik kxik 1 i 1M stepOptimizing ClusterCenters cik µk k221 k argminj kxi0 k 6 argminj kxiµj k22µj k22There is also a soft version of the k-means clusteringreassigningE step m C@ XXcik kxi µk k22@µki 1 k 1@ Xkxi µk k22@µkxi 2CkXX2(xi µk ) 2xixi 2Ck1 X) µk xi Ck xi 2Ckxi 2Ck2 Ck µk 0

Example

Problem1 234Consider the situation above where we need to cluster 4data points into two clusters: to break ties, we take theleft closest center in membership reassignment Initial cluster centers as {1,3} Initial cluster centers as {2,4}

No guarantee for local minimum Initial cluster centers as {1,3} 2341234Objective (1/2)2 (1/2)2 (1/2)2 (1/2)2 1Initial cluster centers as {2,4} 112341234Objective 1 0 1 0 2conclusion: k-means algorithm may not converge to alocal minimum of the objective function

knowing one piece of information (the model assignment or param-eters) makes determining the other relatively easy. But, lacking either piece of information makes this a considerably more difficult estimation problem. The EM algorithm is an iterative two step algorithm that estimates both the model assignment and para m-eters.