Lifted Relational Probabilistic Inference

                       Eyal Amir
             Computer Science Department
       University of Illinois, Urbana-Champaign
              http://www.cs.uiuc.edu/~eyal

* Joint work with Rodrigo de-Salvo Braz and Dan Roth

Probabilistic models offer a natural way to model domains with noise
or incomplete information. It is often convenient to represent large
probabilistic models in a relational fashion, using logical atoms such
as partners(X,Y) as random variables parameterized by logical
variables. In this talk I present a lifted variable elimination
algorithm for computing marginal probabilities from such relational
probabilistic models. This algorithm is lifted because it works
directly at the First-Order-Logic level, eliminating all the
instantiations of a set of atoms in a single step, in some cases
independently of the number of these instantiations.  I also present a
lifted algorithm for computing Most-Probable Explanations of
observation which consists of calculating the most probable assignment
of the random variables in a model.  These contributions advance the
theoretical understanding of probabilistic inference with large
models.


Short Bio

Eyal Amir is an Assistant Professor of Computer Science at the
University of Illinois at Urbana-Champaign (UIUC) since January 2004.  His
research includes reasoning, learning, and decision making with
logical and probabilistic knowledge, dynamic systems, and commonsense
reasoning. Before UIUC he was a postdoctoral researcher at UC
Berkeley (2001-2003) with Stuart Russell, and did his Ph.D. on logical
reasoning in AI with John McCarthy. He received B.Sc. and
M.Sc. degrees in mathematics and computer science from Bar-Ilan
University, Israel in 1992 and 1994, respectively.  Eyal is a Fellow of
the Center for Advanced Studies and of the Beckman Institute
at UIUC (2007-2008), was chosen by IEEE as one of the "10 to watch in
AI" (2006), received the NSF CAREER award (2006), and awarded the
Arthur L. Samuel award for best Computer Science Ph.D. thesis (2001-2002)
at Stanford University.