Improvements to variable elimination and symbolic probabilistic inference for evaluating influence diagrams. (English) Zbl 1351.68282
Summary: 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.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 62C10 | Bayesian problems; characterization of Bayes procedures |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
influence diagrams; probabilistic graphical models; combinatorial optimization problem; exact evaluation; heuristic algorithm; lazy evaluationReferences:
| [1] | Cabañas, R.; Madsen, A. L.; Cano, A.; Gómez-Olmedo, M., On SPI for evaluating Influence Diagrams, (Information Processing and Management of Uncertainty in Knowledge-Based Systems (2014), Springer), 506-516 · Zbl 1419.68091 |
| [2] | Cabañas, R.; Cano, A.; Gómez-Olmedo, M.; Madsen, A. L., On SPI-lazy evaluation of influence diagrams, (Probabilistic Graphical Models (2014), Springer), 97-112 · Zbl 1351.68281 |
| [3] | Howard, R. A.; Matheson, J. E., Influence diagram retrospective, Decis. Anal., 2, 3, 144-147 (2005) |
| [4] | Kjærulff, U. B.; Madsen, A. L., Bayesian Networks and Influence Diagrams: A Guide to Construction and Analysis, vol. 22 (2013), Springer · Zbl 1257.68008 |
| [5] | Shachter, R. D.; Bhattacharjya, D., Solving influence diagrams: exact algorithms, (Wiley Encyclopedia of Operations Research and Management Science (2010)) |
| [6] | Shachter, R. D., Evaluating influence diagrams, Oper. Res., 871-882 (1986) |
| [7] | Madsen, A. L.; Jensen, F. V., Lazy evaluation of symmetric Bayesian decision problems, (Proceedings of the 15th Conference on Uncertainty in AI (1999), Morgan Kaufmann Publishers Inc.), 382-390 |
| [8] | Jensen, F.; Jensen, F. V.; Dittmer, S. L., From Influence Diagrams to junction trees, (Proceedings of the 10th International Conference on Uncertainty in AI (1994), Morgan Kaufmann Publishers Inc.), 367-373 |
| [9] | Bloemeke, M.; Valtorta, M., A hybrid algorithm to compute marginal and joint beliefs in Bayesian networks and its complexity, (Proceedings of the 14th Conference on Uncertainty in AI (1998), Morgan Kaufmann Publishers Inc.), 16-23 |
| [10] | Shachter, R. D.; D’Ambrosio, B.; Del Favero, B., Symbolic probabilistic inference in belief networks, (AAAI, vol. 90 (1990)), 126-131 |
| [11] | Li, Z.; D’Ambrosio, B., Efficient inference in Bayes networks as a combinatorial optimization problem, Int. J. Approx. Reason., 11, 1, 55-81 (1994) · Zbl 0808.68098 |
| [12] | D’Ambrosio, B.; Burgess, S., Some experiments with real-time decision algorithms, (Proceedings of the 12th International Conference on Uncertainty in AI (1996), Morgan Kaufmann Publishers Inc.), 194-202 |
| [13] | Shenoy, P. P., Binary join trees for computing marginals in the Shenoy-Shafer architecture, Int. J. Approx. Reason., 17, 2, 239-263 (1997) · Zbl 0939.68021 |
| [14] | Geiger, D.; Verma, T.; Pearl, J., Identifying independence in Bayesian networks, Networks, 20, 5, 507-534 (1990) · Zbl 0724.05066 |
| [15] | Shachter, R. D., Bayes-ball: rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams), (Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (1998), Morgan Kaufmann Publishers Inc.), 480-487 |
| [16] | Fagiuoli, E.; Zaffalon, M., A note about redundancy in influence diagrams, Int. J. Approx. Reason., 19, 3, 351-365 (1998) · Zbl 0947.68141 |
| [17] | Nilsson, D.; Lauritzen, S. L., Evaluating influence diagrams using LIMIDs, (Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (2000), Morgan Kaufmann Publishers Inc.), 436-445 |
| [18] | Jensen, F.; Nielsen, T., Bayesian Networks and Decision Graphs (2007), Springer-Verlag · Zbl 1277.62007 |
| [19] | Zhang, N.; Poole, D., Exploiting causal independence in Bayesian network inference, J. Artif. Intell. Res., 5, 301-328 (1996) · Zbl 0900.68384 |
| [20] | Kjærulff, U., Triangulation of graphs - algorithms giving small total state space (1990), Department of Mathematics and Computer Science, Aalborg University: Department of Mathematics and Computer Science, Aalborg University Denmark, Research report R-90-09 |
| [21] | Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), MIT Press · Zbl 1183.68483 |
| [22] | Bodlaender, H. L., A linear time algorithm for finding tree-decompositions of small treewidth, (Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (1993), ACM), 226-234 · Zbl 1310.05194 |
| [23] | Robertson, N.; Seymour, P. D., Graph minors. IV. Tree-width and well-quasi-ordering, J. Comb. Theory, Ser. B, 48, 2, 227-254 (1990) · Zbl 0719.05032 |
| [24] | Madsen, A. L.; Jensen, F. V., Lazy propagation: a junction tree inference algorithm based on lazy evaluation, Artif. Intell., 113, 1-2, 203-245 (1999) · Zbl 0939.68848 |
| [25] | Rose, D., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (Graph Theory and Computing, vol. 183 (1972)), 217 · Zbl 0266.65028 |
| [26] | Madsen, A. L., Variations over the message computation algorithm of lazy propagation, IEEE Trans. Syst. Man Cybern., Part B, Cybern., 36, 3, 636-648 (2005) |
| [28] | Bielza, C.; Gómez, M.; Ríos Insua, S.; Fernández del Pozo, J. A.; García Barreno, P.; Caballero, S.; Sánchez Luna, M., Ictneo system for jaundice management, Rev. R. Acad. Cienc. Exactas Fís. Nat., 92, 4, 307-315 (1998) |
| [29] | Raiffa, H., Decision Analysis: Introductory Lectures on Choices under Uncertainty (1968), Addison-Wesley · Zbl 0181.21802 |
| [30] | Dawid, P.; Lauritzen, S. L.; Spiegelhalter, D. J., Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks (2007), Springer · Zbl 1120.68444 |
| [31] | Qi, R.; Zhang, L.; Poole, D., Solving asymmetric decision problems with influence diagrams, (Proceedings of the Tenth International Conference on Uncertainty in Artificial Intelligence (1994), Morgan Kaufmann Publishers Inc.), 491-497 |
| [32] | Marcot, B.; Holthausen, R.; Raphael, M.; Rowland, M.; Wisdom, M., Using bayesian belief networks to evaluate fish and wildlife population viability under land management alternatives from an environmental impact statement, For. Ecol. Manag., 153, 1, 29-42 (2001) |
| [33] | Goutis, C., A graphical method for solving a decision analysis problem, IEEE Trans. Syst. Man Cybern., 25, 8, 1181-1193 (1995) |
| [34] | Yuan, C.; Wu, X.; Hansen, E., Solving multistage influence diagrams using branch-and-bound search, (Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, UAI 2010 (2010)), 691-700 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
