5 ms·
Approximate, not compute. The function also must be continuous. NNs are good for approximation / interpolation / extrapolation, which makes them quite useful fo
by a-nikolaev 8y ago
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).
- electricslpnsld 8y ago> 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.
- johnwatson11218 8y agoWhen 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.
- Cybiote 8y agoWhat 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.
- deleted 8y ago[deleted]
- YeGoblynQueenne 8y agoWhat 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_cvpr11.pdf https://people.csail.mit.edu/torralba/publications/datasets_...
- tel 8y agoNot 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.
- velcroscientist 8y agoYou'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.
- killjoywashere 8y agoLet'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"
- contravariant 8y agoI reckon piecewise continuity is enough.
- whatshisface 8y agoNeural networks can't be discontinuous, even piecewise, because you wouldn't be able to differentiate at the discontinuities.
- dual_basis 8y agoYou're talking about training. That's a totally different question than approximation and representability.
- edflsafoiewq 8y agoIf that was the reason, the argument would demand the function be differentiable, not just continuous, wouldn't it?
- contravariant 8y agoPiecewise 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.
- tprice7 8y ago"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.
- deleted 8y ago[deleted]
- analog31 8y agoDo 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.
- 13415 8y agoWait 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!
- xtacy 8y agoYes, 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.html http://mathworld.wolfram.com/WeierstrassApproximationTheorem... - [2] http://mathworld.wolfram.com/Stone-WeierstrassTheorem.html http://mathworld.wolfram.com/Stone-WeierstrassTheorem.html Neural Networks use a different "basis" (sigmoid, ReLU, etc.), but the underlying idea shares the same spirit.
- mturmon 8y agoYes. 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.
- Certhas 8y agoThere 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...
- deleted 8y ago[deleted]
- sgillen 8y agoFeedforward neural networks are not turing complete but recurrent neural networks are.
- deleted 8y ago[deleted]
- czr 8y agoWhile "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-nampi.pdf https://uclmr.github.io/nampi/2016/talk_slides/grefenstette-...) for some discussion.
- bhl 8y agoThe 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.
- sl1ck731 8y agoI 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.
- pauljurczak 8y agoMy elementary school teacher would disagree: 2+2=4 not somewhere around 3.997.
- deleted 8y ago[deleted]
- dang 8y agoOk we'll give you some approximation and some continuousness in the title above.
- mturmon 8y agoBecause 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.
- allthing 8y agoI 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)."