Foundations of Data Science (2018) [pdf]
📰 Hacker News · dilawar
Learn the foundations of data science, including high-dimensional space, singular value decomposition, and random walks, to improve your skills in data analysis and machine learning
Action Steps
- Read Chapter 2 to understand high-dimensional space and its properties
- Apply Singular Value Decomposition (SVD) to real-world data using Python or R
- Implement random walks and Markov chains to model complex systems
- Use the concepts learned to analyze and visualize data
- Practice solving exercises in the book to reinforce understanding
Who Needs to Know This
Data scientists, machine learning engineers, and analysts can benefit from this resource to improve their understanding of data science fundamentals and apply them to real-world problems
Key Insight
💡 Understanding high-dimensional space, SVD, and random walks is crucial for data science and machine learning applications
Share This
📚 Learn data science fundamentals with 'Foundations of Data Science'! 📊
Key Takeaways
Learn the foundations of data science, including high-dimensional space, singular value decomposition, and random walks, to improve your skills in data analysis and machine learning
Full Article
Title: book.pdf
URL Source: https://www.cs.cornell.edu/jeh/book.pdf?file=book.pdf
Published Time: Thu, 04 Jan 2018 06:40:01 GMT
Number of Pages: 479
Markdown Content:
# Foundations of Data Science ∗
# Avrim Blum, John Hopcroft, and Ravindran Kannan Thursday 4 th January, 2018
> ∗Copyright 2015. All rights reserved
1Contents
1 Introduction 92 High-Dimensional Space 12
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 The Geometry of High Dimensions . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 Volume of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.2 Volume Near the Equator . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Generating Points Uniformly at Random from a Ball . . . . . . . . . . . . 22 2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.7 Random Projection and Johnson-Lindenstrauss Lemma . . . . . . . . . . . 25 2.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.9 Fitting a Spherical Gaussian to Data . . . . . . . . . . . . . . . . . . . . . 29 2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Best-Fit Subspaces and Singular Value Decomposition (SVD) 40
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 45 3.5 Best Rank-k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.7 Power Method for Singular Value Decomposition . . . . . . . . . . . . . . . 51 3.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 54 3.9 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 54 3.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 56 3.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 56 3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . . 62 3.9.5 An Application of SVD to a Discrete Optimization Problem . . . . 63 3.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Random Walks and Markov Chains 76
4.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 83 4.2.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 24.4 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 88 4.4.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 94 4.5 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 97 4.6 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 102 4.7 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 109 4.8 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4.9 Bibliographic Notes . . . . . . . . . . . . . . . . . .
URL Source: https://www.cs.cornell.edu/jeh/book.pdf?file=book.pdf
Published Time: Thu, 04 Jan 2018 06:40:01 GMT
Number of Pages: 479
Markdown Content:
# Foundations of Data Science ∗
# Avrim Blum, John Hopcroft, and Ravindran Kannan Thursday 4 th January, 2018
> ∗Copyright 2015. All rights reserved
1Contents
1 Introduction 92 High-Dimensional Space 12
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 The Geometry of High Dimensions . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 Volume of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.2 Volume Near the Equator . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Generating Points Uniformly at Random from a Ball . . . . . . . . . . . . 22 2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.7 Random Projection and Johnson-Lindenstrauss Lemma . . . . . . . . . . . 25 2.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.9 Fitting a Spherical Gaussian to Data . . . . . . . . . . . . . . . . . . . . . 29 2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Best-Fit Subspaces and Singular Value Decomposition (SVD) 40
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 45 3.5 Best Rank-k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.7 Power Method for Singular Value Decomposition . . . . . . . . . . . . . . . 51 3.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 54 3.9 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 54 3.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 56 3.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 56 3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . . 62 3.9.5 An Application of SVD to a Discrete Optimization Problem . . . . 63 3.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Random Walks and Markov Chains 76
4.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 83 4.2.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 24.4 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 88 4.4.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 94 4.5 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 97 4.6 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 102 4.7 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 109 4.8 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4.9 Bibliographic Notes . . . . . . . . . . . . . . . . . .
DeepCamp AI