Rapidly Mixing Gibbs Sampling for a Class of Factor Graphs Using Hierarchy Width
Gibbs sampling on factor graphs is a widely used inference technique, which often produces good empirical results. Theoretical guarantees for its performance are weak: even for tree structured graphs, the mixing time of Gibbs may be exponential in the number of variables. To help understand the behavior of Gibbs sampling, we introduce a new (hyper)graph property, called hierarchy width. We show that under suitable conditions on the weights, bounded hierarchy width ensures polynomial mixing time. Our study of hierarchy width is in part motivated by a class of factor graph templates, hierarchical templates, which have bounded hierarchy width-regardless of the data used to instantiate them. We demonstrate a rich application from natural language processing in which Gibbs sampling provably mixes rapidly and achieves accuracy that exceeds human volunteers.
This paper develops a new property of hypergraphs that helps bound the mixing time in Gibbs sampling. Analyzing the mixing time is always a hard problem in MCMC, so this paper addresses an important issue in Gibbs sampling. The paper defines the notion of hierarchy width for factor graphs. The main result that the authors show is that, the mixing time is exponential in the hierarchy-width of the factor graph and the maximum difference in weights encoded by the potentials of the factor graph. The authors then show that for specific factor graph templates, the aforementioned results can be applied and the mixing time of Gibbs sampling can be bounded polynomially in the number of variables that instantiate the templates.The main novelty is theoretical results that show that for specific classes of template factor graphs, Gibbs sampling mixes rapidly.Figure 1 seems to come out of the blue. It is hard to understand this figure since almost everything in this figure is explained much later. One of the main problems with Gibbs sampling is mixing when there are 0 values (or near-determinism) in the potentials. I was not sure how your results would change in such cases. Are there some assumptions about the underlying distribution structure.What is the treewidth typically when factor graph templates are hierarchical? That is, can we have high treewidth models using these templates? If not, then it might not require approximate inference such as Gibbs sampling.I was a little confused by what the three semantics represent. That is, is there a drawback from using the logical/ratio semantics (where your results hold) over the linear semantics (where your results do not hold)On the real world applications, if only subgraphs are hierarchical do your results of rapid mixing hold? I assumed that you need the entire factor graph template to be hierarchical as in section 3.1. Does this happen often in practice?