NonCount Symmetries in Boolean & MultiValued Prob. Graphical Models
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:15411549, 2017.
Abstract
Lifted inference algorithms commonly exploit symmetries in a probabilistic graphical model (PGM) for efficient inference. However, existing algorithms for Booleanvalued 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 multivalued domains also compute a multivalued extension of count symmetries only. These algorithms miss many symmetries in a domain. In this paper, we present first algorithms to compute noncount symmetries in both Booleanvalued and multivalued domains. Our methods can also find symmetries between multivalued 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 variablevalue (VV) pair. Our experiments find that exploiting these symmetries in MCMC can obtain substantial computational gains over existing algorithms.
Related Material


