Number of the records: 1
On the Non-Learnability of a Single Spiking Neuron
- 1.
SYSNO ASEP 0405292 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title On the Non-Learnability of a Single Spiking Neuron Title O nenaučitelnosti jednoho spiking neuronu Author(s) Šíma, Jiří (UIVT-O) RID, SAI, ORCID
Sgall, Jiří (MU-W) RID, ORCID, SAISource Title Neural Computation - ISSN 0899-7667
Roč. 17, č. 12 (2005), s. 2635-2647Number of pages 13 s. Language eng - English Country US - United States Keywords spiking neuron ; consistency problem ; NP-completness ; PAC model ; robust learning ; representation problem Subject RIV BA - General Mathematics R&D Projects GA201/02/1456 GA ČR - Czech Science Foundation (CSF) 1ET100300517 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) LN00A056 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10300504 - UIVT-O (2005-2011) AV0Z10190503 - MU-W (2005-2011) UT WOS 000232530300005 EID SCOPUS 27144501832 DOI 10.1162/089976605774320601 Annotation The computational complexity of training a single spiking neuron N with adjustable synaptic delays and binary coded inputs and output is studied. A synchronization technique is introduced so that the results concerning the non-learnability of spiking neurons with binary delays are generalized to arbitrary delays. In particular, the consistency problem for N with programmable 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, i.e., 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2006
Number of the records: 1