Hacker News Reader

Comment by reader5000 | Hacker News Reader

I wonder why gradient descent (gating all compute/memory operations with parameters, gradient updates to parameter vectors along sample loss gradient) ended up dominant over genetic programming (algorithms as parse trees, mutate/recombine to minimize sample loss). Both seem equally theoretically unjustified, although I guess SGD is more friendly for gpus.

Also I wonder if all programming should just be done by showing a sgd-solver example i/o. Of course this notion has been around since the 80s with prolog but apparently representing "concepts" as 1000 dimension feature vectors is more robust than single boolean variables.

View on HN

FAIRie here. GA is essentially guess-and-check. SGD doesn't require guess or even check; if your error function is differentiable, and you didn't screw up the chain rule, you know what direction to head in to make it go down. For large models with lots of parameters, finding a setting for each parameter that makes the model as a whole go down by random choice has complexity n * f(n) for some monotonically increasing f, while SGD really finds you your next model, with decent guarantees it will be better, in O(n) time.

The theoretical hand-wringing about SGD for neural nets is that their loss surface isn't convex. It turns out this doesn't matter. The loss surface is a high-dimensional egg-carton, and you need to get winning-the-lottery-while-struck-by-lightning unlucky to find a significantly shallow local minimum. There are lots of saddle points, and you need to do something to drive out of those, but stochasticity seems sufficient in practice.

It doesn't have anything to do with GPUs. Genetic programming simply does not actually work for solving any nontrivial problem, in particular it does not work significantly better (and oftentimes worse) than brute force search.

Well, finding stable lifeforms is a nontrivial problem, assuming GP is somewhat faithful to biological evolution.

That's definitely the best problem ever solved by GP, though given the unfathomably enormous computational resources poured into it, it's still hard to say it was any better than a brute force approach! ;)

It's almost definitely better than brute force. The number of possible sequences of dna of size n base pairs is exponential in n.

The earth has only existed ~1e9 years. Assuming some finite average number of "computational ops per year", the number of possible dna strands quickly exceeds the total computational capacity of the planet since its birth.

Evolution is not trying to find one particular DNA string out of that exponentially sized set. There are lots of members of that set that are viable organisms.

In any case this is beside the point. The fact remains that genetic programming is a class of algorithms that has not been succesful in the slightest. People should just stop talking about it as if it was anything other than a complete failure, since that will only lead to even more wasted human effort. Gradient descent on the other hand is hugely succesful in solving a wide variety of real problems.

Im not advocating GP > nn+grad. I'm just saying nobody knows why nn+grad performs better on practical problems. Also nn+grad methods were essentially complete failures for the first 3-4 decades of their existence (invented in 60s, legit results like Lecun or Hinton in like 90s/00s).

This is so wrong at so many levels (sadly quite characteristic of the GA crowd) that I can only suggest reading up on the background and the math of it. Good keywords would be stochastic gradient descent, spin glasses and renormalization groups.

Whether nns have an interpretation as spin systems is completely nonresponsive to the hardness of training them. Ie minimizing "free energy" in spin systems is as NP-hard as minimizing training error in nns.

I'm guessing the search space of SGD is more manageable and GP is too generic

How would you go about designing a GP to identify handwritten digits from, let's say, 32x32 px images? You would need operators operating on the images, then other operators reducing its dimensionality to an answer between 0 and 9

I'm a big fan of GP but it seems they're stuck into a niche for now

GP has operators operating on a multidimensional input. GP builds simple programs, GP is good enough for the task, you could discover the same function that SGD discovers, but unfortunately in practice they are too slow, because they are blind to the landscape of the function.

With SGD, you know how to take steps in the direction of a better solution. You don't have that with genetic programming, there you just know if a solution happened to be better.

There's a weight perturbation algorithm, which is somewhat similar to genetic programming. The reason it's not as popular as SGD/backprop is it's computationally intensive, and it's hard to parallelize.

With sgd you only know a locally better solution. GP has this as well: take the best current instance and mutate it/recombine it.

Reply on news.ycombinator.com