4 ms·

I wonder why gradient descent (gating all compute/memory operations with parameters, gradient updates to parameter vectors along sample loss gradient) ended up

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.

lars 11y ago
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.
- p1esk 11y ago
  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.
- reader5000 11y ago
  With sgd you only know a locally better solution. GP has this as well: take the best current instance and mutate it/recombine it.
raverbashing 11y ago
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
- skimpycompiler 11y ago
  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.
jules 11y ago
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.
- reader5000 11y ago
  Well, finding stable lifeforms is a nontrivial problem, assuming GP is somewhat faithful to biological evolution.
  - _broody 11y ago
    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! ;)
    - reader5000 11y ago
      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.
      - jules 11y ago
        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.
kmavm 11y ago
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.

lars 11y ago

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.

p1esk 11y ago
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.
reader5000 11y ago
With sgd you only know a locally better solution. GP has this as well: take the best current instance and mutate it/recombine it.

raverbashing 11y ago

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

skimpycompiler 11y ago
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.

jules 11y ago

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.

reader5000 11y ago
Well, finding stable lifeforms is a nontrivial problem, assuming GP is somewhat faithful to biological evolution.
- _broody 11y ago
  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! ;)
  - reader5000 11y ago
    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.
    - jules 11y ago
      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.

kmavm 11y ago

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.