Abstract

Many AI inference problems arising in a wide variety of fields such as machine learning, semantic web, network communication, computer vision, and robotics can be solved using message-passing algorithms that operate on factor graphs. Often, however, we are facing inference problems with symmetries not reflected in the factor graph structure and, hence, not exploitable by efficient message-passing algorithms. For instance, unifying first-order logic and probability is a long-standing goal of AI, and in recent years many representations combining aspects of the two have been proposed. In the inference stage, however, they still operate on a mostly propositional representation level and do not exploit the additionaly symmetries often induced.

In this talk, I shall present lifted message-passing algorithms that exploit such additional symmetries. Starting from a given factor graph, they essentially first construct a lifted factor graph of supernodes and superfactors, corresponding to sets of nodes and factors that send and receive the same messages, i.e., that are indistinguishable given the evidence. Then, they run a modified message-passing algorithm on the lifted factor. In particular, I shall present lifted variants of loopy and Gaussian belief propagation as well as warning and survey propagation, and demonstrate that significant efficiency gains are obtainable, often by orders of magnitude. These contributions advance the theoretical understanding of inference within large probabilistic models. More importantly, they put a ‘Big Picture’ view on AI in reach that can be called “Statistical Relational AI”.