Exploiting Data-Independence for Fast Belief-Propagation
Julian McAuley, Tibério S. Caetano · 2010
Maximum a posteriori (MAP) inference in graphical models requires that we maximize the sum of two terms: a data-dependent term, encoding the conditional likelihood of a cer-tain labeling given an observation, and a data-independent term, encoding some prior on labelings. Often, data-dependent fac-tors contain fewer latent variables than data-independent factors – for instance, many grid and tree-structured models contain only first-order conditionals despite having pairwise priors. In this paper, we note that MAP-inference in such models can be made sub-stantially faster by appropriately preprocess-ing their data-independent terms. Our main result is to show that message-passing in any such pairwise model has an expected-case ex-ponent of only 1.5 on the number of states per node, leading to significant improvements over existing quadratic-time solutions. 1.