Preprint: Complexity of learning for spiking neurons

[Michael Schmitt]

Dear colleagues,

the following paper has been accepted for publication in "Information
and Computation" and is available from

http://www.cis.tu-graz.ac.at/igi/maass/96.ps.gz
  or
http://www.ruhr-uni-bochum.de/lmi/mschmitt/spikingneurons.ps.gz
  (24 pages, 136K).

Regards,

Michael Schmitt

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

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

AUTHORS: Wolfgang Maass and Michael Schmitt

ABSTRACT
  Spiking neurons are models for the computational units in biological
  neural systems where information is considered to be encoded mainly
  in the temporal patterns of their activity.  In a network of spiking
  neurons a new set of parameters becomes relevant which has no
  counterpart in traditional neural network models: the time that a
  pulse needs to travel through a connection between two neurons (also
  known as delay of a connection).  It is known that these delays
  are tuned in biological neural systems through a variety of
  mechanisms. In this article we consider the arguably most simple
  model for a spiking neuron, which can also easily be implemented in
  pulsed VLSI. 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
LS Mathematik & Informatik, Fakultaet fuer Mathematik
Ruhr-Universitaet Bochum, D-44780 Bochum, Germany
Phone: ++49 234 700-3209 , Fax: ++49 234 7094-465