4 ms·

This is a very misleading title. The result here is not that TM's are recurrent neural networks, it is that it is possible to construct an (infinite) recurrent

by lisper 4y ago

This is a very misleading title. The result here is not that TM's are recurrent neural networks, it is that it is possible to construct an (infinite) recurrent neural network that emulates a TM. But the fact that a TM can be built out of perceptrons is neither surprising nor interesting. It's pretty obvious that you can build a NAND gate out of perceptrons, and so of course you can build a TM out them. In fact, it's probably the case that you can build a NAND gate (and hence a TM) out of any non-linear transfer function. I'd be surprised if this is not a known result one way or the other.

whatshisface 4y ago
I don't remember the name of the theorem, but you can approximate any nonlinear multivariable function arbitrarily with a multi-layer perceptron with any non-polynomial nonlinear function, applied after the linear weights and bias. It has to be non-polynomial because the set of all polynomials is closed under linear combinations, adding a constant, and composition, so if the nonlinear function was (say) x^3 you would only get polynomials out of the model. I'm not sure why that's a problem because polynomial approximations are still useful.
- kkylin 4y ago
  Are you talking about something like this? https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Arnold_representation_theorem https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Arnold_repr...
- jmalicki 4y ago
  https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore...
- tsimionescu 4y ago
  Note that there are two caveats. For one, only continuous functions can be represented. Much more importantly, the theorem doesn't prove that it's possible to learn the necessary weights to approximate any function, just that such weights much exist. With our current methods, only a subset of all possible NNs are actually trainable, so we can only automate the construcion approximations for certain continuous functions (generally those that are differentiable, but there may be exceptions, I'm not as sure).
  - whatshisface 4y ago
    If we're talking about approximation, continuous functions can converge to step functions just fine. Take a regular sigmoid and keep raising the weight to see one example. That's a good point about training though, that theorem doesn't fully explain why NNs work, although it somewhat sounds like it does.
    - mjburgess 4y ago
      Their derivatives, f^n(x) for arbitrary n, do not converge fine. Indeed, even n=1 is usually terrible in practice. Fit a pleasant day-trip velocity curve with a NN and the acceleration would kill you.
      - whatshisface 4y ago
        Wouldn't that be mostly a consequence of the loss function used to compute the distance between the curve and the model output?
    - tsimionescu 4y ago
      There are discontinuous functions which are not steps - one of the more useful ones being tan(x) for any real x. Of course, since tan(x) is piece wise continuous and periodic, it is probably easy to work around in practice.
- joe_the_user 4y ago
  The basic approximation theorem you might be thinking of is known as Kolmagorov's Theorem (dude got around). It's an early theorem, from 1957, that's about the universality of functions of a linear combination of single variable function. But all the other universality theorems refer back to it and don't have their own names, for example; Optimal approximation of continuous functions by very deep ReLU networks by Dmitry Yarotsky [1]. The reference for the original theorem would be On The Structure Of Continuous Functions Of Several Variable, David A. Sprecker [2], [1] http://proceedings.mlr.press/v75/yarotsky18a http://proceedings.mlr.press/v75/yarotsky18a [2] https://www.ams.org/journals/tran/1965-115-00/S0002-9947-1965-0210852-X/S0002-9947-1965-0210852-X.pdf https://www.ams.org/journals/tran/1965-115-00/S0002-9947-196...
IIAOPSW 4y ago
It strikes me as the classical version of a well known result in quantum computing: "nearly any gate set is universal for quantum computing".
otabdeveloper4 4y ago
> infinite This is the key part. "Turing completeness" is just a way of reasoning about infinities. (Anything that can recurse or loop infinitely is eventually Turing-complete.)

by lisper 4y ago

whatshisface 4y ago

I don't remember the name of the theorem, but you can approximate any nonlinear multivariable function arbitrarily with a multi-layer perceptron with any non-polynomial nonlinear function, applied after the linear weights and bias. It has to be non-polynomial because the set of all polynomials is closed under linear combinations, adding a constant, and composition, so if the nonlinear function was (say) x^3 you would only get polynomials out of the model. I'm not sure why that's a problem because polynomial approximations are still useful.

kkylin 4y ago
Are you talking about something like this? https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Arnold_representation_theorem https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Arnold_repr...
jmalicki 4y ago
https://en.wikipedia.org/wiki/Universal_approximation_theorem https://en.wikipedia.org/wiki/Universal_approximation_theore...
tsimionescu 4y ago
Note that there are two caveats. For one, only continuous functions can be represented. Much more importantly, the theorem doesn't prove that it's possible to learn the necessary weights to approximate any function, just that such weights much exist. With our current methods, only a subset of all possible NNs are actually trainable, so we can only automate the construcion approximations for certain continuous functions (generally those that are differentiable, but there may be exceptions, I'm not as sure).
- whatshisface 4y ago
  If we're talking about approximation, continuous functions can converge to step functions just fine. Take a regular sigmoid and keep raising the weight to see one example. That's a good point about training though, that theorem doesn't fully explain why NNs work, although it somewhat sounds like it does.
  - mjburgess 4y ago
    Their derivatives, f^n(x) for arbitrary n, do not converge fine. Indeed, even n=1 is usually terrible in practice. Fit a pleasant day-trip velocity curve with a NN and the acceleration would kill you.
    - whatshisface 4y ago
      Wouldn't that be mostly a consequence of the loss function used to compute the distance between the curve and the model output?
  - tsimionescu 4y ago
    There are discontinuous functions which are not steps - one of the more useful ones being tan(x) for any real x. Of course, since tan(x) is piece wise continuous and periodic, it is probably easy to work around in practice.
joe_the_user 4y ago
The basic approximation theorem you might be thinking of is known as Kolmagorov's Theorem (dude got around). It's an early theorem, from 1957, that's about the universality of functions of a linear combination of single variable function. But all the other universality theorems refer back to it and don't have their own names, for example; Optimal approximation of continuous functions by very deep ReLU networks by Dmitry Yarotsky [1]. The reference for the original theorem would be On The Structure Of Continuous Functions Of Several Variable, David A. Sprecker [2], [1] http://proceedings.mlr.press/v75/yarotsky18a http://proceedings.mlr.press/v75/yarotsky18a [2] https://www.ams.org/journals/tran/1965-115-00/S0002-9947-1965-0210852-X/S0002-9947-1965-0210852-X.pdf https://www.ams.org/journals/tran/1965-115-00/S0002-9947-196...

IIAOPSW 4y ago

It strikes me as the classical version of a well known result in quantum computing: "nearly any gate set is universal for quantum computing".

otabdeveloper4 4y ago

> infinite This is the key part. "Turing completeness" is just a way of reasoning about infinities. (Anything that can recurse or loop infinitely is eventually Turing-complete.)