Preprint on query learning in Neuroprose archive

[P Sollich]

FTP-host: archive.cis.ohio-state.edu
FTP-filename: /pub/neuroprose/sollich.queries.ps.Z

The file sollich.queries.ps.Z (16 pages) is now available via anonymous
ftp from the Neuroprose archive.  Title and abstract are given below.
We regret that hardcopies are not available. 

---------------------------------------------------------------------------

                     Query Construction, Entropy and 
                             Generalization 
                       in Neural Network Models


                             Peter Sollich

             Department of Physics, University of Edinburgh,
         Kings Buildings, Mayfield Road, Edinburgh EH9 3JZ, U.K.

                    (To appear in Physical Review E) 


                               Abstract 

    We study query construction algorithms, which aim at improving the
    generalization ability of systems that learn from examples by
    choosing optimal, non-redundant training sets.  We set up a
    general probabilistic framework for deriving such algorithms from
    the requirement of optimizing a suitable objective function;
    specifically, we consider the objective functions entropy (or
    information gain) and generalization error. 
    
    For two learning scenarios, the high-low game and the linear
    perceptron, we evaluate the generalization performance obtained by
    applying the corresponding query construction algorithms and
    compare it to training on random examples.  We find qualitative
    differences between the two scenarios due to the different
    structure of the underlying rules (nonlinear and `non-invertible'
    vs.linear); in particular, for the linear perceptron, random
    examples lead to the same generalization ability as a sequence of
    queries in the limit of an infinite number of examples. 
    
    We also investigate learning algorithms which are ill-matched to
    the learning environment and find that in this case, minimum
    entropy queries can in fact yield a lower generalization ability
    than random examples.  Finally, we study the efficiency of single
    queries and its dependence on the learning history, i.e. on
    whether the previous training examples were generated randomly or
    by querying, and the difference between globally and locally
    optimal query construction. 

---------------------------------------------------------------------------
 Peter Sollich                           Dept. of Physics
                                         University of Edinburgh
 e-mail: P.Sollich at ed.ac.uk              Kings Buildings
 Tel. +44-31-650 5236                    Mayfield Road
                                         Edinburgh EH9 3JZ, U.K.
---------------------------------------------------------------------------