Foundations of Data Science - TTIC

1 Foundations of data Science Avrim Blum, John Hopcroft, and Ravindran KannanThursday 27thFebruary, 2020 This material has been published by Cambridge University Press asFoundations of data SciencebyAvrim Blum, John Hopcroft, and Ravi Kannan. This pre-publication version is free to view and downloadfor personal use only. Not for re-distribution, re-sale or use in derivative works. Please do not re-postor mirror, instead link Avrim Blum, John Hopcroft, and RaviKannan Introduction92 High-Dimensional Introduction .. The Law of Large Numbers.

2 The Geometry of High Dimensions .. Properties of the Unit Ball .. of the Unit Ball .. Near the Equator .. Generating Points Uniformly at Random from a Ball .. Gaussians in High Dimension .. Random Projection and Johnson-Lindenstrauss Lemma .. Separating Gaussians .. Fitting a Spherical Gaussian to data .. Bibliographic Notes .. Exercises .. 323 Best-Fit Subspaces and Singular Value Decomposition (SVD) Introduction .. Preliminaries .. Singular Vectors.

3 Singular Value Decomposition (SVD) .. Best Rank-kApproximations .. Left Singular Vectors .. Power Method for Singular Value Decomposition .. Faster Method .. Singular Vectors and Eigenvectors .. Applications of Singular Value Decomposition .. data .. Component Analysis .. a Mixture of Spherical Gaussians .. Documents and Web Pages .. Illustrative Application of SVD .. Application of SVD to a Discrete Optimization Problem .. Bibliographic Notes.

4 Exercises .. 684 Random Walks and Markov Stationary Distribution .. Markov Chain Monte Carlo .. Algorithm .. Sampling .. Areas and Volumes .. Convergence of Random Walks on Undirected Graphs .. Normalized Conductance to Prove Convergence .. Electrical Networks and Random Walks .. Random Walks on Undirected Graphs with Unit Edge Weights .. Random Walks in Euclidean Space .. The Web as a Markov Chain .. Bibliographic Notes .. Exercises .. 1195 Machine Introduction.

5 The Perceptron Algorithm .. Kernel Functions and Non-linearly Separable data .. Generalizing to New data .. and Uniform Convergence .. s Razor .. : Penalizing Complexity .. VC-Dimension .. and Key Theorems .. of Some Set Systems .. Function for Set Systems of Bounded VC-Dimension.. of Combinations of Concepts .. Key Theorem .. VC-dimension and Machine Learning .. Other Measures of Complexity .. Deep Learning .. Adversarial Networks (GANs) .. Gradient Descent.

6 Gradient Descent .. Online Learning .. An Example: Learning Disjunctions .. The Halving Algorithm .. The Perceptron Algorithm .. Inseparable data and Hinge Loss .. Online to Batch Conversion .. Combining (Sleeping) Expert Advice .. Boosting .. Further Current Directions .. Semi-Supervised Learning .. Active Learning .. Multi-Task Learning .. Bibliographic Notes .. Exercises .. 1796 Algorithms for Massive data : Streaming, Sketching, and Introduction.

7 Frequency Moments of data Streams .. of Distinct Elements in a data Stream .. of Occurrences of a Given Element.. Elements .. Second Moment .. Matrix Algorithms using Sampling .. Multiplication using Sampling .. Length Squared Sampling in Two Passes .. of a Large Matrix .. Sketches of Documents .. Bibliographic Notes .. Exercises .. 2097 Introduction .. General Assumptions on the Form of Clusters .. Clustering .. Clustering .. Maximum-Likelihood Motivation.

8 Properties of thek-Means Objective .. s Algorithm .. s Algorithm .. Clustering on the Line .. Clustering .. Finding Low-Error Clusterings .. Spectral Clustering .. Project? .. Algorithm .. Separated by (1) Standard Deviations .. spectral clustering .. Approximation Stability .. Conceptual Idea .. this Formal .. and Analysis .. High-Density Clusters .. Linkage .. Linkage .. Kernel Methods .. Recursive Clustering Based on Sparse Cuts .. Dense Submatrices and Communities.

9 Community Finding and Graph Partitioning .. Spectral Clustering Applied to Social Networks .. Bibliographic Notes .. Exercises .. 2458 Random TheG(n,p) Model .. Distribution .. of Triangles inG(n,d/n) .. Phase Transitions .. Giant Component .. of a Giant Component .. Other Large Components .. Case ofp <1/n.. Cycles and Full Connectivity .. of Cycles .. Connectivity .. forO(lnn) Diameter .. Phase Transitions for Increasing Properties .. Branching Processes.

10 CNF-SAT .. in practice .. Transitions for CNF-SAT .. Non-uniform Models of Random Graphs .. Component in Graphs with Given Degree Distribution .. Growth Models .. Model Without Preferential Attachment .. Model With Preferential Attachment .. Small World Graphs .. Bibliographic Notes .. Exercises .. 3089 Topic Models, Non-negative Matrix Factorization, Hidden Markov Mod-els, and Graphical Topic Models .. An Idealized Model .. Non-negative Matrix Factorization - NMF.