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 .. 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.

2 Separating Gaussians .. Fitting a Spherical Gaussian to data .. Bibliographic Notes .. Exercises .. 323 Best-Fit Subspaces and Singular Value Decomposition (SVD) Introduction .. Preliminaries .. Singular Vectors .. 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 .. Exercises .. 684 Random Walks and Markov Stationary Distribution.

3 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 .. 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.

4 Key Theorem .. VC-dimension and Machine Learning .. Other Measures of Complexity .. Deep Learning .. Adversarial Networks (GANs) .. Gradient Descent .. 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 .. Frequency Moments of data Streams .. of Distinct Elements in a data Stream .. of Occurrences of a Given Element.

5 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 .. 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.

6 Linkage .. Linkage .. Kernel Methods .. Recursive Clustering Based on Sparse Cuts .. Dense Submatrices and Communities .. 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 .. CNF-SAT .. in practice .. Transitions for CNF-SAT .. Non-uniform Models of Random Graphs .. Component in Graphs with Given Degree Distribution.

7 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 .. NMF with Anchor Terms .. Hard and Soft Clustering .. The Latent Dirichlet Allocation Model for Topic Modeling .. The Dominant Admixture Model .. Formal Assumptions .. Finding the Term-Topic Matrix .. Hidden Markov Models .. Graphical Models and Belief Propagation .. Bayesian or Belief Networks .. Markov Random Fields .. Factor Graphs .. Tree Algorithms .. Message Passing in General Graphs.

8 Graphs with a Single Cycle .. Belief Update in Networks with a Single Loop .. Maximum Weight Matching .. Warning Propagation .. Correlation Between Variables .. Bibliographic Notes .. Exercises .. 36410 Other Ranking and Social Choice .. Randomization .. Examples .. Compressed Sensing and Sparse Vectors .. Unique Reconstruction of a Sparse Vector .. Efficiently Finding the Unique Sparse Solution .. Applications .. Biological .. Low Rank Matrices .. An Uncertainty Principle .. Sparse Vector in Some Coordinate Basis .. A Representation Cannot be Sparse in Both Time and FrequencyDomains .. Gradient .. Linear Programming .. The Ellipsoid Algorithm .. Integer Optimization .. Semi-Definite Programming.

9 Bibliographic Notes .. 388611 Dilation .. The Haar Wavelet .. Wavelet Systems .. Solving the Dilation Equation .. Conditions on the Dilation Equation .. Derivation of the Wavelets from the Scaling Function .. Sufficient Conditions for the Wavelets to be Orthogonal .. Expressing a Function in Terms of Wavelets .. Designing a Wavelet System .. Bibliographic Notes .. Exercises .. 41112 Definitions and Notation .. Integers .. Substructures .. Asymptotic Notation .. Useful Relations .. Useful Inequalities .. Probability .. Sample Space, Events, and Independence .. Linearity of Expectation .. Union Bound .. Indicator Variables .. Variance .. Variance of the Sum of Independent Random Variables .. Median.

10 The Central Limit Theorem .. Probability Distributions .. Bayes Rule and Estimators .. Bounds on Tail Probability .. Chernoff Bounds .. More General Tail Bounds .. Applications of the Tail Bound .. Eigenvalues and Eigenvectors .. Symmetric Matrices .. Relationship between SVD and Eigen Decomposition .. Extremal Properties of Eigenvalues .. Eigenvalues of the Sum of Two Symmetric Matrices .. Norms .. Important Norms and Their Properties .. Additional Linear Algebra .. Distance Between Subspaces .. Positive Semidefinite Matrix .. Generating Functions.. Generating Functions for Sequences Defined by Recurrence Rela-tionships .. The Exponential Generating Function and the Moment GeneratingFunction .. Miscellaneous.