MPE and partial inversion in lifted probabilistic variable elimination

Rodrigo De Salvo Braz, Eyal Amir, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is often convenient to represent probabilistic models in a first-order fashion, using logical atoms such as partners(X,Y) as random variables parameterized by logical variables, (de Salvo Braz, Amir, & Roth 2005), following (Poole 2003), give a lifted variable elimination algorithm (FOVE) for computing marginal probabilities from first-order probabilistic models (belief assessment, or BA). FOVE is lifted because it works directly at the first-order level, eliminating all the instantiations of a set of atoms in a single step, in some cases independently of the number of these instantiations. Previous work could treat only restricted potential functions. There, atoms' instantiations cannot constrain each other: predicates can appear at most once, or logical variables must not interact across atoms, In this paper, we present two contributions, The first one is a significantly more general lifted variable elimination algorithm, FOVE-P, that covers many cases where atoms share logical variables. The second contribution is to use FOVE-P for solving the Most Probable Explanation (MPE) problem, which consists of calculating the most probable assignment of the random variables in a model. The transition from BA to MPE is straightforward in prepositional models, but the lifted first-order case is harder. We introduce the notion of lifted assignments, a distribution of values to a set of random variables rather than to each individual one. Lifted assignments are cheaper to compute while being as useful as regular assignments over that group. Both contributions advance the theoretical understanding of lifted probabilistic inference.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Pages1123-1130
Number of pages8
StatePublished - Nov 13 2006
Event21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06 - Boston, MA, United States
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume2

Other

Other21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Country/TerritoryUnited States
CityBoston, MA
Period7/16/067/20/06

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'MPE and partial inversion in lifted probabilistic variable elimination'. Together they form a unique fingerprint.

Cite this