信息时代的计算机科学理论

内容概要

John Hopcroft为图灵奖获得者。

Ravindran Kannan is a principal researcher with Microsoft Research Labs located in India

书籍目录

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

 信息时代的计算机科学理论下载 更多精彩书评