14
$\begingroup$

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to see that this has at least the same computational power as $AC^0$. Just for fun, we'll call the set of functions computable by a single layer neural network "$Neural$".

It seems, however, that it might have more computational power than $AC^0$ alone.

So ... is $AC^0 \subseteq Neural$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 4, 2010 at 18:33

1 Answer 1

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting, thanks. This is what I was looking for. More interesting still is that $TC^0$ has a complete problems ... hmm ... $\endgroup$
    – gabgoh
    Commented Nov 4, 2010 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.