4 ms·

I 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

by Dn_Ab 14y ago

I 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 ago
  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 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 ago
    Good 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.
    - coherentpony 14y ago
      Annealing is hit or miss. I often have to sample a distribution on a domain that approximates an infinite dimensional space and annealing doesn't cut it for me. There are just far too many modes. Personally, I'd like to see what GAs and GPs have to offer in this regard.
      - jacques_chester 14y ago
        Well to pick between GA and GP, the question is: are you trying to evolve a list of parameters, or create a novel function/program? Parameters into function: use GA. Function/program: use GP. (speaking very roughly, that's the historical distinction between them)
        coherentpony 14y ago
        From a mathematical perspective, it looks as though your statement could imply that GA may potentially be viewed as a finite dimensional analogue of GP. Interesting.
coherentpony 14y ago
>This is counter to the more targeted idea of MCMC, which generates a bunch of correlated samples to more efficiently sample the distribution. The idea of MCMC is not to more efficiently sample a distribution through to use of correlated samples. Sampling a Gaussian exactly is more efficient than constructing a Markov chain with some random walk proposal (for example) to sample it. The idea of MCMC is to sample distributions that are considered intractable. Correlation in samples skews moment calculations, and this is bad. In fact, there is a whole field of research dedicated to designing proposals that allow chains to reach stationarity more quickly.
- Dn_Ab 14y ago
  Yeah I know that it is to aid in the computation of intractable inference, I should have been more careful in my wording. I am not saying it works by generating correlated samples, I'm saying because of how it works it will exhibit autocorrelation. Essentially, MCMC will generate samples that are near each other which will tend to be positively correlated. This property is why one needs to tune the variance of the proposal, do burn in and test for convergence. However, due to the nature of markov chains, large enough samples will have you sampling from P(x). The idea is to approximate the density of P(x) while trying to reject as little as possible. Hence less wasteful. But unlike simpler rejection methods samples will not be i.i.d. I've also read the actual paper now, which I should have done in the first place. I see how they make use of MCMC. And looking at it, I think my suspicion that what they have is very close to annealing (sans Temp) is accurate since they emulate density with cost and proposal with local edits. The particulars of the more general (though less generally applicable) MCMC as I understand it involve actual distributions. I'm not sure why the blog emphasizes searching sparsely instead of sampling.
  - coherentpony 14y ago
    >The idea is to approximate the density of P(x) while trying to reject as little as possible. Hence less wasteful. The idea is to approximate P(x) period. Rejecting as little as possible means nothing other than one's choice of proposal was poor. There are published works stating the optimal acceptance probability in high dimensions is 23.4% (see the work of Roberts et al (1997)). I think if one wanted to reject as little as possible one would have, albeit naïvely, tuned to a much higher acceptance rate.

by Dn_Ab 14y ago

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 ago
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 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 ago
  Good 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.
  - coherentpony 14y ago
    Annealing is hit or miss. I often have to sample a distribution on a domain that approximates an infinite dimensional space and annealing doesn't cut it for me. There are just far too many modes. Personally, I'd like to see what GAs and GPs have to offer in this regard.
    - jacques_chester 14y ago
      Well to pick between GA and GP, the question is: are you trying to evolve a list of parameters, or create a novel function/program? Parameters into function: use GA. Function/program: use GP. (speaking very roughly, that's the historical distinction between them)
      - coherentpony 14y ago
        From a mathematical perspective, it looks as though your statement could imply that GA may potentially be viewed as a finite dimensional analogue of GP. Interesting.

coherentpony 14y ago

>This is counter to the more targeted idea of MCMC, which generates a bunch of correlated samples to more efficiently sample the distribution. The idea of MCMC is not to more efficiently sample a distribution through to use of correlated samples. Sampling a Gaussian exactly is more efficient than constructing a Markov chain with some random walk proposal (for example) to sample it. The idea of MCMC is to sample distributions that are considered intractable. Correlation in samples skews moment calculations, and this is bad. In fact, there is a whole field of research dedicated to designing proposals that allow chains to reach stationarity more quickly.

Dn_Ab 14y ago
Yeah I know that it is to aid in the computation of intractable inference, I should have been more careful in my wording. I am not saying it works by generating correlated samples, I'm saying because of how it works it will exhibit autocorrelation. Essentially, MCMC will generate samples that are near each other which will tend to be positively correlated. This property is why one needs to tune the variance of the proposal, do burn in and test for convergence. However, due to the nature of markov chains, large enough samples will have you sampling from P(x). The idea is to approximate the density of P(x) while trying to reject as little as possible. Hence less wasteful. But unlike simpler rejection methods samples will not be i.i.d. I've also read the actual paper now, which I should have done in the first place. I see how they make use of MCMC. And looking at it, I think my suspicion that what they have is very close to annealing (sans Temp) is accurate since they emulate density with cost and proposal with local edits. The particulars of the more general (though less generally applicable) MCMC as I understand it involve actual distributions. I'm not sure why the blog emphasizes searching sparsely instead of sampling.
- coherentpony 14y ago
  >The idea is to approximate the density of P(x) while trying to reject as little as possible. Hence less wasteful. The idea is to approximate P(x) period. Rejecting as little as possible means nothing other than one's choice of proposal was poor. There are published works stating the optimal acceptance probability in high dimensions is 23.4% (see the work of Roberts et al (1997)). I think if one wanted to reject as little as possible one would have, albeit naïvely, tuned to a much higher acceptance rate.