×

zbMATH — the first resource for mathematics

Evaluating interval-valued influence diagrams. (English) Zbl 1401.68319
Summary: Influence diagrams are probabilistic graphical models used to represent and solve sequential decision problems under uncertainty. Sharp numerical values are required to quantify probabilities and utilities. This might be an issue with real models, whose parameters are typically obtained from expert judgments or partially reliable data. We consider an interval-valued quantification of the parameters to gain realism in the modeling and evaluate the sensitivity of the inferences with respect to perturbations in the sharp values of the parameters. An extension of the classical influence diagrams formalism to support such interval-valued potentials is presented. The variable elimination and arc reversal inference algorithms are generalized to cope with these models. At the price of an outer approximation, the extension keeps the same complexity as with sharp values. Numerical experiments show improved performances with respect to previous methods. As a natural application, we propose these models for practical sensitivity analysis in traditional influence diagrams. The maximum perturbation level on single or multiple parameters preserving the optimal strategy can be computed. This allows the identification of the parameters deserving a more careful elicitation.
Reviewer: Reviewer (Berlin)

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
62C05 General considerations in statistical decision theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Antonucci, A.; de Campos, C.; Zaffalon, M., Probabilistic graphical models, (Augustin, T.; Coolen, F.; de Cooman, G.; Troffaes, M., Introduction to Imprecise Probabilities, (2014), Wiley), 207-229, Chap. 9 · Zbl 1298.68262
[2] Antonucci, A.; de Campos, C.; Zaffalon, M.; Huber, D., Approximate credal network updating by linear programming with applications to decision making, Int. J. Approx. Reason., 58, 25-38, (2014) · Zbl 1328.68225
[3] Artaso Landa, M. A., An empirical comparison of influence diagrams algorithms, (2014), UNED, Escuela Técnica Superior de Ingeniería Informática, Master’s thesis
[4] Benferhat, S.; Smaoui, S., Hybrid possibilistic networks, Int. J. Approx. Reason., 44, 3, 224-243, (2007) · Zbl 1116.68094
[5] 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
[6] Breese, J. S.; Fertig, K. W., Decision making with interval influence diagrams, (Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, (1990), Elsevier Science Inc.), 467-480
[7] Butz, C. J.; Chen, J.; Konkel, K.; Lingras, P., A comparative study of variable elimination and arc reversal in Bayesian network inference, (FLAIRS Conference, (2009))
[8] Cabañas, R.; Antonucci, A.; Cano, A.; Gómez-Olmedo, M., Variable elimination for interval-valued influence diagrams, (Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 13th European Conference, Proceedings, ECSQARU 2015, Compiègne, France, July 15-17, 2015, LNAI, vol. 9161, (2015), Springer), 541-551 · Zbl 06507047
[9] Cozman, F. G., Credal networks, Artif. Intell., 120, 199-233, (2000) · Zbl 0945.68163
[10] de Campos, L. M.; Huete, J. F.; Moral, S., Probability intervals: a tool for uncertain reasoning, Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 2, 02, 167-196, (1994) · Zbl 1232.68153
[11] E. Fagiuoli, M. Zaffalon, Decisions under uncertainty with credal influence diagrams, Tech. rep. 51-98, IDSIA, 1998 (unpublished). · Zbl 0947.68141
[12] Fertig, K. W.; Breese, J. S., Interval influence diagrams, (Proceedings of the Fifth Annual Conference on Uncertainty in Artificial Intelligence, (1990), North-Holland Publishing Co.), 149-162 · Zbl 0721.68061
[13] Fertig, K. W.; Breese, J. S., Probability intervals over influence diagrams, IEEE Trans. Pattern Anal. Mach. Intell., 15, 3, 280-286, (1993)
[14] Garcia, L.; Sabbadin, R., Complexity results and algorithms for possibilistic influence diagrams, Artif. Intell., 172, 8-9, 1018-1044, (2008) · Zbl 1183.62133
[15] Howard, R. A.; Matheson, J. E., Influence diagram retrospective, Decis. Anal., 2, 3, 144-147, (2005)
[16] Huntley, N.; Troffaes, M. C.M., Normal form backward induction for decision trees with coherent lower previsions, Ann. Oper. Res., 195, 1, 111-134, (2012) · Zbl 1259.91039
[17] Jeantet, G.; Spanjaard, O., Computing rank dependent utility in graphical models for sequential decision problems, Artif. Intell., 175, 7, 1366-1389, (2011) · Zbl 1225.68256
[18] Jensen, F.; Nielsen, T., Bayesian networks and decision graphs, (2007), Springer Verlag · Zbl 1277.62007
[19] Kikuti, D.; Cozman, F. G.; de Campos, C. P., Partially ordered preferences in decision trees: computing strategies with imprecision in probabilities, (IJCAI Workshop on Advances in Preference Handling, (2005)), 118-123
[20] Kjaerulff, U., Triangulation of graphs - algorithms giving small total state space, (1990), 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
[22] Nielsen, T.; Jensen, F., Sensitivity analysis in influence diagrams, IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum., 33, 2, 223-234, (2003)
[23] Raiffa, H., Decision analysis: introductory lectures on choices under uncertainty, (1968), Addison-Wesley · Zbl 0181.21802
[24] 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
[25] Shachter, R., Evaluating influence diagrams, Oper. Res., 871-882, (1986)
[26] Shenoy, P. P., Valuation-based systems for Bayesian decision analysis, Oper. Res., 40, 3, 463-484, (1992) · Zbl 0850.62131
[27] Troffaes, M. C.M., Decision making under uncertainty using imprecise probabilities, Int. J. Approx. Reason., 45, 1, 17-29, (2007) · Zbl 1119.91028
[28] Xu, H.; Smets, P., Reasoning in evidential networks with conditional belief functions, Int. J. Approx. Reason., 14, 2-3, 155-185, (1996) · Zbl 0941.68764
[29] Zaffalon, M., The naive credal classifier, J. Stat. Plan. Inference, 105, 1, 5-21, (2002) · Zbl 0992.62057
[30] Zaffalon, M.; Miranda, E., Desirability and the birth of incomplete preferences, CoRR
[31] Zhang, N.; Poole, D., Exploiting causal independence in Bayesian network inference, J. Artif. Intell. Res., 5, 301-328, (1996) · Zbl 0900.68384
[32] Zhou, L.; Liu, W.; Wang, L., Influence diagram model with interval-valued utilities, (Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing, (2009), IEEE Computer Society), 601-605
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.