Lifted first-order belief propagation

摘要: Unifying first-order logic and probability is a long-standing goal of AI, in recent years many representations combining aspects the two have been proposed. However, inference them generally still at level propositional logic, creating all ground atoms formulas applying standard probabilistic methods to resulting network. Ideally, should be lifted as handling whole sets indistinguishable objects together, time independent their cardinality. Poole (2003) Braz et al. (2005, 2006) developed version variable elimination algorithm, but it extremely complex, does not scale realistic domains, has only applied very small artificial problems. In this paper we propose first scalable belief propagation (loopy or not). Our approach based on constructing network, where each node represents set that pass same messages during propagation. We then run prove correctness optimality our algorithm. Experiments show can greatly reduce cost inference.