[PDF] Foundations of Data Science Feb 27 2020 Page 1.

View - Download Foundations of Data Science

Previous PDF

Next PDF

Foundations of Data Science

Avrim Blum, John Hopcroft, and Ravindran Kannan

Thursday 27

thFebruary, 2020 This material has been published by Cambridge University Press asFoundations of Data Scienceby

Avrim Blum, John Hopcroft, and Ravi Kannan. This pre-publication version is free to view and download

for personal use only. Not for re-distribution, re-sale or use in derivative works. Please do not re-post

or mirror, instead link tohttp://ttic.edu/blum/book.pdf.c

Avrim Blum, John Hopcroft, and Ravi

Kannan 2020.https://www.cambridge.org/9781108485067 1

Contents

1 Introduction 9

2 High-Dimensional Space 12

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.3 The Geometry of High Dimensions . . . . . . . . . . . . . . . . . . . . . .

16

2.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.4.1 Volume of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . .

17

2.4.2 Volume Near the Equator . . . . . . . . . . . . . . . . . . . . . . .

19

2.5 Generating Points Uniformly at Random from a Ball . . . . . . . . . . . .

22

2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.7 Random Projection and Johnson-Lindenstrauss Lemma . . . . . . . . . . .

25

2.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.9 Fitting a Spherical Gaussian to Data . . . . . . . . . . . . . . . . . . . . .

29

2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

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

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . .

46

3.5 Best Rank-kApproximations . . . . . . . . . . . . . . . . . . . . . . . . .47

3.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.7 Power Method for Singular Value Decomposition . . . . . . . . . . . . . . .

51

3.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

3.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . .

54

3.9 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . .

54

3.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . .

56

3.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . .

57

3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . .

62

3.9.5 An Illustrative Application of SVD . . . . . . . . . . . . . . . . . .

63

3.9.6 An Application of SVD to a Discrete Optimization Problem . . . .

64

3.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

4 Random Walks and Markov Chains 77

4.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

4.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . .

82

4.2.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . .

84

4.2.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85
2

4.3 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87

4.4 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . .

89

4.4.1 Using Normalized Conductance to Prove Convergence . . . . . . . .

95

4.5 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . .

98

4.6 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . .

103

4.7 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . .

110

4.8 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . .

113

4.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

117

4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

119

5 Machine Learning 131

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

131

5.2 The Perceptron Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .

132

5.3 Kernel Functions and Non-linearly Separable Data . . . . . . . . . . . . . .

134

5.4 Generalizing to New Data . . . . . . . . . . . . . . . . . . . . . . . . . . .

135

5.4.1 Overtting and Uniform Convergence . . . . . . . . . . . . . . . . .

137

5.4.2 Occam's Razor . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

139

5.4.3 Regularization: Penalizing Complexity . . . . . . . . . . . . . . . .

140

5.5 VC-Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

141

5.5.1 Denitions and Key Theorems . . . . . . . . . . . . . . . . . . . . .

142

5.5.2 VC-Dimension of Some Set Systems . . . . . . . . . . . . . . . . .

143

5.5.3 Shatter Function for Set Systems of Bounded VC-Dimension . . .

145

5.5.4 VC-Dimension of Combinations of Concepts . . . . . . . . . . . . .

147

5.5.5 The Key Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . .

148

5.6 VC-dimension and Machine Learning . . . . . . . . . . . . . . . . . . . . .

150

5.7 Other Measures of Complexity . . . . . . . . . . . . . . . . . . . . . . . . .

151

5.8 Deep Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

151

5.8.1 Generative Adversarial Networks (GANs) . . . . . . . . . . . . . . .

157

5.9 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

159

5.9.1 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . .

161

5.9.2 Regularizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

162

5.10 Online Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

162

5.10.1 An Example: Learning Disjunctions . . . . . . . . . . . . . . . . . .

163

5.10.2 The Halving Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .

16 4

5.10.3 The Perceptron Algorithm . . . . . . . . . . . . . . . . . . . . . . .

164

5.10.4 Inseparable Data and Hinge Loss . . . . . . . . . . . . . . . . . . .

166

5.10.5 Online to Batch Conversion . . . . . . . . . . . . . . . . . . . . . .

166

5.10.6 Combining (Sleeping) Expert Advice . . . . . . . . . . . . . . . . .

168

5.11 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

170

5.12 Further Current Directions . . . . . . . . . . . . . . . . . . . . . . . . . . .

174

5.12.1 Semi-Supervised Learning . . . . . . . . . . . . . . . . . . . . . . .

174

5.12.2 Active Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

176

5.12.3 Multi-Task Learning . . . . . . . . . . . . . . . . . . . . . . . . . .

17 7 3

5.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .177

5.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

179

6 Algorithms for Massive Data: Streaming, Sketching, and Sampling 186

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

186

6.2 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . .

187

6.2.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . .

188

6.2.2 Number of Occurrences of a Given Element. . . . . . . . . . . . . .

192

6.2.3 Frequent Elements . . . . . . . . . . . . . . . . . . . . . . . . . . .

192

6.2.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . .

194

6.3 Matrix Algorithms using Sampling . . . . . . . . . . . . . . . . . . . . . .

197

6.3.1 Matrix Multiplication using Sampling . . . . . . . . . . . . . . . . .

198

6.3.2 Implementing Length Squared Sampling in Two Passes . . . . . . .

202

6.3.3 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . .

202

6.4 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

206

6.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

208

6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

209

7 Clustering 213

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

213

7.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

214

7.1.2 Two General Assumptions on the Form of Clusters . . . . . . . . .

214

7.1.3 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . .

216

7.2k-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .216

7.2.1 A Maximum-Likelihood Motivation . . . . . . . . . . . . . . . . . .

216

7.2.2 Structural Properties of thek-Means Objective . . . . . . . . . . .217

7.2.3 Lloyd's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .

218

7.2.4 Ward's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .

220

7.2.5k-Means Clustering on the Line . . . . . . . . . . . . . . . . . . . .220

7.3k-Center Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220

7.4 Finding Low-Error Clusterings . . . . . . . . . . . . . . . . . . . . . . . . .

221

7.5 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

221

7.5.1 Why Project? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

222

7.5.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

223

7.5.3 Means Separated by

(1) Standard Deviations . . . . . . . . . . . . 224

7.5.4 Laplacians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

226

7.5.5 Local spectral clustering . . . . . . . . . . . . . . . . . . . . . . . .

22 7

7.6 Approximation Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . .

229

7.6.1 The Conceptual Idea . . . . . . . . . . . . . . . . . . . . . . . . . .

229

7.6.2 Making this Formal . . . . . . . . . . . . . . . . . . . . . . . . . . .

230

7.6.3 Algorithm and Analysis . . . . . . . . . . . . . . . . . . . . . . . .

230

7.7 High-Density Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

232

7.7.1 Single Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23 2
4

7.7.2 Robust Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233

7.8 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

234

7.9 Recursive Clustering Based on Sparse Cuts . . . . . . . . . . . . . . . . . .

234

7.10 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . .

235

7.11 Community Finding and Graph Partitioning . . . . . . . . . . . . . . . . .

238

7.12 Spectral Clustering Applied to Social Networks . . . . . . . . . . . . . . .

241

7.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

244

7.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

245

8 Random Graphs 250

8.1 TheG(n;p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .250

8.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 1

8.1.2 Existence of Triangles inG(n;d=n) . . . . . . . . . . . . . . . . . .255

8.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

258

8.3 Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

269

8.3.1 Existence of a Giant Component . . . . . . . . . . . . . . . . . . .

269

8.3.2 No Other Large Components . . . . . . . . . . . . . . . . . . . . .

271

8.3.3 The Case ofp <1=n. . . . . . . . . . . . . . . . . . . . . . . . . .272

8.4 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . .

272

8.4.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . .

27 3

8.4.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . .

274

8.4.3 Threshold forO(lnn) Diameter . . . . . . . . . . . . . . . . . . . .276

8.5 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . .

277

8.6 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

279

8.7 CNF-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

285

8.7.1 SAT-solvers in practice . . . . . . . . . . . . . . . . . . . . . . . . .

quotesdbs_dbs11.pdfusesText_17

[PDF] foundations of data science stanford

[PDF] foundations of data science syllabus

[PDF] four crucial stages of language development

[PDF] four day work week proposal

[PDF] four features of graphical user interface

[PDF] four skills of language acquisition

[PDF] four skills of language learning pdf

[PDF] four skills of language learning ppt

[PDF] four skills of language learning slideshare

[PDF] four skills of language pdf

[PDF] four skills of language slideshare

[PDF] four skills of language teaching

[PDF] four stages of language development

[PDF] four stages of language development in mathematics classroom

[PDF] four stages of language development in mathematics classroom in order are