Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models

Ankit Anand, Ritesh Noothigattu, Parag Singla,  Mausam
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1541-1549, 2017.

Abstract

Lifted inference algorithms commonly exploit symmetries in a probabilistic graphical model (PGM) for efficient inference. However, existing algorithms for Boolean-valued domains can identify only those pairs of states as symmetric, in which the number of ones and zeros match exactly (count symmetries). Moreover, algorithms for lifted inference in multi-valued domains also compute a multi-valued extension of count symmetries only. These algorithms miss many symmetries in a domain. In this paper, we present first algorithms to compute non-count symmetries in both Boolean-valued and multi-valued domains. Our methods can also find symmetries between multi-valued variables that have different domain cardinalities. The key insight in the algorithms is that they change the unit of symmetry computation from a variable to a variable-value (VV) pair. Our experiments find that exploiting these symmetries in MCMC can obtain substantial computational gains over existing algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-anand17a, title = {{Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models}}, author = {Anand, Ankit and Noothigattu, Ritesh and Singla, Parag and Mausam, }, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1541--1549}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/anand17a/anand17a.pdf}, url = {https://proceedings.mlr.press/v54/anand17a.html}, abstract = {Lifted inference algorithms commonly exploit symmetries in a probabilistic graphical model (PGM) for efficient inference. However, existing algorithms for Boolean-valued domains can identify only those pairs of states as symmetric, in which the number of ones and zeros match exactly (count symmetries). Moreover, algorithms for lifted inference in multi-valued domains also compute a multi-valued extension of count symmetries only. These algorithms miss many symmetries in a domain. In this paper, we present first algorithms to compute non-count symmetries in both Boolean-valued and multi-valued domains. Our methods can also find symmetries between multi-valued variables that have different domain cardinalities. The key insight in the algorithms is that they change the unit of symmetry computation from a variable to a variable-value (VV) pair. Our experiments find that exploiting these symmetries in MCMC can obtain substantial computational gains over existing algorithms.} }
Endnote
%0 Conference Paper %T Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models %A Ankit Anand %A Ritesh Noothigattu %A Parag Singla %A Mausam %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-anand17a %I PMLR %P 1541--1549 %U https://proceedings.mlr.press/v54/anand17a.html %V 54 %X Lifted inference algorithms commonly exploit symmetries in a probabilistic graphical model (PGM) for efficient inference. However, existing algorithms for Boolean-valued domains can identify only those pairs of states as symmetric, in which the number of ones and zeros match exactly (count symmetries). Moreover, algorithms for lifted inference in multi-valued domains also compute a multi-valued extension of count symmetries only. These algorithms miss many symmetries in a domain. In this paper, we present first algorithms to compute non-count symmetries in both Boolean-valued and multi-valued domains. Our methods can also find symmetries between multi-valued variables that have different domain cardinalities. The key insight in the algorithms is that they change the unit of symmetry computation from a variable to a variable-value (VV) pair. Our experiments find that exploiting these symmetries in MCMC can obtain substantial computational gains over existing algorithms.
APA
Anand, A., Noothigattu, R., Singla, P. & Mausam, . (2017). Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1541-1549 Available from https://proceedings.mlr.press/v54/anand17a.html.

Related Material