8

The Universal Approximation Theorem says that under certain conditions on your activation function, you can approximate any bounded continuous function with a feedforward neural network.

I believe this result can be extended to LSTMs, since with certain choices, the LSTM can be simplified into a feedforward network.

Is there a stronger result for LSTMs?

Mark
  • 181
  • 3

1 Answers1

5

There are previous results that RNNs are turing complete: Siegelmann 1992, Korsky 2019. (They have some slight technical differences). I found this answer which goes into more technical detail about the proof.

Turing completeness should be a stronger statement than universal approximation, since there are perfectly computable but unbounded or discontinuous functions.

I am aware of the results that any computable real-valued total function is continuous (see here). I don't really have the expertise to comment on this, except to say that I'm still sure turing completeness is still strictly more powerful than universal approximation.

shimao
  • 22,706
  • 2
  • 42
  • 81
  • Hmmm, that's the same Siegelmann who later published a paper claiming that NNets can go beyond the Turing limit, a paper which is mathematically unsound and was rebuked by many prominent researchers, and was ignored by the theoretical CS community, but unfortunately keeps coming in various philosophy of ML and philosophy of mind discussions :-( – Skander H. Jan 20 '20 at 22:55
  • thanks for that note. i didn't read the siegelmann paper in enough detail to verify correctness, but the fact that there exist several other papers proving turing completness for similar architectures (e.g. transformers) inspires confidence in the result. from a very brief skim of the "beyond the turing limit" article, and some literature search, it seems the "unsound" part is reliance on analog computation, or real arithmetic. fwiw [some other proofs](https://openreview.net/pdf?id=HyGBdo0qFm) work with rational arithmetic (but of arbitrary precision). – shimao Jan 20 '20 at 23:22
  • but then, i expect UAT to also rely on arbitrary precision or real arithmetic, so i don't believe that to be a real objection to the turing completness of RNNs – shimao Jan 20 '20 at 23:24
  • After reading the wikipedia article on turing complete and turing machines, it seems that you're saying that RNNs can solve any problem that can be solved by comptuters. Is that right? – Mark Jan 23 '20 at 04:15
  • yes, something like that. – shimao Jan 23 '20 at 08:55