Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Empiricism and the limits of gradient descent

togelius.blogspot.com

Post reply on HN
Print view View original

21–30 of 46 posts

Re: Empiricism and the limits of gradient descent

#21

Post by [deleted] »

simonster wrote: post #20
roywiggins wrote: post #19

Earlier quoted context omitted.

> Given sufficient data, according to the Universal Approximation Theorem, a neural network can learn to model physics. It just says there are weights to approximate any function, not that you can actually learn the weights. Neural networks trivially can't learn how to approximate noncomputable functions to any accuracy, and there might be a lot of other functions that neural networks are terrible at actually learnin…

It's a fair point that the Universal Approximation Theorem does not guarantee that the weights can be learned. OTOH, the physical laws that the article states a neural network cannot discover are computable functions.

[deleted]

Re: Empiricism and the limits of gradient descent

#22

Post by LolWolf »

maxander wrote: post #8
perl4ever wrote: post #3

Earlier quoted context omitted.

I don't understand how E=mc^2 can not be in the data. If it's a universal law, isn't it in more (all) data than any pattern that isn't universal?

The article is making a simpler point than that. If I show you the table: A B C 1 4 3 20 45 15 8 15 7 And so on for some arbitrary number of rows, you can look at the table all you want but you will not perceive "A+C=B". It's just not written there. To get A+C=B you have to generate something else in addition to the table, namely a hypothesis- but this is a creative act, not an empirical one.

In this case, any linear model (with reasonable, minimizable loss, which could be, say convex) will learn the correct thing.

Here's a quick gist[0] doing it using least-squares, and learning it exactly (also, for B in the third row you may have intended 35 instead of 45?).

This simple regression model learns exactly the weights (-1, 1)—equivalently, it learns -A + B = C.

------

[0] https://gist.github.com/guillean/6f3ff05fa99b2b377fcf309bdc4...

Re: Empiricism and the limits of gradient descent

#23

Post by visarga »

tlb wrote: post #2

I'm optimistic about the potential for evolutionary algorithms. I've used both EAs and gradient descent in developing robot controllers. But the argument here about why gradient descent won't be able to learn certain things is weak. Thought experiments are not a reliable guide to what what GD can or can't do. It's fair enough to say that F=ma and E=mc² aren't in the data. Indeed, it took thousands of years of human t…

The author of the article mistook the importance of environment interactivity, considering that the learning algorithm is the key difference.

I think the distinction here should be between dataset based learning and simulator based learning. The genetic algorithms mentioned in the article rely on a dynamic environment, not a static dataset. Given the dynamic environment (which is like an infinite dataset) gradient methods can learn just as well - look at AlphaGo for example. But when the model can't experiment / try new actions and see the effects, it can't separate causes from correlations.

You can extract only so much from a dataset, the model needs a way to cause and observe external effects. The environment could be the real world, a simulated world, a game, a meta neural net optimiser (AutoML), or any domain where the model can act and influence the path of learning and the environment by its previous actions.

I'm happy to see the boom in RL and simulator based learning in the last few years. It means we are on the right track.

Re: Empiricism and the limits of gradient descent

#24

Post by ozy »

Notice how blacks swans is a labeling/categorization problem. Whereas F=ma is a causal relationship. The first has no induction problem, there is no swan-ness except in our minds. The second has no induction problem, because you model causal relationships and predict from them, better predictions means less wrong. The problem of induction is only one of "ultimate reality".

Re: Empiricism and the limits of gradient descent

#25

Post by PeterisP »

maxander wrote: post #8
perl4ever wrote: post #3

Earlier quoted context omitted.

I don't understand how E=mc^2 can not be in the data. If it's a universal law, isn't it in more (all) data than any pattern that isn't universal?

The article is making a simpler point than that. If I show you the table: A B C 1 4 3 20 45 15 8 15 7 And so on for some arbitrary number of rows, you can look at the table all you want but you will not perceive "A+C=B". It's just not written there. To get A+C=B you have to generate something else in addition to the table, namely a hypothesis- but this is a creative act, not an empirical one.

Given a sufficiently large table, an agent can certainly perceive without acting (testing a hypothesis) that "A+C=B" through its compressibility; the most compact(least complex) representation of the data can replace the many individual datapoints in one column with a learned rule how to calculate it.

There's related research on how children learn language, namely, how much observed evidence (i.e. based on cases where we have monitored and counted every word a child has heard in their life) is needed for a child to switch from a "lookup table" approach for certain features to "rule based" approach (detectable by observing overregularization, applying a systematic rule even when the actual language, including examples the child has heard, has an exception to that rule) and then to a "rule+exceptions" correct understanding; the experiments point towards "learning a rule" then and only then when a "compressed representation" is beneficial from information theory point of view.

Re: Empiricism and the limits of gradient descent

#26

Post by AstralStorm »

joe_the_user wrote: post #16
simonster wrote: post #14

There are a couple of factual errors here. First, the difference between backprop and evolution is smaller than the author indicates. The error signal used in modern backprop training is stochastic because it is computed on a minibatch (which is why it's called stochastic gradient descent). This stochasticity seems important to achieving good results. And the most popular evolutionary algorithm in the deep learning w…

Given sufficient data, according to the Universal Approximation Theorem, a neural network can learn to model physics. The ability of a system of linked functions to approximate any continuous function seems rather far from the ability to "learn modern physics". It would seem like knowing modern physics would involve symbolic calculations rather than just approximating the behavior of any system.

A lot of physics is functions with singularities. ANN can only approximate these to a specified limit...

I want to see a neutral network that correctly solves SAT-3.

Re: Empiricism and the limits of gradient descent

#27

Post by AstralStorm »

simonster wrote: post #20
roywiggins wrote: post #19

Earlier quoted context omitted.

> Given sufficient data, according to the Universal Approximation Theorem, a neural network can learn to model physics. It just says there are weights to approximate any function, not that you can actually learn the weights. Neural networks trivially can't learn how to approximate noncomputable functions to any accuracy, and there might be a lot of other functions that neural networks are terrible at actually learnin…

It's a fair point that the Universal Approximation Theorem does not guarantee that the weights can be learned. OTOH, the physical laws that the article states a neural network cannot discover are computable functions.

You need a stronger bound than this. They have to be possible to approximate govern specific network size, architecture and activation functions. Calculating that (or good statistics that will say so approximately) is a hard problem... It is solvable for a bunch of activations in a layered perceptron but attempt extending this to something more complex.

Re: Empiricism and the limits of gradient descent

#28

Post by PeterisP »

andbberger wrote: post #17

Meh, weird article. None of the nice modern results (imagenet family, etc) were achieved just through gradient descent - this article, like most, seems to be missing the forest for the trees with deep learning. It's not about the network architecture, or gradient descent on their own - it's the interaction, the dynamical system over weight space that training is. Behind every great modern deep learning result? An eno…

"An enormous hyperparameter search and lots of elbow grease to carefully tune that dynamical system" i.e. the classic GDGS (gradient descent by grad student) approach where you have a grad student train a system, decide in which direction the parameters should be updated (i.e. look at the gradient), tweak the system and repeat until convergence.

Re: Empiricism and the limits of gradient descent

#29

Post by _0w8t »

simonster wrote: post #14

There are a couple of factual errors here. First, the difference between backprop and evolution is smaller than the author indicates. The error signal used in modern backprop training is stochastic because it is computed on a minibatch (which is why it's called stochastic gradient descent). This stochasticity seems important to achieving good results. And the most popular evolutionary algorithm in the deep learning w…

Recently I was involved in calibrating a thermal infrared camera at work. A colleague out of curiosity tried to use machine learning and ended up with model containing hundreds of parameters (weights). Yet it was not better than a trivial model using a Planck integral (based on simple assumption about how things worked) and a linear regression (to account for systematic errors), 2 parameters in total. And the simple model completely ignored time dependencies assuming thermal stabilization which could be accounted using a couple of extra parameters based on a typical solution of heat transfer equation. Initially it was puzzling as I thought that Planck integral should be easily modeled with basic blocks of ML models. But then I realized that Planck function in our case was integrated over a complex profile of an infrared filter and may not be something that is easy to capture within ML.

Re: Empiricism and the limits of gradient descent

#30

Post by creo »

(This is of course my opinion, not scientific fact) The biggest argument for EA is that proper implementation does not get stuck in local minimum. GD and SGD have that tendency, if not in one spot then probably looping between many. Problem with EA by the other hand is that its mathematical model is based on probability which is quite tricky to operate on even for above-average programmer.
Post reply on HN