Title:      A Theory of Learning and Generalization
Subtitle:   With Applications to Neural Networks and Control Systems
Author:     M. Vidyasagar
Publisher:  Springer-Verlag London, 1997.
Details:    382 pages, 36 figures, 150 references

This book contains a comprehensive treatment of so-called statistical
learning theory and its applications both to neural networks and control
systems.  Other names for the subject are PAC learning theory and
computational learning theory.  In addition to a thorough treatment of known
results, the book also presents several new results for the first time, as
well as a list of sixteen open problems.

The Table of Contents of the book is shown below:

Preface                                                                 xiii

1. Introduction                                                           3

2. Preliminaries                                                            15
   2.1 Pseudometric Spaces, Packing and Covering Numbers                  15
   2.2 Probability Measures                                               19
   2.3 Large Deviation Type Inequalities                                  21
   2.4 Some Advanced Ideas                                                25

3. Problem Formulations                                                     29
   3.1 Uniform Convergence of Empirical Means                             29
   3.2 Learning Concepts and Functions                                    39
   3.3 Model-Free Learning                                                59

4. Vapnik-Chervonenkis and Pollard (Pseudo-) Dimensions                     69
   4.1 Definitions                                                        69
   4.2 Bounds on Growth Functions                                         75
   4.3 Growth Functions of Iterated Families                              87

5. Uniform Convergence of Empirical Means                                   95
   5.1 Restatement of the Problems Under Study                            95
   5.2 Equivalence of the UCEM and ASCEM Properties                       99
   5.3 Main Theorems                                                     101
   5.4 Preliminary Lemmas                                                108
   5.5 Theorem 5.1: Proof of Necessity                                   119
   5.6 Theorem 5.1: Proof of Sufficiency                                 124
   5.7 Proofs of the Remaining Theorems                                  136
   5.8 Uniform Convergence Properties of Iterated Families               140

6. Learning Under a Fixed Probability Measure                               153
   6.1 UCEM Property Implies ASEC Learnability                           155
   6.2 Shrinking Width is Equivalent to Consistent Learnability          161
   6.3 Finite Metric Entropy Implies Learnability                        167
   6.4 Examples                                                          176
   6.5 Learnable Concept Classes Have Finite Metric Entropy              179
   6.6 Model-Free Learning                                               185

7. Distribution-Free Learning                                               195
   7.1 Uniform Convergence of Empirical Means                            195
   7.2 Function Learning                                                 202
   7.3 Concept Learning                                                  207
   7.4 Learnability of Functions with a Finite Range                     219

8. Learning Under an Intermediate Family of Probabilities                   223
   8.1 General Families of Probabilities                                 225
   8.2 Totally Bounded Families of Probabilities                         235
   8.3 Families of Probabilities with a Nonempty Interior                246

9. Alternate Models of Learning                                             249
   9.1 Efficient Learning                                                250
   9.2 Active Learning                                                   264
   9.3 Learning with Prior Information                                   273

10. Applications to Neural Networks                                         291
   10.1 What is a Neural Network?                                        292
   10.2 Learning in Neural Networks                                      295
       10.2.1 Problem Formulation                                     295
       10.2.2 Reprise of Sample Complexity Estimates                  298
       10.2.3 Complexity-Theoretic Limits to Learnability             303
   10.3 Estimates of VC-Dimensions of Families of Networks               307
       10.3.1 Multi-Layer Perceptron Networks                         308
       10.3.2 A Network with Infinite VC-Dimension                    314
       10.3.3 Neural Networks as Verifiers of Formulas                316
       10.3.4 Neural Networks with Piecewise-Polynomial Activation Functions
                                                                      323
       10.3.5 A General Approach                                      328
       10.3.6 Networks with Pfaffian Activation Functions             332
       10.3.7 Results Based on Order-Minimality                       335
   10.4 Structural Risk Minimization                                     337

11. Applications to Control Systems                                         343
   11.1 Identification                                                   344
   11.2 Robust Control                                                   352

12. Some Open Problems                                                      361