Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

May 2013, Vol. 25, No. 5, Pages 1213-1260
(doi: 10.1162/NECO_a_00441)
© 2013 Massachusetts Institute of Technology
Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
Article PDF (1.28 MB)
Abstract

We offer a solution to the problem of efficiently translating algorithms between different types of discrete statistical model. We investigate the expressive power of three classes of model—those with binary variables, with pairwise factors, and with planar topology—as well as their four intersections. We formalize a notion of “simple reduction” for the problem of inferring marginal probabilities and consider whether it is possible to “simply reduce” marginal inference from general discrete factor graphs to factor graphs in each of these seven subclasses. We characterize the reducibility of each class, showing in particular that the class of binary pairwise factor graphs is able to simply reduce only positive models. We also exhibit a continuous “spectral reduction” based on polynomial interpolation, which overcomes this limitation. Experiments assess the performance of standard approximate inference algorithms on the outputs of our reductions.