10
$\begingroup$

It is proven that neural networks with rational weights has the computational power of the Universal Turing Machine Turing computability with Neural Nets. From what I get, it seems that using real-valued weights yields even more computational power, though I'm not certain of this one.

However, is there any correlation between the computational power of a neural net and its activation function? For example, if the activation function compares the input against a limit of a Specker sequence (something you can't do with a regular Turing machine, right?), does this make the neural net computationally "stronger"? Could someone point me to a reference in this direction?

$\endgroup$
  • $\begingroup$ What do you mean by computational power? $\endgroup$ – edA-qa mort-ora-y Jun 13 '12 at 5:18
  • $\begingroup$ @edA-qamort-ora-y I've made some edits to clarify the question. If you have any other edit suggestions, I'd be glad to accomodate them, too $\endgroup$ – K.Steff Jun 13 '12 at 21:46
12
$\begingroup$

Just a note:

  • rational-weighted recurrent $NN$s having boolean activation functions (simple thresholds) are equivalent to finite state automata (Minsky, "Computation: finite and infinite machines", 1967);

  • rational-weighted recurrent $NN$s having linear sigmoid activation functions are equivalent to Turing Machines (Siegelmann and Sontag, "On the computational power of neural nets", 1995);

  • real-weighted recurrent $NN$s having linear sigmoid activation functions are more powerful than Turing Machines (Siegelmann and Sontag, "Analog computation via neural networks", 1993);

but ...

$\endgroup$
5
$\begingroup$

I'm going to take the easy solution and say "Yes". Consider an activation function which accepts any inputs and simply returns a constant value (that is, it ignores the inputs). This network always results in a constant output, and thus the computational power (likely by any definition) of this network is zero. It is not capable of calculating anything.

This is enough to show a correlation between the activation function on the the power of the network. It of course does not show, nor disprove, that a network could have more power than a universal turing machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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