Kekuatan Komputasi Jaringan Saraf Tiruan?

Katakanlah kita memiliki jaringan saraf maju umpan tunggal dengan input k dan satu output. Ini menghitung fungsi dari , cukup mudah untuk melihat bahwa ini memiliki setidaknya kekuatan komputasi yang sama dengan . Hanya untuk bersenang-senang, kita akan memanggil sekumpulan fungsi yang dapat dihitung oleh jaringan saraf lapis tunggal " ". $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace$ $AC^0$ $Neural$

$AC^0$

$AC^0 \subseteq Neural$ $Neural = AC^0$ ? Juga apakah kelas kompleksitas semacam ini telah dipelajari sebelumnya?

cc.complexity-theory circuit-complexity machine-learning ne.neural-evol gabgoh
sumber

A note on terminology -- important information is how many hidden layers there are. Zero hidden layer neural network with one output is just a linear threshold function, and is often (confusingly) called one layer or two layer neural network/perceptron, depending on whether inputs/outputs are considered layers. Also, in AI literature, neural networks are typically defined in terms of sigmoid functions which means that input/outputs are real valued. One hidden layer networks are known to be universal approximators in a sense that any continuous function can be approximated arbitrarily close

Yaroslav Bulatov

Jawaban:

There are some references I could find: General-purpose computation with neural networks: A survey of complexity theoretic results, 2003 and Counting hierarchies: polynomial time and constant depth circuits, 1993.

It appears that neural networks are considered threshold circuits; i.e. those circuits using MAJORITY gates. In (2) it is the case that a depth $d$ neural network has complexity $TC^0_d$ (here's a link to link to complexity zoo entry about $TC^0$ ).

Since $TC^0$ containts $ACC^0$ , which is $AC^0$ with arbitrary MOD gates, then $AC^0 \subset TC^0$ . Also, it is mentioned in the zoo that such circuits with depth 3 are strictly more powerful than those of depth 2.

In On the computational power of sigmoid versus Boolean threshold circuits,1991 it is mentioned that for a constant depth $d$ , Boolean and real-valued threshold circuits (with polynomially bounded weights) are essentially the same.

M. Alaggan
sumber

Interesting, thanks. This is what I was looking for. More interesting still is that

T C^{0}

$TC^0$ has a complete problems ... hmm ...

gabgoh