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

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

#111

Post by mkl » Sun, Apr 21, 2019, 10:12 AM UTC

Gravityloss wrote: post #105

mkl wrote: post #77

I think you can explain it even more clearly with smooth relative shifts, rather than sharp bump functions. I made a quick demo: https://www.desmos.com/calculator/rfaqogkbmy Drag the sliders for w and n to change how step-like the sigmoids are and how many are combined. The purple lines are the sigmoids, relative changes at each (regularly spaced) position, which are added together to make the blue approximation to t…

This deserves its own submission. Maybe the number of neurons slider could be logarithmic?

Done: https://news.ycombinator.com/item?id=19711416

I couldn't find a nice way of making the slider logarithmic (in Desmos the only way to do it is with an intermediate variable, which is kind of confusing), so I reduced the maximum number on the slider. I also fixed a bug.

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

#112

Post by [deleted] » Sun, Apr 21, 2019, 11:09 AM UTC

pauljurczak wrote: post #107

bhl wrote: post #85

Earlier quoted context omitted.

The line between approximate and compute is a blurry one: some may say if the polynomial approximation depends on log of the error, meaning you can exponentially get better with each step, computation and approximation are the same.

My elementary school teacher would disagree: 2+2=4 not somewhere around 3.997.

[deleted]

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

#113

Post by fluffything » Sun, Apr 21, 2019, 11:17 AM UTC

So can any lagrange polynomial, Fourier series, ...

The real question is whether the approximation is a good one:

- can you prove error bounds ?

- can you bound the maximum error?

- is it efficient ? (low storage, low computational effort)

- is it fast to build? (low computational effort of coefficients)

- derivatives: how well does it approximate gradients, what's the error on the gradient, is it bounded? can one bound it, how fast can one evaluate them, etc.

- there are many other interesting properties: https://en.wikipedia.org/wiki/Approximation_theory

From pretty much every single aspect of approximation theory, neural nets are one of the worst methods to approximate a continuous function. If you were to make an analogy with sorting algorithms, they would be worse than bogosort. There are no error bounds, you can't bound the maximum error, computing their coefficients is very slow (training, needs GPUs, ...), they require a lot of storage and computational power to evaluate, ...

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

#114

Post by 0815test » Sun, Apr 21, 2019, 11:29 AM UTC

fluffything wrote: post #113

So can any lagrange polynomial, Fourier series, ... The real question is whether the approximation is a good one: - can you prove error bounds ? - can you bound the maximum error? - is it efficient ? (low storage, low computational effort) - is it fast to build? (low computational effort of coefficients) - derivatives: how well does it approximate gradients, what's the error on the gradient, is it bounded? can one bo…

> From pretty much every single aspect of approximation theory, neural nets are one of the worst methods to approximate a continuous function.

What about scalability? I don't know of many approximation methods that can routinely work with the amount of coefficients, datapoints, dimensionality of data etc. that neural networks are coping with. (Though AIUI compressed sensing methods might come close; compressed sensing can be seen as a kind of approximation as well.)

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

#115

Post by simonster » Sun, Apr 21, 2019, 12:02 PM UTC

0815test wrote: post #114

fluffything wrote: post #113

So can any lagrange polynomial, Fourier series, ... The real question is whether the approximation is a good one: - can you prove error bounds ? - can you bound the maximum error? - is it efficient ? (low storage, low computational effort) - is it fast to build? (low computational effort of coefficients) - derivatives: how well does it approximate gradients, what's the error on the gradient, is it bounded? can one bo…

> From pretty much every single aspect of approximation theory, neural nets are one of the worst methods to approximate a continuous function. What about scalability? I don't know of many approximation methods that can routinely work with the amount of coefficients, datapoints, dimensionality of data etc. that neural networks are coping with. (Though AIUI compressed sensing methods might come close; compressed sensin…

Yes, neural nets are successful is in large part because they are asymptotically more efficient than other models. Training time is O(n) with O(1) memory, and prediction time is O(1) with O(1) memory. Compare to e.g. kernel methods, which have nicer theory behind them, but kernel least squares is O(n^3) with O(n^2) memory to fit and O(n^2) with O(n^2) memory to predict. The coefficients are larger for neural nets, but if your data are big enough, the asymptotics win out.

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

#116

Post by Certhas » Sun, Apr 21, 2019, 12:12 PM UTC

xtacy wrote: post #53

13415 wrote: post #47

Earlier quoted context omitted.

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

Yes, the claims are pretty much in the same spirit. Although the first (Weierstrass's) theorem [1] was stated for real-valued functions in a 1-D closed interval [a, b], Stone-Weirstrass is a generalisation of the above theorem [2] that's applicable in more general scenarios. Here is the formal statement: - [1] http://mathworld.wolfram.com/WeierstrassApproximationTheorem... - [2] http://mathworld.wolfram.com/Stone-Wei…

There are many such ways to approximate somewhat arbitrary functions. Reproducing Kernel Hilbert Spaces for example.

The fact that NN can reproduce arbitrary functions is decidedly not what makes them special...

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

#117

Post by blamestross » Sun, Apr 21, 2019, 1:14 PM UTC

simonster wrote: post #115

0815test wrote: post #114

Earlier quoted context omitted.

> From pretty much every single aspect of approximation theory, neural nets are one of the worst methods to approximate a continuous function. What about scalability? I don't know of many approximation methods that can routinely work with the amount of coefficients, datapoints, dimensionality of data etc. that neural networks are coping with. (Though AIUI compressed sensing methods might come close; compressed sensin…

Yes, neural nets are successful is in large part because they are asymptotically more efficient than other models. Training time is O(n) with O(1) memory, and prediction time is O(1) with O(1) memory. Compare to e.g. kernel methods, which have nicer theory behind them, but kernel least squares is O(n^3) with O(n^2) memory to fit and O(n^2) with O(n^2) memory to predict. The coefficients are larger for neural nets, bu…

Training time for a NN is not O(n), it is a function of the dataset size and the complexity of NN to approximate a given function. Similarly the memory cost is also a function of the size of the network required. The same is true for prediction time and memory costs. If you data are big enough, all the O(1) lies we tell ourselves start breaking down.

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

#118

Post by allthing » Sun, Apr 21, 2019, 2:00 PM 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).

I believe the universal approximation theorem is for a single hidden layer. When more layers are added arbitrary functions can be approximated.

From section 4.6.2 of Tom Mitchell's Machine Learning book: "Arbitrary functions. Any function can be approximated to arbitrary accuracy by a network with three layers of units (Cybenko 1988)."

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

#119

Post by zepearl » Sun, Apr 21, 2019, 2:29 PM UTC

mkl wrote: post #79

zepearl wrote: post #35

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

If you want to know the details, you should read the article more thoroughly. There is no back-propagation (or any training) involved, as this article is about what kinds of things neural networks can do in principle. I.e. how we can be sure that neural networks can in theory solve some problem we have. In practice, you have to actually find a network (by training) that solves your problem with a reasonable amount of…

Ok, thanks for the explanation.

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

#120

Post by simonster » Sun, Apr 21, 2019, 3:39 PM UTC

blamestross wrote: post #117

simonster wrote: post #115

Earlier quoted context omitted.

Yes, neural nets are successful is in large part because they are asymptotically more efficient than other models. Training time is O(n) with O(1) memory, and prediction time is O(1) with O(1) memory. Compare to e.g. kernel methods, which have nicer theory behind them, but kernel least squares is O(n^3) with O(n^2) memory to fit and O(n^2) with O(n^2) memory to predict. The coefficients are larger for neural nets, bu…

Training time for a NN is not O(n), it is a function of the dataset size and the complexity of NN to approximate a given function. Similarly the memory cost is also a function of the size of the network required. The same is true for prediction time and memory costs. If you data are big enough, all the O(1) lies we tell ourselves start breaking down.

By this logic, (naive) matrix multiplication is not O(n^3) because it is a function of the precision required. The size of the neural network required to approximate a given function to within some epsilon does not change with the dataset size.