Lifted Message Passing: A Step Towards Gaining a 'Big Picture' View on AI

Add to your list(s) Download to your calendar using vCal

• Kristian Kersting
• Tuesday 30 November 2010, 10:00-11:00
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

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”.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.