14

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?

András Salamon
  • 19,000
  • 3
  • 64
  • 150
gabgoh
  • 1,548
  • 12
  • 22
  • 1
    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 Nov 04 '10 at 18:33

1 Answers1

17

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.

Mohammad Alaggan
  • 1,812
  • 18
  • 29
  • Interesting, thanks. This is what I was looking for. More interesting still is that $TC^0$ has a complete problems ... hmm ... – gabgoh Nov 04 '10 at 05:34