This book provides an introduction to the mathematical and algorithmic foundations of data science, including machine learning, high-dimensional geometry, and analysis of large networks. Topics include the counterintuitive nature of data in high dimensions, important linear algebraic techniques such as singular value decomposition, the theory of random walks and Markov chains, the fundamentals of and important algorithms for machine learning, algorithms and analysis for clustering, probabilistic models for large networks, representation learning including topic modelling and non-negative matrix factorization, wavelets and compressed sensing. Important probabilistic techniques are developed including the law of large numbers, tail inequalities, analysis of random projections, generalization guarantees in machine learning, and moment methods for analysis of phase transitions in large random graphs. Additionally, important structural and complexity measures are discussed such as matrix norms and VC-dimension. This book is suitable for both undergraduate and graduate courses in the design and analysis of algorithms for data.
Author(s): Avrim Blum, John Hopcroft, Ravindran Kannan
Publisher: Cambridge University Press
Year: 2020
Language: English
Pages: 433
Tags: Computer Science, Statistics, Quantitative research, Spatial Analysis (Statistics)
Contents......Page 6
1 Introduction page......Page 10
2.2 The Law of Large Numbers......Page 13
2.4 Properties of the Unit Ball......Page 17
2.5 Generating Points Uniformly at Random from a Ball......Page 22
2.6 Gaussians in High Dimension......Page 24
2.7 Random Projection and Johnson-Lindenstrauss Lemma......Page 25
2.8 Separating Gaussians......Page 27
2.9 Fitting a Spherical Gaussian to Data......Page 29
2.10 Bibliographic Notes......Page 30
2.11 Exercises......Page 31
3.1 Introduction......Page 38
3.3 Singular Vectors......Page 40
3.4 Singular Value Decomposition (SVD)......Page 43
3.5 Best Ranк-k Approximations......Page 45
3.6 Left Singular Vectors......Page 46
3.7 Power Method for Singular Value Decomposition......Page 48
3.9 Applications of Singular Value Decomposition......Page 51
3.10 Bibliographic Notes......Page 62
3.11 Exercises......Page 63
4 Random Walks and Markov Chains......Page 71
4.1 Stationary Distribution......Page 74
4.4 Convergence of Random Walks on Undirected Graphs......Page 82
4.5 Electrical Networks and Random Walks......Page 90
4.6 Random Walks on Undirected Graphs with Unit Edge Weights......Page 94
4.7 Random Walks in Euclidean Space......Page 101
4.8 The Web as a Markov Chain......Page 104
4.9 Bibliographic Notes......Page 107
4.10 Exercises......Page 108
5.1 Introduction......Page 118
5.2 The Perception Algorithm......Page 119
5.3 Kernel Functions and Nonlinearly Separable Data......Page 120
5.4 Generalizing to New Data......Page 121
5.5 VC-Dimension......Page 127
5.6 VC-Dimension and Machine Learning......Page 135
5.7 Other Measures of Complexity......Page 136
5.8 Deep Learning......Page 137
5.9 Gradient Descent......Page 143
5.10 Online Learning......Page 147
5.11 Boosting......Page 154
5.12 Further Current Directions......Page 157
5.14 Exercises......Page 161
6.1 Introduction......Page 168
6.2 Frequency Moments of Data Streams......Page 169
6.3 Matrix Algorithms Using Sampling......Page 178
6.4 Sketches of Documents......Page 186
6.5 Bibliographic Notes......Page 187
6.6 Exercises......Page 188
7.1 Introduction......Page 191
7.2 k-Means Clustering......Page 194
7.4 Finding Low-Error Clusterings......Page 198
7.5 Spectral Clustering......Page 199
7.6 Approximation Stability......Page 206
7.7 High-Density Clusters......Page 208
7.8 Kernel Methods......Page 210
7.10 Dense Submatrices and Communities......Page 211
7.11 Community Finding and Graph Partitioning......Page 214
7.12 Spectral Clustering Applied to Social Networks......Page 217
7.14 Exercises......Page 219
8.1 The G(n,p) Model......Page 224
8.2 PhaseTransitions......Page 231
8.3 Giant Component......Page 241
8.4 CyclesandFullConnectivity......Page 244
8.5 PhaseTransitions for Increasing Properties......Page 248
8.6 BranchingProcesses......Page 250
8.7 CNF-SAT......Page 255
8.8 Nonuniform Modelsof Random Graphs......Page 261
8.9 Growth Models......Page 263
8.10 Small-World Graphs......Page 270
8.12 Exercises......Page 275
9.1 TopicModels......Page 283
9.2 AnIdealized Model......Page 286
9.3 Nonnegative Matrix Factorization......Page 288
9.4 NMFwithAnchorTerms......Page 290
9.5 HardandSoftClustering......Page 291
9.6 TheLatent Dirichlet Allocation Modelfor TopicModeling......Page 292
9.7 TheDominant Admixture Model......Page 294
9.8 Formal Assumptions......Page 296
9.9 FindingtheTerm-Topic Matrix......Page 299
9.10 HiddenMarkov Models......Page 304
9.11 Graphical ModelsandBelief Propagation......Page 307
9.12 Bayesian orBelief Networks......Page 308
9.13 Markov RandomFields......Page 309
9.15 TreeAlgorithms......Page 310
9.16 Message PassinginGeneralGraphs......Page 312
9.17 Warning Propagation......Page 319
9.18 Correlation betweenVariables......Page 320
9.20 Exercises......Page 324
10.1 Ranking andSocialChoice......Page 327
10.2 CompressedSensingandSparseVectors......Page 331
10.3 Applications......Page 334
10.4 AnUncertainty Principle......Page 336
10.5 Gradient......Page 339
10.6 LinearProgramming......Page 341
10.8 Semi-Definite Programming......Page 343
10.9 Bibliographic Notes......Page 345
10.10 Exercises......Page 346
11.1 Dilation......Page 350
11.2 TheHaar Wavelet......Page 351
11.3 Wavelet Systems......Page 354
11.4 Solving theDilation Equation......Page 355
11.5 Conditions ontheDilation Equation......Page 356
11.6 Derivation of theWavelets from theScaling Function......Page 359
11.7 Sufficient Conditions for theWaveletsto BeOrthogonal......Page 362
11.8 Expressing aFunction inTermsof Wavelets......Page 364
11.9 Designing aWavelet System......Page 365
11.12 Exercises......Page 366
12.1 Definitions andNotation......Page 369
12.2 Useful Relations......Page 370
12.3 Useful Inequalities......Page 374
12.4 Probability......Page 381
12.5 BoundsonTailProbability......Page 389
12.6 Applications of the TailBound......Page 395
12.7 Eigenvalues andEigenvectors......Page 396
12.8 Generating Functions......Page 409
12.9 Miscellaneous......Page 413
12.10 Exercises......Page 416
References......Page 420
Index......Page 430
