Cover

Title

Copyright

Dedication

Contents

Preface

1 Introduction

1.1 Supervised Learning

1.2 Artificial neural networks

1.3 Outline of the book

1.4 Bibliographical notes

Part one: Pattern Classification with Binary-Output Neural Networks

2 The Pattern Classification Problem

2.1 The learning problem

2.2 Learning finite function classes

2.3 Applications to perceptrons

2.4 Restricted model

2.5 Remarks

2.6 Bibliographical notes

3 The Growth Function and VC-Dimension

3.1 Introduction

3.2 The growth function

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.5 The restricted model

4.6 Remarks

4.7 Bibliographical notes

5 General Lower Bounds on Sample Complexity

5.1 Introduction

5.2 A lower bound for learning

5.3 The restricted model

5.4 VC-dimension quantifies sample complexity

5.5 Remarks

5.6 Bibliographical notes

6 The VC-Dimension of Linear Threshold Networks

6.1 Feed-forward neural networks

6.2 Upper bound

6.3 Lower bounds

6.4 Sigmoid networks

6.5 Bibliographical notes

7 Bounding the VC-Dimension using Geometric Techniques

7.1 Introduction

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

8.2 Function Classes that are Polynomial in their Parameters

8.3 Piecewise-polynomial networks

8.4 Standard sigmoid networks

8.5 Remarks

8.6 Bibliographical notes

Part two: Pattern Classification with Real-Output Networks

9 Classification with Real-Valued Functions

9.1 Introduction

9.2 Large margin classifiers

9.3 Remarks

9.4 Bibliographical Notes

10 Covering Numbers and Uniform Convergence

10.1 Introduction

10.2 Covering Numbers

10.3 A Uniform Convergence Result

10.4 Covering numbers in general

10.5 Remarks

10.6 Bibliographical notes

11 The Pseudo-Dimension and Fat-Shattering Dimension

11.1 Introduction

11.2 The Pseudo-Dimension

11.3 The fat-shattering dimension

11.4 Bibliographical notes

12 Bounding Covering Numbers with Dimensions

12.1 Introduction

12.2 Packing Numbers

12.3 Bounding with the pseudo-dimension

12.4 Bounding with the fat-shattering dimension

12.5 Comparing the two approaches

12.6 Remarks

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

13.6 Bibliographical notes

14 The Dimensions of Neural Networks

14.1 Introduction

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

14.6 Bibliographical notes

15 Model Selection

15.1 Introduction

15.2 Model selection results

15.3 Proofs of the results

15.4 Remarks

15.5 Bibliographical Notes

Part three: Learning Real-Valued Functions

16 Learning Classes of Real Functions

16.1 Introduction

16.2 The learning framework for real estimation

16.3 Learning finite classes of real functions

16.4 A substitute for finiteness

16.5 Remarks

16.6 Bibliographical notes

17 Uniform Convergence Results for Real Function Classes

17.1 Uniform Convergence for Real Functions

17.2 Remarks

17.3 Bibliographical notes

18 Bounding Covering Numbers

18.1 Introduction

18.2 Bounding with the fat-shattering dimension

18.3 Bounding with the pseudo-dimension

18.4 Comparing the different approaches

18.5 Remarks

18.6 Bibliographical notes

19 Sample Complexity of Learning Real Function Classes

19.1 Introduction

19.2 Classes with Finite Fat-Shattering Dimension

19.3 Classes with finite pseudo-dimension

19.4 Results for neural networks

19.5 Lower bounds

19.6 Remarks

19.7 Bibliographical notes

20 Convex Classes

20.1 Introduction

20.2 Lower bounds for non-convex classes

20.3 Upper bounds for convex classes

20.4 Remarks

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

21.6 Bibliographical notes

Part four: Algorithmics

22 Efficient Learning

22.1 Introduction

22.2 Graded function classes

22.3 Efficient learning

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

23.2 Randomized Algorithms

23.3 Learning as randomized optimization

23.4 A characterization of efficient learning

23.5 The hardness of learning

23.6 Remarks

23.7 Bibliographical notes

24 The Boolean Perceptron

24.1 Introduction

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

24.6 Bibliographical notes

25 Hardness Results for Feed-Forward Networks

25.1 Introduction

25.2 Linear Threshold Networks with Binary Inputs

25.3 Linear threshold networks with real inputs

25.4 Sigmoid networks

25.5 Remarks

25.6 Bibliographical notes

26 Constructive Learning Algorithms for Two-Layer Networks

26.1 Introduction

26.2 Real Estimation with Convex Combinations

26.3 Classification learning using boosting

26.4 Bibliographical notes

Appendix 1 Useful Results

Bibliography

Author index 3

Subject index