A visual proof that neural nets can approximate any function • Hacker News Board

Re: A visual proof that neural nets can approximate any function

#91

Post by dragon96 » Sun, Apr 21, 2019, 5:13 AM UTC

nisuni wrote: post #48

braised_babbage wrote: post #34

Earlier quoted context omitted.

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 fun…

> You are nitpicking, and completely missing my point.

> I was just pointing out that there exists much cheaper ways of representing any function. Therefore the article seems very unexciting to me.

To be fair, your original comment didn't really make a point. What kind of cheaper representations do you have in mind? What makes an orthogonal basis of functions too "expensive" a representation for your taste?

> I would say that all non-pathological functions you can think of are there!

I'd argue that most "real functions" that we care to learn (e.g. mappings between high dimensional data and labels) are pathological. In this sense, we should really care about the completeness of these spaces, perhaps even more than the well-behaved ones.

Re: A visual proof that neural nets can approximate any function

#92

Post by Too » Sun, Apr 21, 2019, 5:46 AM UTC

personjerry wrote: post #63

I skimmed it, but at a glance, isn't this almost identical to the Taylor Series? https://en.wikipedia.org/wiki/Taylor_series

Fourier transforms also smell quite similar. With those you also know how many samples you need to represent a function which changes at some known maximum frequency, using the Nyquist theorem. Is there anything translatable with neural nets? Like would you be able to prove you need X nr of neurons to represent a given function?

It seems the choice of function inside the neuron is kindof arbitary or is it locked to the sigmoid function? If so you could put cos and i*sin as function in your neurons and your neural net essentially becomes DFT?

https://en.wikipedia.org/wiki/Discrete_Fourier_transform

Re: A visual proof that neural nets can approximate any function

#93

Post by czr » Sun, Apr 21, 2019, 5:46 AM UTC

sgillen wrote: post #67

a-nikolaev wrote: post #31

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).

Feedforward neural networks are not turing complete but recurrent neural networks are.

While "RNNs are Turing-complete" is true in theory under certain assumptions, it is not true in practice. See slide 12 and on here (https://uclmr.github.io/nampi/2016/talk_slides/grefenstette-...) for some discussion.

Re: A visual proof that neural nets can approximate any function

#94

Post by rodionos » Sun, Apr 21, 2019, 5:55 AM UTC

For an alternative approach, if you treat this function as a time series where x is time, you can get a reasonably good approximation by performing SVD of the trajectory matrix and building the forecast from the principal components (eigen vectors) using a recurrent formula.

Here's an example:

https://apps.axibase.com/chartlab/9922f98f

* Chart 1. Function value for x in [0, 1).

* Chart 2. Function value for x in [0, 2).

* Chart 3. Function value for x in [0, 1) and extrapolated values for x in [1, 2).

Re: A visual proof that neural nets can approximate any function

#95

Post by uuwp » Sun, Apr 21, 2019, 6:03 AM UTC

Of course they can, because an NN can be any function. If we can pick tanh as the "activation" then we can as easily pick arctan as the activation ans say our NN computes arctan. What an achievement! A better question is whether conv+relu based NNs can approximate any function. But that's most likely false because there are many weird functions that are impossible to compute, not even approximate (I'm talking about those curious counter-examples in math).

Re: A visual proof that neural nets can approximate any function

#96

Post by DavidSJ » Sun, Apr 21, 2019, 6:18 AM UTC

uuwp wrote: post #95

Of course they can, because an NN can be any function. If we can pick tanh as the "activation" then we can as easily pick arctan as the activation ans say our NN computes arctan. What an achievement! A better question is whether conv+relu based NNs can approximate any function. But that's most likely false because there are many weird functions that are impossible to compute, not even approximate (I'm talking about t…

This is a non sequitur in this context. The universality described here depends only on changing connection weights, not the neuronal activation functions. An important caveat is the approximated function must be continuous, but that covers a very large family.

Re: A visual proof that neural nets can approximate any function

#97

Post by killjoywashere » Sun, Apr 21, 2019, 6:20 AM UTC

velcroscientist wrote: post #84

electricslpnsld wrote: post #40

Earlier quoted context omitted.

> 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.

You're correct. As long as your test set remains within the training distribution, you can expect the NN to be well behaved. However, its behavior is undefined for testing data out of training distribution. There is a lot of work on detecting out of distribution inputs, regularizing NNs to follow a simple prior, etc. but the core problem remains because NNs learn from data. Extrapolation is something that symbolic sy…

Let's say I have an interesting problem, like classifying cancer from images. What are some classes of symbolic systems that can reason about types of cancer the system wasn't trained on? Even humans don't know what to do until they've seen it. And then, the grown up answer is "variance is infinite when N=1"

Re: A visual proof that neural nets can approximate any function

#98

Post by DavidSJ » Sun, Apr 21, 2019, 6:23 AM UTC

personjerry wrote: post #63

I skimmed it, but at a glance, isn't this almost identical to the Taylor Series? https://en.wikipedia.org/wiki/Taylor_series

Taylor series only approximate an (infinitely differentiable) function well locally, i.e. in some neighborhood of the approximation point. There are other methods applicable to less smooth functions and which approximate well uniformly (bounding the maximum absolute error) or by some other metric (e.g. L2 distance — integrated squared error).

Re: A visual proof that neural nets can approximate any function

#99

Post by dang » Sun, Apr 21, 2019, 6:46 AM UTC

a-nikolaev wrote: post #31

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).

Ok we'll give you some approximation and some continuousness in the title above.

Re: A visual proof that neural nets can approximate any function

#100

Post by mturmon » Sun, Apr 21, 2019, 7:43 AM UTC

a-nikolaev wrote: post #31

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).

Because of Lusin’s theorem, the much larger class of measurable functions is approximated by continuous functions across almost all of their domain. So continuity isn’t a major restriction here.