On the Non-Learnability of a Single Spiking Neuron

0405292 - UIVT-O 330614 RIV US eng J - Článek v odborném periodiku
Šíma, Jiří - Sgall, Jiří
On the Non-Learnability of a Single Spiking Neuron.
[O nenaučitelnosti jednoho spiking neuronu.]
Neural Computation. Roč. 17, č. 12 (2005), s. 2635-2647. ISSN 0899-7667. E-ISSN 1530-888X
Grant CEP: GA ČR GA201/02/1456; GA AV ČR 1ET100300517; GA MŠMT LN00A056; GA MŠMT(CZ) 1M0545
Výzkumný záměr: CEZ:AV0Z10300504; CEZ:AV0Z10190503
Klíčová slova: spiking neuron * consistency problem * NP-completness * PAC model * robust learning * representation problem
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 2.591, rok: 2005

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.

Studujeme výpočetní složitost trénování jednoho spiking neuronu N s binárně kódovanými vstupy a výstupem, který má kromě adaptivních vah a prahu nastavitelná synaptická zpoždění. Zavádíme synchronizační techniku, která výsledky o nenaučitelnosti spiking neuronu s binárními zpožděními zobecňuje pro libovolná reálná zpoždění. Konkrétně je ukázáno, že problém konzistence pro N s programovatelnými vahami, prahem a zpožděními, a jeho aproximační verze jsou NP-úplné. Z toho vyplývá, že spiking neurony s libovolnými synaptickými zpožděními nejsou naučitelné v rámci vlastního PAC modelu a nepřipouští robustní učení, pokud neplatí RP=NP. Navíc ukážeme, že problém reprezentace, tj. otázka, zda booleovskou funkci n proměnných v DNF (nebo vyjádřenou jako disjunkci O(n) prahových hradel) lze počítat pomocí spiking neuronu, je coNP-těžký.
Trvalý link: http://hdl.handle.net/11104/0125473