Technical Report Series in Neural and Computational Learning

[John Shawe-Taylor]

The European Community ESPRIT Working Group in Neural and Computational 
       Learning Theory (NeuroCOLT): several new reports available

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-022:
----------------------------------------
Option price forecasting using artificial neural networks 
by A. Fiordaliso, Universite de Mons-Hainaut

Abstract: (Paper is in French)
The problem considered here, in forecasting the price of a call option on a
short term interest rate future, namely the 3 months Eurodollar (ED3). The
aim of our research is to build up Artificial Neural Network models (ANN)
that could be integreated in a fuzzy expert system to dynamically manage 
an option portfolio.  We detail some problems and techniques related to
the set up of ANN models for univariate and multivariate previsions.  We 
compare our results with some other forecasting techniques.


----------------------------------------
NeuroCOLT Technical Report NC-TR-95-041:
----------------------------------------
A General Feedforward Neural Network Model
by  C\'edric GEGOUT, Bernard GIRAU and Fabrice ROSSI
    Ecole Normale Sup\'erieure de Lyon, Ecole Normale Sup\'erieure
    de Paris, THOMSON-CSF/SDC/DPR/R4, Bagneux, France

Abstract:
In this paper, we generalize a model proposed by L\'eon Bottou and
Patrick Gallinari. This model gives a general mathematical description
of feedforward neural networks, for which standard models, such as
Multi-Layer Perceptrons or Radial Basis Function based neural networks,
are only particular cases. A generalized back-propagation, which gives
an efficient way to compute the differential of the function computed
by the neural network, is introduced and carefully proved. We also
introduce an evaluation of the theoretical time needed to compute the
differential with the help of both direct algorithm and
back-propagation.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-043:
----------------------------------------
On-line Learning with Malicious Noise and the Closure Algorithm
by Peter Auer, IGI, Graz University of Technology
   Nicol\`o Cesa-Bianchi, DSI, University of Milan

Abstract:
We investigate a variant of the on-line learning model for classes of
$\Bool$-valued functions (concepts) in which the labels of a certain
amount of the input instances are corrupted by adversarial noise.  We
propose an extension of a general learning strategy, known as ``Closure
Algorithm'', to this noise model, and show a worst-case mistake bound
of $m + (d+1)K$ for learning an arbitrary intersection-closed concept
class $\scC$, where $K$ is the number of noisy labels, $d$ is a
combinatorial parameter measuring $\scC$'s complexity, and $m$ is the
worst-case mistake bound of the Closure Algorithm for learning $\scC$
in the noise-free model.  For several concept classes our extended
Closure Algorithm is efficient and can tolerate a noise rate up to the
information-theoretic upper bound.  Finally, we show how to efficiently
turn any algorithm for the on-line noise model into a learning
algorithm for the PAC model with malicious noise.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-044:
----------------------------------------
Neural Networks with Quadratic VC Dimension
by  Pascal Koiran, Ecole Normale Sup\'erieure de Lyon
    Eduardo D. Sontag, Rutgers University

Abstract:
This paper shows that neural networks which use continuous activation
functions have VC dimension at least as large as the square of the
number of weights $w$.  This result settles a long-standing open
question, namely whether the well-known $O(w \log w)$ bound, known for
hard-threshold nets, also held for more general sigmoidal nets.
Implications for the number of samples needed for valid generalization
are discussed.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-045:
----------------------------------------
Learning Internal Representations (Short Version)
by Jonathan Baxter, Royal Hollloway, University of London

Abstract:
Probably the most important problem in machine learning is the
preliminary biasing of a learner's hypothesis space so that it is
small enough to ensure good generalisation from reasonable training
sets, yet large enough that it contains a good solution to the problem
being learnt.  In this paper a mechanism for {\em automatically}
learning or biasing the learner's hypothesis space is introduced.  It
works by first learning an appropriate {\em internal representation}
for a learning environment and then using that representation to bias
the learner's hypothesis space for the learning of future tasks drawn
from the same environment.

An internal representation must be learnt by sampling from {\em many
similar tasks}, not just a single task as occurs in ordinary machine
learning. It is proved that the number of examples $m$ {\em per task}
required to ensure good generalisation from a representation learner
obeys $m = O(a+b/n)$ where $n$ is the number of tasks being learnt and
$a$ and $b$ are constants. If the tasks are learnt independently ({\em
i.e.} without a common representation) then $m=O(a+b)$.  It is argued
that for learning environments such as eech and character recognition
$b\gg a$ and hence representation learning in these environments can
potentially yield a drastic reduction in the number of examples
required per task. It is also proved that if $n = O(b)$ (with
$m=O(a+b/n)$) then the representation learnt will be good for learning
novel tasks from the same environment, and that the number of examples
required to generalise well on a novel task will be reduced to $O(a)$
(as opposed to $O(a+b)$ if no representation is used).

It is shown that gradient descent can be used to train neural network
representations and the results of an experiment are reported in which a
neural network representation was learnt for an environment consisting
of {\em translationally invariant} Boolean functions. The experiment

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-046:
----------------------------------------
Learning Model Bias
by Jonathan Baxter, Royal Hollloway, University of London

Abstract:
In this paper the problem of {\em learning} appropriate domain-specific
bias is addressed. It is shown that this can be achieved by learning
many related tasks from the same domain, and a sufficient bound is
given on the number tasks that must be learnt.  A corollary of the
theorem is that in appropriate domains the number of examples required
per task for good generalisation when learning $n$ tasks scales like
$\frac1n$. An experiment providing strong qualitative support for the
theoretical results is reported.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-047:
----------------------------------------
The Canonical Metric for Vector Quantization
by Jonathan Baxter, Royal Hollloway, University of London

Abstract:
To measure the quality of a set of vector quantization points a means
of measuring the distance between two points is required. Common
metrics such as the {\em Hamming} and {\em Euclidean} metrics, while
mathematically simple, are inappropriate for comparing speech signals
or images.  In this paper it is argued that there often exists a
natural {\em environment} of functions to the quantization process (for
example, the word classifiers in speech recognition and the character
classifiers in character recognition) and that such an enviroment
induces a {\em canonical metric} on the space being quantized.  It is
proved that optimizing the {\em reconstruction error} with respect to
the canonical metric gives rise to optimal approximations of the
functions in the environment, so that the canonical metric can be
viewed as embodying all the essential information relevant to learning
the functions in the environment.  Techniques for {\em learning} the
canonical metric are discussed, in particular the relationship between
learning the canonical metric and {\em internal representation
learning}.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-048:
----------------------------------------
The Complexity of Query Learning Minor Closed Graph Classes
by Carlos Domingo, Tokyo Institute of Technology
   John Shawe-Taylor, Royal Holloway, University of London

Abstract:
The paper considers the problem of learning classes of graphs closed
under taking minors. It is shown that any such class can be properly
learned in polynomial time using membership and equivalence queries.
The representation of the class is in terms of a set of minimal
excluded minors (obstruction set).  Moreover, a negative result for
learning such classes using only equivalence queries is also provided,
after introducing a notion of reducibility between query learning
problems.

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-049:
----------------------------------------
Generalisation of A Class of Continuous Neural Networks
by John Shawe-Taylor and Jieyu Zhao, Royal Holloway, University of London

Abstract:
We propose a way of using boolean circuits to perform real valued
computation in a way that naturally extends their boolean
functionality.  The functionality of multiple fan in threshold gates in
this model is shown to mimic that of a hardware implementation of
continuous Neural Networks.  A Vapnik-Chervonenkis dimension and sample
size analysis for the systems is performed giving best known sample
sizes for a real valued Neural Network.  Experimental results confirm
the conclusion that the sample sizes required for the networks are
significantly smaller than for sigmoidal networks.


-----------------------
The Report NC-TR-95-011 can be accessed and printed as follows 

% ftp cscx.cs.rhbnc.ac.uk  (134.219.200.45)
Name: anonymous
password: your full email address
ftp> cd pub/neurocolt/tech_reports
ftp> binary
ftp> get nc-tr-95-022.ps.Z
ftp> bye
% zcat nc-tr-95-022.ps.Z | lpr -l

Similarly for the other technical report.

Uncompressed versions of the postscript files have also been
left for anyone not having an uncompress facility.

A full list of the currently available Technical Reports in the 
Series is held in a file `abstracts' in the same directory.

The files may also be accessed via WWW starting from the NeuroCOLT homepage:

http://www.dcs.rhbnc.ac.uk/neural/neurocolt.html


Best wishes
John Shawe-Taylor