We present a method for sampling high-dimensional probability spaces, applicable to Markov fields with both discrete and continuous variables, based on an approximate acyclic representation of the probability density. Our method generalizes and places in a common framework some recent work on computing renormalized Hamiltonians and stochastic multigrid sampling.

An acyclic representation of a probability distribution function (PDF) is obtained when one chooses an ordering of the variables and writes the PDF as a product of conditional probabilities, so that the probability of any variable is conditional only on the variables that precede it in the ordering. An acyclic representation makes the sampling efficient, because it uses the sparsity present in the model. We derive an approximate acyclic representation for general graphs by finding marginals through a fast marginalization scheme. The partial derivatives of the logarithm of the marginal probability are computed approximately through stochastic linear projection onto a polynomial basis, followed by reconstruction of the marginal through integration. The projection is based on an optimized inner product, making possible the use of Gaussian quadrature. Probability distributions involving discrete variables are handled by embedding the PDFs in differentiable extensions. Our algorithm can be extended to the evaluation of renormalized Hamiltonians formed using general renormalization schemes.

The approximate acyclic representation of the PDF is then used for sampling. The variables are sampled in a fixed order, producing independent samples together with their sampling weights. We present an optimized sampling strategy that uses a maximum amount of information to choose individual variable values. The samples are further improved using techniques from particle filtering. We also introduce a block Markov chain Monte Carlo scheme based on the sampling weights. Finally, we present applications of our methodology to the Ising model.