|
NeuroCOLT
Technical Report NC-TR-94-003
Probabilistic
Analysis of Learning in Artificial Neural Networks: The PAC Model
and its Variants
Martin
Anthony
Dept of Mathematics
London School of Economics
Abstract
This report (72 pages) surveys the probably approximately correct
model of machine learning, with emphasis on the sample complexity
of learning. Applications to the theory of learning in artificial
neural networks are discussed.
The survey should be accessible to those unfamiliar with computational
learning theory. It is assumed the reader has some familiarity with
neural networks, but otherwise the survey is largely self-contained.
The basic PAC model of concept learning is discussed and the key results
involving the Vapnik-Chervonenkis dimension are derived. Implications
for the theory of artificial neural networks are discussed through
a survey of known results on the VC-dimension of neural nets. A brief
discussion of the computational complexity of PAC learning follows.
We then discuss generalisations and extensions of the PAC model: stochastic
concepts, learning with respect to particular distributions, and the
learnability of functions and p-concepts. (We do not discuss computational
complexity in these contexts.)
Contents:
1.
Introduction
2. The Basic PAC Model of Learning
3. VC-Dimension and Growth Function
4. VC-Dimension and Linear Dimension
5. A Useful Probability Theorem
6. PAC Learning and the VC-Dimension
7. VC-Dimension of Binary-Output Networks
introduction
linearly weighted neural networks
linear threshold networks
other activation functions
the effect of weight restrictions
8. Computational Complexity of Learning
9. Stochastic Concepts
10. Distribution-Specific Learning
11. Graph Dimension and Multiple-Output Nets
the graph dimension
multiple-output feedforward threshold networks
12. Pseudo-Dimension and Function Learning
the pseudo-dimension
learning real-valued functions
13. Capacity of a Function Space
capacity and learning
applications to sigmoid neural networks
14. Scale-Sensitive Dimensions
learnability of p-concepts
learnability of functions
15. Conclusions
Download Compressed Postscript
|