Uprooting and Rerooting Graphical Models
View / Open Files
Authors
Weller, Adrian
Publication Date
2016-06-11Journal Title
Proceedings of the 33rd International Conference on Machine Learning
Publisher
Microtome Publishing
Volume
48
Pages
21-29
Language
English
Type
Article
This Version
AM
Metadata
Show full item recordCitation
Weller, A. (2016). Uprooting and Rerooting Graphical Models. Proceedings of the 33rd International Conference on Machine Learning, 48 21-29. https://doi.org/10.17863/CAM.236
Description
This is the author accepted manuscript. The final version is available from Microtome Publishing via http://www.jmlr.org/proceedings/papers/v48/weller16.html
Abstract
We show how any binary pairwise model may be ‘uprooted’ to a fully symmetric model, wherein original singleton potentials are transformed to potentials on edges to an added variable, and then ‘rerooted’ to a new model on the original number of variables. The new model is essentially equivalent to the original model, with the same partition function and allowing recovery of the original marginals or a MAP configuration, yet may have very different computational properties that allow much more efficient inference. This meta-approach deepens our understanding, may be applied to any existing algorithm to yield improved methods in practice, generalizes earlier theoretical results, and reveals a remarkable interpretation of the triplet-consistent polytope.
Identifiers
This record's DOI: https://doi.org/10.17863/CAM.236
This record's URL: https://www.repository.cam.ac.uk/handle/1810/256295