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

## 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: | 18 May 2016 18:05 |

Last Modified: | 25 Jul 2016 09:02 |

DOI: | 10.1162/NECO_a_00441 |