没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
484页
主要讲解未来40年都会有用的数据科学,如数据分析、机器学习、深度学习、数据挖掘等相关方面,最重要的基础理论。涉及高维空间、最佳拟合子空间和奇异值分解( SVD )、随机游走和马尔可夫链、机器学习、海量数据问题相关的算法:Streaming,Sketching,Sampling、聚类、Random Graph、主题模型、非负矩阵分解、隐马尔可夫模型和图形模型等12个主题。
资源推荐
资源详情
资源评论
Foundations of Data Science
∗
Avrim Blum, John Hopcroft, and Ravindran Kannan
Saturday 2
nd
March, 2019
∗
Copyright 2015. All rights reserved
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 . . . . . . . . . . . . . . . . . . . . . . . . . 23
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-k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 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 Overfitting 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 Definitions 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 . . . . . . . . . . . . . . . . . . . . . 149
5.7 Other Measures of Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 150
5.8 Deep Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.8.1 Generative Adversarial Networks (GANs) . . . . . . . . . . . . . . . 157
5.9 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
5.9.1 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . 160
5.9.2 Regularizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
5.10 Online Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
5.10.1 An Example: Learning Disjunctions . . . . . . . . . . . . . . . . . . 163
5.10.2 The Halving Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.10.3 The Perceptron Algorithm . . . . . . . . . . . . . . . . . . . . . . . 164
5.10.4 Inseparable Data and Hinge Loss . . . . . . . . . . . . . . . . . . . 165
5.10.5 Online to Batch Conversion . . . . . . . . . . . . . . . . . . . . . . 166
5.10.6 Combining (Sleeping) Expert Advice . . . . . . . . . . . . . . . . . 167
5.11 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.12 Further Current Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.12.1 Semi-Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . 173
5.12.2 Active Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.12.3 Multi-Task Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 176
3
5.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6 Algorithms for Massive Data Problems: Streaming, Sketching, and
Sampling 184
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
6.2 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 185
6.2.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 186
6.2.2 Number of Occurrences of a Given Element. . . . . . . . . . . . . . 189
6.2.3 Frequent Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
6.2.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 192
6.3 Matrix Algorithms using Sampling . . . . . . . . . . . . . . . . . . . . . . 195
6.3.1 Matrix Multiplication using Sampling . . . . . . . . . . . . . . . . . 196
6.3.2 Implementing Length Squared Sampling in Two Passes . . . . . . . 199
6.3.3 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . 200
6.4 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
6.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7 Clustering 211
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.1.2 Two General Assumptions on the Form of Clusters . . . . . . . . . 212
7.1.3 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.2 k-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.2.1 A Maximum-Likelihood Motivation . . . . . . . . . . . . . . . . . . 214
7.2.2 Structural Properties of the k-Means Objective . . . . . . . . . . . 215
7.2.3 Lloyd’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.2.4 Ward’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
7.2.5 k-Means Clustering on the Line . . . . . . . . . . . . . . . . . . . . 218
7.3 k-Center Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
7.4 Finding Low-Error Clusterings . . . . . . . . . . . . . . . . . . . . . . . . . 219
7.5 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
7.5.1 Why Project? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
7.5.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
7.5.3 Means Separated by Ω(1) Standard Deviations . . . . . . . . . . . . 222
7.5.4 Laplacians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.5.5 Local spectral clustering . . . . . . . . . . . . . . . . . . . . . . . . 224
7.6 Approximation Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.6.1 The Conceptual Idea . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.6.2 Making this Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.6.3 Algorithm and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 228
7.7 High-Density Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
4
7.7.1 Single Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
7.7.2 Robust Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.8 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.9 Recursive Clustering Based on Sparse Cuts . . . . . . . . . . . . . . . . . . 232
7.10 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . . 233
7.11 Community Finding and Graph Partitioning . . . . . . . . . . . . . . . . . 236
7.12 Spectral Clustering Applied to Social Networks . . . . . . . . . . . . . . . 239
7.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8 Random Graphs 248
8.1 The G(n, p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
8.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
8.1.2 Existence of Triangles in G(n, d/n) . . . . . . . . . . . . . . . . . . 253
8.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
8.3 Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
8.3.1 Existence of a Giant Component . . . . . . . . . . . . . . . . . . . 267
8.3.2 No Other Large Components . . . . . . . . . . . . . . . . . . . . . 269
8.3.3 The Case of p < 1/n . . . . . . . . . . . . . . . . . . . . . . . . . . 269
8.4 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.4.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.4.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
8.4.3 Threshold for O(ln n) Diameter . . . . . . . . . . . . . . . . . . . . 273
8.5 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . . 275
8.6 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
8.7 CNF-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
8.7.1 SAT-solvers in practice . . . . . . . . . . . . . . . . . . . . . . . . . 283
8.7.2 Phase Transitions for CNF-SAT . . . . . . . . . . . . . . . . . . . . 284
8.8 Non-uniform Models of Random Graphs . . . . . . . . . . . . . . . . . . . 289
8.8.1 Giant Component in Graphs with Given Degree Distribution . . . . 290
8.9 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
8.9.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 292
8.9.2 Growth Model With Preferential Attachment . . . . . . . . . . . . 298
8.10 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
8.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
8.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
9 Topic Models, Non-negative Matrix Factorization, Hidden Markov Mod-
els, and Graphical Models 315
9.1 Topic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
9.2 An Idealized Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
9.3 Non-negative Matrix Factorization - NMF . . . . . . . . . . . . . . . . . . 320
9.4 NMF with Anchor Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
5
剩余483页未读,继续阅读
资源评论
wzbyytm
- 粉丝: 0
- 资源: 35
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功