CUED Publications database

Model reductions for inference: generality of pairwise, binary, and planar factor graphs.

Eaton, F and Ghahramani, Z (2013) Model reductions for inference: generality of pairwise, binary, and planar factor graphs. Neural Comput, 25. pp. 1213-1260.

Full text not available from this repository.

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.

Item Type: Article
Subjects: UNSPECIFIED
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 07 Mar 2014 11:29
Last Modified: 10 Mar 2014 17:04
DOI: 10.1162/NECO_a_00441

Actions (login required)

View Item