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

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

#131

Post by fluffything » Sun, Apr 21, 2019, 9:09 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…

People routinely use lagrange polynomials, fourier approximations, etc. with 10^10 or more coefficients and many more data-points. That's often orders of magnitude larger than what training most neural nets for AI need.

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

#132

Post by fluffything » Sun, Apr 21, 2019, 9:11 PM UTC

simonster wrote: post #120

blamestross wrote: post #117

Earlier quoted context omitted.

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.

Do you have a proof that the neural network approximates the function within some epsilon for all possible inputs within some range ?

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

#133

Post by dang » Sun, Apr 21, 2019, 10:07 PM UTC

kmm wrote: post #127

dang wrote: post #99

Earlier quoted context omitted.

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

It can approximate any function, not just continuous ones. It's just that every approximation will be continuous, but pointwise they will converge

Ok, we'll take that bit out.

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

#134

Post by darkkindness » Sun, Apr 21, 2019, 10:29 PM UTC

uuwp wrote: post #130

This proof is largely irrelevant in the real world. An interesting question would be how much can be approximated with a model that has 1 MB worth of weights and can use only relu/tanh/softmax activations.

The first paragraph of the conclusion addresses that this is merely a proof of what is possible, not what is practical:

> The explanation for universality we've discussed is certainly not a practical prescription for how to compute using neural networks! In this, it's much like proofs of universality for NAND gates and the like. For this reason, I've focused mostly on trying to make the construction clear and easy to follow, and not on optimizing the details of the construction. However, you may find it a fun and instructive exercise to see if you can improve the construction.

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

#135

Post by DavidSJ » Mon, Apr 22, 2019, 2:32 AM UTC

uuwp wrote: post #129

DavidSJ wrote: post #96

Earlier quoted context omitted.

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.

I don't think every continuous function can be approximated this way because we can make an infinitely complex, but continuous function that would have any n-th derivative also continuous. I'm thinking about those weird zeta-riemann-style functions. In order to approximate such a function we'd need a huge model that couldn't be computed or stored even by a universe-size perfect computer.

It’s a theorem, so it’s been proven: https://en.wikipedia.org/wiki/Universal_approximation_theore...

Another caveat that I forgot in my previous comment is the domain has to be compact (closed and bounded). But if so, then it doesn’t really matter how weird your continuous function is, because compactness of the domain guarantees uniform continuity, i.e. your delta only depends on epsilon and not x in the epsilon-delta criterion of continuity. That allows you to partition the domain into patches of diameter delta, in which very simple functions are sufficient to approximate within epsilon.

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

#136

Post by dual_basis » Mon, Apr 22, 2019, 12:40 PM UTC

acdc4life wrote: post #125

"No matter what the function, there is guaranteed to be a neural network so that for every possible input, x , the value f(x) or some close approximation) is output from the network" Okay, so what? You require more and more neurons (ie. parameters) to approximate your function better and better. You can do the same with piecewise constant (Riemann sums). You can do this with trig functions too (Fourier transform). "T…

It's a baseline desirable property. It tells us that, at the very least, neutral networks are capable of approximating any continuous function. This isn't true for linear functions, for example, so we wouldn't want to try and model everything using linear functions.

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

#137

Post by simonster » Mon, Apr 22, 2019, 1:55 PM UTC

fluffything wrote: post #132

simonster wrote: post #120

Earlier quoted context omitted.

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.

Do you have a proof that the neural network approximates the function within some epsilon for all possible inputs within some range ?

The universal approximation theorem guarantees that a finite-width neural network that approximates the function to within some epsilon exists. But, regardless of the approximation method, there is no way to certify that a given approximation method is sufficient for an arbitrary continuous function given only a finite number of samples (i.e., without oracle knowledge of the underlying function), which is the typical situation where neural networks are applied. I can construct a continuous function that has an arbitrary (but non-infinite) number of peaks in an arbitrary interval. Thus, any method that approximates the function within some epsilon for all possible inputs within that arbitrary interval must encode an arbitrary amount of information. I can also ensure that whatever the number of samples is, it's not enough to properly approximate the function.

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

#138

Post by tylerhou » Mon, Apr 22, 2019, 5:51 PM UTC

czr wrote: post #14

codesternews wrote: post #4

Any deeplearning expert here. Why Neural network can't compute a linear function Celsius to Fahrenheit 100% accurately. Is it data or is it something can be optimised. ``` celsius_q = np.array([-40, -10, 0, 8, 15, 22, 38], dtype=float) fahrenheit_a = np.array([-40, 14, 32, 46, 59, 72, 100], dtype=float) for i,c in enumerate(celsius_q): print("{} degrees Celsius = {} degrees Fahrenheit".format(c, fahrenheit_a[i])) l0…

* Fix the data. Right now the optimal coefficients on your data (using least-squares) are m=1.79794911, b=31.952525636156476, which yields 211.74743638 when predicting on 100. * Tune the hyperparameters. In particular, tune the learning rate. To quote the Deep Learning Book [0]: > The learning rate is perhaps the most important hyperparameter. If you have time to tune only one hyperparameter, tune the learning rate.…

Code blocks don't work on HN; you need to format all your code with spaces:

    celsius_q = np.array([-40, -10, 0, 8, 15, 22, 38], dtype=float)
    fahrenheit_a = np.array([x * 1.8 + 32 for x in celsius_q], dtype=float)

    for i, c in enumerate(celsius_q):
        print("{} degrees Celsius = {} degrees Fahrenheit".format(c, fahrenheit_a[i]))

    l0 = tf.keras.layers.Dense(units=1, input_shape=[1])
    model = tf.keras.Sequential([l0])

    model.compile(loss='mean_squared_error', optimizer=tf.keras.optimizers.Adam(lr=1.0))
    history = model.fit(celsius_q, fahrenheit_a, epochs=500, verbose=False)

    print("Finished training the model")
    print(model.predict([100.0]))