11Dimensionality ReductionPCAMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityNovember 30th, 2009©2005-2009 Carlos Guestrin2Dimensionality 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 Guestrin23Feature 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 Score each feature (or sets of features) Select set of features with best score©2005-2009 Carlos Guestrin4Simple greedy forwardfeature 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., Xjthat results in lowest cross-validation error learner when learning withFt∪{Xj} Ft+1←Ft ∪{Xi} Recurse©2005-2009 Carlos Guestrin35Simple 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., Xjthat results in lowest cross-validation error learner when learning withFt- {Xj} Ft+1←Ft - {Xi} Recurse©2005-2009 Carlos Guestrin6Impact of feature selection on classification of fMRI data [Pereira et al. ’05] ©2005-2009 Carlos Guestrin47Lower 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©2005-2009 Carlos Guestrin8Linear projection and reconstructionx1x2project into1-dimensionz1reconstruction:only know z1, what was (x1,x2)©2005-2009 Carlos Guestrin59Principal 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©2005-2009 Carlos Guestrin10Linear 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©2005-2009 Carlos Guestrin611PCA 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: Given k·n, find (u1,…,uk) minimizing reconstruction error:x1x2©2005-2009 Carlos Guestrin12Understanding the reconstruction error Note that xican be represented exactly by n-dimensional projection: Rewriting error:Given k<n, find (u1,…,uk) minimizing reconstruction error:©2005-2009 Carlos Guestrin713Reconstruction error and covariance matrix©2005-2009 Carlos Guestrin14Minimizing 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 Guestrin815Basic PCA algoritm Start from m by n data matrix X Recenter: subtract mean from each row of X Xc←←←← X – X Compute covariance matrix: Σ ←←←← 1/m XcTXc Find eigen vectors and values of Σ Principal components: k eigen vectors with highest eigen values©2005-2009 Carlos Guestrin16PCA example©2005-2009 Carlos Guestrin917PCA example – reconstruction only used first principal component©2005-2009 Carlos Guestrin18Eigenfaces [Turk, Pentland ’91] Input images: Principal components:©2005-2009 Carlos Guestrin1019Eigenfaces reconstruction Each image corresponds to adding 8 principal components:©2005-2009 Carlos Guestrin20Scaling 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 Guestrin1121SVD Write X = W S VT X ← data matrix, one row per datapoint W ← weight matrix, one row per datapoint – coordinate of xiin 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©2005-2009 Carlos Guestrin22PCA 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 Guestrin1223What 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 Guestrin24Markov DecisionProcesses (MDPs)Machine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityNovember 30th, 2009©2005-2009 Carlos Guestrin1325Thus far this semester Regression: Classification: Density estimation:©2005-2009 Carlos Guestrin26Learning to act Reinforcement learning An agent Makes sensor observations Must select action Receives rewards positive for “good” states negative for “bad” states[Ng et al. ’05] ©2005-2009 Carlos Guestrin1427Learning to play backgammon [Tesauro ’95] Combines reinforcement learning with neural networks Played 300,000 games against itself Achieved grandmaster
View Full Document