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

11–20 of 46 posts

Re: Empiricism and the limits of gradient descent

#11

Post by tlb »

petermcneeley wrote: post #7
qop wrote: post #6

Earlier quoted context omitted.

Data has to be obtainable and is often dimensional. How would you have measured the speed of light in the forties? Even having lots of test cases, you wouldn't be able to deduce something like that with test cases alone.

Speed of light has been experimentally determined long before the 40s. The discovery of the speed of light being constant lead to the special relativity (aka before GR which is the E=mcc). http://www.speed-light.info/measure/speed_of_light_history.h...

The speed of light is easy to measure. What's hard is measuring the change in mass when something gains or loses energy. A large nuclear reactor running for a year only loses a few grams of mass-energy -- you can't measure it accurately enough or be sure that the mass didn't go somewhere else like into the cooling water.

Re: Empiricism and the limits of gradient descent

#12

Post by tlb »

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.

If you connect A and B as the input to a linear neural net, and train against C, it'll very quickly arrive at weights of [-1, +1] and be able to correctly predict C given A and B. Whether or not it represents it in notation humans are familiar with, it has learned it for the practical purpose of being able to compute the function.

Re: Empiricism and the limits of gradient descent

#13

Post by pmalynin »

Once again, there is a general conflation of evolutionary algorithms and learning without a differentiable error function. I've presented this argument again with a discussion with antirez here on HN [1], but the crux of is that Reinforcement Learning as it stands is optimization over (maybe)-non-differential errors. For AlphaGo there is no gradient, per se, that says you will optimize your wins if you go this way (now, it is optimized by training towards the win-rate "score", which could be an error score) -- look at REINFORCE for other variations. Evolutionary Learning and Reinforcement Learning as two sides of the same coin.

[1] https://news.ycombinator.com/item?id=16652138

Re: Empiricism and the limits of gradient descent

#14

Post by simonster »

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 world is Evolution Strategies, which effectively approximates a gradient. Ordinary genetic algorithms are not gradient-based and have recently shown promise in limited domains, but can't compete with gradient-based algorithms for supervised learning.

The key claim in the article, that gradient descent could not discover physics from equations seems, like it is a statement about neural networks, not gradient descent. Given sufficient training data, a neural network can probably learn to model physics. I sympathize with the concern that it's very difficult to translate a neural network's knowledge into human concepts, but I see no reason to believe that optimizing the same system with an evolutionary algorithm would make this problem any easier. You could e.g. try to do program induction (which was supposed to be the future of AI many decades ago) instead of modeling the data directly, but choosing to perform program induction does not preclude the use of a neural network. Neural networks trained by gradient descent can generate ASTs (e.g. http://nlp.cs.berkeley.edu/pubs/Rabinovich-Stern-Klein_2017_...).

[Edited to remove reference to universal approximation; as comments point out, even if a neural network can approximate a function, it isn't guaranteed to be able to learn it. But I am reasonably confident that a neural network can learn Newton's second law.]

Re: Empiricism and the limits of gradient descent

#15

Post by tlb »

joe_the_user wrote: post #10
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…

In wikipedia and numerous references, I get the impression that EAs, evolutionary algorithms, are a huge and fuzzily defined field. With Genetic algorithms, just one kind of evolutionary algorithm, the fitness, the mutation and the crossover function seem to require the implementor to look at the problem domain and "come up with something" whereas once you have a goal, gradient descent requires lots of tuning but is…

Salimans et al evolved weights in convolutional neural nets -- the same structure of network that works with deep reinforcement learning -- to play Atari games from pixels. https://blog.openai.com/evolution-strategies/

So you can make it work with generic models. Although as you say, many of the big successes like the Backgammon players and Kosa's work on electronic circuits used domain-specific models.

Re: Empiricism and the limits of gradient descent

#16

Post by joe_the_user »

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.

Re: Empiricism and the limits of gradient descent

#17

Post by andbberger »

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 enormous hyperparameter search and lots of elbow grease to carefully tune that dynamical system juuuuust right so the weight particle ends up in just the right place when training finishes. Smells like evolution to me. Deepmind even formalized the evolutionary process a deep learning researcher runs manually when fine-tuning a model into population based training https://deepmind.com/blog/population-based-training-neural-n...

Re: Empiricism and the limits of gradient descent

#18

Post by perl4ever »

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.

It seems to me that A+C=B and E=mc^2 are both written in, or consistent with, that table. But widening the context produces something different in each from a probabilistic perspective. A+C=B is 100% certain with narrow context, but falsified with a little more context, while E=mc^2 is less certain with narrow context, but increasingly certain with wider context.*

*Like, this table is on a computer connected to a global network, which is based on electromagnetism, which is intimately related to relativity. The more you understand what the table is, the more certain you can be of E=mc^2.

Re: Empiricism and the limits of gradient descent

#19

Post by roywiggins »

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.

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 learning.

Re: Empiricism and the limits of gradient descent

#20

Post by simonster »

roywiggins wrote: post #19
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. 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.
Post reply on HN