Two NIPS 7 preprints: Query learning, relevance of thermodynamic limit

[P Sollich]

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


Hi all,

the following two papers are now available from the neuroprose archive
(8 pages each, to appear in: Advances in Neural Information Processing
Systems 7, Tesauro G, Touretzky D S and Leen T K (eds.), MIT Press,
Cambridge, MA, 1995). 

Sorry, hardcopies are not available. Any feedback is much appreciated!

Regards,
Peter Sollich

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



          Learning from queries for maximum information gain in 
                     imperfectly learnable problems

                       Peter Sollich, David Saad
              Department of Physics, University of Edinburgh
                        Edinburgh EH9 3JZ, U.K.

  ABSTRACT: In supervised learning, learning from queries rather than from
  random examples can improve generalization performance significantly. 
  We study the performance of query learning for problems where the
  student cannot learn the teacher perfectly, which occur frequently in
  practice.  As a prototypical scenario of this kind, we consider a linear
  perceptron student learning a binary perceptron teacher.  Two kinds of
  queries for maximum information gain, i.e., minimum entropy, are
  investigated: Minimum {\em student space} entropy (MSSE) queries, which
  are appropriate if the teacher space is unknown, and minimum {\em
  teacher space} entropy (MTSE) queries, which can be used if the teacher
  space is assumed to be known, but a student of a simpler form has
  deliberately been chosen.  We find that for MSSE queries, the structure
  of the student space determines the efficacy of query learning, whereas
  MTSE queries lead to a higher generalization error than random examples,
  due to a lack of feedback about the progress of the student in the way
  queries are selected. 


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

     Learning in large linear perceptrons and why the thermodynamic
                   limit is relevant to the real world

                              Peter Sollich
              Department of Physics, University of Edinburgh
                         Edinburgh EH9 3JZ, U.K.


  ABSTRACT: We present a new method for obtaining the response function
  ${\cal G}$ and its average $G$ from which most of the properties of
  learning and generalization in linear perceptrons can be derived.  We
  first rederive the known results for the `thermodynamic limit' of
  infinite perceptron size $N$ and show explicitly that ${\cal G}$ is
  self-averaging in this limit.  We then discuss extensions of our method
  to more general learning scenarios with anisotropic teacher space
  priors, input distributions, and weight decay terms.  Finally, we use
  our method to calculate the finite $N$ corrections of order $1/N$ to $G$
  and discuss the corresponding finite size effects on generalization and
  learning dynamics.  An important spin-off is the observation that
  results obtained in the thermodynamic limit are often directly relevant
  to systems of fairly modest, `real-world' sizes. 
  
----------------------------------------------------------------------------