Dimensionality Reduction : Above PCA
1 like227 views
Topics Covered : 1. SVD 2. Non-Linear Dimensionality Reduction and important types 3. ISOMAP 4. SNE 5. t-SNE
More Related Content
Similar to Dimensionality Reduction : Above PCA (20)
Recently uploaded (20)
Dimensionality Reduction : Above PCA
- 2. Singular Value Decomposition first right singular vector Singular Value Decomposition (SVD) is also called Spectral Decomposition Instead of using two coordinates (, ) to describe point locations, lets use only one coordinate Points position is its location along vector How to choose ? Minimize reconstruction error J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org
- 3. Singular Value Decomposition Goal: Minimize the sum of reconstruction errors: ) ) +, +, / 0 ,12 3 +12 where are the old and are the new coordinates SVD gives best axis to project on: best = minimizing the reconstruction errors In other words, minimum reconstruction error J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org
- 4. Singular Value Decomposition A = U 裡 VT - example: V: movie-to-concept matrix U: user-to-concept matrix = x x 1 1 1 0 0 3 3 3 0 0 4 4 4 0 0 5 5 5 0 0 0 2 0 4 4 0 0 0 5 5 0 1 0 2 2 0.13 0.02 -0.01 0.41 0.07 -0.03 0.55 0.09 -0.04 0.68 0.11 -0.05 0.15 -0.59 0.65 0.07 -0.73 -0.67 0.07 -0.29 0.32 12.4 0 0 0 9.5 0 0 0 1.3 0.56 0.59 0.56 0.09 0.09 0.12 -0.02 0.12 -0.69 -0.69 0.40 -0.80 0.40 0.09 0.09 variance (spread) on the v1 axis Movie 1 rating Movie2rating J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org
- 5. Singular Value Decomposition A U Sigma VT = B U Sigma VT = B is best approximation of A How Many Singular Values Should We Retain? A useful rule of thumb is to retain enough singular values to make up 90% of the energy in 裡. Sum of the squares of the retained singular values should be at least 90% of the sum of the squares of all the singular values. Example: the total energy is (12.4)2 + (9.5)2 + (1.3)2 = 245.70, while the retained energy is (12.4)2 + (9.5)2 = 244.01. We have retained over 99% of the energy. However, were we to eliminate the second singular value, 9.5, the retained energy would be only (12.4)2/245.70 or about 63%.J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org
- 6. Relation to Eigen-decomposition SVD gives us: A = U 裡 VT Eigen-decomposition: A = X XT A is symmetric U, V, X are orthonormal (UTU=I), , 裡 are diagonal Now lets calculate: AAT= U裡 VT(U裡 VT)T = U裡 VT(V裡TUT) = U裡裡T UT ATA = V 裡T UT (U裡 VT) = V 裡裡T VT X 2 XT X 2 XT Shows how to compute SVD using eigenvalue decomposition! J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org
- 8. Brainstorming What is dimensionality of data ? What is degree of freedoms of data ? Is the data always exist in high-dimensional space ? What is the rank of a matrix ? What motivates us for non-linear dimensionality reduction ? Can the deep learnings popular MNIST dataset problem, solvable by simple machine learning model ?
- 9. Why do we need dimensionality reduction? You need to visualize it to some non-technical board members which are probably not familiar with : terms like cosine similarity etc. Based on the constraint, such as preserve 80% of the data. You need to reduce the data you have and any new data as it comes, which method would you choose?
- 10. Non-Linear Dimensionality Reduction Given a low dimensional surface embedded non-linearly in high dimensional space. Such a surfaceiscalledManifold. Agood wayto representdatapointsisbytheir low-dimensionalcoordinates. The low-dimensional representation of the data should capture information about high- dimensionalpairwisedistances. Non-lineardimensionalityreductionisalsocalledManifoldlearning. Idea :- Torecoverthe lowdimensionalsurface
- 12. NLDR over PCA NLDR PCA https://en.wikipedia.org/wiki/Nonlinear_dimensionality_reduction
- 13. Isomap Isomapusesthesame core ideasastheMDS algorithm: Obtainamatrixofproximities(distancesbetweenpointsinadataset). Thisdistancematrixisamatrixofinnerproducts. AnEigendecompositionofthismatrixgivesusthelowerdimensionembedding.
- 14. Stochastic Neighbor Embedding (SNE) ,|+ = ;(<=;<>) /?= @ @ ;(<=;<B) /?= @ @ CD+ ,|+ = F=;F> @ F=;F> @ CD+ = 1 2 情(| = ) log F=,F> 情(||) High dimensional space Minimization function Low dimensional space (2-D) 1.Large 倹| is modeled as Low | High Cost 2.Small 倹| is modeled as High | Low Cost 1.SNE is not Symmetric whereas t-SNE is Symmetric. 2.Symmetricity makes t-SNE fast.
- 15. T-Stochastic Neighbor Embedding (t-SNE) ,+ = (1 + ( + , / );2 (1 + ( + , / );2 CD+ ,+ = ;(<=;<>) /?@ @ ;(<=;<B) /?@ @ CD+ 1. t-distribution has longer tails, embeds more points in higher dimension to low dimension. 2. There are some heuristics underlying t- SNE. 3. Develops an intuition for whats going on in the high dimensional data 4. Find structure where other dimensionality-reduction algorithms cannot High dimensional space Low dimensional space (2-D)