Preprint available

[Michael Schmitt]

Dear Connectionists,

the following preprint (21 pages) is available at

   http://www.cis.tu-graz.ac.at/igi/maass/96.ps.gz
   (104463 bytes, gzipped PostScript)

or at

   http://www.cis.tu-graz.ac.at/igi/mschmitt/spikingneurons.ps.Z 
   (158163 bytes, compressed PostScript).

TITLE: On the Complexity of Learning for Spiking Neurons with Temporal
Coding

AUTHORS: Wolfgang Maass and Michael Schmitt

ABSTRACT: In a network of spiking neurons a new set of parameters
becomes relevant which has no counterpart in traditional neural network
models (such as threshold or sigmoidal networks): the time that a pulse
needs to travel through a connection between two neurons (also known as
delay of a connection). We investigate the VC-dimension of networks of
spiking neurons where the delays are viewed as programmable parameters
and we prove tight bounds for this VC-dimension. Thus we get
quantitative estimates for the diversity of functions that a network
with fixed architecture can compute with different settings of its
delays. In particular, it turns out that a network of spiking neurons
with $k$ adjustable delays is able to compute a much richer class of
functions than a threshold circuit with $k$ adjustable weights. The
results also yield bounds for the number of training examples that an
algorithm needs for tuning the delays of a network of spiking neurons.
Results about the computational complexity of such algorithms are also
given. 


-- 
Michael Schmitt
Institute for Theoretical Computer Science
TU Graz, Klosterwiesgasse 32/2, A-8010 Graz, Austria
Tel: +43 316 873-5814, Fax: +43 316 873-5805
E-mail: mschmitt at igi.tu-graz.ac.at
http://www.cis.tu-graz.ac.at/igi/mschmitt/