AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Lifted Inference via k-Locality
Martin Mladenov, Kristian Kersting

Last modified: 2013-06-29

Abstract


Lifted inference approaches exploit symmetries of a graphical model. So far, only the automorphismgroup of the graphical model has been proposed to formalize thesymmetries used. We show that this is only theGI-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 oflifting decreases monotonically with k.This induces a hierarchyof lifted inference algorithms, with lifted BP and MPLP at the bottom and exact inference methodsat the top. In between, there are relaxations whose liftings are equitable partitions of intermediate coarseness, which all can be computed in polynomial time.

Full Text: PDF