发帖
雷达卡
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 theEquator . . . . . . . . . . . . . . . 17
2.5 Generating Points Uniformly atRandom from a Ball . . . . . . . . . . .. 20
2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . .. . . 21
2.7 Random Projection andJohnson-Lindenstrauss Lemma . . . . . . . . . . . 23
2.8 Separating Gaussians . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 25
2.9 Fitting a Single SphericalGaussian 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 theSingular Value Decomposition . . . . . . 49
3.7.1 A Faster Method . . . . . . . .. . . . . . . . . . . . . . . . . . . . 50
3.8 Singular Vectors andEigenvectors . . . . . . . . . . . . . . . . . . . . . . . 52
3.9 Applications of Singular ValueDecomposition . . . . . . . . . . . . . . . . 52
3.9.1 Centering Data . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 52
3.9.2 Principal Component Analysis .. . . . . . . . . . . . . . . . . . . . 53
3.9.3 Clustering a Mixture ofSpherical Gaussians . . . . . . . . . . . . . 54
3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . . 59
3.9.5 An Application of SVD to aDiscrete 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
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(lnn) Diameter . . . . . . . . . . . . . . . . . . . . 105
4.6 Phase Transitions forIncreasing Properties . . . . . . . . . . . . . . . . . . 107
4.7 Phase Transitions for CNF-sat .. . . . . . . . . . . . . . . . . . . . . . . . 109
4.8 Nonuniform and Growth Models ofRandom Graphs . . . . . . . . . . . . . 114
4.8.1 Nonuniform Models . . . . . . .. . . . . . . . . . . . . . . . . . . . 114
4.8.2 Giant Component in RandomGraphs with Given Degree Distribution114
4.9 Growth Models . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 116
4.9.1 Growth Model Without PreferentialAttachment . . . . . . . . . . . 116
4.9.2 Growth Model With PreferentialAttachment . . . . . . . . . . . . 122
4.10 Small World Graphs . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 129
4.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 130
5 RandomWalks and Markov Chains 1395.1 StationaryDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.2 Markov Chain MonteCarlo .. . . . . . . . . . . . . . . . . . . . . . . . . 145
5.2.1 Metropolis-HastingAlgorithm . . . . . . . . . . . . . . . . . . . . . 146
5.2.2 GibbsSampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.3 Areasand Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
5.4 Convergence of RandomWalks on Undirected Graphs . . . . . . . . . . . . 151
5.4.1 Using Normalized Conductanceto Prove Convergence . . . . . . . . 157
5.5 ElectricalNetworks and Random Walks . . . . . . . . . . . . . . . . . . . . 160
5.6 Random Walks on UndirectedGraphs with Unit Edge Weights . . . . . . . 164
5.7 Random Walks inEuclidean Space .. . . . . . . . . . . . . . . . . . . . . 171
5.8 TheWeb as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.9 BibliographicNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.10 Exercises . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6 MachineLearning 1906.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
6.2 Overfittingand Uniform Convergence . . . . . . . . . . . . . . . . . . . . . 192
6.3 IllustrativeExamples and Occam’s Razor . . . . . . . . . . . . . . . . . . . 194
6.3.1 Learningdisjunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 194
6.3.2 Occam’srazor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
6.3.3 Application:learning decision trees . . . . . . . . . . . . . . . . . . 196
6.4 Regularization:penalizing complexity . . . . . . . . . . . . . . . . . . . . . 197
6.5 Online learning and thePerceptron algorithm .. . . . . . . . . . . . . . . 198
6.5.1 An example:learning disjunctions . . . . . . . . . . . . . . . . . . . 198
6.5.2 TheHalving algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 199
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 Definitions and Key Theorems. . . . . . . . . . . . . . . . . . . . . 207
6.9.2 Examples: VC-Dimension and GrowthFunction . . . . . . . . . . . 209
6.9.3 Proof of Main Theorems . .. . . . . . . . . . . . . . . . . . . . . . 211
6.9.4 VC-dimension of combinations ofconcepts . . . . . . . . . . . . . . 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) ExpertAdvice . . . . . . . . . . . . . . . . . . . . . 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 2377.1 Introduction . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
7.2 Frequency Moments of DataStreams . . . . . . . . . . . . . . . . . . . . . 238
7.2.1 Number of DistinctElements in a Data Stream . . .. . . . . . . . 239
7.2.2 Counting the Numberof 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 MultiplicationUsing Sampling . . . . . . .. . . . . . . . . 249
7.3.2 Implementing Length Squared Samplingin 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
书在这 ：链接：https://pan.baidu.com/s/15XphNXuchnKdP2lP4xhW1w 密码：6wkf
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
