  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.
