New paper

[Sean Holden]

The following paper does not specifically address connectionist 
networks. However it may be of interest to readers of this list.



The following research note is now available
--------------------------------------------


            Cross-Validation and the PAC Learning Model


                         Sean B. Holden


                     Research Note RN/96/64

                 Department of Computer Science
                   University College London
                         Gower Street
                     London WC1E 6BT, U.K.


                           Abstract

A large body of research exists within the general field of
computational learning theory which, informally speaking, addresses
the following question: how many examples are required so that, with
`high probability', after training a supervised learner we can expect
the error on the training set to be `close' to the actual probability
of error (the {\em generalization error\/}) of the learner?
Theoretical frameworks inspired by {\em probably approximately correct
(PAC) learning\/} formalise what is meant by `high probability' and
`close' in the above statement. A statistician might recognize this
problem as that of knowing under what conditions the `resubstitution
estimate'---as the error on the training set is often referred
to---provides in a particular sense a good estimate of the
generalization error. It is well-known that, in fact, the
resubstitution estimate usually provides a rather bad estimate of this
quantity, and that several better estimates exist. In this paper we
study two of the latter estimates---the {\em holdout estimate\/} and
the {\em cross-validation estimate\/}---within a framework inspired by
PAC learning theory. We derive upper and lower bounds on the sample
complexity of the error estimation problem for these estimates. Our
bounds apply for {\em any\/} consistent supervised learner.
 


A copy can be obtained as follows:
----------------------------------

a) By anonymous ftp
-------------------

address: cs.ucl.ac.uk

research/rn/rn-96-64.ps.Z


b) From my Web page
-------------------

http://www.cs.ucl.ac.uk/staff/S.Holden/


c) By postal mail
------------------

A limited number of paper copies is available. Request a 
copy from:

Dr. Sean B. Holden
Department of Computer Science
University College London
Gower Street
London WC1E 6BT
U.K.

or make a request by email: s.holden at cs.ucl.ac.uk