Abstract
Many AI inference problems arising in a wide variety of fields such as network communication, activity recognition, computer vision, machine learning, 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. In this talk, I will survey lifted message-passing algorithms that exploit 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 will 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.This talk is based on collaborations with Babak Ahmadi, Youssef El Massaoudi, Fabian Hadiji, Sriraam Natarajan, and Scott Sanner.
Biography
Kristian Kersting is the head of the “statistical relational activity mining” (STREAM) group at Fraunhofer IAIS, Bonn, Germany, a research fellow of the University of Bonn, Germany, and a research affiliate of the Massachusetts Institute of Technology (MIT), USA. He received his Ph.D. from the University of Freiburg, Germany, in 2006. After a PostDoc at MIT, he joined Fraunhofer IAIS in 2008 to build up the STREAM research group using an ATTRACT Fellowship. His main research interests are statistical relational reasoning and learning (SRL), acting under uncertainty, and robotics. He has published over 60 peer-reviewed papers, has received the ECML Best Student Paper Award in 2006 and the ECCAI Dissertation Award 2006 for the best European dissertation in the field of AI, and is an ERCIM Cor Baayen Award 2009 finalist for the “Most Promising Young Researcher In Europe in Computer Science and Applied Mathematics”. He gave several tutorials at top conferences (AAAI, ECML-PKDD, ICAPS, IDA, ICML, ILP) and co-chaired MLG-07, SRL-09 and the recent AAAI-10 workshop on Statistical Relational AI (StarAI-10). He (will) serve(d) as area chair for ECML-06, ECML-07, ICML-10, as Senior PC member at IJCAO-10, and on the PC of several top conference (IJCAI, AAAI, ICML, KDD, RSS, ECAI, ECML/PKDD, ICML, ILP, …). He was a guest co-editor for special issues of the Annals of Mathematics and AI (AMAI), the Journal of Machine Learning Research (JMLR), and the Machine Learning Journal (MLJ). Currently, he serves on the editorial board of the Machine Learning Journal (MLJ) and the Journal of Artificial Intelligence Research (JAIR).