First-order Probabilistic Inference

Rodrigo de Salvo Braz

U. of Iillinois (Urbana-Champaign)


Logic and Probabilistic Inference are the two main inference models available today in Artificial Intelligence (AI). Logic, particularly first-order, is expressive and high-level, but lacks modelling of probabilistic uncertainty, which is important in many AI applications such as common sense, natural language processing and vision. Probabilistic Inference excels in modeling uncertainty and has been a success story in many areas. However, it lacks expressivity, being propositional rather than first-order. This prevents us from applying them to structured data such as collections of graphs, trees and frames in a convenient manner.

Several languages have been proposed that allow the expression of probabilistic knowledge in rich first-order languages. However, at inference time these solutions still operate at a mostly propositional level, by grounding the original first-order specification. This is a severe limitation because the number of propositional random variables will typically be exponential in the number of objects, and because the first-order specification contains explicit representation of valuable domain structure that gets lost in the process.

We present an algorithm that operates directly on the first-order level specification of a model, thus taking advantage of compact first-order structures and being potentially much faster. The algorithm keeps the representation as compact and high-level as possible even during inference. We show how this brings probabilistic inference closer to first-order logical inference methods such as resolution.


Rodrigo de Salvo Braz is finishing his Ph.D. at the Department of Computer Science, University of Illinois at Urbana-Champaign. Before UIUC he received a Masters in Computer Science from the University of Sao Paulo and spent two years at the Cognitive and Linguistic Sciences Department at Brown University. His research interests are First-Order Probabilistic Inference, Natural Language Processing, Machine Learning and Human-Computer Interaction.
Maintained by: Fei Sha