Hacker News Reader

Comment by a-nikolaev | Hacker News Reader

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

View on HN

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.

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.

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"

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.

Reply on news.ycombinator.com