Can 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.
A visual proof that neural nets can approximate any function
21–30 of 138 posts
Re: A visual proof that neural nets can approximate any function
#22*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 surprised there's a substantive theorem for this. Is it not a corollary on the fact that we can construct a vector space of all continuous functions?
Re: A visual proof that neural nets can approximate any function
#23[deleted]
Re: A visual proof that neural nets can approximate any function
#24Re: A visual proof that neural nets can approximate any function
#25Re: A visual proof that neural nets can approximate any function
#26*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…
> 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?
Pretty much, but you have to show that neural networks can create a basis in that vector space which is essentially the proof presented in the article.
> If the continuous function is additive, it's linear. If it's nonlinear, you can differentiate it to obtain a linear approximation.
Differentiating to obtain a linear approximation does not give you an arbitrarily good approximation like the theorem does.
> A neural network computes linear transformations, so unless I'm missing something I'm a little surprised there's a substantive theorem for this. Is it not a corollary on the fact that we can construct a vector space of all continuous functions?
Neural networks using sigmoid transfer functions do not compute linear transformations anymore.
Importantly this theorem also states that you can approximate any function with only two hidden layers. A similar proof could not be made for a single hidden layer so it seems that the non-linearity of a single layer is not enough to form a basis for all continuous functions.
Re: A visual proof that neural nets can approximate any function
#27Can it compute y=sin x?
A recurrent network can with ease.
For a vanilla MLP, you'd need to add in a few previous values (ie you'd predict x_{t+1} = f(x_t, ..., x_{t-N}), where f is your neural network and N is some fixed integer).
Re: A visual proof that neural nets can approximate any function
#28*any continuous function
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.
Re: A visual proof that neural nets can approximate any function
#29Earlier quoted context omitted.
Your data is suspiciously rounded off. Just doing linear regression on that data isn't going to give you a perfect fit either.
There is that. And also what I learned in school which is doing linear regression using a function with more degrees of freedom than the data tends to generate garbage. It can match the data points exactly and then be wildly off between them.
A classic demonstration of similar effect - any set of N data points in a time series, e.g. (t,f(t)), can be fit by a N-1 order polynomial to pass through each point. So fit a high order poly to a set of points sampled (esp. with a little noise) from a low order poly. You'll get crazy oscillations, and outside the sampling area it will likely diverge fast. Now add a smoothness term and crank it up until you get more reasonable results - regularization.
It's a simplification, but informative about some ML techniques.
Re: A visual proof that neural nets can approximate any function
#30*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…
One of the things about continuous functions is that they aren't necessarily differentiable, cf. https://en.wikipedia.org/wiki/Weierstrass_function