Improvements to Variable Elimination and Symbolic Probabilistic Inference for evaluating Influence Diagrams

• Optimization of the order for the operations involved in the ID evaluation.
• Description of the Symbolic Probabilistic Inference for evaluating IDs.
• Improved version of the Variable Elimination algorithm for IDs.
• Use of Symbolic Probabilistic Inference in Lazy Evaluation of IDs.
• Several IDs from the literature are used in the experimentation.

An Influence Diagram is a probabilistic graphical model used to represent and solve decision problems under uncertainty. Its evaluation requires performing several combinations and marginalizations on the potentials attached to the Influence Diagram. Finding an optimal order for these operations, which is NP-hard, is an element of crucial importance for the efficiency of the evaluation. In this paper, two methods for optimizing this order are proposed. The first one is an improvement of the Variable Elimination algorithm while the second is the adaptation of the Symbolic Probabilistic Inference for evaluating Influence Diagrams. Both algorithms can be used for the direct evaluation of IDs but also for the computation of clique-to-clique messages in Lazy Evaluation of Influence Diagrams. In the experimental work, the efficiency of these algorithms is tested with several Influence Diagrams from the literature.