On the complexity of learning for a spiking neuron (extended 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. They provide a way of analyzing neural computation that is not captured by the traditional neuron models such as sigmoidal and threshold gates (or “Perceptrons”). We introduce a simple model of a spiking neuron that, in addition to the weights that model the plasticity of synaptic strength, also has variable transmission delays between neurons as programmable parameters. For coding of input and output values two modes are taken into account: binary coding for the Boolean and analog coding for the real-valued domain. We investigate the complexity of learning for a single spiking neuron within the framework of PAC-learnability. With regard to sample complexity, we prove that the VC-dimension is O(nlogn) and, hence, strictly larger than that of a threshold gate. In particular, the lower bound holds for binary coding and even if all weights are kept fixed. The upper bound is valid for the case of analog coding if weights and delays are programmable. With regard to computational complexity, we show that there is no polynomial-time PAClearning algorithm, unless RP = NP, for a quite *Address: Institute for Theoretical Computer Science, Technische Universitgt Graz, Klosterwiesgasse 32/2, A-8010 Graz, Austria. Email: {maass,mschmitt}Qigi.tu-graz.ac.at, http://www.cis.tu-graz.ac.at/igi/ pennisioll to make di&l/hnrd copies ofall or pa11 ofthis mated for perso,,al or &qsroom use is granted without Ike provided chat lhe copia me not made or distributed for profit or commercial advantage. 11~ COPY right notice, the title of the puhlicntiou and it< date appear. ad notice is given thar copyright is hy pemkion of the ACM, Inc. TO copy othemk. to republish, to post on servers or to redistribute lo list%, requires specific permission and/or fee COLT 97 Nashville, Tennesee. USA Copy+1 1997 ACM 0-89791-891-6/97t7..S3.TO restricted spiking neuron that is only slightly more powerful than a Boolean threshold gate: The consistency problem for a spiking neuron using binary coding and programmable delays from (0, l} is NP-complete. This holds even if all weights are kept fixed. The results demonstrate that temporal coding has a surprisingly large impact on the complexity of learning for single neurons.