Uprooting and Rerooting Graphical Models
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
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.
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