Contents
1 Introduction 6
2 High-Dimensional Space 7
2.1 Properties of High-Dimensional Space . . . . . . . . . . . . . . . . . . . . . 9
2.2 The High-Dimensional Sphere . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 The Sphere and the Cube in Higher Dimensions . . . . . . . . . . . 10
2.2.2 Volume and Surface Area of the Unit Sphere . . . . . . . . . . . . . 11
2.2.3 The Volume is Near the Equator . . . . . . . . . . . . . . . . . . . 14
2.2.4 The Volume is in a Narrow Annulus . . . . . . . . . . . . . . . . . . 16
2.2.5 The Surface Area is Near the Equator . . . . . . . . . . . . . . . . 16
2.3 The High-Dimensional Cube and Chernoff Bounds . . . . . . . . . . . . . . 18
2.4 Volumes of Other Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Generating Points Uniformly at Random on the surface of a Sphere . . . . 24
2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 Random Projection and the Johnson-Lindenstrauss Theorem . . . . . . . . 31
2.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Random Graphs 46
3.1 The G(n; p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.1.2 Existence of Triangles in G(n; d=n) . . . . . . . . . . . . . . . . . . 51
3.1.3 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1.4 Phase Transitions for Monotone Properties . . . . . . . . . . . . . . 62
3.1.5 Phase Transitions for CNF-sat . . . . . . . . . . . . . . . . . . . . . 65
3.1.6 The Emerging Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.7 The Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.2 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3 Nonuniform and Growth Models of Random Graphs . . . . . . . . . . . . . 85
3.3.1 Nonuniform Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.2 Giant Component in Random Graphs with Given Degree Distribution 86
3.4 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.4.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 87
3.4.2 A Growth Model With Preferential Attachment . . . . . . . . . . . 94
3.5 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4 Singular Value Decomposition (SVD) 110
4.1 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 115
4.3 Best Rank k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 116
1
4.4 Power Method for Computing the Singular Value Decomposition . . . . . . 118
4.5 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 122
4.5.1 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 122
4.5.2 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 123
4.5.3 An Application of SVD to a Discrete Optimization Problem . . . . 127
4.5.4 SVD as a Compression Algorithm . . . . . . . . . . . . . . . . . . . 130
4.5.5 Spectral Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 130
4.5.6 Singular Vectors and ranking documents . . . . . . . . . . . . . . . 131
4.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5 Markov Chains 142
5.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.2 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 144
5.3 Random Walks on Undirected Graphs . . . . . . . . . . . . . . . . . . . . . 148
5.4 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 155
5.5 Random Walks on Directed Graphs . . . . . . . . . . . . . . . . . . . . . . 158
5.6 Finite Markov Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
5.7 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.7.1 Time Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.7.2 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 165
5.7.3 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.8 Convergence to Steady State . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.8.1 Using Minimum Escape Probability to Prove Convergence . . . . . 173
5.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6 Learning and VC-dimension 183
6.1 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
6.2 Linear Separators, the Perceptron Algorithm, and Margins . . . . . . . . . 184
6.3 Nonlinear Separators, Support Vector Machines, and Kernels . . . . . . . . 189
6.4 Strong and Weak Learning - Boosting . . . . . . . . . . . . . . . . . . . . . 194
6.5 Number of Examples Needed for Prediction: VC-Dimension . . . . . . . . 196
6.6 Vapnik-Chervonenkis or VC-Dimension . . . . . . . . . . . . . . . . . . . . 199
6.6.1 Examples of Set Systems and Their VC-Dimension . . . . . . . . . 199
6.6.2 The Shatter Function . . . . . . . . . . . . . . . . . . . . . . . . . 202
6.6.3 Shatter Function for Set Systems of Bounded VC-Dimension . . . 204
6.6.4 Intersection Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 205
6.7 The VC Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.8 Priors and Bayesian Learning . . . . . . . . . . . . . . . . . . . . . . . . . 209
6.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
2
7 Algorithms for Massive Data Problems 217
7.1 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 217
7.1.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 218
7.1.2 Counting the Number of Occurrences of a Given Element. . . . . . 221
7.1.3 Counting Frequent Elements . . . . . . . . . . . . . . . . . . . . . . 222
7.1.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.2 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.2.1 Matrix Multiplication Using Sampling . . . . . . . . . . . . . . . . 229
7.2.2 Approximating a Matrix with a Sample of Rows and Columns . . . 231
7.3 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
8 Clustering 240
8.1 Some Clustering Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
8.2 A Simple Greedy Algorithm for k-clustering . . . . . . . . . . . . . . . . . 242
8.3 Lloyd's Algorithm for k-means Clustering . . . . . . . . . . . . . . . . . . . 243
8.4 Meaningful Clustering via Singular Value Decomposition . . . . . . . . . . 245
8.5 Recursive Clustering based on Sparse Cuts . . . . . . . . . . . . . . . . . . 250
8.6 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.7 Agglomerative Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.8 Communities, Dense Submatrices . . . . . . . . . . . . . . . . . . . . . . . 258
8.9 Flow Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
8.10 Linear Programming Formulation . . . . . . . . . . . . . . . . . . . . . . . 263
8.11 Finding a Local Cluster Without Examining the Whole graph . . . . . . . 264
8.12 Statistical Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.13 Axioms for Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.13.1 An Impossibility Result . . . . . . . . . . . . . . . . . . . . . . . . 270
8.13.2 A Satisfiable Set of Axioms . . . . . . . . . . . . . . . . . . . . . . 276
8.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9 Graphical Models and Belief Propagation 283
9.1 Bayesian Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
9.2 Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
9.3 Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
9.4 Tree Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
9.5 Message Passing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 287
9.6 Graphs with a Single Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 290
9.7 Belief Update in Networks with a Single Loop . . . . . . . . . . . . . . . . 292
9.8 Graphs with Multiple Loops . . . . . . . . . . . . . . . . . . . . . . . . . . 293
9.9 Clustering by Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . 294
9.10 Maximum Weight Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 296
9.11 Warning Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
9.12 Correlation Between Variables . . . . . . . . . . . . . . . . . . . . . . . . . 301
3
9.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
10 Other Topics 307
10.1 Rankings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.2 Hare System for Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
10.3 Compressed Sensing and Sparse Vectors . . . . . . . . . . . . . . . . . . . 310
10.3.1 Unique Reconstruction of a Sparse Vector . . . . . . . . . . . . . . 311
10.3.2 The Exact Reconstruction Property . . . . . . . . . . . . . . . . . . 313
10.3.3 Restricted Isometry Property . . . . . . . . . . . . . . . . . . . . . 314
10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
10.4.1 Sparse Vector in Some Coordinate Basis . . . . . . . . . . . . . . . 316
10.4.2 A Representation Cannot be Sparse in Both Time and Frequency
Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
10.4.3 Biological . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
10.4.4 Finding Overlapping Cliques or Communities . . . . . . . . . . . . 320
10.4.5 Low Rank Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
11 Appendix 325
11.1 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.2 Useful Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
11.3 Sums of Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
11.4 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
11.4.1 Sample Space, Events, Independence . . . . . . . . . . . . . . . . . 338
11.4.2 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.4.3 Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
11.4.4 Variance of Sum of Independent Random Variables . . . . . . . . . 341
11.4.5 Sum of independent random variables, Central Limit Theorem . . . 341
11.4.6 Median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
11.4.7 Unbiased estimators . . . . . . . . . . . . . . . . . . . . . . . . . . 342
11.4.8 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . 344
11.4.9 Tail Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
11.4.10 Chernf Bounds: Bounding of Large Deviations . . . . . . . . . . . 354
11.4.11Holding's Inequality . . . . . . . . . . . . . . . . . . . . . . . . . 358
11.5 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
11.5.1 Generating Functions for Sequences Depened by Recurrence Relationships
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
11.5.2 Exponential Generating Function . . . . . . . . . . . . . . . . . . . 363
11.6 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 369
11.6.1 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . 369
11.6.2 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 370
11.6.3 Extremal Properties of Eigenvalues . . . . . . . . . . . . . . . . . . 372
11.6.4 Eigenvalues of the Sum of Two Symmetric Matrices . . . . . . . . . 374
4
11.6.5 Separator Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
11.6.6 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
11.6.7 Important Norms and Their Properties . . . . . . . . . . . . . . . . 377
11.6.8 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
11.7 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
11.7.1 Variational Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 388
11.7.2 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
11.7.3 Sperner's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
Index 391
5
评价“信息时代的计算机科学理论”