3 ms·
Very cool. It reminds me a bit of the genetic programming work (aside: GP and genetic algos are different schools of research) on evolving programs where the ge
by jacques_chester 14y ago
Very cool. It reminds me a bit of the genetic programming work (aside: GP and genetic algos are different schools of research) on evolving programs where the genome is a string of assembler instructions.
Markov chain Monte Carlo would appear on its face to be better suited to this problem than a pure GP approach; at least to speed up convergence to a solution. It's actually quite different from GP -- no crossovers, more global state etc. Maybe a flock/swarm optimiser approach would be a better analogy in the nature-inspired computation world.
I'd be interested to know whether they experimented with other cost functions. For example, in some schemes, some candidates which fall outside the acceptable solution state (eg code that doesn't run, code that produces the wrong answer) are simply culled. In some you try to perform "repairs". In this case they've taken the other common approach of assigning a cost to incorrectness.
- ced 14y agoWikipedia claims that MCMC is for sampling from probability distributions, and that's what I was taught, too. Is there a way to use it to sample from a general search space?
- Dn_Ab 14y agoI don't think this is MCMC. The way I read it, monte-carlo was mentioned with regards to the idea of searching widely and sparsely. This is counter to the more targeted idea of MCMC, which generates a bunch of correlated samples to more efficiently sample the distribution. Another reason to suspect this is closer to genetic programming is that they talk about mutation and fitness. I got the impression that the algorithm searches a space of program trees via mutation, without keeping a population - so no crossover. If they did use MCMC it would be as a very specialized form, such as simulated annealing. Also, the Monte Carlo technique used in Go is with tree search, not MCMC. I find it amazing that randomization works so effectively, we must live in a friendly universe. Many real world problems tend to have enough exploitable structure that the idea of saving effort on optimization (xor measurement) via randomization is a powerful one.
- jacques_chester 14y ago> I got the impression that the algorithm searches a space of program trees via mutation, without keeping a population - so no crossover. My reading is that they're generating programs of gradually increasing length using markov chains (because the original superoptimizer work was generating random programs of progressively greater length until one worked). So not really a classic GP scheme at all. > Also, the Monte Carlo technique used in Go is with tree search, not MCMC. Monte Carlo tree search, right. That connection was drawn by the blogger, not in the paper. > I find it amazing that randomization works so effectively, we must live in a friendly universe. http://en.wikipedia.org/wiki/Anthropic_principle http://en.wikipedia.org/wiki/Anthropic_principle
- Dn_Ab 14y agoMy reading is that they're generating programs of gradually increasing length using markov chains (because the original superoptimizer work was generating random programs of progressively greater length until one worked). So not really a classic GP scheme at al. It seems my definition of Markov Chain Monte Carlo is more specific than yours (approximate a probability distribution using a simpler proportional one and conditional samples) while I am more generous about GP: any search technique using mutation operators on program trees. What do you make of the fact that the blogger specifically stated that the key to the technique is searching sparsely, which suggests very large jumps and runs counter to the idea of chains? There is also no hint of the idea of probabilistic acceptance. So even my mention of annealing is likely to be mistaken. Anthropic Principle Yes. Still doesn't stop me from chuckling at the audacity of things like Random Kitchen Sinks though (google it).
- jacques_chester 14y agoGood question about whether it's sparse searching. To me the point of using markov chains seemed to be to converge more quickly, not to increase coverage (where you'd actually want to introduce more variation). Annealing is always worth mentioning because a lot of the time, it's a better performer. GAs and GPs carry a lot of systemic overhead.