Dimensionality Reduction PCA Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University 2005 2009 Carlos Guestrin November 30th 2009 1 Dimensionality reduction Input data may have thousands or millions of dimensions e g text data has Dimensionality reduction represent data with fewer dimensions easier learning fewer parameters visualization hard to visualize more than 3D or 4D discover intrinsic dimensionality of data high dimensional data that is truly lower dimensional 2005 2009 Carlos Guestrin 2 1 Feature selection Want to learn f X Y X X1 Xn but some features are more important than others Approach select subset of features to be used by learning algorithm each feature or sets of features Select set of features with best score Score 2005 2009 Carlos Guestrin 3 Simple greedy forward feature selection algorithm Pick a dictionary of features e g polynomials for linear regression Greedy heuristic Start from empty or simple set of features F0 Run learning algorithm for current set of features Ft Obtain ht Select next best feature Xi e g Xj that results in lowest crossvalidation error learner when learning with Ft Xj Ft 1 Ft Xi Recurse 2005 2009 Carlos Guestrin 4 2 Simple greedy backward feature selection algorithm Pick a dictionary of features e g polynomials for linear regression Greedy heuristic Start from all features F0 F Run learning algorithm for current set of features Ft Obtain ht Select next worst feature Xi e g Xj that results in lowest crossvalidation error learner when learning with Ft Xj Ft 1 Ft Xi Recurse 2005 2009 Carlos Guestrin 5 Impact of feature selection on classification of fMRI data Pereira et al 05 2005 2009 Carlos Guestrin 6 3 Lower dimensional projections Rather than picking a subset of the features we can new features that are combinations of existing features Let s see this in the unsupervised setting just X but no Y 7 2005 2009 Carlos Guestrin Linear projection and reconstruction x2 project into 1 dimension z1 x1 reconstruction only know z1 what was x1 x2 2005 2009 Carlos Guestrin 8 4 Principal component analysis basic idea Project n dimensional data into k dimensional space while preserving information e g project space of 10000 words into 3 dimensions e g project 3 d into 2 d Choose projection with minimum reconstruction error 9 2005 2009 Carlos Guestrin Linear projections a review Project a point into a lower dimensional space x1 xn select a basis set of basis vectors u1 uk point x we consider orthonormal basis ui ui 1 and ui uj 0 for i j a center x defines offset of space best coordinates in lower dimensional space defined by dot products z1 zk zi x x ui select minimum squared error 2005 2009 Carlos Guestrin 10 5 PCA finds projection that minimizes reconstruction error Given m data points xi x1i xni i 1 m Will represent each point as a projection where and PCA x2 Given k n find u1 uk minimizing reconstruction error x1 2005 2009 Carlos Guestrin 11 Understanding the reconstruction error Note that xi can be represented exactly by n dimensional projection Rewriting error 2005 2009 Carlos Guestrin Given k n find u1 uk minimizing reconstruction error 12 6 Reconstruction error and covariance matrix 2005 2009 Carlos Guestrin 13 Minimizing reconstruction error and eigen vectors Minimizing reconstruction error equivalent to picking orthonormal basis u1 un minimizing Eigen vector Minimizing reconstruction error equivalent to picking uk 1 un to be eigen vectors with smallest eigen values 2005 2009 Carlos Guestrin 14 7 Basic PCA algoritm Start from m by n data matrix X Recenter subtract mean from each row of X Compute covariance matrix Xc X X 1 m XcT Xc Find eigen vectors and values of Principal components k eigen vectors with highest eigen values 2005 2009 Carlos Guestrin 15 PCA example 2005 2009 Carlos Guestrin 16 8 PCA example reconstruction only used first principal component 2005 2009 Carlos Guestrin 17 Eigenfaces Turk Pentland 91 Input images 2005 2009 Carlos Guestrin Principal components 18 9 Eigenfaces reconstruction Each image corresponds to adding 8 principal components 2005 2009 Carlos Guestrin 19 Scaling up Covariance matrix can be really big is n by n 10000 features finding eigenvectors is very slow Use singular value decomposition SVD finds to k eigenvectors great implementations available e g Matlab svd 2005 2009 Carlos Guestrin 20 10 SVD Write X W S VT X data matrix one row per datapoint W weight matrix one row per datapoint coordinate of xi in eigenspace S singular value matrix diagonal matrix VT in our setting each entry is eigenvalue j singular vector matrix in our setting each row is eigenvector vj 2005 2009 Carlos Guestrin 21 PCA using SVD algoritm Start from m by n data matrix X Recenter subtract mean from each row of X Xc X X Call SVD algorithm on Xc ask for k singular vectors Principal components k singular vectors with highest singular values rows of VT Coefficients become 2005 2009 Carlos Guestrin 22 11 What you need to know Dimensionality reduction why and when it s important Simple feature selection Principal component analysis minimizing reconstruction error relationship to covariance matrix and eigenvectors using SVD 2005 2009 Carlos Guestrin 23 Markov Decision Processes MDPs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University November 30th 2009 2005 2009 Carlos Guestrin 24 12 Thus far this semester Regression Classification Density estimation 2005 2009 Carlos Guestrin 25 Learning to act Reinforcement learning An agent Makes sensor observations Must select action Receives rewards Ng et al 05 2005 2009 Carlos Guestrin positive for good states negative for bad states 26 13 Learning to play backgammon Tesauro 95 Combines reinforcement learning with neural networks Played 300 000 games against itself Achieved grandmaster level 27 2005 2009 Carlos Guestrin Roadmap to learning about reinforcement learning When we learned about Bayes nets First talked representation inference Then about formal framework learning for BNs For reinforcement learning Formal framework Markov decision processes Then 2005 2009 Carlos Guestrin learning 28 14 peasant footman building Real time Strategy Game Peasants collect resources and build Footmen attack enemies Buildings train peasants and footmen 2005 2009 Carlos Guestrin 29 States and actions State space Joint state x of entire system Action space Joint action a a1 an for all agents 2005 2009 Carlos Guestrin 30 15 States change over time Like an HMM state changes over time
View Full Document
Unlocking...