12 ms·
A visual proof that neural nets can compute any function
- amelius 5y agoI want to see it compute the Ackermann function.
- W0lf 5y agoGiven that any stock is a function over time as well, there should theoretically exist a neural net that can approximate the stock price for the future? This reasoning is obviously wrong, what is my exact error of thought though?
- fkfkno 5y agoπ was a great movie! https://www.youtube.com/watch?v=ShdmErv5jvs https://www.youtube.com/watch?v=ShdmErv5jvs
- amalcon 5y agoYour mistake is that you left off "given the right inputs". There are a lot of inputs to stock prices that are unlikely to be readily available to your function.
- Bootvis 5y agoDoesn't seem wrong to me, the tricky part is to find this network and convince yourself that it is indeed predicts correctly over the period of interest.
- karelp 5y agoYour reasoning is not wrong, there is a neural net that approximates future stock price. The problem is we don’t know which one :)
- dzaima 5y agoAnd knowing which one it is will probably influence which one it should be, in a halting-problem-esque way.
- vimacs2 5y agoSo it's somewhat akin to the Library of Babel but instead of the set of all possible books, it's the set of all possible functions :p
- hedora 5y agoThose are equivalent as long as you allow for infinite length books.
- Banana699 5y agoNo need for infinite-length books to encode all possible functions, as there are notations to express infinity in finite space (e.g. programs, encoding an infinity of behaviour in a finite number of instructions). The library of babel contain every possible finite description of every possible function.
- hedora 5y agoSure we do. Partition your neurons into a few billion independent networks, embed them on a spinning globe of mostly molten rock, and put each one in a leaky bag of mostly water. Wait long enough, and one leaky bag will emit the number "42". If you get the initial conditions just right (and quantum nondeterminism isn't really a thing), then you'll also get a good approximation to the stock market.
- pawelduda 5y agoIt would be the same as predicting the future, which is not possible using past performance
- callesgg 5y agoIt is not wrong. It is just that the neural network would have to compute a model of the entire world or even the universe on an atomic scale. It would be computationally unfeasible but not theoretically impossible. It is theoretically possible that the universe we live is already being computed on a neural network in some other external universe.
- arghwhat 5y agoThe error is that stock price is not a function over time, but instantaneous demand which we record over time. That demand is a function over an undefined number of variables.
- ddingus 5y agoWe can find a function to express past stock prices. There isn't one for the future, unless said future is somehow predetermined? Is it, given enough input data? Does this discussion then distill down to philosophy? Do living beings have agency, or are they simply very complex NNs? How one answers that speaks to consciousness as much as it does the prospect of a predictive stock price model.
- paskozdilar 5y ago> what is my exact error of thought though? There isn't one, you're just overestimating the value of existence-propositions. In practice, knowing that something exists is not a very useful result - it is often more useful to know that something does NOT exist (e.g. solution to the halting problem).
- max__d 5y agoWith the same type of reasoning, we could plot whatever output our brain gives and there will be some type of neural network that can predict what we'll think/see/feel in the future. What you said and the thing i just said were both ideas i had when starting learning how ai works, sadly it's something we can still not reach.at least for now
- tluyben2 5y agoIf I understand you correctly, we are very far away from that example as that is AGI and then some. You will not see that in your lifetime so ‘we can still’ seems an interesting (overly optimistic?) take on it.
- laichzeit0 5y agoAGI, since it lacks a technical/mathematical definition, can be anything. It’s mere philosophy at this point, actually even vaguer than most philosophical problems.
- posterboy 5y agoAlthough I share your sentiment in general, I would presume that @tluyben's take is fairly true to the broader philosophical view. The ritique of this view being at least as weak as the views on intelligence per se is a drop in the ocean really. Implying, there is a wealth of thought devoted to inteligence! That fact is actually proving the conjecture in a nicely constructive way by itself, that we are thoughtful indeed, if only you believe this axiomatically like. The quintessential theorem was distiled by Descartes, of course, wherefore he is remembered.
- tluyben2 5y agoI meant it to mean, indeed in a vague way, what we call human intelligence or beyond; the parent says to make a neural network that can predict what someone will think/feel in the future, which seems the same or at least indistinguishable from the subject’s human intelligence as it will result in the same outputs. So to create the network implied by the parent, we would have to a) be able to make networks of that (unknown) complexity and b) ‘copy’ , or rather make it learn from the outputs, the current ‘state’ of the subject’s brain in it. That is incredibly far removed from anything cutting edge we know how to do. If it is at all possible. So I was just surprised by their use of language as it seems to imply parent thought we would be closer to or there already with our developments of AI tech.
- nnq 5y agobesides karelp's sister comment, there's also the "obvious" fact that stock price is not a function of time, it's not P(t), it's a function of time and the entire f universe that also evolves through time, more like P(t, U(t, ....)) ....you can simplify things by assuming the laws of physics are deterministic and you only need one instance of the state of the universe, U, so you'd have P(t, U) ...now if you don't explicitly represent U as a parameter, you'll have it implicit in the function. So your "neural network" contains the entire state of the freakin universe (!!). Ergo, contingent on your stance on theologic immanence vs. transcendence, what you'd call "neural network approximation of the stock's price function" is probably quite close to what other call... God (!). (Now, if relativity as we know it is right, you might get aways with a "smaller slice of U" - lear about "light cone". And to phrase this in karelp's explanation context: you'd need to know U to know which of the practically infinitely many such neural networks to pick. The core of (artificial) intelligence is not neural networks in themselves, it's learning, the NN is a quite boring computational structure, but you can implement tractable learning strategies for it, both in code, and in living cells as evolution has shown...)
- DennisP 5y agoAnd you'd have to know the state of U to infinite precision. Which makes me wonder whether neural nets have any hope with a simple chaotic function. Maybe they do but just in the short term, like predicting the weather.
- alexchamberlain 5y agoStock prices are not well modelled as continuous functions- the prices you see are generally trades (discrete function) and the price may or may not have been available to you at the volume you wanted (there are more variables than time).
- posterboy 5y agoContrary to the recent top comment on this, which fails to show that such a net existing could be no coincidence, I guess, the answer to your problem might be deeply physical and information theoretic, as soon as you speak of time. Simply speaking, any model is good enough if the approximation is tolerably accurate. In that sense, crude nets as well as expert systems that trigger off clear signals and ample evidence may already exist. In particular, the way the stockmarkets are distributed the function of time is likely relativistic and every participant is acting under incomplete information even in the infinite limit. Also, you have to be cautious what any function in this context really means, as I imagine it means differentiable functions (after somebody mentioned the Ackermann function, which is not anywhere differentiable).
- visarga 5y agoYour input features are incomplete and mixed with noise. The value of a dice is also a function over time. Can we learn this function with a neural net? No, because our features don't include the nitty gritty details of each throw so it's essentially random.
- ComradePhil 5y agoTheoritically, there exists a model that predicts all future stock prices EXACTLY at any given time in the future, as long as the results are completely isolated from all market participants (i.e. the knowledge of the result is COMPLETELY isolated from the market). Here is how you can theoritically prove it exists: Train a model today so that it is overfitting for a given stock. It would predict everything very accurately upto today. The ONLY way to make sure that the results are completely isolated from the market is to not make the result available to ANYONE (how do you know that an isolated human observer is not leaking data with some unknown phenomena... say quantum entanglement with particles in other people's brains, for example). So, the ONLY way to test the models is back-testing. You can extend that to saying that for any given point in the future (say, this is a reference point), there will be an overtrained model which will backtest perfectly i.e. the theoritical model that works at any time during the past to predict the exact stock price in the future upto the point of reference.
- hprotagonist 5y agoany “well behaved” function.
- qwerty1793 5y agoA number of assumptions seem to be missing from this article. Since the author is using the sigmoid function which is smooth, this argument actually only applies to approximating smooth functions. That is, you dont just need f to be continuous, you need all of its derivatives to exist and all be continuous. Also, since we are only able to have finitely many neurons, we need to be able to approximate f using step functions with definitely many pieces. So this argument can only be used if f is constant outside of a compact region.
- hprotagonist 5y agoat which point, a fourier transform is a hell of a lot cheaper ;)
- joppy 5y agoWhy does the function you are approximating need to be smooth? From the paper cited in the article, all you need is for f to be continuous on a compact subset of R^n.
- j16sdiz 5y agoThe author is taking non-linear neurons. This is, IMO, cheating.
- JustFinishedBSG 5y agoIt's not cheating considering it's not even possible otherwise.
- deleted 5y ago[deleted]
- j16sdiz 5y agoThis is obviously true for non-linear neurons. Who need a proof for that?
- civilized 5y agoWhy do you think it's obvious? Can you spell it out? I hope it's more than "presumably, non-linear neurons can approximate any non-linear function since they both have non-linear in the name".
- programmer_dude 5y agoAll functions can be approximated by the Fourier transform. Look up the equation to see why it applies here (Hint: it is an integral of f(t)e^(t)).
- civilized 5y agoThis is about as far from a proof as we are from the Andromeda Galaxy.
- kovacs_x 5y agovery fitting- https://earthsky.org/astronomy-essentials/earths-night-sky-milky-way-andromeda-merge/#:~:text=The%20Andromeda%20galaxy%20is%20currently,our%20galaxies%20is%20already%20underway https://earthsky.org/astronomy-essentials/earths-night-sky-m....
- The_rationalist 5y ago
- The_rationalist 5y ago
- mjburgess 5y agoThere are many caveats to this, esp. that this "fact" has nothing to do with whether training a neural network on a dataset will be useful. There is often no function to find in solving a problem, ie., there is no mapping from ImageSpace -> DogCatSpace. Ie., most things are genuine ambiguitites --- a stick in a water appears bent, indistinguishably from an actually bent stick in some other transparent fluid. Animals solve the problem of the "ambiguity of inference" by being in the world and being able to experiment. Ie., taking the stick out of the water. A neural network, in this sense, cannot "take the stick out the water" -- it cannot resolve ambiguities. So that it can "approximate functions" is neither necessary nor sufficient for a useful learning system. More significantly, a NN is a very very bad approximator of many functions. Consider approximating a trajectory so that one can then find an acceleration, ie., here we need f(x) to find d2f/dx2 -- NN approximations are typically "OK" at the f(x) level and really really crappy at the df/dx level, because the non-linear functions NNs just glue together are only trainable if theyre very rough. For these, and lots of other reasons, this theoretical approach to learning is largely marketing none-sense. If you go out and actually study the only known systems which learn effectively (ie., animals), one does not find the need for universal approximator theorems in explaining their capacities. These theorems only show that NNs are, like many computational statistical techniques, sufficient for a wide class of "mere approximation" problems that are only narrowly useful within the whole field of learning-as-such.
- benrbray 5y agoWhat techniques are used to estimate trajectories? Would something like a Gaussian Process perform better?
- mjburgess 5y agoWell NNs like GPs are "basically" non-parametric methods, in the sense that one does not start with a known parameterised statistical distribution that comes from domain expertise. These are worst-case techniques when we dont have the option to start with "the right answer", eg., in the case of large datasets where we have no idea how some pixels distribute over cat/dog images. In the case of a trajectory we would likey already know the answer, in the form of just doing some physics. The role of computational stats here then is to start with the known form of the solution and find the specific parameters to fit it. Since we have physics, we can find the "perfect answer" to the trajectory question with very few data points -- and take as many derivatives as we like. Brute-force ML is often used when we dont have theories, making it all the more dangerous; and alas, all the more useful. We can get a 5% improvement on click-thru rate without having any theory of human behavioural psychology --- god knows then, what we are doing to human behaviour when we implement this system. `
- charcircuit 5y agoWhat about a function like f(x) = sin(x)? I feel like when x gets big the error will start to increase.
- qwerty1793 5y agoThis argument only applies to functions on a compact domain. So we should only consider trying to approximate sin(x) when x is in [0, 1], for example.
- deleted 5y ago[deleted]
- CJefferson 5y agoYou are right. The argument is that it can approximate sin(x) over a compact interval, like [0,1]. You answer to that might be "I could approximate over [0,1] with just a lookup table, where I split the input range into n equal sized pieces for increasing values of n", and you'd be right -- the "proof" is basically just doing that. It's one of those things which is nice to show as a basic theory thing (there are approximation methods which can never simulate certain functions), but it's not really of any real value.
- credit_guy 5y agoThis often cited fact is a red herring. Lots of things can compute (or rather approximate) any functions. Piece-wise constant functions obviously can approximate anything, but nobody's giddy about using piece-wise constant functions for any numerical purpose (if they do, and they often do, they don't point with pride of their new application of the piece-wise constant functions "universal approximation theorem"). Polynomials, trigonometric polynomials, splines (i.e piecewise polynomials), radial basis functions, and on and on. Just put neural networks to a test against splines, and see how they fare. Take your favorite function, let's say sin(x) and try to approximate it with a neural net with 1000 nodes, or with splines with 20 nodes. You don't stand a chance to match the quality of the spline approximation. Edit: here's a short python snippet to show how much better a spline with 20 nodes is vs a neural network with 1000 nodes for approximating the sin function import numpy as np from sklearn.neural_network import MLPRegressor from scipy.interpolate import UnivariateSpline N = 10000 X_train = 2*np.pi*np.random.uniform(size=N) Y_train = np.sin(X_train) sin_NN = MLPRegressor(hidden_layer_sizes= (1000,)).fit(X_train.reshape(N,1), Y_train) spline_nodes = np.linspace(0,2*np.pi, 20, endpoint=True) sin_spl = UnivariateSpline(spline_nodes, np.sin(spline_nodes), s=0) X_test = np.linspace(0,2*np.pi, 5000, endpoint=True) Y_test = np.sin(X_test) rmse_NN = np.mean((Y_test-sin_NN.predict(X_test.reshape(-1,1)))**2) rmse_spl = np.mean((Y_test-sin_spl(X_test))**2) print("RMSE for NN approx: ", rmse_NN) print("RMSE for spline approx: ", rmse_spl) >> RMSE for NN approx: 0.00011776185865537907 >> RMSE for spline approx: 9.540536500968638e-10
- gowld 5y agoUniversality shows potential, not optimality. the article covers this.
- srean 5y agoIndeed. I cannot upvote this enough New fanboys of DNN seem so enamored by the universal approximation property and cite it at the slightest provocation. There is no dearth of universal approximators, that's not what makes DNN special. The special thing is how does simple training procedures seem to find these approximations that generalize well (or doesnt as shown by the adversarial examples).
- 5y ago
- aaaaaaaaaaab 5y agoThat’s a pretty useless “proof” which gives no insight into how neural networks learn in practice. The author takes a sigmoid neuron, tweaks its parameters to the extreme so that it looks like a step function, then concludes that since a linear combination of step functions can approximate anything, so do neural networks. Bravo.
- r-zip 5y agoDid you ever consider that explaining how deep nets "learn in practice" is not the point?
- anothernewdude 5y agoIf it's not about learning this result is useless. A lookup table can compute any function, but who cares?
- mdp2021 5y ago> who cares The people who need to build some (sophisticated kind of) lookup table for a function of unavailable details through automation.
- gowld 5y agoThis is a long written argument with some animations, not a visual proof.
- alephnan 5y agos/function/computable function
- kolbe 5y agoSo can most linear combinations of functions set to the nth power.
- deleted 5y ago[deleted]
- __MatrixMan__ 5y agoI think the author might be overlooking just how weird something can be while still being a function. Let f(x):R->{1,0} be such that f(x)=1 if x is rational and 0 otherwise.
- vecter 5y agoHe says continuous function
- jjgreen 5y agoHe also says in the first sentence "One of the most striking facts about neural networks is that they can compute any function at all", that later caveat is incompatible, most function are not continuous.
- laichzeit0 5y agoOk so what about the Cantor function? Can it learn that?
- Banana699 5y ago"Visual proof" pretty much gave away the fact that it was going to be a non-rigorous reasoning process based on drawing an arbitary plot, once you draw a plot you're already assuming a lot about its underlying function. The title isn't very misleading.
- nautilius 5y agoI don't understand all of the criticism here. This is Ch. 4 in a basic intro to neural networks. The author provides a well written, intuitive, and concise demonstration of how sigmoids can be pieced together to approximate functions, in the layman's sense of the word. It helped me build intuition when I came across this maybe 5 (?) years ago. There are other good 'Chapters' about vanishing gradient or backprop. The criticism here is mostly about things that aren't even the topic of the article: 'it cannot compute non-computable functions', 'it cannot predict tomorrow's stock price', 'splines are more efficient', 'it cannot predict how a stick looks bent in water'. It's like saying 'I read "Zen and the art of motorcycle maintenance, twice, and still don't know how to adjust spark plugs. Stupid book"'.
- GTP 5y agoThe criticism is that is over-representing neural networks' capabilities: saying that they can compute any function is a very big and incorrect claim, IMO it should at least mention that non-computable functions are a thing and of course a neural network can't have better capabilities than the machine that is running it. This is especially because there are people out there thinking that machine learning is able to solve any possible problem, if one of those people comes across this proof they'll think: "Neural netwoks really can solve any conceivable problem! Look, there's even a mathematical proof of this!"
- renewiltord 5y agoIt’s funny, but this is how I felt about my son’s kindergarten. They taught him about “numbers” but instead they only used Natural numbers. The least they could have done is mention at least the one-point compactification of that space. Fortunately, I was able to intervene before he was permanently damaged by the class. He’s still struggling with showing that it is homeomorphic to the subspace of R formed by {1/n for all n in R that are in N} union {0} and I blame today’s pedagogy for that.
- GTP 5y agoThe context is different, the problem here is the hype that goes in a very specific direction (i.e. you can do anything with ML) as I briefly explained in another comment
- kmod 5y agoI think these sorts of arguments are not great because they confuse "limiting behavior" with "behavior at the limit". Yes if you are able to construct an infinite-sized MLP it can exactly replicate a given function, and you can construct a sequence of MLPs that in some sense converge to this infinite behavior. But in other measures the approximation might be infinitely bad and never get better unless the net is truly infinite. For an example, consider approximating the identity function [f(x) = x] with a sigmoid-activation MLP. For any finite size of the net, the output will have a minimum and maximum value. One can change the parameters of the net to increase the range of the output, but at no point is the output range infinite. So even though you can construct a sequence of MLPs that in the limit in some sense converges to the identity function, in some sense it never does. The same kind of thinking that leads to the conclusion "neural nets are universal approximators" would support the existence of perpetual motion machines; check out the "ellipsoid paradox" for more info.
- kazinator 5y agoReally? Can a neural compute the function halts(N, I): the neural net N will halt on input I, for any neural net N and input I?
- advisedwang 5y agoThe article says: > The second caveat is that the class of functions which can be approximated in the way described are the continuous functions. If a function is discontinuous, i.e., makes sudden, sharp jumps, then it won't in general be possible to approximate using a neural net. This is not surprising, since our neural networks compute continuous functions of their input. However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough. If that's so, then we can use a neural network. In practice, this is not usually an important limitation.
- Kalanos 5y agoit can't learn exponents. it can only multiply. there's also a difference between memorizing part of a line, and being able to extrapolate it.
- iamcurious 5y agoI find this very interesting, can you expand or provide links?
- Kalanos 5y agoweights that connect neurons can only be multiplied. now i am looking at activation functions like `exponent`. i just doubt a neural network regression would be able to predict rlly high values accurately for something like E = mc^2.
- iamcurious 5y agothank you.
- hlbjhblbljib 5y agoThey can with the right activation function. I'm thinking inverse log.
- marsven_422 5y ago
- FpUser 5y ago>"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" With "or some close approximation" being a key I fail to understand why is it not obvious.
- voldacar 5y agoThis "proof" is pretty sketchy. I think he means every differentiable function? Because I fail to see how you can make a neural network evaluate the indicator function of the rationals
- bjourne 5y ago"The second caveat is that the class of functions which can be approximated in the way described are the continuous functions. If a function is discontinuous, i.e., makes sudden, sharp jumps, then it won't in general be possible to approximate using a neural net. This is not surprising, since our neural networks compute continuous functions of their input. However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough. If that's so, then we can use a neural network. In practice, this is not usually an important limitation."
- voldacar 5y agoI guess I didn't see that. But he's still using continuous where the correct term would be differentiable
- kevinventullo 5y agoYou can uniformly approximate any continuous function on a compact domain with a differentiable/smooth function.
- bjourne 5y agoContinuous functions aren't necessarily differentiable.
- voldacar 5y agoyes, that's my point
- bmitc 5y agoThis is called out deep into the article, but shouldn't it be "neural nets can approximate any function"? Also, how does this relate to the traditional notation of computability of functions?
- t_mann 5y agoAs someone who has taught this to CS students, just scrolling through I have to say it looks like this has about 5x more text it should have. This is a homework problem for second-year students (literally, where I used to teach) that should take them no more than a page to answer.
- UtDeo 5y ago
- kevinventullo 5y agoI see a lot of commenters up in arms about Universal Approximation for NN’s, and I think the issue is that it’s often framed as a superpower rather than table stakes for any kind of general purpose algorithm. I posit that any modeling technique which does not have the universal approximation property will be guaranteed to fail on large classes of problems no matter how much elbow grease (say feature engineering) one puts into it. That is, UA is a necessary but not sufficient condition for a modeling technique to be fully general (i.e. could form the basis of whatever AGI is).
- DiggyJohnson 5y agoReally well said. Is there a term or concept in the AI literature++ that captures this point/conjecture?
- kevinventullo 5y agoI’m not sure. My intuition comes from real analysis, where one can think of the “space of all continuous functions” as being kind of geometric like Euclidean space. Then “Universal Approximation” for some Special set of functions (say those coming from neural networks) is equivalent to saying those special functions are “dense” in the space of all continuous functions. My geometric reasoning is that if a special collection is not dense, then it’s probably something like a lower-dimensional subspace, which really means you’re missing most of the ambient space in some sense. It’s all a bit handwavy but I hope that paints a picture. Getting more in the weeds, there are theorems like https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem#Stone%E2%80%93Weierstrass_theorem,_real_version https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theo... which suggest that being “dense in the space of continuous functions” is not as hard to achieve as one might guess.
- Jenz 5y ago“Any function” is a big wide claim. Can someone fill me in on what’s required of these functions? Can a neural nets for example compute non-continuous functions like f(x) = [x is rational]?
- advisedwang 5y agoThe article says: > The second caveat is that the class of functions which can be approximated in the way described are the continuous functions. If a function is discontinuous, i.e., makes sudden, sharp jumps, then it won't in general be possible to approximate using a neural net. This is not surprising, since our neural networks compute continuous functions of their input. However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough. If that's so, then we can use a neural network. In practice, this is not usually an important limitation.
- smolder 5y agoYeah, all you need to do is show you can build a NAND gate with a neural network and every other logical network follows from that. I remember doing that project in a machine learning class in 2010.
- grafs50 5y agoWith the top comments (now) all talking about the fact that this universal approximation theorem doesn't really have much impact in the real world. I wonder, is this interesting outside of theory? Has this motivated any techniques that have created (or may create) real-world, empirical results? Could it even?
- mr_toad 5y agoPlenty of problems in the area of computation have little impact on the real world, but they contribute to our fundamental understanding of ‘understanding’. The Entscheidungsproblem is probably the most significant of these. https://en.wikipedia.org/wiki/Entscheidungsproblem https://en.wikipedia.org/wiki/Entscheidungsproblem
- anothernewdude 5y agoDid you know a big enough hash-table can compute any function?
- lisper 5y ago> a more precise statement of the universality theorem is that neural networks with a single hidden layer can be used to approximate any continuous function to any desired precision. That is a very different claim than being able to compute any function.
- moffkalast 5y agoI was about to feed P = NP into GPT-3, sigh
- code_witch_sam 5y agos/neural net/turing machine/gi
- deleted 5y ago[deleted]
- TheRealNGenius 5y agoeh, more a proof with visual, not a visual proof.
- jnash 5y agoA sequence of sinus curves can compute any function. A Turing machine can compute any function. Lambda calculus can compute any function. etc. etc.