AAAI Publications, Twenty-Third International FLAIRS Conference

Font Size: 
Structured Value Elimination with D-Separation Analysis
Lionel Torti, Pierre-Henri Wuillemin

Last modified: 2010-05-06


In the last ten years, new models based on Bayesian Networks (BN) emerged to handle large and complex systems. These new models can be divided in two: the unification with First Order Logic and uncertainty (Markov Logic Networks, Bayesian Logic) and Knowledge Base Construction Models (Probabilistic Relational Models, Multy-Entity Bayesian Networks, Relational Bayesian Networks). SKOOB, a consortium of researchers and engineers in risk management, focuses on Probabilistic Relational Models (PRM). Inference in such models is a much more difficult task than in BN. Structured Value Elimination (SVE) is the state-of-the-art algorithm for PRM models. In this paper, we propose an enhancement of SVE based on a well known complexity reduction technique from BN. We show how to integrate a d-separation analysis in SVE and how this leads to important improvements for the inference task.


PRM; Inference; Graphical model; Bayesian Network; D-separation; SVE

Full Text: PDF