请选择 进入手机版 | 继续访问电脑版
楼主: MRchesian
1249 6

[书籍介绍] Foundations of Data Science (page 439) [推广有奖]

  • 1关注
  • 7粉丝

硕士生

17%

还不是VIP/贵宾

-

威望
0
论坛币
6932 个
通用积分
68.0845
学术水平
2 点
热心指数
2 点
信用等级
1 点
经验
1074 点
帖子
49
精华
0
在线时间
214 小时
注册时间
2017-12-9
最后登录
2024-3-11

MRchesian 学生认证  发表于 2018-3-15 22:37:36 |显示全部楼层 |坛友微信交流群

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币
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 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                                                                                 139

        5.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                                                                                                                190

        6.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    237

        7.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

二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:Data Science Foundations foundation Science ATION

yazxf 发表于 2018-3-15 22:48:08 |显示全部楼层 |坛友微信交流群
你的书呢?!

使用道具

20115326 学生认证  发表于 2018-3-16 08:28:54 |显示全部楼层 |坛友微信交流群

使用道具

tsangwm 发表于 2018-3-16 08:41:48 |显示全部楼层 |坛友微信交流群
thank you

使用道具

MRchesian 学生认证  发表于 2018-3-16 11:36:21 |显示全部楼层 |坛友微信交流群
yazxf 发表于 2018-3-15 22:48
你的书呢?!
链接:https://pan.baidu.com/s/15XphNXuchnKdP2lP4xhW1w 密码:6wkf

使用道具

line_us 发表于 2018-3-16 15:46:57 |显示全部楼层 |坛友微信交流群
支持分享

使用道具

sigmund 在职认证  发表于 2018-3-19 14:25:26 |显示全部楼层 |坛友微信交流群
不错,谢谢!

使用道具

您需要登录后才可以回帖 登录 | 我要注册

本版微信群
加好友,备注cda
拉您进交流群

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2024-3-29 15:59