Dimensionality reduction cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 25th 2007 2005 2007 Carlos Guestrin 1 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 2 2005 2007 Carlos Guestrin Linear projection and reconstruction x2 project into 1 dimension z1 x1 reconstruction only know z1 what was x1 x2 3 2005 2007 Carlos Guestrin 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 4 2005 2007 Carlos Guestrin Linear projections a review Project a point into a lower dimensional space point x x1 xn select a basis set of basis vectors u1 uk we consider orthonormal basis ui ui 1 and ui uj 0 for i j select a center x defines offset of space best coordinates in lower dimensional space defined by dot products z1 zk zi x x ui minimum squared error 5 2005 2007 Carlos Guestrin 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 PCA and x2 Given k n find u1 uk minimizing reconstruction error x1 6 2005 2007 Carlos Guestrin Understanding the reconstruction error Note that xi can be represented exactly by n dimensional projection Rewriting error Given k n find u1 uk minimizing reconstruction error 7 2005 2007 Carlos Guestrin Reconstruction error and covariance matrix 8 2005 2007 Carlos Guestrin 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 9 2005 2007 Carlos Guestrin 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 10 2005 2007 Carlos Guestrin PCA example 11 2005 2007 Carlos Guestrin PCA example reconstruction only used first principal component 12 2005 2007 Carlos Guestrin Eigenfaces Turk Pentland 91 Input images Principal components 13 2005 2007 Carlos Guestrin Eigenfaces reconstruction Each image corresponds to adding 8 principal components 14 2005 2007 Carlos Guestrin Relationship to Gaussians x2 PCA assumes data is Gaussian x N x Equivalent to weighted sum of simple Gaussians Selecting top k principal components equivalent to lower dimensional Gaussian approximation x1 N 0 2 where 2 is defined by errork 15 2005 2007 Carlos Guestrin 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 16 2005 2007 Carlos Guestrin 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 in our setting each entry is eigenvalue j VT singular vector matrix in our setting each row is eigenvector vj 17 2005 2007 Carlos Guestrin 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 18 2005 2007 Carlos Guestrin Using PCA for dimensionality reduction in classification Want to learn f XaY X X1 Xn but some features are more important than others Approach Use PCA on X to select a few important features 19 2005 2007 Carlos Guestrin PCA for classification can lead to problems Direction of maximum variation may be unrelated to discriminative directions PCA often works very well but sometimes must use more advanced methods e g Fisher linear discriminant 20 2005 2007 Carlos Guestrin 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 problems with PCA 21 2005 2007 Carlos Guestrin Announcements Homework 5 Extension Due Friday at 10 30am Hand in to Monica Wean 4619 Project Poster session Friday May 4th 2 5pm NSH Atrium Paper Thursday May 10th by 2pm please arrive a 15mins early to set up electronic submission by email to instructors list maximum of 8 pages NIPS format no late days allowed FCEs Please please please please please please give us your feedback it helps us improve the class http www cmu edu fce 2005 2007 Carlos Guestrin 22 Markov Decision Processes MDPs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 25th 2006 2005 2007 Carlos Guestrin 23 Thus far this semester Regression Classification Density estimation 24 2005 2007 Carlos Guestrin Learning to act Reinforcement learning An agent Makes sensor observations Must select action Receives rewards Ng et al 05 positive for good states negative for bad states 25 2005 2007 Carlos Guestrin Learning to play backgammon Tesauro 95 Combines reinforcement learning with neural networks Played 300 000 games against itself Achieved grandmaster level 26 2005 2007 Carlos Guestrin Roadmap to learning about reinforcement learning When we learned about Bayes nets First talked about formal framework representation inference Then learning for BNs For reinforcement learning Formal framework Markov decision processes Then learning 27 2005 2007 Carlos Guestrin peasant footman building Real time Strategy Game Peasants collect resources and build Footmen attack enemies Buildings train peasants and footmen 28 2005 2007 Carlos Guestrin States and actions State space Joint state x of entire system Action space Joint action a a1 an for all agents 29 2005 2007 Carlos Guestrin States change over time Like an HMM state changes over time Next state depends on current state and action selected e g action build castle likely to lead to a state where you have a castle Transition model Dynamics of the entire system P x x a 30 2005 2007 Carlos Guestrin Some states and actions are better than others Each state x is associated with a reward positive reward for successful attack negative for loss
View Full Document
Unlocking...