数据科学基础.pdf

Foundations of Data Science Avrim Blum, John Hopcroft, and Ravindran KannanThursday 4th January, 2018Copyright 2015. All rights reserved1Contents1 Introduction 92 High-Dimensional Space 122.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 The Geometry of High Dimensions . . . . . . . . . . . . . . . . . . . . . . 152.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4.1 Volume of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . 172.4.2 Volume Near the Equator . . . . . . . . . . . . . . . . . . . . . . . 192.5 Generating Points Uniformly at Random from a Ball . . . . . . . . . . . . 222.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 232.7 Random Projection and Johnson-Lindenstrauss Lemma . . . . . . . . . . . 252.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.9 Fitting a Spherical Gaussian to Data . . . . . . . . . . . . . . . . . . . . . 292.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 Best-Fit Subspaces and Singular Value Decomposition (SVD) 403.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 453.5 Best Rank-k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 473.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.7 Power Method for Singular Value Decomposition . . . . . . . . . . . . . . . 513.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 543.9 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 543.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 563.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 563.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . . 623.9.5 An Application of SVD to a Discrete Optimization Problem . . . . 633.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674 Random Walks and Markov Chains 764.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 814.2.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 834.2.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.3 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8624.4 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 884.4.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 944.5 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 974.6 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 1024.7 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 1094.8 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185 Machine Learning 1295.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1295.2 The Perceptron algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1305.3 Kernel Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1325.4 Generalizing to New Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.5 Over tting and Uniform Convergence . . . . . . . . . . . . . . . . . . . . . 1355.6 Illustrative Examples and Occams Razor . . . . . . . . . . . . . . . . . . . 1385.6.1 Learning Disjunctions . . . . . . . . . . . . . . . . . . . . . . . . . 1385.6.2 Occams Razor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.6.3 Application: Learning Decision Trees . . . . . . . . . . . . . . . . . 1405.7 Regularization: Penalizing Complexity . . . . . . . . . . . . . . . . . . . . 1415.8 Online Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1415.8.1 An Example: Learning Disjunctions . . . . . . . . . . . . . . . . . . 1425.8.2 The Halving Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 1435.8.3 The Perceptron Algorithm . . . . . . . . . . . . . . . . . . . . . . . 1435.8.4 Extensions: Inseparable Data and Hinge Loss . . . . . . . . . . . . 1455.9 Online to Batch Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . 1465.10 Support-Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1475.11 VC-Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1485.11.1 De nitions and Key Theorems . . . . . . . . . . . . . . . . . . . . . 1495.11.2 Examples: VC-Dimension and Growth Function . . . . . . . . . . . 1515.11.3 Proof of Main Theorems . . . . . . . . . . . . . . . . . . . . . . . . 1535.11.4 VC-Dimension of Combinations of Concepts . . . . . . . . . . . . . 1565.11.5 Other Measures of Complexity . . . . . . . . . . . . . . . . . . . . . 1565.12 Strong and Weak Learning - Boosting . . . . . . . . . . . . . . . . . . . . . 1575.13 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . 1605.14 Combining (Sleeping) Expert Advice . . . . . . . . . . . . . . . . . . . . . 1625.15 Deep Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1645.15.1 Generative Adversarial Networks (GANs) . . . . . . . . . . . . . . . 1705.16 Further Current Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1715.16.1 Semi-Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . 1715.16.2 Active Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1745.16.3 Multi-Task Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 1745.17 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17535.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1766 Algorithms for Massive Data Problems: Streaming, Sketching, andSampling 1816.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1816.2 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 1826.2.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 1836.2.2 Number of Occurrences of a Given Element. . . . . . . . . . . . . . 1866.2.3 Frequent Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . 1876.2.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 1896.3 Matrix Algorithms using Sampling . . . . . . . . . . . . . . . . . . . . . . 1926.3.1 Matrix Multiplication using Sampling . . . . . . . . . . . . . . . . . 1936.3.2 Implementing Length Squared Sampling in Two Passes . . . . . . . 1976.3.3 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . 1976.4 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2016.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2036.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2047 Clustering 2087.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2087.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2087.1.2 Two General Assumptions on the Form of Clusters . . . . . . . . . 2097.1.3 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 2117.2 k-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2117.2.1 A Maximum-Likelihood Motivation . . . . . . . . . . . . . . . . . . 2117.2.2 Structural Properties of the k-Means Objective . . . . . . . . . . . 2127.2.3 Lloyds Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2137.2.4 Wards Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2157.2.5 k-Means Clustering on the Line . . . . . . . . . . . . . . . . . . . . 2157.3 k-Center Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2157.4 Finding Low-Error Clusterings . . . . . . . . . . . . . . . . . . . . . . . . . 2167.5 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2167.5.1 Why Project? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2167.5.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2187.5.3 Means Separated by (1) Standard Deviations . . . . . . . . . . . . 2197.5.4 Laplacians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2217.5.5 Local spectral clustering . . . . . . . . . . . . . . . . . . . . . . . . 2217.6 Approximation Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2247.6.1 The Conceptual Idea . . . . . . . . . . . . . . . . . . . . . . . . . . 2247.6.2 Making this Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . 2247.6.3 Algorithm and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 2257.7 High-Density Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2277.7.1 Single Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22747.7.2 Robust Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2287.8 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2287.9 Recursive Clustering based on Sparse Cuts . . . . . . . . . . . . . . . . . . 2297.10 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . . 2307.11 Community Finding and Graph Partitioning . . . . . . . . . . . . . . . . . 2337.12 Spectral clustering applied to social networks . . . . . . . . . . . . . . . . . 2367.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2397.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2408 Random Graphs 2458.1 The G(n;p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2458.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 2468.1.2 Existence of Triangles in G(n;d=n) . . . . . . . . . . . . . . . . . . 2508.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2528.3 Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2618.3.1 Existence of a giant component . . . . . . . . . . . . . . . . . . . . 2618.3.2 No other large components . . . . . . . . . . . . . . . . . . . . . . . 2638.3.3 The case of p 1=n . . . . . . . . . . . . . . . . . . . . . . . . . . . 2648.4 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 2658.4.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 2658.4.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2668.4.3 Threshold for O(lnn) Diameter . . . . . . . . . . . . . . . . . . . . 2688.5 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . . 2708.6 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2728.7 CNF-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2778.7.1 SAT-solvers in practice . . . . . . . . . . . . . . . . . . . . . . . . . 2788.7.2 Phase Transitions for CNF-SAT . . . . . . . . . . . . . . . . . . . . 2798.8 Nonuniform Models of Random Graphs . . . . . . . . . . . . . . . . . . . . 2848.8.1 Giant Component in Graphs with Given Degree Distribution . . . . 2858.9 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2868.9.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 2878.9.2 Growth Model With Preferential Attachment . . . . . . . . . . . . 2938.10 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2948.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2998.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3019 Topic Models, Nonnegative Matrix Factorization, Hidden Markov Mod-els, and Graphical Models 3109.1 Topic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3109.2 An Idealized Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3139.3 Nonnegative Matrix Factorization - NMF . . . . . . . . . . . . . . . . . . . 3159.4 NMF with Anchor Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3179.5 Hard and Soft Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31859.6 The Latent Dirichlet Allocation Model for Topic Modeling . . . . . . . . . 3209.7 The Dominant Admixture Model . . . . . . . . . . . . . . . . . . . . . . . 3229.8 Formal Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3249.9 Finding the Term-Topic Matrix . . . . . . . . . . . . . . . . . . . . . . . . 3279.10 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3329.11 Graphical Models and Belief Propagation . . . . . . . . . . . . . . . . . . . 3379.12 Bayesian or Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 3389.13 Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3399.14 Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3409.15 Tree Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3419.16 Message Passing in General Graphs . . . . . . . . . . . . . . . . . . . . . . 3429.17 Graphs with a Single Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 3449.18 Belief Update in Networks with a Single Loop . . . . . . . . . . . . . . . . 3469.19 Maximum Weight Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 3479.20 Warning Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3519.21 Correlation Between Variables . . . . . . . . . . . . . . . . . . . . . . . . . 3519.22 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3559.23 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35710 Other Topics 36010.1 Ranking and Social Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . 36010.1.1 Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36210.1.2