Publication
Lifted Inference via k-Locality
Martin Mladenov; Kristian Kersting
In: Statistical Relational Artificial Intelligence, Papers from the 2013 AAAI Workshop. AAAI Conference on Artificial Intelligence (AAAI-2013), July 15, Bellevue, Washington, USA, AAAI Technical Report, Vol. WS-13-16, AAAI, 2013.
Abstract
Lifted inference approaches exploit symmetries of a graphical model. So far, only the automorphism group of the graphical model has been proposed to formalize the symmetries used. We show that this is only the GI-complete tip of a hierarchy and that the amount of lifting depends on how local the inference algorithm is: if the LP relaxation introduces constraints involving features over at most k variables, then the amount of lifting decreases monotonically with k. This induces a hierarchy of lifted inference algorithms, with lifted BP and MPLP at the bottom and exact inference methods at the top. In between, there are relaxations whose liftings are equitable partitions of intermediate coarseness, which all can be computed in polynomial time.