Bertrand Clarke · Ernest Fokou´e · Hao Helen Zhang，
Principles and Theory for Data Mining and Machine Learning
Springer Science+Business Media, LLC 2009

729页



Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Variability, Information, and Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.0.1 The Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.0.2 The Two Extremes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Perspectives on the Curse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Sparsity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Exploding Numbers of Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Multicollinearity and Concurvity . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.4 The Effect of Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Coping with the Curse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Selecting Design Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Local Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Parsimony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Two Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 The Bootstrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Cross-Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4 Optimization and Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.4.1 Univariate Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.4.2 Multivariate Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4.3 General Searches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4.4 Constraint Satisfaction and Combinatorial Search . . . . . . . . . . . 35
1.5 Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5.1 Hammersley Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5.2 Edgeworth Expansions for the Mean . . . . . . . . . . . . . . . . . . . . . . 39
1.5.3 Bootstrap Asymptotics for the Studentized Mean . . . . . . . . . . . . 41
1.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2 Local Smoothers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1 Early Smoothers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.2 Transition to Classical Smoothers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.2.1 Global Versus Local Approximations . . . . . . . . . . . . . . . . . . . . . 60
2.2.2 LOESS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.3 Kernel Smoothers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.3.1 Statistical Function Approximation . . . . . . . . . . . . . . . . . . . . . . . 68
2.3.2 The Concept of Kernel Methods and the Discrete Case . . . . . . . 73
2.3.3 Kernels and Stochastic Designs: Density Estimation . . . . . . . . . 78
2.3.4 Stochastic Designs: Asymptotics for Kernel Smoothers . . . . . . 81
2.3.5 Convergence Theorems and Rates for Kernel Smoothers . . . . . 86
2.3.6 Kernel and Bandwidth Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.3.7 Linear Smoothers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2.4 Nearest Neighbors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.5 Applications of Kernel Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.5.1 A Simulated Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.5.2 Ethanol Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3 Spline Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.1 Interpolating Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.2 Natural Cubic Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.3 Smoothing Splines for Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
3.3.1 Model Selection for Spline Smoothing . . . . . . . . . . . . . . . . . . . . 129
3.3.2 Spline SmoothingMeets Kernel Smoothing . . . . . . . . . . . . . . . . 130
3.4 Asymptotic Bias, Variance, and MISE for Spline Smoothers . . . . . . . . . 131
3.4.1 Ethanol Data Example – Continued . . . . . . . . . . . . . . . . . . . . . . . 133
3.5 Splines Redux: Hilbert Space Formulation . . . . . . . . . . . . . . . . . . . . . . . . 136
3.5.1 Reproducing Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.5.2 Constructing an RKHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.5.3 Direct Sum Construction for Splines . . . . . . . . . . . . . . . . . . . . . . 146
3.5.4 Explicit Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
3.5.5 Nonparametrics in Data Mining and Machine Learning . . . . . . 152
3.6 Simulated Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.6.1 What Happens with Dependent Noise Models? . . . . . . . . . . . . . 157
3.6.2 Higher Dimensions and the Curse of Dimensionality . . . . . . . . 159
3.7 Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
3.7.1 Sobolev Spaces: Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4 New Wave Nonparametrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
4.1 Additive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.1.1 The Backfitting Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.1.2 Concurvity and Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.1.3 Nonparametric Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
4.2 Generalized Additive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.3 Projection Pursuit Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
4.4 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
4.4.1 Backpropagation and Inference . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.4.2 Barron’s Result and the Curse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
4.4.3 Approximation Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
4.4.4 Barron’s Theorem: Formal Statement . . . . . . . . . . . . . . . . . . . . . 200
4.5 Recursive Partitioning Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.5.1 Growing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
4.5.2 Pruning and Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
4.5.3 Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
4.5.4 Bayesian Additive Regression Trees: BART . . . . . . . . . . . . . . . . 210
4.6 MARS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
4.7 Sliced Inverse Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
4.8 ACE and AVAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
4.9 Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
4.9.1 Proof of Barron’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224