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

Font Size: 
Lifted Inference on Transitive Relations
Wen Pu, Jaesik Choi, Eyal Amir

Last modified: 2013-06-29

Abstract


Lifted inference algorithms are able to boost efficiency through  exploiting symmetries and exchangeability of the underling  first-order probabilistic models.  Models with transitive relations  (e.g., if X and Y are friends and so are Y and Z, then X and Z will  likely be friends) are essential in social network analysis. With  n elements in a transitive relation model, the computational  complexity of exact propositional inference is O(2n(n-1)/2),  making it intractable for large domains. However, no tractable exact  inference on the transitive relations has been reported on the  transitive relations. In this paper, we report a novel deterministic  approximate lifted inference algorithm, which efficiently solves  inference problems on the transitive relations without degenerating  input models. We introduce an alternative graph representation for  first-order probabilistic models with formulas of homogeneous  bivariate predicates. The new representation, which is closely  related to exponential-family random graph models, leads to an  efficient deterministic approximate lifting algorithm by exploiting  the asymptotic properties of the state space. We perform experiments  to verify the effectiveness of the proposed algorithm.

Full Text: PDF