Learning theory: An approximation theory viewpoint

Felipe Cucker, Ding Xuan Zhou052186559X, 9780521865593, 9780511275517

The goal of learning theory is to approximate a function from sample values. To attain this goal learning theory draws on a variety of diverse subjects, specifically statistics, approximation theory, and algorithmics. Ideas from all these areas blended to form a subject whose many successful applications have triggered a rapid growth during the last two decades. This is the first book to give a general overview of the theoretical foundations of the subject emphasizing the approximation theory, while still giving a balanced overview. It is based on courses taught by the authors, and is reasonably self-contained so will appeal to a broad spectrum of researchers in learning theory and adjacent fields. It will also serve as an introduction for graduate students and others entering the field, who wish to see how the problems raised in learning theory relate to other disciplines.

---

Table of contents :
Half-title……Page 3
Series-title……Page 4
Title……Page 5
Copyright……Page 6
Contents……Page 7
Foreword……Page 10
Preface……Page 12
1.1 Introduction……Page 14
1.2 A formal setting……Page 18
1.3 Hypothesis spaces and target functions……Page 22
1.4 Sample, approximation, and generalization errors……Page 24
1.5 The bias–variance problem……Page 26
1.6 The remainder of this book……Page 27
1.7 References and additional remarks……Page 28
2.1 First examples of hypothesis space……Page 30
2.2 Reminders I……Page 31
2.3 Hypothesis spaces associated with Sobolev spaces……Page 34
2.4 Reproducing Kernel Hilbert Spaces……Page 35
2.5 Some Mercer kernels……Page 37
2.6 Hypothesis spaces associated with an RKHS……Page 44
2.7 Reminders II……Page 46
2.8 On the computation of empirical target functions……Page 47
2.9 References and additional remarks……Page 48
3.1 Exponential inequalities in probability……Page 50
3.2 Uniform estimates on the defect……Page 56
3.3 Estimating the sample error……Page 57
3.4 Convex hypothesis spaces……Page 59
3.5 References and additional remarks……Page 62
4 Polynomial decay of the approximation error……Page 67
4.1 Reminders III……Page 68
4.2 Operators defined by a kernel……Page 69
4.3 Mercer’s theorem……Page 72
4.4 RKHSs revisited……Page 74
4.5 Characterizing the approximation error in RKHSs……Page 76
4.6 An example……Page 81
4.7 References and additional remarks……Page 82
5 Estimating covering numbers……Page 85
5.1 Reminders IV……Page 86
5.2 Covering numbers for Sobolev smooth kernels……Page 89
5.3 Covering numbers for analytic kernels……Page 96
5.4 Lower bounds for covering numbers……Page 114
5.5 On the smoothness of box spline kernels……Page 119
5.6 References and additional remarks……Page 121
6 Logarithmic decay of the approximation error……Page 122
6.1 Polynomial decay of the approximation error for … kernels……Page 123
6.2 Measuring the regularity of the kernel……Page 125
6.3 Estimating the approximation error in RKHSs……Page 130
6.5 References and additional remarks……Page 138
7 On the bias–variance problem……Page 140
7.1 A useful lemma……Page 141
7.2 Proof of Theorem 7.1……Page 142
7.3 A concrete example of bias–variance……Page 145
7.4 References and additional remarks……Page 146
8 Least squares regularization……Page 147
8.1 Bounds for the regularized error……Page 148
8.2 On the existence of target functions……Page 152
8.3 A first estimate for the excess generalization error……Page 153
8.4 Proof of Theorem 8.1……Page 161
8.6 Compactness and regularization……Page 164
8.7 References and additional remarks……Page 168
9 Support vector machines for classification……Page 170
9.1 Binary classifiers……Page 172
9.2 Regularized classifiers……Page 174
9.3 Optimal hyperplanes: the separable case……Page 179
9.4 Support vector machines……Page 182
9.5 Optimal hyperplanes: the nonseparable case……Page 184
9.6 Error analysis for separable measures……Page 186
9.7 Weakly separable measures……Page 195
9.8 References and additional remarks……Page 198
10 General regularized classifiers……Page 200
10.1 Bounding the misclassification error in terms of the generalization error……Page 202
10.2 Projection and error decomposition……Page 207
10.3 Bounds for the regularized error D(Gamma,Phi) of fGamma……Page 209
10.4 Bounds for the sample error term involving fGamma……Page 211
10.5 Bounds for the sample error term involving fPhiz,Gamma……Page 214
10.6 Stronger error bounds……Page 217
10.7 Improving learning rates by imposing noise conditions……Page 223
References……Page 224
Index……Page 235