4 ms·

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

by 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.
- Dn_Ab 14y ago
  You misconstrued. Reject as little as possible (<> reject little) was the motivation with respect to more naive random walks which suffer at dimensionality. I was not talking about leniency of proposal, where you are of course correct.
  - coherentpony 14y ago
    >You misconstrued. Reject as little as possible (<> reject little) was the motivation with respect to more naive random walks which suffer at dimensionality. Misunderstanding on my part; apologies. Can you clarify the statement on dimensionality? Moment calculations converge at a sharp rate of 1/sqrt(n). Riemann sums as approximations to integrals (moments) suffer from the curse of dimensionality.

by Dn_Ab 14y ago

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.

Dn_Ab 14y ago
You misconstrued. Reject as little as possible (<> reject little) was the motivation with respect to more naive random walks which suffer at dimensionality. I was not talking about leniency of proposal, where you are of course correct.
- coherentpony 14y ago
  >You misconstrued. Reject as little as possible (<> reject little) was the motivation with respect to more naive random walks which suffer at dimensionality. Misunderstanding on my part; apologies. Can you clarify the statement on dimensionality? Moment calculations converge at a sharp rate of 1/sqrt(n). Riemann sums as approximations to integrals (moments) suffer from the curse of dimensionality.