1 Lifted First-Order Probabilistic Inference
Most probabilistic inference algorithms are specified and processed on a proposi-tional level, even though many domains are better represented by first-order specifications that compactly stand for a class of propositional instantiations. In the last fifteen years, many algorithms accepting first-order specifications have been proposed. However, these algorithms still perform inference on a mostly propositional model, generated by the instantiation of first-order constructs. When this is done, the rich and useful first-order structure is not explicit anymore. This first-order representation and structure allow us to perform lifted inference, that is, inference on the first-order representation directly, manipulating not only individuals but also groups of individuals. This has the potential of greatly speeding up inference. We precisely define the problem and present an algorithm that generalizes variable elimination and manipulates first-order representations in order to perform lifted inference. Probabilistic inference algorithms are widely employed in artificial intelligence. Among those, graphical models such as Bayesian and Markov networks (BNs and MNs respectively) (?)) are among the most popular. These models are specified by a set of conditional probabilities (for BNs) or factors, also called potential functions (for MNs). Both conditional probabilities and factors are defined over particular subsets of the available random variables, and map assignments of those random variables to positive real numbers (called potentials in MNs). For our purposes, it will be helpful to think of graphical models in general and simply consider conditional probabilities as a type of factor. For example, in an application for document subject classification, one can specify a dependence between the random variables subject apple, word mac (which