9
$\begingroup$

I want to improve my understanding of neural networks and their benefits compared to other machine learning algorithms. My understanding is as below and my question is:

Can you correct and supplement my understanding please? :)

My understanding:

(1) Artificial neural networks = A function, which predicts output values from input values. According to a Universal Approximation Theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem), you usually can have any possible (though it should behave well) prediction function, given enough neurons.

(2) The same is true for linear regression, by taking polynomials of the input values as additional input values, since you can approximate (compare Taylor expansion) each function well by polynomials.

(3) This means, that (in a sense, with respect to best possible outcomes), those 2 methods are equivalent.

(4) Hence, their main difference lies in which method lends itself to better computational implementation. In other words, with which method can you find, based on training examples, faster good values for the parameters which eventually define the prediction function.

I welcome any thoughts, comments and recommendations to other links or books to improve my thinking.

$\endgroup$

migrated from mathoverflow.net Sep 29 '17 at 20:09

This question came from our site for professional mathematicians.

  • 2
    $\begingroup$ Should be moved to math.stackexchange.com Neural networks with $\tanh$ activation approximate arbitrary well any smooth function but they have one more feature : the smoothness (the scaling of the weights) depends on the point, this is the key to a good global approximation. You can't achieve that with polynomial approximation (given a continuous function, take its convolution with $n^d e^{-\pi |n x|^2}$ and use the first few terms of the Taylor expansion around some point, which only gives a good local approximation) $\endgroup$ – user1952009 Sep 29 '17 at 16:35
  • $\begingroup$ @user1952009 - doesn't Stone-Weierstrass imply arbitrarily good global approximation, due to the uniformity of the approximation in the theorem? $\endgroup$ – jbowman Oct 7 '17 at 22:05
  • $\begingroup$ @jbowman It does a good local approximation : for any $f$ continuous, $r$ and $\epsilon$ there exists a smooth, analytic or polynomial function (as you wish) $f_{r,\epsilon}$ such that $\sup_{|x| \le r} |f(x)-f_{r,\epsilon}(x)| \le \epsilon$. So does a neural network, but the feature is that it can take many different local approximations (around different $x_0$) and mix them to obtain some kind of global approximation. $\endgroup$ – user1952009 Oct 8 '17 at 1:35
  • 1
    $\begingroup$ This is potentially a duplicate of stats.stackexchange.com/questions/41289/… I'd flag this question, but with the bounty on it, I guess I'm just going to comment here instead :) $\endgroup$ – Hugh Perkins Oct 13 '17 at 10:13
  • 1
    $\begingroup$ +1 @HughPerkins for the link to an insightful related Q. But, even though the answers in the related question do provide insight on the question here (e.g. as Stephan Kolassa explains aNN takes into account non-linearity as default while regression only does so when specifically modelled through additional techniques) I would not flag for duplicate. You asked which one model type can give better results, while this question specifically ask to explain whether or not two methods are similar in their results and their generalizability. $\endgroup$ – IWS Oct 13 '17 at 10:52
4
+100
$\begingroup$

Here's the deal:

Technically you did write true sentences(both models can approximate any 'not too crazy' function given enough parameters), but those sentences do not get you anywhere at all!

Why is that? Well, take a closer look at the universal approximation theory, or any other formal proof that a neural network can compute any f(x) if there are ENOUGH neurons.

All of those kind of proofs which I have seen use only one hidden layer.

Take a quick look here http://neuralnetworksanddeeplearning.com/chap5.html for some intuition. There are works showing that in a sense the number of neurons needed grow exponentially if you are just using one layer.

So, while in theory you are right, in practice, you do not have infinite amount of memory, so you don't really want to train a 2^1000 neurons net,do you? Even if you did have infinite amount of memory,that net will overfit for sure.

To my mind, the most important point of ML is the practical point! Let's expand a little on that. The real big issue here isn't just how polynomials increase/decrease very quickly outside the training set. Not at all. As a quick example, any picture's pixel is within a very specific range ([0,255] for each RGB color) so you can rest assured that any new sample will be within your training set range of values. No. The big deal is: This comparison is not useful to begin with(!).

I suggest that you will experiment a bit with MNIST, and try and see the actual results you can come up with by using just one single layer.

Practical nets use way more than one hidden layers, sometimes dozens (well, Resnet even more...) of layers. For a reason. That reason is not proved, and in general, choosing an architecture for a neural net is a hot area of research. In other words, while we still need to know more, both models which you have compared(linear regression and NN with just one hidden layer ), for many datasets, are not useful whatsoever!

By the way, in case you will get into ML, there is another useless theorem which is actually a current 'area of research'- PAC (probably approximately correct)/VC dimension. I will expand on that as a bonus:

If the universal approximation basically states that given infinite amount of neurons we can approximate any function (thank you very much?), what PAC says in practical terms is, given (practically!) infinite amount of labelled examples we can get as close as we want to the best hypothesis within our model. It was absolutely hilarious when I calculated the actual amount of examples needed for a practical net to be within some practical desired error rate with some okish probability :) It was more than the number of electrons in the universe. P.S. to boost it also assumes that the samples are IID (that is never ever true!).

$\endgroup$
  • $\begingroup$ So, are artificial neural networks equivalent to linear regression with polynomial features or not? Your answer seems to focus on the amount of layers and required neurons, but does not explain why these two analyses should/could be equivalent. Does adding more (hidden) layers make a neural network able to handle (even) more functions than a regression with polynomials? And, as OP has wondered in an answer him/herself, how about the external validity/out-of-sample performance of these models (and the trade-offs between using more intricate model options and performance)? $\endgroup$ – IWS Oct 13 '17 at 9:43
  • $\begingroup$ I refer you to my very first sentence: "Technically you did write true sentences". $\endgroup$ – Yoni Keren Oct 13 '17 at 9:45
  • $\begingroup$ Well, I asked because the reasoning for your statement that 'the OP wrote true sentences' was not clear to me based on your answer. Would you be so kind to elaborate on this? $\endgroup$ – IWS Oct 13 '17 at 9:56
  • $\begingroup$ For sure. Is this better, or do you find anything else still unclear? $\endgroup$ – Yoni Keren Oct 13 '17 at 10:14
5
$\begingroup$

It is true that any function can be approximated arbitrarily close both by something that counts as a neural network and something that counts as a polynomial.

First of all, keep in mind that this is true for a lot of constructs. You could approximate any function by combining sines and cosines (Fourier transforms), or simply by adding a lot of "rectangles" (not really a precise definition, but I hope you get the point).

Second, much like Yoni's answer, whenever you are training a network, or fitting a regression with a lot of powers, the number of neurons, or the number of powers, are fixed. Then you apply some algorithm, maybe gradient descent or something, and find the best parameters with that. The parameters are the weights in a network, and the coefficients for a large polynomial. The maximum power you take in a polynomial, or the number of neurons used, are called the hyperparameters. In practice, you'll try a couple of those. You can make a case that a parameter is a parameter, sure, but that is not how this is done in practice.

The point though, with machine learning, you don't really want a function that fits through your data perfectly. That wouldn't be too hard to achieve actually. You want something that fits well, but also probably works for points that you haven't seen yet. See this picture for example, taken from the documentation for scikit-learn.

A line is too simple, but the best approximation is not on the right, it's in the middle, allthough the function on the right fits best. The function on the right would make some pretty weird (and probably suboptimal) predictions for new data points, especially if they fall near the wiggly bits on the left.

The ultimate reason for neural networks with a couple of parameters working so well, is that they can fit something but not really overfit it. This also has a lot to do with the way they are trained, with some form of stochastic gradient descent.

$\endgroup$
2
$\begingroup$

Since no answers have yet been provided (though I would accept the comment of user1952009 was it posted as an answer), let me share what I have learned in the meantime:

(1) It seems to me that my understanding is generally right, but the devil is in the details.

(2) One thing that missed in "my understanding": How good will the parametrized hypothesis generalize to data outside the training set? The non-polynomial nature of the neural network predictions may be better there than simple linear/polynomial regression (remember how polynomials increase/decrease very quickly outside the training set).

(3) A link which further explains the importance of being able to compute parameters quickly: http://www.heatonresearch.com/2017/06/01/hidden-layers.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.