On the nonlearnability of a single spiking neuron.
We study the computational complexity of training a single spiking neuron N with binary coded inputs and output that, in addition to adaptive weights and a threshold, has adjustable synaptic delays. A synchronization technique is introduced so that the results concerning the nonlearnability of spiking neurons with binary delays are generalized to arbitrary real-valued delays. In particular, the consistency problem for N with programmable weights, a threshold, and delays, and its approximation version are proven to be NP-complete. It follows that the spiking neurons with arbitrary synaptic delays are not properly PAC learnable and do not allow robust learning unless RP = NP. In addition, the representation problem for N, a question whether an n-variable Boolean function given in DNF (or as a disjunction of O(n) threshold gates) can be computed by a spiking neuron, is shown to be coNP-hard.
Síma
Jirí
J
Institute of Computer Science, Academy of Sciences of the Czech Republic, P.O. Box 5, 18207 Prague 8, Czech Republic. sima@cs.cas.cz
Sgall
Jirí
J
D000200:Action Potentials / Q000502:physiology; D000465:Algorithms; D003344:Cortical Synchronization / Q000379:methods*; D008959:Models, Neurological; D016571:Neural Networks, Computer; D009474:Neurons / Q000502:physiology*