I'd like to see a neural network that can compute a hash function.
http://cs.nju.edu.cn/lwj/L2H.html
This is just crazy! I can't even begin to understand what is going on... Bravo
A visual proof that neural nets can approximate any function
41–50 of 138 posts
Re: A visual proof that neural nets can approximate any function
#42Approximate, 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).
I reckon piecewise continuity is enough.
Re: A visual proof that neural nets can approximate any function
#43*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…
A vector space with a countable basis to be precise.
The set of all (real) functions is also linear, but is a lot trickier to work with.
Re: A visual proof that neural nets can approximate any function
#44Approximate, 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).
I reckon piecewise continuity is enough.
Neural networks can't be discontinuous, even piecewise, because you wouldn't be able to differentiate at the discontinuities.
Re: A visual proof that neural nets can approximate any function
#45Earlier quoted context omitted.
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…
Well, you're not exactly wrong but what you're saying is a bit weird.
Technically something capable of arbitrary computation in the Turing machine sense can be stronger than a Turing machine (the obvious example being a Turing machine with access to a halting oracle).
Also if you want to show something is limited by the capabilities of a Turing machine it's way easier to point out it's being run on a Turing machine, as opposed to showing it's capable of arbitrary computation (which might not even be sufficient, as I explained above).
As it stands it's not entirely obvious that a neural network with access to arbitrary precision arithmetic might not be more powerful than a Turing machine, but since we couldn't possibly construct a neural network precise enough that's a bit of a moot point.
Re: A visual proof that neural nets can approximate any function
#46Earlier quoted context omitted.
I reckon piecewise continuity is enough.
Neural networks can't be discontinuous, even piecewise, because you wouldn't be able to differentiate at the discontinuities.
You're talking about training. That's a totally different question than approximation and representability.
Re: A visual proof that neural nets can approximate any function
#47Approximate, 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).
Wait a minute, isn't it also the case that according to the Weierstrass approximation theorem any continuous function on a closed interval can be approximated by a polynomial function? And isn't that kind of pointless for practical applications because we also need to avoid overfitting?
To clarify, I'm not trying to make a snippy remark, I just happened to have used polynomial curve fitting before and looked up the Wikipedia page for the Stone-Weierstrass theorem and am trying to figure out the relevance of that post on NNs. Is it essentially the same claim?
Any clarification appreciated!
Re: A visual proof that neural nets can approximate any function
#48Any 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.
You are nitpicking, and completely missing my point. Let me rephrase it.
The original article is about neural networks being able to represent any function (for some definition of any).
I was just pointing out that there exists much cheaper ways of representing any function. Therefore the article seems very unexciting to me.
Btw, you have chose L^2(R) yourself and then used that to show that there are interesting function not in the space you have chosen, quite a circular argument.
Since the article on neural networks never mentions functions defined on a infinite domain, one can easily take L^2([0,1]) or L^2([0,Lambda]) up to some cutoff Lambda. I would say that all non-pathological functions you can think of are there!
Re: A visual proof that neural nets can approximate any function
#49Earlier quoted context omitted.
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…
One of my labs some students curve fitted a sixth order poly onto five data points they collected. The process being measured was y = something something minus ln(x). It fit all five points exactly and smoothly and wildly diverged on either side. The professor was really amused.
Re: A visual proof that neural nets can approximate any function
#50*any continuous function
Aren't all total functions continuous?