Recommended reading Bishop Chapters 3 6 8 6 Shlens PCA tutorial Wall et al 2003 PCA applied to gene expression data Dimensionality reduction cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 26th 2006 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 Liner projection and reconstruction x2 project into 1 dimension z1 x1 reconstruction only know z1 what was x1 x2 3 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 Linear projections a review Project a point into a lower dimensional space x x1 xn select a basis set of basis vectors u1 uk point 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 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 PCA and x2 Given k n find u1 uk minimizing reconstruction error x1 6 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 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 XcT Xc Find eigen vectors and values of Principal components k eigen vectors with highest eigen values New features are linear combination of old features 8 PCA example 9 PCA example reconstruction only used first principal component 10 Eigenfaces Turk Pentland 91 Input images Principal components 11 Eigenfaces reconstruction Each image corresponds to adding 8 principal components 12 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 13 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 14 SVD Write X U S VT X data matrix one row per datapoint U 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 15 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 16 Using PCA for dimensionality reduction in classification Want to learn f Xa aY X X1 Xn but some features are more important than others Approach Use PCA on X to select a few important features 17 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 18 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 19 Reading Kaelbling et al 1996 see class website Markov Decision Processes MDPs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University April 26th 2006 20 Announcements Project Poster session Friday May 5th 2 5pm NSH Atrium please arrive a little early to set up Monday May 8th by noon to Monica Hopes Wean Hall 4616 Paper maximum of 8 pages NIPS format FCEs Please please please please please please give us your feedback it helps us improve the class http www cmu edu fce 21 Thus far this semester Regression Classification Density estimation 22 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 23 Learning to play backgammon Tesauro 95 Combines reinforcement learning with neural networks Played 300 000 games against itself Achieved grandmaster level 24 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 25 peasant footman building Real time Strategy Game Peasants collect resources and build Footmen attack enemies Buildings train peasants and footmen 26 States and actions State space Joint state x of entire system Action space Joint action a a1 an for all agents 27 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 28 Some states and actions are better than others Each state x is associated with a reward positive reward for successful attack negative for loss Reward function Total reward R x 29 Discounted Rewards An assistant professor gets paid say 20K per year How much in total will the A P earn in their life 20 20 20 20 20 Infinity What s wrong with this argument 30 Discounted Rewards A reward payment in the future is not worth quite as much as a reward now Because of chance of obliteration Because of inflation Example Being promised 10 000 next year is worth only 90 as much as receiving 10 000 right now Assuming payment n years in future is worth only 0 9 n of payment now what is the AP s Future Discounted Sum of Rewards 31 Discount Factors People in economics and probabilistic decision making do this all the time The Discounted sum of future rewards using discount factor is reward now reward in 1 time step 2 reward in 2 time steps 3 reward in 3 time steps infinite sum 32 The Academic Life 0 6 0 6 0 2 B Assoc Prof 60 A Assistant Prof 20 0 2 S On
View Full Document
Unlocking...