Theoretical results behind Artificial Neural Networks

Question

I have just covered Artificial Neural Networks on Coursera's Machine Learning course and I would like to know more theory behind them. I find the motivation that they mimic biology somewhat unsatisfactory.

On the surface it appears that at each level we replace covariates with a linear combination of them. By doing it repeatedly we allow for non-linear model fitting. This begs the question: why the neural networks are sometimes preferred to just fitting a non-linear model.

More generally, I would like to know how Artificial Neural Networks fit within the Bayesian Framework of inference which is described in detail in E.T. Jaynes' book "Probability Theory: The Logic Of Science". Or, to put it simply, why do artificial neural networks work when they work? And, of course, the fact that they make successful predictions implies that they follow the aforementioned framework.

Answer 1

Here is a quote from "A Backward Look to the Future", by E. T. Jaynes.

New Adhockeries

In recent years the orthodox habit of inventing intuitive devices rather than appealing to any connected theoretical principles has been extended to new problems in a way that makes it appear at first that several new fields of science have been created. Yet all of them are concerned with reasoning from incomplete information; and we believe that we have theorems establishing that probability theory as logic is the general means of dealing with all such problems. We note three examples.

Fuzzy Sets are -- quite obviously, to anyone trained in Bayesian inference -- crude approximations to Bayesian prior probabilities. They were created only because their practitioners persisted in thinking of probability in terms of a "randomness" supposed to exist in Nature but never well defined; and so concluded that probability theory is not applicable to such problems. As soon as one recognizes probability as the general way to specify incomplete information, the reason for introducing Fuzzy Sets disappears.

Likewise, much of Artificial Intelligence (AI) is a collection of intuitive devices for reasoning from incomplete information which, like the older ones of orthodox statistics, are approximations to Bayesian methods and usable in some restricted class of problems; but which yield absurd conclusions when we try to apply them to problems outside that class. Again, its practitioners are caught in this only because they continue to think of probability as representing a physical "randomness" instead of incomplete information. In Bayesian inference all those results are contained automatically -- and rather trivially -- without any limitation to a restricted class of problems.

The great new development is Neural Nets, meaning a system of algorithms with the wonderful new property that they are, like the human brain, adaptive so that they can learn from past errors and correct themselves automatically (WOW! What a great new idea!). Indeed, we are not surprised to see that Neural Nets are actually highly useful in many applications; more so than Fuzzy Sets or AI. However, present neural nets have two practical shortcomings; (a) They yield an output determined by the present input plus the past training information. This output is really an estimate of the proper response, based on all the information at hand, but it gives no indication of its accuracy, and so it does not tell us how close we are to the goal (that is, how much more training is needed); (b) When nonlinear response is called for, one appeals to an internally stored standard "sigmoid" nonlinear function, which with various amplifications and linear mixtures can be made to approximate, to some degree, the true nonlinear function. (Note: emphasis mine.)

But, do we really need to point out that (1) Any procedure which is adaptive is, by definition, a means of taking into account incomplete information; (2) Bayes' theorem is precisely the mother of all adaptive procedures; the general rule for updating any state of knowledge to take account of new information; (3) When these problems are formulated in Bayesian terms, a single calculation automatically yields both the best estimate and its accuracy; (4) If nonlinearity is called for, Bayes' theorem automatically generates the exact nonlinear function called for by the problem, instead of trying to construct an approximation to it by another ad hoc device.

In other words, we contend that these are not new fields at all; only false starts. If one formulates all such problems by the standard Bayesian prescription, one has automatically all their useful results in improved form. The difficulties people seem to have in comprehending this are all examples of the same failure to conceptualize the relation between the abstract mathematics and the real world. As soon as we recognize that probabilities do not describe reality -- only our information about reality -- the gates are wide open to the optimal solution of problems of reasoning from that information.

A few comments:

1. Point (a) ignores the developments in Bayesian Neural Networks, which started in the late eighties and early nineties (but notice that Jaynes's paper was written in 1993). Take a look at this post. Also, consider reading Yarin Gal's beautiful PhD thesis, and watching this great presentation by Zoubin Ghahramani.

2. I don't see how point (b) could be a "shortcoming". In fact, it's the essence of why neural nets can approximate a large class of functions well. Notice that recent successful architectures moved from sigmoid to ReLU activations in the inner layers, favoring "depthness" over "wideness". Approximation theorems have been recently proved for ReLU nets.

Answer 2

First of all we do not stack linear functions into each other in order to obtain a nonlinear function. There is a clear reason why NNs might never work like that: Stacking linear functions into each other would yield again a linear function.

What makes NNs nonlinear is the activation function that comes behind the linear function! However, in principal you are right: We simply stack a lot of logistic regressions (not linear ones though!) into each other and ... tadaa: we get something good out of it... is that fair? Turns out that (from a theoretical point of view) it actually is fair. Even worse: Using the celebrated and well known Theorem of Stone-Weierstrass we simply prove that neural networks with just one hidden layer and no output function at the final node is enough to approximize any continuous functions (and beleive me, continuous functions can be ugly beasts, see the "devils staircase": https://en.wikipedia.org/wiki/Cantor_distribution) on intervals of the form $[a,b]$ (NNs with just one hidden layer and no output function at the final node are exactly functions of the form $x \mapsto = b + a_1\phi_1(x) + ... + a_l\phi_l(x)$ where $l$ is the size of the hidden layer, i.e. polynomials in logistic functions and they form an algebra by definition!). I.e. 'by construction', NNs are very expressive.

Why do we use deep NNs then? The reason is that the SW-theorem above only guarantees that there is a sufficiently large layer size so that we can come close to our (hopefully continuous) target function. However, the layer size needed may be so large that no computer could ever handle weight matrices of that size. NNs with more hidden layers seem to be a good compromise between 'accuracy' and computability. I do not know of any theoretical results that points into the direction of 'how much' the expresiveness of NNs grows when putting in more hidden layers in comparison to just increasing the size of the single hidden layer but maybe there are some resources on the web...

Can we truly understand deep NNs? Example questions: Why exactly does the NN predict this case to be TRUE while it predicts this other, similar case to be FALSE? Why exactly does it rate this customer more valuable than the other one? I do not really believe so. It comes with the complicatedness of the model that you cannot explain it reasonably well anymore... I only hear that this is still an active area of research but I do not know any resources...

What makes NNs so unique among all models? The true reason why we use NNs so much these days is because of the following two reasons:

1. They come with a natural 'streaming' property.
2. We can pimp them to the max in many directions.

By 1. I mean that given a training set $T$, a NN $f$ that was trained on this set $T$ and some new training samples $T'$, we can easily include these training samples into the NN by just continuing the gradient descent/backprop algorithm while only selecting batches from $T'$ for the training. The whole area of reinforcement learning (used to win games like Tic Tac Toe, Pong, Chess, Go, many different Atari games with just one model, etc) is based on this property. People have tried to infuse this streaming property to other models (for example Gradient Boosting) but it does not come that naturally and is not as computationally cheap as in the NN setup.

By 2. I mean that people have trained NNs to do the weirdest things but in principle they just used the same framework: stacking smooth functions into each other and then let the computer (i.e. PyTorch/Tensorflow) do the dirty math for you like computing the derivative of the loss function w.r.t. the weights. One example would be this paper where people have used the RL approach and also pimped the architecture of the NN to learn the complex language of chemical substances by teaching it how to operate on a memory stack (!). Try to do that with gradient boosting ;-) The reason why they must do that is that the language of chemicals is at least as 'hard to learn' as the bracket language (i.e. every opening bracket has a closing one later on in the word) because the SMILES language that peopple use in order to describe molecules contains the symbols '(' and ')'. From theoretical computer science (Chomsky hierarchy) one knows that one cannot describe this language with a regular automata but one needs a push down automata (i.e. an automata with a stack memory). That was the motivation for them (I guess) to teach this weird thing to the NN.

Answer 3

"Why does it work when it works?"

Another answer here quotes E. T. Jaynes. He says that other machine learning algorithms are ad hoc, but neural network are not. The reason is that the algorithm corrects itself. In reality, if you have $n$ instances in a sample, why would it be better to use them one after another rather than use them all together? There is no proof that NN approach is better. In most of cases with limited data NN is, actually, worse.

So, all machine learning are similarly ad hoc.

Machine Learning is similar to alchemy: there are plenty of enigmatic recipes, you apply one, and you may get gold. If not, just apply another recipe.

Nobody asks the question you asked, at least not in the publications I know.

On top of this, there is statistical learning theory. Statistical learning theory assumes that the size of the training set goes to infinity. Most of results I know have the form: "under certain conditions, if you have a large enough training set, you can get almost as good result as possible using this procedure". The estimates of what is "large enough" are beyond imagination.

Of course, the problem is, the training set size is not going anywhere, let alone to infinity.

So, I think, it is a good time to (1) ask this question, (2) to develop a mathematical apparatus to answer the question about all possible machine learning algorithms and (3) answer this question.