A visual proof that neural nets can approximate any function | Hacker News Reader

A visual proof that neural nets can approximate any function

neuralnetworksanddeeplearning.com

341 pointsantman128 comments

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

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!

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

Neural Networks use a different "basis" (sigmoid, ReLU, etc.), but the underlying idea shares the same spirit.

Yes. A NN consisting of, for example, sigmoids will form an “algebra” that separates points in the sense of the Stone Weierstrass theorem, and the NN approximation result will follow.

All that’s really needed is that the limit of the NN basis function is different at plus versus minus infinity on the real line. This will give you the “separates points “ property.

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

> 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 systems do well, and NNs do not.

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"

When they don't generalize well it usually means you have over trained on your training data. When you take classes on this stuff they have whole sections that talk about trying to detect this and what to do about it e.g. regularization, better models, more training data etc.

What you list remains insufficient to tackle the difficulty of extrapolation. Extrapolation of the kind we're able to do with Physics theories is difficult in the general case for all methods, not just deep learning. With even the relevant variables subject to change, things like distribution shift and non-stationarity are but the tip of the ice-berg.

For neural networks, if you take something basic like sorting a list or multiplying two decimal numbers, the further you are from range the models were trained on, the worse they will do (yes, transformers too). Only exception I can think of are carefully trained Neural GPUs, which will quickly struggle to be 100% correct as you depart simple tasks. While consuming a great deal of computational resources. Program synthesis is the general area, with no approach clearly dominant in the same way deep learning has dominated machine learning.

What is meant above by "generalisation" is generalisation on out-of-sample data, i.e. not the sample on which you train and test your model (whether you have access to the test set or not). If out-of-sample data has a different distribution than the sampled dataset, then you're SOL, regularisation or not.

As a for instance, here's an interesting paper I found out about from HN that describes how image classifiers trained on one standard dataset (ImageNet etc) do much worse on other standard datasets and how it's even possible to identify the dataset a classifier was trained on:

Unbiased look at dataset bias

https://people.csail.mit.edu/torralba/publications/datasets_...

Not strictly true, regularization in various forms can help have expert knowledge apply to create better extrapolation. Parametric models could be thought of as a kind of regularization even.

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.

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.

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.

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.

I think it is important in the context of what people are trying to use NNs for. Most of the time it is some type of classification, in which case there is always a chance it will be completely wrong in the sense that anything other than the expected output is not correct in any way.

Which leads into unknowingly building NNs that are actually building classification networks and not realizing approximations might not fit into your model.

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

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

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.

If that was the reason, the argument would demand the function be differentiable, not just continuous, wouldn't it?

Piecewise continuous functions can be approximated by differentiable ones. You lose some properties though. As you pointed out the derivatives might not converge, or even exist, and the limit converges pointwise at best, not uniformly.

"Piecewise continuous functions can be approximated by differentiable ones."

It depends on how you measure the distance between functions. If you are using the uniform norm (as is used in the universal approximation theorem) then this is false.

Do neural nets need to be continuous functions of the inputs, or of the parameters? My recollection is that it only has to be the latter.

Member of a Sobolev space enough? I think we're just reinventing finite difference and element methods here.

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

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

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.

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 ?

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.

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.

People make far too big a deal of the universal function approximation property of a hidden-layer neural network. Universality should be a basic property of any decent interpolation method.

Piecewise linear regression is a universal function approximator.

And GMMs and 4th order DAEs and a bunch of other things. The really interesting thing is if the sensitivity of the weights to the loss function is a simple function. Best case would be a convex optimization problem, e.g. like SVMs

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 the red function. You can change the function f(x) to see how it handles other possibilities, including piecewise/discontinuous ones like "{x<.5: 0, x>=5: x}".

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.

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

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

Well, in the sense that polynomials are universal approximators too (on a compact domain). See this comment:

https://news.ycombinator.com/item?id=19709834

The Stone-Weierstrass theorem is not related to Taylor series, in fact the target function need not have a derivative, let alone have all higher-order derivatives, a prerequisite for the Taylor series to even exist.

No.

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

"This result tells us that neural networks have a kind of universality."

I don't know what this statement means. What mathematical properties do neural networks have that other functions don't? The ability to approximate continuous functions isn't special. Given 5 points, I can perfectly fit an elephant to your function. And it's not like you are fitting the function with as few parameters as possible.

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.

*any continuous function

Came here to suggest the function that is 1 on the rationals and 0 on the irrationals.

Not continuous.

I think that was the point.

Also can't be computed.

That depends on the input format.

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?

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

One of the things about continuous functions is that they aren't necessarily differentiable, cf. https://en.wikipedia.org/wiki/Weierstrass_function

True, but that was kind of an afterthought of my point. All continuous functions still comprise a vector space.

I don't see how that helps?

> A neural network computes linear transformations

They compute a nonlinear function of an affine transform. Neural networks are nonlinear functions.

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.

Continuous != differentiable.

The standard proof uses some functional analysis techniques but nothing too complicated to show you can get arbitrarily close to any continuous function with an NN. That includes things like step functions whose derivatives are not defined everywhere.

You could also just cite the Weierstrass function, which is continuous everywhere and differentiable nowhere. But that's separate from the meat of my point, which is that C(R) is a vector space.

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.

You're correct, the statement of the theorem refers to continuous functions.

In practice, however, the input to neural networks is represented by floating point values, which is a discrete set. So pick whatever arbitrary function you would like, there is some continuous approximation to that function which is actually equal to it on every floating point value, and that function can be approximated arbitrarily closely by a neural network.

Aren't all total functions continuous?

Weierstrauss function ;)?

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 = 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(0.1)) history = model.fit(celsius_q, fahrenheit_a, epochs=500, verbose=False)

print("Finished training the model")

print(model.predict([100.0])) // it results 211.874 which is not 100% accurate (100×1.8+32=212)

```

What can be done to make this NN 100% accurate for simple linear equation 𝑓=1.8𝑐+32

https://colab.research.google.com/github/tensorflow/examples...

* 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. It controls the effective capacity of the model in a more complicated way than other hyperparameters—the effective capacity of the model is highest when the learning rate is correct for the optimization problem, not when the learning rate is especially large or especially small.

The following code will yield exactly 212 almost every run (using fixed data and a different choice of learning rate):

```

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

```

[0] https://www.deeplearningbook.org/contents/guidelines.html

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

It's the optimization strategy. Optimizers for neural nets are designed to perform well for non-linear problems, which comes at the expense of not providing exact solutions for linear regressions. A general exact solution is not possible for nonlinear, over-specified problems (which is what neural nets are good at), so strategies different than those used in linear regression are necessary.

If you wanted 100% accuracy, technically infinite data points and training time would be required. You could likely get >99% accuracy within a few epochs of training though. With such a simple function you're trying to emulate, your model will very quickly converge.

Neural networks are much better suited for distilling down and compressing very complex high dimensional data though anyways, and you really don't need to be using them for problems like this. It's completely overkill in addition to being very computationally inefficient. There's nothing wrong with just simply using linear regression. In many cases it's the right choice.

In your toy problem case you coded above, you are effectively just doing linear regression, except you added in an Adam gradient descent optimizer instead of just doing least squares, which by the way would have been infinitely faster and immediately given you an answer.

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.

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.

It’s called

https://en.m.wikipedia.org/wiki/Runge's_phenomenon

and can be mitigated eg by non-uniform interpolation grids like chebychev nodes.

Your activation function needs to be linear to be able to achieve fully linear results.

However, this kills the neural network as a general purpose computation device.

Set your weights manually, and you'll see that the network can easily compute any linear function.

If you're interested in classical approximation with polynomials, check out Nick Trefethen's lectures on the subject.

https://people.maths.ox.ac.uk/trefethen/atapvideos.html

Chebfun is pretty cool too!

http://www.chebfun.org

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

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(s) does not feed itself.

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 resources, using the data you have, and that's a whole other issue (in fact, an entire research field!).

Ok, thanks for the explanation.

I just got a downvote => I think that it's not fair to downvote a question, especially without posting the reason for the downvote :(

Isn't this a bit like saying you just created an nth-order polynomial regresion for any set of points x/y that someone hands you? They are essentially the same amount of parameters, and both can only approximate one function. So.... no kidding?

Great book, this is how I learned NNs

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.

How would it be possible to implememnt/approximate a simple SIN or COS function using a neural network? I would like to implement it but I was not able to find out how.

A system mirroring a polynomial has the same properties as a polynomial - gee whizz - that really doesn't deserve to be at the top of of hacker news!

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

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.

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.

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 hypercomputation, which is still largely a conjuncture.

Just my two cents, correct me if I'm wrong.

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.

If you are referring to our modern computers then they are actually computed on finite state machines - just with a lot of states. After all a Turing machine requires unbounded memory.

So I guess neural networks can only compute a very small portion of all possible functions.

> neural nets can approximate any continuous function

So-called "neural nets" are just logistic regression with a fancy name. Seems "deep learning" is just a wavelet transform with a sigmoid basis. (So, boring math stuff we already knew forever, plus marketing mumbo-jumbo.)

> Seems "deep learning" is just a wavelet transform with a sigmoid basis

Well... more like an iterated transform.

You're right, most of the mathematics is very old indeed. What changed was the hardware (parallelism), software (easy-to-use autodiff packages) and the availability of data.

There's a lot of hype in the field, but some of that hype is deserved. Computer vision was practically in crisis in the late 00's and early 10's. No significant progress was being made on problems, and there were few strategic directions to move in that hadn't been done to death already. Then smash: along comes deep learning, which changed everything.

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

Look into neural Turing machines

Wow, it's real! I didn't know running a Turing machine on a neural network is practically possible.

title is false since there exist uncomputable functions, no?

Can it compute y=sin x?

> First, this doesn't mean that a network can be used to exactly compute any function. Rather, we can get an approximation that is as good as we want. By increasing the number of hidden neurons we can improve the approximation.

Also, the article doesn't mention a crucial part of the universal approximation theorem: It is about functions on compact subsets of R^n, so it doesn't say anything about functions that take the whole of R as input.

It's also important to note the theorem doesn't help you find the right weights, just notes they exist.

They can't approximate functions on unbound domain in general case.

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

Downvoted for asking a genuine question?

I think it's because it looks like you didn't read the article, which explains repeatedly that this is a theorem of universality. Any continuous function will work, and sin is continuous.

Check this out: https://www.desmos.com/calculator/rfaqogkbmy

Try changing f(x) to "sin(x)" or whatever you like (e.g. sin(10x) may be more interesting). Then drag the sliders for w (how step-like the purple pieces are) and n (how many pieces to add together). The function f(x) is red, and the approximation is blue.

Any orthonormal ~set~ basis of functions can represent any function. So what?

No, the set must be an orthonormal basis. For example, two Fourier components technically form an orthonormal set, but do not form a complete basis.

Yes, I meant basis. My point still stands: 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!

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

Most functions are pathological? Are you serious?

All physics assumes you are dealing with non-pathological functions, except for some really particular cases. You can do nearly everything in Electromagnetism and nearly all Quantum Mechanics with non pathological functions.

Maybe we have a different definition of pathological, I am using it in the way a physicist would use (i.e. continuous, continuous derivatives, so on)

The physics I've done have only done with n-particle systems, where n is a number I can count on a hand. Likewise, most of the examples I'd learn in a pure math class are either (a) relatively well-behaved objects with nice properties or (b) "pathological" objects that are constructed specifically to prove a counterpoint.

The kind of pathological function that I'm referring to is neither of these. For example, what does the manifold of all 1 second clips of the word "the" look like? If the clip is sampled at 60 Hz, each clip is already in 60d space. I'm inclined to think that it's some unimaginably complicated manifold that would likely fall into the category of "edge cases", which previous commenters have mentioned and it sounds like you're discounting as nitpicking.

I don't know if this aligns with what you mean by a pathological function, and I'm happy to continue having this discussion with a more concrete example of what you mean. :)

Reply on news.ycombinator.com