On the Non-Learnability of a Single Spiking Neuron

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F05%3A00405292" target="_blank" >RIV/67985807:_____/05:00405292 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On the Non-Learnability of a Single Spiking Neuron

Original language description

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.

Czech name

O nenaučitelnosti jednoho spiking neuronu

Czech description

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 spikingneuronu 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 disjunkciO(n) prahových hradel) lze počítat pomocí spiking neuronu, je coNP-těžký.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2005

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Neural Computation

ISSN

0899-7667

e-ISSN

—

Volume of the periodical

17

Issue of the periodical within the volume

-

Country of publishing house

US - UNITED STATES

Number of pages

13

Pages from-to

2635-2647

UT code for WoS article

—

EID of the result in the Scopus database

—