没有合适的资源?快使用搜索试试~ 我知道了~
首页Foundations of Data Science
资源详情
资源评论
资源推荐
Foundations of Data Science
1
John Hopcroft
Ravindran Kannan
Version 30/12/2013
These notes are a first draft of a book being written by Hopcroft and Kannan and
in many places are incomplete. However, the notes are in good enough shape to prepare
lectures for a modern theoretical course in computer science. Please do not put solutions
to exercises online as it is important for students to work out solutions for themselves
rather than copy them from the internet.
Thanks
JEH
1
Copyright 2011. All rights reserved
1
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Generating Points Uniformly at Random on the Surface of a Sphere . . . . 26
2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7 Bounds on Tail Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.8 Applications of the tail bound . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.9 Random Projection and Johnson-Lindenstrauss Theorem . . . . . . . . . . 37
2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Random Graphs 51
3.1 The G(n, p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1.2 Existence of Triangles in G(n, d/n) . . . . . . . . . . . . . . . . . . 57
3.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3 The Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.5.3 Threshold for O(ln n) Diameter . . . . . . . . . . . . . . . . . . . . 83
3.6 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . . 85
3.7 Phase Transitions for CNF-sat . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.8 Nonuniform and Growth Models of Random Graphs . . . . . . . . . . . . . 91
3.8.1 Nonuniform Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.8.2 Giant Component in Random Graphs with Given Degree Distribution 92
3.9 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.9.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 93
3.9.2 Growth Model With Preferential Attachment . . . . . . . . . . . . 100
3.10 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2
4 Singular Value Decomposition (SVD) 117
4.1 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 122
4.3 Best Rank k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.4 Power Method for Computing the Singular Value Decomposition . . . . . . 126
4.5 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 130
4.5.1 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 130
4.5.2 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 130
4.5.3 Spectral Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 135
4.5.4 Singular Vectors and Ranking Documents . . . . . . . . . . . . . . 136
4.5.5 An Application of SVD to a Discrete Optimization Problem . . . . 137
4.6 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 140
4.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5 Random Walks and Markov Chains 150
5.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.2 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 155
5.3 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 159
5.4 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 166
5.5 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.6 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.6.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 175
5.6.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.7 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.8 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 180
5.8.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 185
5.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
6 Learning and VC-dimension 199
6.1 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
6.2 Linear Separators, the Perceptron Algorithm, and Margins . . . . . . . . . 201
6.3 Nonlinear Separators, Support Vector Machines, and Kernels . . . . . . . . 206
6.4 Strong and Weak Learning - Boosting . . . . . . . . . . . . . . . . . . . . . 211
6.5 Number of Examples Needed for Prediction: VC-Dimension . . . . . . . . 213
6.6 Vapnik-Chervonenkis or VC-Dimension . . . . . . . . . . . . . . . . . . . . 216
6.6.1 Examples of Set Systems and Their VC-Dimension . . . . . . . . . 217
6.6.2 The Shatter Function . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.6.3 Shatter Function for Set Systems of Bounded VC-Dimension . . . 221
6.6.4 Intersection Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 223
6.7 The VC Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
6.8 Simple Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
3
6.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
7 Algorithms for Massive Data Problems 235
7.1 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 235
7.1.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 236
7.1.2 Counting the Number of Occurrences of a Given Element. . . . . . 240
7.1.3 Counting Frequent Elements . . . . . . . . . . . . . . . . . . . . . . 240
7.1.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.2 Matrix Algorithms Using Sampling . . . . . . . . . . . . . . . . . . . . . . 246
7.2.1 Matrix Multiplication Using Sampling . . . . . . . . . . . . . . . . 246
7.2.2 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . 248
7.3 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8 Clustering 258
8.1 Some Clustering Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
8.2 A k-means Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . . . 261
8.3 A Greedy Algorithm for k-Center Criterion Clustering . . . . . . . . . . . 263
8.4 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
8.5 Recursive Clustering Based on Sparse Cuts . . . . . . . . . . . . . . . . . . 270
8.6 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.7 Agglomerative Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
8.8 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . . 276
8.9 Flow Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
8.10 Finding a Local Cluster Without Examining the Whole Graph . . . . . . . 281
8.11 Axioms for Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
8.11.1 An Impossibility Result . . . . . . . . . . . . . . . . . . . . . . . . 287
8.11.2 A Satisfiable Set of Axioms . . . . . . . . . . . . . . . . . . . . . . 293
8.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
9 Topic Models, Hidden Markov Process, Graphical Models, and Belief
Propagation 299
9.1 Topic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
9.2 Hidden Markov Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
9.3 Graphical Models, and Belief Propagation . . . . . . . . . . . . . . . . . . 308
9.4 Bayesian or Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 309
9.5 Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.6 Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
9.7 Tree Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
9.8 Message Passing in general Graphs . . . . . . . . . . . . . . . . . . . . . . 313
9.9 Graphs with a Single Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 315
9.10 Belief Update in Networks with a Single Loop . . . . . . . . . . . . . . . . 317
9.11 Maximum Weight Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 318
4
9.12 Warning Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
9.13 Correlation Between Variables . . . . . . . . . . . . . . . . . . . . . . . . . 323
9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
10 Other Topics 330
10.1 Rankings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
10.2 Hare System for Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
10.3 Compressed Sensing and Sparse Vectors . . . . . . . . . . . . . . . . . . . 333
10.3.1 Unique Reconstruction of a Sparse Vector . . . . . . . . . . . . . . 334
10.3.2 The Exact Reconstruction Property . . . . . . . . . . . . . . . . . . 337
10.3.3 Restricted Isometry Property . . . . . . . . . . . . . . . . . . . . . 338
10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
10.4.1 Sparse Vector in Some Coordinate Basis . . . . . . . . . . . . . . . 340
10.4.2 A Representation Cannot be Sparse in Both Time and Frequency
Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
10.4.3 Biological . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
10.4.4 Finding Overlapping Cliques or Communities . . . . . . . . . . . . 343
10.4.5 Low Rank Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
11 Appendix 349
11.1 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
11.2 Sums of Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
11.3 Useful Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
11.4 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
11.4.1 Sample Space, Events, Independence . . . . . . . . . . . . . . . . . 362
11.4.2 Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . 363
11.4.3 Indicator Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
11.4.4 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
11.4.5 Variance of the Sum of Independent Random Variables . . . . . . . 364
11.4.6 The Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . . 364
11.4.7 Median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
11.4.8 Unbiased Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . 365
11.4.9 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . 365
11.4.10 Maximum Likelihood Estimation MLE . . . . . . . . . . . . . . . . 368
11.4.11 Tail Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
11.5 Chernoff Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
11.6 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 374
11.6.1 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . 374
11.6.2 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 376
11.6.3 Extremal Properties of Eigenvalues . . . . . . . . . . . . . . . . . . 377
11.6.4 Eigenvalues of the Sum of Two Symmetric Matrices . . . . . . . . . 379
11.6.5 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
5
剩余411页未读,继续阅读
i_you
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0