Approximate, not compute. The function also must be continuous. NNs are good for approximation / interpolation / extrapolation, which makes them quite useful for certain domains of problems. But of course, it does not make them a kind of universal computing machine (in the computability sense, like universal Turing machines).
A visual proof that neural nets can approximate any function
31–40 of 138 posts
Re: A visual proof that neural nets can approximate any function
#32Earlier quoted context omitted.
> First, this doesn't mean that a network can be used to exactly compute any function. Rather, we can get an approximation that is as good as we want. By increasing the number of hidden neurons we can improve the approximation.
Also, the article doesn't mention a crucial part of the universal approximation theorem: It is about functions on compact subsets of R^n, so it doesn't say anything about functions that take the whole of R as input.
It's also important to note the theorem doesn't help you find the right weights, just notes they exist.
Re: A visual proof that neural nets can approximate any function
#33*any continuous function
While we're at it, doesn't the "universality theorem" (as the article calls it) basically follow immediately from the fact that the set of all continuous functions comprises a vector space? If the continuous function is additive, it's linear. If it's nonlinear, you can differentiate it to obtain a linear approximation. A neural network computes linear transformations, so unless I'm missing something I'm a little surp…
Continuous != differentiable.
The standard proof uses some functional analysis techniques but nothing too complicated to show you can get arbitrarily close to any continuous function with an NN. That includes things like step functions whose derivatives are not defined everywhere.
Re: A visual proof that neural nets can approximate any function
#34Any orthonormal ~set~ basis of functions can represent any function. So what?
This is, strictly speaking, not true. Talking about an "orthonormal" basis implies that you have in mind some Hilbert space; but in any such instance there will be interesting functions that are not in this Hilbert space. So consider for example the standard space L^2(R) of square-integrable functions on the real line. This does not contain the function f(x) = 1, as a really dumb example.
Re: A visual proof that neural nets can approximate any function
#35Skimming through the article, I understand that the author...
A) was focusing on functions that take a certain amount of input variables and
B) that the function (that s/he mirrored using the neural net) computes out of it directly one or more of result(s).
C) To do that s/he used a backpropagation network (which is the only model I know very well).
Right or wrong?
EDIT: when I say "directly" I mean that the function(s) does not feed itself.
Re: A visual proof that neural nets can approximate any function
#36Can neural networks solve the halting problem?
No. Neural networks are still computed on Turing machines, which are mathematically proven to not be able to solve the halting problem.
It doesn't matter if neural networks are computed on Turing machines or not. The term "compute" or "computation" is commonly defined by a Turing machine, as all other models have been shown to have equivalent power, and so far there is no indication that the Church-Turing thesis is false. So if one says a model can perform arbitrary computation, it cannot be stronger than a Turing machine, unless one is talking about hypercomputation, which is still largely a conjuncture.
Just my two cents, correct me if I'm wrong.
Re: A visual proof that neural nets can approximate any function
#37Can neural networks solve the halting problem?
[deleted]
Re: A visual proof that neural nets can approximate any function
#38title is false since there exist uncomputable functions, no?
Re: A visual proof that neural nets can approximate any function
#39Earlier quoted context omitted.
It can represent any arbitrary function. If you are using gradient descent, then you'll need the desired loss function to be differentiable with respect to the parameters, but that's a totally different matter.
No, neural networks cannot "represent any arbitrary function". Find a theorem that you think states otherwise, and then read what the theorem actually states.
You're correct, the statement of the theorem refers to continuous functions.
In practice, however, the input to neural networks is represented by floating point values, which is a discrete set. So pick whatever arbitrary function you would like, there is some continuous approximation to that function which is actually equal to it on every floating point value, and that function can be approximated arbitrarily closely by a neural network.
Re: A visual proof that neural nets can approximate any function
#40Approximate, not compute. The function also must be continuous. NNs are good for approximation / interpolation / extrapolation, which makes them quite useful for certain domains of problems. But of course, it does not make them a kind of universal computing machine (in the computability sense, like universal Turing machines).
> NNs are good for approximation / interpolation / extrapolation
Extrapolation? I was under the impression that generalizability of NNs beyond the training data was one of the major problems faced by NNs.