Chapter
2.6 Bibliographical notes
3 The Growth Function and VC-Dimension
3.3 The Vapnik-Chervonenkis dimension
3.4 Bibliographical notes
4 General Upper Bounds on Sample Complexity
4.1 Learning by minimizing sample error
4.2 Uniform convergence and learnability
4.3 Proof of uniform convergence result
4.4 Application to the perceptron
4.7 Bibliographical notes
5 General Lower Bounds on Sample Complexity
5.2 A lower bound for learning
5.4 VC-dimension quantifies sample complexity
5.6 Bibliographical notes
6 The VC-Dimension of Linear Threshold Networks
6.1 Feed-forward neural networks
6.5 Bibliographical notes
7 Bounding the VC-Dimension using Geometric Techniques
7.2 The Need for Conditions on the Activation Functions
7.3 A bound on the growth function
7.4 Proof of the growth function bound
7.5 More on solution set components bounds
7.6 Bibliographical notes
8 Vapnik-Chervonenkis Dimension Bounds for Neural Networks
8.2 Function Classes that are Polynomial in their Parameters
8.3 Piecewise-polynomial networks
8.4 Standard sigmoid networks
8.6 Bibliographical notes
Part two: Pattern Classification with Real-Output
Networks
9 Classification with Real-Valued Functions
9.2 Large margin classifiers
9.4 Bibliographical Notes
10 Covering Numbers and Uniform Convergence
10.3 A Uniform Convergence Result
10.4 Covering numbers in general
10.6 Bibliographical notes
11 The Pseudo-Dimension and Fat-Shattering Dimension
11.2 The Pseudo-Dimension
11.3 The fat-shattering dimension
11.4 Bibliographical notes
12 Bounding Covering Numbers with Dimensions
12.3 Bounding with the pseudo-dimension
12.4 Bounding with the fat-shattering dimension
12.5 Comparing the two approaches
12.7 Bibliographical notes
13 The Sample Complexity of Classification Learning
13.1 Large Margin SEM algorithms
13.2 Large margin SEM algorithms as learning algorithms
13.3 Lower bounds for certain function classes
13.4 Using the pseudo-dimension
13.6 Bibliographical notes
14 The Dimensions of Neural Networks
14.2 Pseudo-dimension of neural networks
14.3 Fat-shattering dimension bounds: number of parameters
14.4 Fat-shattering dimension bounds: size of parameters
14.6 Bibliographical notes
15.2 Model selection results
15.3 Proofs of the results
15.5 Bibliographical Notes
Part three: Learning Real-Valued Functions
16 Learning Classes of Real Functions
16.2 The learning framework for real estimation
16.3 Learning finite classes of real functions
16.4 A substitute for finiteness
16.6 Bibliographical notes
17 Uniform Convergence Results for Real Function Classes
17.1 Uniform Convergence for Real Functions
17.3 Bibliographical notes
18 Bounding Covering Numbers
18.2 Bounding with the fat-shattering dimension
18.3 Bounding with the pseudo-dimension
18.4 Comparing the different approaches
18.6 Bibliographical notes
19 Sample Complexity of Learning Real Function Classes
19.2 Classes with Finite Fat-Shattering Dimension
19.3 Classes with finite pseudo-dimension
19.4 Results for neural networks
19.7 Bibliographical notes
20.2 Lower bounds for non-convex classes
20.3 Upper bounds for convex classes
20.5 Bibliographical notes
21 Other Learning Problems
21.1 Loss Functions in general
21.2 Convergence for general loss functions
21.3 Learning in multiple-output networks
21.4 Interpolation models
21.6 Bibliographical notes
22.2 Graded function classes
22.4 General classes of efficient learning algorithms
22.5 Efficient learning in the restricted model
22.6 Bibliographical notes
23 Learning as Optimization
23.2 Randomized Algorithms
23.3 Learning as randomized optimization
23.4 A characterization of efficient learning
23.5 The hardness of learning
23.7 Bibliographical notes
24 The Boolean Perceptron
24.2 Learning is Hard for the Simple Perceptron
24.3 Learning is easy for fixed fan-in perceptrons
24.4 Perceptron learning in the restricted model
24.6 Bibliographical notes
25 Hardness Results for Feed-Forward Networks
25.2 Linear Threshold Networks with Binary Inputs
25.3 Linear threshold networks with real inputs
25.6 Bibliographical notes
26 Constructive Learning Algorithms for Two-Layer Networks
26.2 Real Estimation with Convex Combinations
26.3 Classification learning using boosting
26.4 Bibliographical notes
Appendix 1 Useful Results