Evolution Is the New Deep Learning • Hacker News Board

Re: Evolution Is the New Deep Learning

#121

Post by tree_of_item » Thu, Mar 22, 2018, 9:56 PM UTC

dorgo wrote: post #120

resu_nimda wrote: post #64

Earlier quoted context omitted.

1) One of the biggest reasons they fell out of favor for more "mathematical" approaches was that no one could really explain why exactly they worked. Kind of like how nobody can really explain how the brain works, or life in general. My gut feeling is that it is hubris to think that we are going to "figure out" intelligence with increasingly sophisticated mathematical models anytime soon. We are not giving proper cre…

> My gut feeling is that it is hubris to think that we are going to "figure out" intelligence with increasingly sophisticated mathematical models anytime soon. We did it already. Compter understand language, translate it, react to it. They can recognize items on a picture. Is there a task left which can't be done by computers better and faster than by humans? >Almost by definition, if we can analytically understand i…

> Is there a task left which can't be done by computers better and faster than by humans?

Are you serious? You think we're done?

Re: Evolution Is the New Deep Learning

#122

Post by beefield » Thu, Mar 22, 2018, 9:58 PM UTC

ScottBurson wrote: post #82

hcrisp wrote: post #58

Earlier quoted context omitted.

The theories I've heard for why you don't get stuck in local optima when using deep learning include: 1. It's hard to get stuck in multidimensional space 2. There are more saddles than convex local optima 3. There are many local optima, but they are all useful 4. Something related to spin glass theory (which I don't understand) 5. There is no theory, or we haven't found it yet; all we know is that it works in practic…

I think it's a combination of (1) and (2): in a high-dimensional space, for a local optimum to be convex it has to be convex in every dimension , the probability of which falls off exponentially in the number of dimensions. So in practice, they're all saddles.

I would not be comfortable making such assumptions on the topologies of fitness functions in high-dimensional spaces. I think it was not so long ago when I read an article here at HN about how weird the high dimensional spaces are, but can't find that quickly.

Further, the mindboggling size of the high-dimensional spaces make me all but guaranteed that not a single non-trivial neural network made by homo sapiens has ever been in global maxima. But I have nothing but my hunch on this.

Re: Evolution Is the New Deep Learning

#123

Post by yters » Thu, Mar 22, 2018, 10:00 PM UTC

_mhr_ wrote: post #86

yters wrote: post #59

The only thing EAs have going for them is a biological metaphor, the magic of Darwinian evolution, fountain of endless novelty. But, modern science shows evolution does not really work in a Darwinian manner, so thus the metaphor ends.

Can you provide a source for what modern science you're referring to? What alternative to Darwinian evolution do you have in mind?

https://en.wikipedia.org/wiki/Extended_evolutionary_synthesi...

Essentially, variation comes from many other sources than random mutation on DNA. Random mutation itself is seen as mostly a bad source of variation, leading to destruction of the genome.

Re: Evolution Is the New Deep Learning

#124

Post by evolutioner » Thu, Mar 22, 2018, 10:13 PM UTC

avilay wrote: post #116

evolutioner wrote: post #72

Earlier quoted context omitted.

Sentient employee here. I'll give an example on a problem for which we use evolutionary algorithms: website optimization. Say you want to try many various changes like the title of your page, the color of the background, the position of your buy button etc. We solve this problem by trying out random variations of these websites - like A/B testing with more candidates - and by crossing the best performing ones to crea…

What is the advantage of using evolutionary algos in this case over using something like Thompson Sampling or Contextual Multi-Armed Bandit? ( http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-a... )

They can actually work together.

Thompson Sampling / Multi-armed bandit algorithms are traffic allocation strategies to use the least amount of traffic to find the optimal variant.

So say you have version A/B/../N variants of a website, you can split the traffic equally or use a a bandit algorithm and find the best performing variant of it.

But that only helps you test N variants. If you want to test for 4 titles and 3 color buttons, 3 layouts and 5 images you already have 4x3x3x5=180 different variations and you can't test them all. Evolutionary algorithms can help you search through a much bigger search space:

First you try 10 variations, and allocate traffic equally or through a bandit algorithm. Then you combine the top performing candidates multiple times to create a new generation and start over again.

Evolution helps you find which candidates to try in a large search space and then a bandits algorithm can help you allocate traffic optimally.

You have to be careful with A/B testing with Bandit algorithms though. If the conversion rate changes over time or if you have visitors that don't always convert instantly you have to take that into account: https://www.chrisstucchio.com/blog/2015/dont_use_bandits.htm...

Re: Evolution Is the New Deep Learning

#125

Post by dorgo » Thu, Mar 22, 2018, 10:19 PM UTC

sampo wrote: post #110

letitgo12345 wrote: post #107

Earlier quoted context omitted.

Not just discontinuous but have high Kolmogorov complexity (effectively meaning that the value of the objective function is random and has no real relation to the input arguments) so not a surprise that you can't do better than random! Honestly, there's no justification to be using NFL theorems to explain why we can't optimize well on real world tasks. Edit: And such high Kolmogorov complexity function constitute mos…

Good notion, pointing the Kolmogorov complexity. Yeah. You have a function, so basically a long array of numbers, and you want to find the maximum. If the data in the array has some structure, like it's sampled from a sine wave or something, you can use some strategies to find the maximum. Like gradient descent, or binary search. Something. But if the array is filled with random numbers, looking at other arrays eleme…

>So there doesn't exist any more efficient strategies to find the maximum number, than linear or random search.

For classic old school computers yes. I'm not so sure about quantum computers. Consider: https://en.wikipedia.org/wiki/Grover%27s_algorithm

Re: Evolution Is the New Deep Learning

#126

Post by breuleux » Thu, Mar 22, 2018, 10:28 PM UTC

yorwba wrote: post #29

ewjordan wrote: post #19

Earlier quoted context omitted.

Wait, I'm confused...you're saying genetic approaches fell out of favor because they're basically just stochastic gradient descent? Most of modern DL relies heavily on SGD at various points during training. My impression is that they fell out of favor precisely because don't actually use any gradients, and end up converging on good maxima slower than you could if you used the gradients from the net. Am I off base her…

If you mutate genomes by small additive modifications to a vector of continuous parameters, then taking lots of samples and keeping the best is essentially a stochastic approximation to gradient descent. However, unlike the SGD used in deep learning, it doesn't make use of calculus and therefore requires many more samples (exponentially more, in the worst case) to get a gradient of equivalent accuracy. I.e. it's slow…

On the other hand, even if evolutionary algorithms require a lot of samples, they are embarrassingly parallel: you can easily try all samples simultaneously. If you have enough resources to throw at the problem, it can be faster (although more resource-intensive) to estimate the gradient this way than to compute an accurate gradient analytically.

Re: Evolution Is the New Deep Learning

#127

Post by pmcgrathm » Thu, Mar 22, 2018, 10:42 PM UTC

avilay wrote: post #116

evolutioner wrote: post #72

Earlier quoted context omitted.

Sentient employee here. I'll give an example on a problem for which we use evolutionary algorithms: website optimization. Say you want to try many various changes like the title of your page, the color of the background, the position of your buy button etc. We solve this problem by trying out random variations of these websites - like A/B testing with more candidates - and by crossing the best performing ones to crea…

What is the advantage of using evolutionary algos in this case over using something like Thompson Sampling or Contextual Multi-Armed Bandit? ( http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-a... )

They can work in conjunction - In the domain of website optimization, where visitor attributes are often greater predictors of value than website content, a system driven by search space optimization can more easily take into account changes in those variables - eg; time of day, traffic source, device type - and incorporate those inputs to climb multiple 'hills' simultaneously.

The allocation of traffic based on the evolving optimal search space (blue button for visitors from Facebook) can then be driven through an MAB or something similar.

Re: Evolution Is the New Deep Learning

#128

Post by ronjobber » Thu, Mar 22, 2018, 10:43 PM UTC

pas wrote: post #89

padthai wrote: post #83

Earlier quoted context omitted.

There is plenty of magic going on. Today we cannot replicate or understand how emergent properties born of biological structures. Not even in "simple" systems as the metabolic pathways.

We mapped the whole genome and connectome of C. elegans, no? And most of that is understood. For example, it seems to be a good model for substance addiction (especially for nicotine). That seems a pretty complex emergent behavior to me. If you mean bigger biology, yes, sure, we don't have a full map of functional genomics for humans, but we're getting there. Or maybe not, maybe it's so exponentially more complex, th…

We have the connectome of C. elegans, yes, but we are still pretty far from understanding how it 'works'. The functional connections are still an active area of research, and it is greatly complicated by connections not explicit in the connectome (neuromodulator effects), as well as the internal dynamics of neurons and non-linear network dynamics.

The connectome is necessary, but far from sufficient, to 'understand' a brain, even one made from only 302 neurons as in C. elegans.

Re: Evolution Is the New Deep Learning

#129

Post by pmalynin » Thu, Mar 22, 2018, 10:48 PM UTC

antirez wrote: post #113

pmalynin wrote: post #98

Earlier quoted context omitted.

Respectfully, We've had "learning-to-learn" algorithms for a few years now. Including LSTMs that can be learn the gradients for other LSTMs, and deep-RL algorithms that can optimize neural networks. Its hard to say its inventing new things... there is still a clear goal - a loss - and we are optimizing it; poorly in the case of genetic algorithms. I would say genetic methods are simply poorly described reinforcement…

I don't want to mean that this is "novel" at all, I played a lot with genetic programming like 20 years ago. However in my opinion genetic algorithms and genetic programming are not the same thing, while closely related: genetic programming is using genetic algorithms as a search strategy to find a way to write a program in order to solve a problem. It is more closely related to reinforcement learning in theory, you…

Right, but what would be the difference if this program was produced by Deep RL algorithm, where the state is the current program (an encoding of the program) and the actions are valid instructions in your stack language?

An episode in this case is an iterative call to the Deep RL system until it outputs at which step you give it a reward (negative number of collisions say), and before that you can send the actions to your stack machine.

Once you're satisfied with the final number, just concatenate all the produced actions to get your final program.

I just don't see a fundamental difference, especially once you start doing things like Asynchronous Actor-Critic et al. And then you can start doing Monte Carlo Tree Search on top of that since you have a simulator available...

Re: Evolution Is the New Deep Learning

#130

Post by cshenton » Thu, Mar 22, 2018, 10:52 PM UTC

make3 wrote: post #52

it's just not. Evolution learns more sloly than reinforcement learning, which itself learns much more slowly than supervised deep learning. Evolution doesn't have gradiants, and needs a huge amount of samples to learn anything.

Actually, evolutionary strategies make use of either empirical or naturalised gradients on the search space.