Mathematical Foundation for Data Analysis

Description

Preface Acknowledgements Contents 1 Probability Review 1.1 Sample Spaces 1.2 Conditional Probability and Independence 1.3 Density Functions 1.4 Expected Value 1.5 Variance 1.6 Joint, Marginal, and Conditional Distributions 1.7 Bayes' Rule 1.7.1 Model Given Data 1.8 Bayesian Inference Exercises 2 Convergence and Sampling 2.1 Sampling and Estimation 2.2 Probably Approximately Correct (PAC) 2.3 Concentration of Measure 2.3.1 Markov Inequality 2.3.2 Chebyshev Inequality 2.3.3 Chernoff-Hoeffding Inequality 2.3.4 Union Bound and Examples 2.4 Importance Sampling 2.4.1 Sampling Without Replacement with Priority Sampling Exercises 3 Linear Algebra Review 3.1 Vectors and Matrices 3.2 Addition and Multiplication 3.3 Norms 3.4 Linear Independence 3.5 Rank 3.6 Square Matrices and Properties 3.7 Orthogonality Exercises 4 Distances and Nearest Neighbors 4.1 Metrics 4.2 Lp Distances and their Relatives 4.2.1 Lp Distances 4.2.2 Mahalanobis Distance 4.2.3 Cosine and Angular Distance 4.2.4 KL Divergence 4.3 Distances for Sets and Strings 4.3.1 Jaccard Distance 4.3.2 Edit Distance 4.4 Modeling Text with Distances 4.4.1 Bag-of-Words Vectors 4.4.2 k-Grams 4.5 Similarities 4.5.1 Set Similarities 4.5.2 Normed Similarities 4.5.3 Normed Similarities between Sets 4.6 Locality Sensitive Hashing 4.6.1 Properties of Locality Sensitive Hashing 4.6.2 Prototypical Tasks for LSH 4.6.3 Banding to Amplify LSH 4.6.4 LSH for Angular Distance 4.6.5 LSH for Euclidean Distance 4.6.6 Min Hashing as LSH for Jaccard Distance Exercises 5 Linear Regression 5.1 Simple Linear Regression 5.2 Linear Regression with Multiple Explanatory Variables 5.3 Polynomial Regression 5.4 Cross-Validation 5.4.1 Other ways to Evaluate Linear Regression Models 5.5 Regularized Regression 5.5.1 Tikhonov Regularization for Ridge Regression 5.5.2 Lasso 5.5.3 Dual Constrained Formulation 5.5.4 Matching Pursuit Exercises 6 Gradient Descent 6.1 Functions 6.2 Gradients 6.3 Gradient Descent 6.3.1 Learning Rate 6.4 Fitting a Model to Data 6.4.1 Least Mean Squares Updates for Regression 6.4.2 Decomposable Functions Exercises 7 Dimensionality Reduction 7.1 Data Matrices 7.1.1 Projections 7.1.2 Sum of Squared Errors Goal 7.2 Singular Value Decomposition 7.2.1 Best Rank-k Approximation of a Matrix 7.3 Eigenvalues and Eigenvectors 7.4 The Power Method 7.5 Principal Component Analysis 7.6 Multidimensional Scaling 7.6.1 Why does Classical MDS work? 7.7 Linear Discriminant Analysis 7.8 Distance Metric Learning 7.9 Matrix Completion 7.10 Random Projections Exercises 8 Clustering 8.1 Voronoi Diagrams 8.1.1 Delaunay Triangulation 8.1.2 Connection to Assignment-Based Clustering 8.2 Gonzalez's Algorithm for k-Center Clustering 8.3 Lloyd's Algorithm for k-Means Clustering 8.3.1 Lloyd's Algorithm 8.3.2 k-Means++ 8.3.3 k-Mediod Clustering 8.3.4 Soft Clustering 8.4 Mixture of Gaussians 8.4.1 Expectation-Maximization 8.5 Hierarchical Clustering 8.6 Density-Based Clustering and Outliers 8.6.1 Outliers 8.7 Mean Shift Clustering Exercises 9 Classification 9.1 Linear Classifiers 9.1.1 Loss Functions 9.1.2 Cross-Validation and Regularization 9.2 Perceptron Algorithm 9.3 Support Vector Machines and Kernels 9.3.1 The Dual: Mistake Counter 9.3.2 Feature Expansion 9.3.3 Support Vector Machines 9.4 Learnability and VC dimension 9.5 kNN Classifiers 9.6 Decision Trees 9.7 Neural Networks 9.7.1 Training with Back-propagation 10 Graph Structured Data 10.1 Markov Chains 10.1.1 Ergodic Markov Chains 10.1.2 Metropolis Algorithm 10.2 PageRank 10.3 Spectral Clustering on Graphs 10.3.1 Laplacians and their EigenStructures 10.4 Communities in Graphs 10.4.1 Preferential Attachment 10.4.2 Betweenness 10.4.3 Modularity Exercises 11 Big Data and Sketching 11.1 The Streaming Model 11.1.1 Mean and Variance 11.1.2 Reservoir Sampling 11.2 Frequent Items 11.2.1 Warm-Up: Majority 11.2.2 Misra-Gries Algorithm 11.2.3 Count-Min Sketch 11.2.4 Count Sketch 11.3 Matrix Sketching 11.3.1 Covariance Matrix Summation 11.3.2 Frequent Directions 11.3.3 Row Sampling 11.3.4 Random Projections and Count Sketch Hashing Exercises Index