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

Evolution Is the New Deep Learning

sentient.ai

Post reply on HN
Print view View original

101–110 of 242 posts

Re: Evolution Is the New Deep Learning

#101

Post by evolutioner »

avip wrote: post #90
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…

Ok... so... let's say your A/B only optimizes the colour and location of a single CTA button, and conversion rate is your fitness. 2 previous generations have top/blue and bottom/red. How does the next one look?

Each generation has like 10~20 candidate websites. The better the conversion rate, the more likely it is to get chosen as a parent.

With your example, let's say two parents with top/blue and bottom/red are chosen, then their offspring will either be top/red or bottom/blue because we make sure the same website isn't tested twice.

More generally each feature of the offspring will be randomly picked from the features of the two parents.

So two parents A/A/B and B/C/B can give the offspring A/C/B or B/A/B. There is also some random mutations that are possible with a low likelihood.

link to the product: https://www.ascend.ai/

Re: Evolution Is the New Deep Learning

#102

Post by yazr »

mav3r1ck wrote: post #15

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. 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. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has…

In your experience, are GA/EA suitable for combinatorical problems?

My domain is basically a combinatorical problem on large, sparse graphs. I am currently focused on DL with lots of custom feature engineering. I am making progress but its slow.

Re: Evolution Is the New Deep Learning

#103

Post by inverse_pi »

mav3r1ck wrote: post #15

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. 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. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has…

My thesis was on Generic Algorithm. I stopped and started working on Deep Learning mainly because like you said, GAs don't really have a strong mathematical foundation. Ironically, no one could really explain why CNNs work mathematically either. I've heard a lot of hand-wavy arguments about local search, local sensitivity, etc. However, no one could really prove anything meaningful. There are some papers around certain types of architecture is invariant under certain types of affine transformations. But all of them sounds like trying to convince ourselves rather than putting a firm mathematical framework to guide our research. Maybe that's why natural inspired algorithms are getting attention, the community is throwing stuff on the wall to see what sticks. It's funny to me because Genetic Algorithms were once frowned upon by majority of the community. I guess the moral lesson is stop chasing what's trendy.

Re: Evolution Is the New Deep Learning

#104

Post by clickok »

hcrisp wrote: post #58
PeterisP wrote: post #54

Earlier quoted context omitted.

DL models don't often get stuck at local optima. In theory, they could be vulnerable to that, but in practice they are not, it simply doesn't happen in most practical supervised learning applications. I'm not up to date on theoretical research about this topic, but as far as I recall there are some interesting demonstrations on realistic problems showing that all the different "local" optima resulting from different…

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 can't comment on #4 but with regards to 1-2 we can make an argument that high dimensional space is generally friendly towards stochastic gradient descent.

Consider a neural net that produces a single output given `N` inputs– it's basically a function `f(x) = f(x_1, x_2, …, x_N)` A local minimum x* has the gradient `∇f(x) = (0, 0, …, 0)` and an NxN Hessian of the form `[H•f(x)]_{ij} = (∂^2 f)/(∂x_i ∂x_j)`.

The critical point is a local maximum if the Hessian is positive definite at x and a local minimum if it's negative definite; it's a saddle point otherwise. This corresponds to the Hessian having a mixture of positive and negative eigenvalues.

Heuristically, we have N eigenvalues, and absent prior information we can expect that the probability of each eigenvalue being positive is 1/2, and 1/2 for the eigenvalue being negative instead. So the probability of an arbitrary critical point being a local minimum is `(1/2)^N`, which becomes extremely small as N grows large. Large values of N are kinda the bread-and-butter of deep learning, so we expect that most critical points we'll encounter are saddle points. Additionally, the inherent noise in SGD means that we're unlikely to stay trapped at a saddle point, because once you're nudged away from the saddle, the rate at which you slide off it increases rapidly.

So if your net appears to have converged, it's probably at a local optimum with a reasonably deep basin of attraction, assuming you're using the bag of tricks we've accumulated in the last decade (stuff like adding a bit of noise and randomizing the order in which the training data is presented).

As for 3 & 5, we kinda cheat because if your model appears to have converged but is not performing adequately, we step outside of the learning algorithm and modify the structure of the neural net or tune the hyperparameters. I don't know if we'll ever have a general theory that explains why neural nets seem to work so well, because you'd have to characterize both the possible tasks and the possible models, but perhaps we'll gradually chip away at the problem as we gather more empirical data and formalize heuristics based on those findings.

Re: Evolution Is the New Deep Learning

#105

Post by sampo »

Cacti wrote: post #69
mav3r1ck wrote: post #15

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. 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. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has…

Yep. The original wave of genetic algorithms largely depended on some hand-wavy "building block" ideas that no one could really prove. It turned out that it was because proving them is impossible in the general sense, as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. So I was surprised to see them make a return about a decade later. Hopeful…

> as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all.

NFL theorems are, should I say, purely theoretical and provide no insight on real-world problems. Say we try to find a function that is an optimal solution to something. NFL theorems consider the space of all possible functions, the overwhelming majority of which are discontinuous. Whereas real life problems tend to have functions that are at least more or less continuous.

Re: Evolution Is the New Deep Learning

#106

Post by patkai »

I wrote my MSc thesis on Genetic Algorithms in 1998 and I've been waiting for the time when they become popular. There is a lot of discussion going on about the need for "explainable models" and I'm quite surprised that it's not considered trivial that e.g. Genetic Programming builds computer programs that are actually models. Explainability is of course harder but how much closer can you get to building models automatically?

Re: Evolution Is the New Deep Learning

#107

Post by letitgo12345 »

sampo wrote: post #105
Cacti wrote: post #69

Earlier quoted context omitted.

Yep. The original wave of genetic algorithms largely depended on some hand-wavy "building block" ideas that no one could really prove. It turned out that it was because proving them is impossible in the general sense, as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. So I was surprised to see them make a return about a decade later. Hopeful…

> as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. NFL theorems are, should I say, purely theoretical and provide no insight on real-world problems. Say we try to find a function that is an optimal solution to something. NFL theorems consider the space of all possible functions, the overwhelming majority of which are discontinuous. Whereas…

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 most possible objective functions -- i.e. exponentially more than the number of objective functions that don't have high Kolmogorov complexity. And all real world objective functions have comparatively low Kolmogorov complexity.

Re: Evolution Is the New Deep Learning

#108

Post by [deleted] »

resu_nimda wrote: post #64
mav3r1ck wrote: post #15

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. 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. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has…

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…

[deleted]

Re: Evolution Is the New Deep Learning

#110

Post by sampo »

letitgo12345 wrote: post #107
sampo wrote: post #105

Earlier quoted context omitted.

> as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. NFL theorems are, should I say, purely theoretical and provide no insight on real-world problems. Say we try to find a function that is an optimal solution to something. NFL theorems consider the space of all possible functions, the overwhelming majority of which are discontinuous. Whereas…

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 elements give absolutely no hint on what might be in an array element you haven't yet looked at. So there doesn't exist any more efficient strategies to find the maximum number, than linear or random search.

And the space of all possible functions mostly consists of discontinuous functions that are, for all purposes, just samples of random noise.

This is all NFL theorems say. I really don't understand how they got be such a big deal.

Post reply on HN