Subscribe to DSC Newsletter

I shared with you four interesting books, also available for free, last week, including one on deep learning. Here's a new one, for those who really love mathematics. It shows what Microsoft thinks data science (at least its foundations) is about, even though I have a very different if not opposite opinion on this subject. My upcoming data science 2.0. book will also be free and deal with foundations; you'll be able to compare the two approaches (theoretical and classic by Microsoft, versus practical and modern by Data Science Central).

Extract from the Book

Contents
1 Introduction 7
2 High-Dimensional Space 10

  • 2.1 Properties of High-Dimensional Space . . . . . . . . . . . . . . . . . . . . . 12
  • 2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 13
  • 2.3 The High-Dimensional Sphere . . . . . . . . . . . . . . . . . . . . . . . . . 15
  • 2.3.1 The Sphere and the Cube in High Dimensions . . . . . . . . . . . . 16
  • 2.3.2 Volume and Surface Area of the Unit Sphere . . . . . . . . . . . . . 17
  • 2.3.3 The Volume is Near the Equator . . . . . . . . . . . . . . . . . . . 20
  • 2.3.4 The Volume is in a Narrow Annulus . . . . . . . . . . . . . . . . . . 23
  • 2.3.5 The Surface Area is Near the Equator . . . . . . . . . . . . . . . . 24
  • 2.4 Volumes of Other Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
  • 2.5 Generating Points Uniformly at Random on the Surface of a Sphere . . . . 27
  • 2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 27
  • 2.7 Bounds on Tail Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
  • 2.8 Applications of the tail bound . . . . . . . . . . . . . . . . . . . . . . . . . 35
  • 2.9 Random Projection and Johnson-Lindenstrauss Theorem . . . . . . . . . . 38
  • 2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
  • 2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3 Best-Fit Subspaces and Singular Value Decomposition (SVD) 52

  • 3.1 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
  • 3.2 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 56
  • 3.3 Best Rank k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 58
  • 3.4 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
  • 3.5 Power Method for Computing the Singular Value Decomposition . . . . . . 62
  • 3.6 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 64
  • 3.6.1 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 64
  • 3.6.2 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 65
  • 3.6.3 Spectral Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 71
  • 3.6.4 Singular Vectors and Ranking Documents . . . . . . . . . . . . . . 71
  • 3.6.5 An Application of SVD to a Discrete Optimization Problem . . . . 72
  • 3.7 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 75
  • 3.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
  • 3.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4 Random Graphs 85

  • 4.1 The G(n; p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
  • 4.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
  • 4.1.2 Existence of Triangles in G(n; d=n) . . . . . . . . . . . . . . . . . . 91
  • 4.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
  • 4.3 The Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
  • 4.4 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
  • 4.5 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 115
  • 4.5.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 115
  • 4.5.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
  • 4.5.3 Threshold for O(ln n) Diameter . . . . . . . . . . . . . . . . . . . . 118
  • 4.6 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . . 119
  • 4.7 Phase Transitions for CNF-sat . . . . . . . . . . . . . . . . . . . . . . . . . 121
  • 4.8 Nonuniform and Growth Models of Random Graphs . . . . . . . . . . . . . 126
  • 4.8.1 Nonuniform Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
  • 4.8.2 Giant Component in Random Graphs with Given Degree Distribution127
  • 4.9 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
  • 4.9.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 128
  • 4.9.2 Growth Model With Preferential Attachment . . . . . . . . . . . . 135
  • 4.10 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
  • 4.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
  • 4.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

5 Random Walks and Markov Chains 153

  • 5.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
  • 5.2 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 158
  • 5.3 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 162
  • 5.4 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 169
  • 5.5 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 173
  • 5.6 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 177
  • 5.6.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 178
  • 5.6.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
  • 5.7 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
  • 5.8 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 183
  • 5.8.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 188
  • 5.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
  • 5.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

6 Learning and VC-dimension 202

  • 6.1 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
  • 6.2 Linear Separators, the Perceptron Algorithm, and Margins . . . . . . . . . 204
  • 6.3 Nonlinear Separators, Support Vector Machines, and Kernels . . . . . . . . 209
  • 6.4 Strong and Weak Learning - Boosting . . . . . . . . . . . . . . . . . . . . . 214
  • 6.5 Number of Examples Needed for Prediction: VC-Dimension . . . . . . . . 216
  • 6.6 Vapnik-Chervonenkis or VC-Dimension . . . . . . . . . . . . . . . . . . . . 219
  • 6.6.1 Examples of Set Systems and Their VC-Dimension . . . . . . . . . 220
  • 6.6.2 The Shatter Function . . . . . . . . . . . . . . . . . . . . . . . . . 223
  • 6.6.3 Shatter Function for Set Systems of Bounded VC-Dimension . . . 224
  • 6.6.4 Intersection Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 226
  • 6.7 The VC Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
  • 6.8 Simple Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
  • 6.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
  • 6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

7 Algorithms for Massive Data Problems 238

  • 7.1 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 238
  • 7.1.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 239
  • 7.1.2 Counting the Number of Occurrences of a Given Element. . . . . . 243
  • 7.1.3 Counting Frequent Elements . . . . . . . . . . . . . . . . . . . . . . 243
  • 7.1.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 245
  • 7.2 Matrix Algorithms Using Sampling . . . . . . . . . . . . . . . . . . . . . . 248
  • 7.2.1 Matrix Multiplication Using Sampling . . . . . . . . . . . . . . . . 248
  • 7.2.2 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . 250
  • 7.3 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
  • 7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

8 Clustering 260

  • 8.1 Some Clustering Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
  • 8.2 A k-means Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . . . 263
  • 8.3 A Greedy Algorithm for k-Center Criterion Clustering . . . . . . . . . . . 265
  • 8.4 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
  • 8.5 Recursive Clustering Based on Sparse Cuts . . . . . . . . . . . . . . . . . . 273
  • 8.6 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
  • 8.7 Agglomerative Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
  • 8.8 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . . 278
  • 8.9 Flow Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
  • 8.10 Finding a Local Cluster Without Examining the Whole Graph . . . . . . . 284
  • 8.11 Axioms for Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
  • 8.11.1 An Impossibility Result . . . . . . . . . . . . . . . . . . . . . . . . 289
  • 8.11.2 A Satisable Set of Axioms . . . . . . . . . . . . . . . . . . . . . . 295
  • 8.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

9 Topic Models, Hidden Markov Process, Graphical Models, and Belief
Propagation 301

  • 9.1 Topic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
  • 9.2 Hidden Markov Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
  • 9.3 Graphical Models, and Belief Propagation . . . . . . . . . . . . . . . . . . 310
  • 9.4 Bayesian or Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 311
  • 9.5 Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
  • 9.6 Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
  • 9.7 Tree Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
  • 9.8 Message Passing in general Graphs . . . . . . . . . . . . . . . . . . . . . . 315
  • 9.9 Graphs with a Single Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 317
  • 9.10 Belief Update in Networks with a Single Loop . . . . . . . . . . . . . . . . 319
  • 9.11 Maximum Weight Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 320
  • 9.12 Warning Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
  • 9.13 Correlation Between Variables . . . . . . . . . . . . . . . . . . . . . . . . . 325
  • 9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

10 Other Topics 332

  • 10.1 Rankings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
  • 10.2 Hare System for Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
  • 10.3 Compressed Sensing and Sparse Vectors . . . . . . . . . . . . . . . . . . . 335
  • 10.3.1 Unique Reconstruction of a Sparse Vector . . . . . . . . . . . . . . 336
  • 10.3.2 The Exact Reconstruction Property . . . . . . . . . . . . . . . . . . 339
  • 10.3.3 Restricted Isometry Property . . . . . . . . . . . . . . . . . . . . . 340
  • 10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
  • 10.4.1 Sparse Vector in Some Coordinate Basis . . . . . . . . . . . . . . . 342
  • 10.4.2 A Representation Cannot be Sparse in Both Time and Frequency
  • Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
  • 10.4.3 Biological . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
  • 10.4.4 Finding Overlapping Cliques or Communities . . . . . . . . . . . . 345
  • 10.4.5 Low Rank Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
  • 10.5 Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
  • 10.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
  • 10.6.1 The Ellipsoid Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 350
  • 10.7 Integer Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
  • 10.8 Semi-Denite Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 352
  • 10.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

11 Appendix 357

  • 11.1 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
  • 11.2 Useful relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
  • 11.3 Useful Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
  • 11.4 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
  • 11.4.1 Sample Space, Events, Independence . . . . . . . . . . . . . . . . . 370
  • 11.4.2 Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . 371
  • 11.4.3 Union Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
  • 11.4.4 Indicator Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
  • 11.4.5 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
  • 11.4.6 Variance of the Sum of Independent Random Variables . . . . . . . 372
  • 11.4.7 Median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
  • 11.4.8 The Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . . 373
  • 11.4.9 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . 373
  • 11.4.10Bayes Rule and Estimators . . . . . . . . . . . . . . . . . . . . . . . 376
  • 11.4.11Tail Bounds and Cherno inequalities . . . . . . . . . . . . . . . . . 378
  • 11.5 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 382
  • 11.5.1 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . 382
  • 11.5.2 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 384
  • 11.5.3 Relationship between SVD and Eigen Decomposition . . . . . . . . 386
  • 11.5.4 Extremal Properties of Eigenvalues . . . . . . . . . . . . . . . . . . 386
  • 11.5.5 Eigenvalues of the Sum of Two Symmetric Matrices . . . . . . . . . 388
  • 11.5.6 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
  • 11.5.7 Important Norms and Their Properties . . . . . . . . . . . . . . . . 391
  • 11.5.8 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
  • 11.5.9 Distance between subspaces . . . . . . . . . . . . . . . . . . . . . . 395
  • 11.6 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
  • 11.6.1 Generating Functions for Sequences Dened by Recurrence Relationships
  • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
  • 11.6.2 The Exponential Generating Function and the Moment Generating
  • Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
  • 11.7 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
  • 11.7.1 Lagrange multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . 401
  • 11.7.2 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
  • 11.7.3 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
  • 11.7.4 Application of Mean Value Theorem . . . . . . . . . . . . . . . . . 402
  • 11.7.5 Sperner's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
  • 11.7.6 Prufer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
  • 11.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

Index

You can download the book here.

DSC Resources

Additional Reading

Follow us on Twitter: @DataScienceCtrl | @AnalyticBridge

Views: 10168

On Data Science Central

© 2020   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service