TY - GEN

T1 - Exploiting data-independence for fast belief-propagation

AU - McAuley, Julian J.

AU - Caetano, Tibério S.

PY - 2010

Y1 - 2010

N2 - 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 certain labeling given an observation, and a data-independent term, encoding some prior on labelings. Often, data-dependent factors 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 substantially faster by appropriately preprocessing their data-independent terms. Our main result is to show that message-passing in any such pairwise model has an expected-case exponent of only 1.5 on the number of states per node, leading to significant improvements over existing quadratic-time solutions.

AB - 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 certain labeling given an observation, and a data-independent term, encoding some prior on labelings. Often, data-dependent factors 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 substantially faster by appropriately preprocessing their data-independent terms. Our main result is to show that message-passing in any such pairwise model has an expected-case exponent of only 1.5 on the number of states per node, leading to significant improvements over existing quadratic-time solutions.

UR - http://www.scopus.com/inward/record.url?scp=77956514708&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781605589077

T3 - ICML 2010 - Proceedings, 27th International Conference on Machine Learning

SP - 767

EP - 774

BT - ICML 2010 - Proceedings, 27th International Conference on Machine Learning

T2 - 27th International Conference on Machine Learning, ICML 2010

Y2 - 21 June 2010 through 25 June 2010

ER -