A study of influence diagrams and their generalizations
Pierre Ndilikilikesha · 1992
During the past decade, a number of algorithms have been developed for solving influence diagrams. Two of the best known algorithms are reduction algorithms and join-tree algorithms. Despite their apparent similarities, these two classes of algorithms have a number of differences. They are based on different graphical representations, and the types of problems they are applied to also differ. Join-tree algorithms are used exclusively for computing marginal probabilities; reduction algorithms are mainly used for computing optimal strategies. When computing marginals, reduction algorithms are thought to be inherently less efficient than join-tree algorithms. One of the goals of this dissertation is to bridge the gap between these two approaches. We start by developing a rigorous theoretical basis for influence diagrams. We introduce formal definitions, and we state and prove some well-known properties of influence diagrams. We then define potential influence diagrams--a hybrid representation that combines the simplicity and power of influence diagrams with the computational efficiency of join-tree algorithms. Their semantic flexibility allows us to develop a new reduction algorithm that computes marginal probabilities and/or optimal strategies without reversing arcs. By avoiding the divisions usually associated with arc reversals, the proposed algorithm improves significantly the efficiency of reduction algorithms. In fact, the proposed algorithm is equivalent to an instance of inward propagation in a join tree, equivalent in the sense that it involves the same numerical computations. Using this insight, we show that join-tree algorithms can also be used for computing optimal strategies.