Uprooting and Rerooting Graphical Models

Adrian Weller
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:21-29, 2016.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-weller16, title = {Uprooting and Rerooting Graphical Models}, author = {Weller, Adrian}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {21--29}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/weller16.pdf}, url = {https://proceedings.mlr.press/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.} }
Endnote
%0 Conference Paper %T Uprooting and Rerooting Graphical Models %A Adrian Weller %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-weller16 %I PMLR %P 21--29 %U https://proceedings.mlr.press/v48/weller16.html %V 48 %X 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.
RIS
TY - CPAPER TI - Uprooting and Rerooting Graphical Models AU - Adrian Weller BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-weller16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 21 EP - 29 L1 - http://proceedings.mlr.press/v48/weller16.pdf UR - https://proceedings.mlr.press/v48/weller16.html AB - 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. ER -
APA
Weller, A.. (2016). Uprooting and Rerooting Graphical Models. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:21-29 Available from https://proceedings.mlr.press/v48/weller16.html.

Related Material