21 ms·
A visual proof that neural nets can approximate any function
- nisuni 8y agoAny orthonormal ~set~ basis of functions can represent any function. So what?
- anonytrary 8y agoNo, the set must be an orthonormal basis. For example, two Fourier components technically form an orthonormal set, but do not form a complete basis.
- nisuni 8y agoYes, I meant basis. My point still stands: so what?
- braised_babbage 8y agoThis 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.
- nisuni 8y agoYou 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!
- dragon96 8y ago> 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.
- nisuni 8y agoMost 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)
- dragon96 8y agoThe 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. :)
- aportnoy 8y ago*any continuous function
- YesProcrast 8y agoCame here to suggest the function that is 1 on the rationals and 0 on the irrationals.
- adrianhel 8y agoNot continuous.
- throwawaymath 8y agoI think that was the point.
- analog31 8y agoAlso can't be computed.
- nightcracker 8y agoThat depends on the input format.
- dual_basis 8y agoIt 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.
- braised_babbage 8y agoNo, neural networks cannot "represent any arbitrary function". Find a theorem that you think states otherwise, and then read what the theorem actually states.
- quickthrower2 8y agoCan it compute y=sin x?
- hcs 8y ago> 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.
- tsbinz 8y agoAlso, 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.
- ska 8y agoIt's also important to note the theorem doesn't help you find the right weights, just notes they exist.
- pauljurczak 8y agoThey can't approximate functions on unbound domain in general case.
- fnbr 8y agoA 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).
- quickthrower2 8y agoDownvoted for asking a genuine question?
- mkl 8y ago
- codesternews 8y agoAny 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/blob/master/courses/udacity_intro_to_tensorflow_for_deep_learning/l02c01_celsius_to_fahrenheit.ipynb#scrollTo=Y2zTA-rDS5Xk https://colab.research.google.com/github/tensorflow/examples...
- xvedejas 8y agoIt'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.
- deleted 8y ago[deleted]
- creato 8y agoYour data is suspiciously rounded off. Just doing linear regression on that data isn't going to give you a perfect fit either.
- Gibbon1 8y agoThere 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.
- Xcelerate 8y agoI'd like to see a neural network that can compute a hash function.
- bowyakka 8y agohttp://cs.nju.edu.cn/lwj/L2H.html http://cs.nju.edu.cn/lwj/L2H.html
- chewzerita 8y agoThis is just crazy! I can't even begin to understand what is going on... Bravo
- toxik 8y agoLook into neural Turing machines
- segfaultbuserr 8y agoWow, it's real! I didn't know running a Turing machine on a neural network is practically possible.
- yters 8y agoCan neural networks solve the halting problem?
- dagav 8y agoNo. Neural networks are still computed on Turing machines, which are mathematically proven to not be able to solve the halting problem.
- segfaultbuserr 8y agoIt 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.
- contravariant 8y agoWell, 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.
- AnaniasAnanas 8y agoIf 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.
- deleted 8y ago[deleted]
- a-nikolaev 8y agoApproximate, 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]
- zepearl 8y agoSkimming 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.
- zepearl 8y agoI just got a downvote => I think that it's not fair to downvote a question, especially without posting the reason for the downvote :(
- mkl 8y agoIf 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!).
- zepearl 8y agoOk, thanks for the explanation.
- jjtheblunt 8y agotitle is false since there exist uncomputable functions, no?
- personjerry 8y agoI skimmed it, but at a glance, isn't this almost identical to the Taylor Series? https://en.wikipedia.org/wiki/Taylor_series https://en.wikipedia.org/wiki/Taylor_series
- YjSe2GMQ 8y agoWell, in the sense that polynomials are universal approximators too (on a compact domain). See this comment: https://news.ycombinator.com/item?id=19709834 https://news.ycombinator.com/item?id=19709834
- tprice7 8y agoThe 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.
- tprice7 8y agoNo.
- Too 8y agoFourier 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 https://en.wikipedia.org/wiki/Discrete_Fourier_transform
- DavidSJ 8y agoTaylor 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).
- drpixie 8y agoA 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!
- alleycat5000 8y agoIf 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 https://people.maths.ox.ac.uk/trefethen/atapvideos.html Chebfun is pretty cool too! http://www.chebfun.org http://www.chebfun.org
- soVeryTired 8y agoPeople 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.
- salty_biscuits 8y agoAnd 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
- chriscaruso 8y agoGreat book, this is how I learned NNs
- mkl 8y agoI 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 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}".
- Gravityloss 8y agoThis deserves its own submission. Maybe the number of neurons slider could be logarithmic?
- mkl 8y agoDone: https://news.ycombinator.com/item?id=19711416 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.
- rodionos 8y agoFor 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 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).
- uuwp 8y agoOf 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).
- DavidSJ 8y agoThis 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.
- uuwp 8y agoI 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.
- DavidSJ 8y agoIt’s a theorem, so it’s been proven: https://en.wikipedia.org/wiki/Universal_approximation_theorem 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.
- otabdeveloper2 8y ago> 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.)
- soVeryTired 8y ago> 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.
- fluffything 8y agoSo 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 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, ...
- 0815test 8y ago> 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.)
- simonster 8y agoYes, 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.
- blamestross 8y ago
- iheartpotatoes 8y agoIsn'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?
- rsiqueira 8y agoHow 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.
- acdc4life 8y 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" 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.
- dual_basis 8y agoIt'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.
- uuwp 8y agoThis 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.
- darkkindness 8y agoThe 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.