Projecting Markov Random Field Parameters for Fast Mixing
Markov chain Monte Carlo (MCMC) algorithms are simple and extremely powerful techniques to sample from almost arbitrary distributions. The flaw in practice is that it can take a large and/or unknown amount of time to converge to the stationary distribution. This paper gives sufficient conditions to guarantee that univariate Gibbs sampling on Markov Random Fields (MRFs) will be fast mixing, in a precise sense. Further, an algorithm is given to project onto this set of fast-mixing parameters in the Euclidean norm. Following recent work, we give an example use of this to project in various divergence measures, comparing univariate marginals obtained by sampling after projection to common variational methods and Gibbs sampling on the original parameters.
The principal contributions of this paper are, first, a set of sufficient conditions to guarantee that univariate Gibbs sampling on an MRF will be fast-mixing (Section 4), and an algorithm to project onto this set in the Euclidean norm (Section 5). A secondary contribution of this paper is considering an alternative matrix norm (the induced ∞-norm) that is somewhat looser than the spectral norm, but more computationally efficient. Following previous work [3], these ideas are experimentally validated via a projected gradient descent algorithm to minimize other divergences, and looking at the accuracy of the resulting marginals. The ability to project onto a fast-mixing parameter set may also be of independent interest. For example, it might be used during maximum likelihood learning to ensure that the gradients estimated through sampling are more accurate.
The paper considers the problem of marginal inference in discreteMRFs. It characterizes conditions on the MRF parameters under whicha Gibbs sampler will be rapidly mixing. Further, it outlines aprocedure by which the parameters of any discrete MRF can beprojected into this family of MRFs. Some preliminary experimentalresults are provided to illustrate the method.The paper makes an important contribution to approximate marginalinference in discrete MRFs. The ideas presented are clear and infact quite simple and natural in hindsight - which is a strength ofthe work. The approach is unique, but draws on existing ideas, such as approximate divergence computation usinglow tree-width sub-graphs and Gibbs sampling.There are several aspects of the work which need clarification -the suggestions below are to help improve the presentation, make itaccessible to a wider audience, and connecting it with otherrelevant related work:i) The idea of considering a smoothed approximation to a non-smoothproblem has been studied in the literature and there are existingresults, e.g., seeYurii Nesterov. Smooth minimization of non-smooth functions. Math.Program., 103(1):127–152, 2005.The characterization and discussion in Section 5 can be improvedusing this literature. In particular, for suitable variants of (4),one may be able to characterize (e.g., give bounds on) the natureof the approximation.ii) A brief comment on how the problem in Section 5.1 satisfies theconditions of Danskin's theorem will be helpful to readers. Also,please add a citation.iii) Section 6.2.2 is interesting. Some discussion on how to choose{\cal T} will be helpful (there is a discussion for the specificexperiments). For example, I wonder if one may be able to choose{\cal T} to be all spanning trees and get away with tractablecomputations using spanning tree LPs.iv) The work is close in spirit to [2], so a brief discussion onwhat aspects are different and/or does not directly follow from theIsing case will be helpful.v) Related to the above point - all experiments seem to be on Isingmodels, which is covered in [2]. Some evidence of performance ongeneral discrete MRFs is needed.vi) The experimental results are promising, but was hard to followin the first read. The proposed methodology works in two stages -approximate the parameters, then run Gibbs sampling. A discussionon the break-up of the run-time between these stages will behelpful. A study of the trade-off between the number of gradientsteps in the first stage and the number of Gibbs sampling steps inthe second stage will be instructive.vii) Over the last few years, a new approach to marginal inferencehas been studied - based on solving suitable random MAP inferenceproblems, e.g., see the following and their referencesT. Hazan and T. Jaakkola. On the partition function and randommaximum a-posteriori perturbations. ICML, 2012.T. Hazan, S. Maji, and T. Jaakkola. On sampling from the Gibbsdistribution with random maximum a posteriori perturbations. NIPS,2013.A discussion and comparison with the random-MAP inference approachwill make the paper stronger.viii) The writing is in bad shape, and seems to have been done in ahurry. Please do a careful pass to fix the flow and presentation.