lxlybytwo的博客

The Elements of Statistical Learning：Data Mining, Inference, and Prediction Trevor Hastie，Robert Tibshirani，Jerome Friedman

统计学习方法 李航著 清华大学出版社 机器学习入门书籍

Foundations of Data Scienceby Avrim Blum, John Hopcroft and Ravindran Kannan 数据科学导论 Contents 1 Introduction 8 2 High-Dimensional Space 11 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 The Geometry of High Dimensions . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.1 Volume of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.2 Most of the Volume is Near the Equator . . . . . . . . . . . . . . . 17 2.5 Generating Points Uniformly at Random from a Ball . . . . . . . . . . . . 20 2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.7 Random Projection and Johnson-Lindenstrauss Lemma . . . . . . . . . . . 23 2.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.9 Fitting a Single Spherical Gaussian to Data . . . . . . . . . . . . . . . . . 27 2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Best-Fit Subspaces and Singular Value Decomposition (SVD) 38 3.1 Introduction and Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 44 3.5 Best Rank-k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.7 Power Method for Computing the Singular Value Decomposition . . . . . . 49 3.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 52 3.9 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 52 3.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 53 3.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 54 3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . . 59 3.9.5 An Application of SVD to a Discrete Optimization Problem . . . . 60 3.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4 Random Graphs 71 4.1 The G(n; p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.1.2 Existence of Triangles in G(n; d=n) . . . . . . . . . . . . . . . . . . 77 4.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.3 The Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2 4.4 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.5 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.5.3 Threshold for O(ln n) Diameter . . . . . . . . . . . . . . . . . . . . 105 4.6 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . . 107 4.7 Phase Transitions for CNF-sat . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.8 Nonuniform and Growth Models of Random Graphs . . . . . . . . . . . . . 114 4.8.1 Nonuniform Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.8.2 Giant Component in Random Graphs with Given Degree Distribution114 4.9 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.9.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 116 4.9.2 Growth Model With Preferential Attachment . . . . . . . . . . . . 122 4.10 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5 Random Walks and Markov Chains 139 5.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.2.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 146 5.2.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.3 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 5.4 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 151 5.4.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 157 5.5 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 160 5.6 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 164 5.7 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 171 5.8 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6 Machine Learning 190 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 6.2 Overtting and Uniform Convergence . . . . . . . . . . . . . . . . . . . . . 192 6.3 Illustrative Examples and Occam's Razor . . . . . . . . . . . . . . . . . . . 194 6.3.1 Learning disjunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 194 6.3.2 Occam's razor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 6.3.3 Application: learning decision trees . . . . . . . . . . . . . . . . . . 196 6.4 Regularization: penalizing complexity . . . . . . . . . . . . . . . . . . . . . 197 6.5 Online learning and the Perceptron algorithm . . . . . . . . . . . . . . . . 198 6.5.1 An example: learning disjunctions . . . . . . . . . . . . . . . . . . . 198 6.5.2 The Halving algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 199 3 6.5.3 The Perceptron algorithm . . . . . . . . . . . . . . . . . . . . . . . 199 6.5.4 Extensions: inseparable data and hinge-loss . . . . . . . . . . . . . 201 6.6 Kernel functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 6.7 Online to Batch Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . 204 6.8 Support-Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6.9 VC-Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.9.1 Denitions and Key Theorems . . . . . . . . . . . . . . . . . . . . . 207 6.9.2 Examples: VC-Dimension and Growth Function . . . . . . . . . . . 209 6.9.3 Proof of Main Theorems . . . . . . . . . . . . . . . . . . . . . . . . 211 6.9.4 VC-dimension of combinations of concepts . . . . . . . . . . . . . . 214 6.9.5 Other measures of complexity . . . . . . . . . . . . . . . . . . . . . 214 6.10 Strong and Weak Learning - Boosting . . . . . . . . . . . . . . . . . . . . . 215 6.11 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . 218 6.12 Combining (Sleeping) Expert Advice . . . . . . . . . . . . . . . . . . . . . 220 6.13 Deep learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 6.14 Further Current directions . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 6.14.1 Semi-supervised learning . . . . . . . . . . . . . . . . . . . . . . . . 228 6.14.2 Active learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 6.14.3 Multi-task learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 6.15 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 6.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 7 Algorithms for Massive Data Problems: Streaming, Sketching, and Sampling 237 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 7.2 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 238 7.2.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 239 7.2.2 Counting the Number of Occurrences of a Given Element. . . . . . 242 7.2.3 Counting Frequent Elements . . . . . . . . . . . . . . . . . . . . . . 243 7.2.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 244 7.3 Matrix Algorithms using Sampling . . . . . . . . . . . . . . . . . . . . . . 247 7.3.1 Matrix Multiplication Using Sampling . . . . . . . . . . . . . . . . 249 7.3.2 Implementing Length Squared Sampling in two passes . . . . . . . . 252 7.3.3 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . 253 7.4 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 7.5 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 8 Clustering 264 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 8.1.1 Two general assumptions on the form of clusters . . . . . . . . . . . 265 8.2 k-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 8.2.1 A maximum-likelihood motivation for k-means . . . . . . . . . . . . 267 4 8.2.2 Structural properties of the k-means objective . . . . . . . . . . . . 268 8.2.3 Lloyd's k-means clustering algorithm . . . . . . . . . . . . . . . . . 268 8.2.4 Ward's algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 8.2.5 k-means clustering on the line . . . . . . . . . . . . . . . . . . . . . 271 8.3 k-Center Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 8.4 Finding Low-Error Clusterings . . . . . . . . . . . . . . . . . . . . . . . . . 272 8.5 Approximation Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 8.6 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 8.6.1 Stochastic Block Model . . . . . . . . . . . . . . . . . . . . . . . . . 276 8.6.2 Gaussian Mixture Model . . . . . . . . . . . . . . . . . . . . . . . . 278 8.6.3 Standard Deviation without a stochastic model . . . . . . . . . . . 278 8.6.4 Spectral Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . 279 8.7 High-Density Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 8.7.1 Single-linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 8.7.2 Robust linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 8.8 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 8.9 Recursive Clustering based on Sparse cuts . . . . . . . . . . . . . . . . . . 283 8.10 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . . 284 8.11 Community Finding and Graph Partitioning . . . . . . . . . . . . . . . . . 287 8.11.1 Flow Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 8.12 Axioms for Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 8.12.1 An Impossibility Result . . . . . . . . . . . . . . . . . . . . . . . . 290 8.12.2 Satisfying two of three . . . . . . . . . . . . . . . . . . . . . . . . . 291 8.12.3 Relaxing the axioms . . . . . . . . . . . . . . . . . . . . . . . . . . 293 8.12.4 A Satisable Set of Axioms . . . . . . . . . . . . . . . . . . . . . . 293 8.13 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 308 9.5 Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 9.6 Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 9.7 Tree Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 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 . . . . . . . . . . . . . . . . 316 9.11 Maximum Weight Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 318 9.12 Warning Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 9.13 Correlation Between Variables . . . . . . . . . . . . . . . . . . . . . . . . . 322 9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 5 10 Other Topics 329 10.1 Rankings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 10.2 Hare System for Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 10.3 Compressed Sensing and Sparse Vectors . . . . . . . . . . . . . . . . . . . 332 10.3.1 Unique Reconstruction of a Sparse Vector . . . . . . . . . . . . . . 333 10.3.2 The Exact Reconstruction Property . . . . . . . . . . . . . . . . . . 336 10.3.3 Restricted Isometry Property . . . . . . . . . . . . . . . . . . . . . 337 10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 10.4.1 Sparse Vector in Some Coordinate Basis . . . . . . . . . . . . . . . 339 10.4.2 A Representation Cannot be Sparse in Both Time and Frequency Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 10.4.3 Biological . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 10.4.4 Finding Overlapping Cliques or Communities . . . . . . . . . . . . 342 10.4.5 Low Rank Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 10.5 Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 10.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 10.6.1 The Ellipsoid Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 347 10.7 Integer Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 10.8 Semi-Denite Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 349 10.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 11 Wavelets 354 11.1 Dilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 11.2 The Haar Wavelet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 11.3 Wavelet Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 11.4 Solving the Dilation Equation . . . . . . . . . . . . . . . . . . . . . . . . . 359 11.5 Conditions on the Dilation Equation . . . . . . . . . . . . . . . . . . . . . 361 11.6 Derivation of the Wavelets from the Scaling Function . . . . . . . . . . . . 363 11.7 Sucient Conditions for the Wavelets to be Orthogonal . . . . . . . . . . . 367 11.8 Expressing a Function in Terms of Wavelets . . . . . . . . . . . . . . . . . 370 11.9 Designing a Wavelet System . . . . . . . . . . . . . . . . . . . . . . . . . . 371 12 Appendix 375 12.1 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 12.2 Useful relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 12.3 Useful Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 12.4 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 12.4.1 Sample Space, Events, Independence . . . . . . . . . . . . . . . . . 388 12.4.2 Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . 389 12.4.3 Union Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 12.4.4 Indicator Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 12.4.5 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 12.4.6 Variance of the Sum of Independent Random Variables . . . . . . . 390 6 12.4.7 Median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 12.4.8 The Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . . 391 12.4.9 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . 391 12.4.10Bayes Rule and Estimators . . . . . . . . . . . . . . . . . . . . . . . 395 12.4.11Tail Bounds and Cherno inequalities . . . . . . . . . . . . . . . . . 397 12.5 Bounds on Tail Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 12.6 Applications of the tail bound . . . . . . . . . . . . . . . . . . . . . . . . . 403 12.7 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 405 12.7.1 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 406 12.7.2 Relationship between SVD and Eigen Decomposition . . . . . . . . 408 12.7.3 Extremal Properties of Eigenvalues . . . . . . . . . . . . . . . . . . 409 12.7.4 Eigenvalues of the Sum of Two Symmetric Matrices . . . . . . . . . 411 12.7.5 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412 12.7.6 Important Norms and Their Properties . . . . . . . . . . . . . . . . 413 12.7.7 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 12.7.8 Distance between subspaces . . . . . . . . . . . . . . . . . . . . . . 417 12.8 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 12.8.1 Generating Functions for Sequences Dened by Recurrence Relationships . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 12.8.2 The Exponential Generating Function and the Moment Generating Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 12.9 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 12.9.1 Lagrange multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . 423 12.9.2 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 12.9.3 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 12.9.4 Application of Mean Value Theorem . . . . . . . . . . . . . . . . . 424 12.9.5 Sperner's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 12.9.6 Prufer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 12.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 Index 433