×

Complexity results for enhanced qualitative probabilistic networks. (English) Zbl 1184.68513

Summary: While quantitative probabilistic networks (QPNs) allow experts to state influences between nodes in the network as influence signs, rather than conditional probabilities, inference in these networks often leads to ambiguous results due to unresolved trade-offs in the network. Various enhancements have been proposed that incorporate a notion of strength of the influence, such as enhanced and rich enhanced operators. Although inference in standard (i.e., not enhanced) QPNs can be done in time polynomial to the length of the input, the computational complexity of inference in these enhanced networks has not been determined yet. In this paper, we introduce relaxation schemes to relate these enhancements to the more general case, where continuous influence intervals are used. We show that inference in networks with continuous influence intervals is NP-hard, and remains NP-hard when the intervals are discretised and the interval [ - 1, 1] is divided into blocks with length of \(\frac{1}{4}\). We discuss membership of NP and show how these general complexity results may be used to determine the complexity of specific enhancements to QPNs. Furthermore, this might give more insight in the particular properties of feasible and infeasible approaches to enhance QPNs.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] H.L. Bodlaender, F. van den Eijkhof, L.C. van der Gaag, On the complexity of the MPA problem in probabilistic networks, in: Proceedings of the Fifteenth European Conference on Artificial Intelligence, 2002, pp. 675-679.; H.L. Bodlaender, F. van den Eijkhof, L.C. van der Gaag, On the complexity of the MPA problem in probabilistic networks, in: Proceedings of the Fifteenth European Conference on Artificial Intelligence, 2002, pp. 675-679.
[2] Cooper, G., The computational complexity of probabilistic inference using Bayesian belief networks, Artificial Intelligence, 42, 2, 393-405 (1990) · Zbl 0717.68080
[3] Druzdzel, M.; Henrion, M., Belief propagation in qualitative probabilistic networks, (Carrete, N. P.; Singh, M., Proceedings of the Qualitative Reasoning and Decision Technologies (1993), CIMNE: CIMNE Barcelona)
[4] M. Druzdzel, M. Henrion, Intercausal reasoning with uninstantiated ancestor nodes, in: Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence, 1993, pp. 317-325.; M. Druzdzel, M. Henrion, Intercausal reasoning with uninstantiated ancestor nodes, in: Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence, 1993, pp. 317-325.
[5] Garey, M.; Johnson, D., Computers and Intractability. A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco · Zbl 0411.68039
[6] L.C. van der Gaag, S. Renooij, P.L. Geenen, Lattices for studying monotonicity of Bayesian networks, in: M. Studeny, J. Vomlel (Eds.), Proceedings of the Third European Workshop on Probabilistic Graphical Models, pp. 99-106.; L.C. van der Gaag, S. Renooij, P.L. Geenen, Lattices for studying monotonicity of Bayesian networks, in: M. Studeny, J. Vomlel (Eds.), Proceedings of the Third European Workshop on Probabilistic Graphical Models, pp. 99-106.
[7] Lauritzen, S. L.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application to expert systems, Journal of the Royal Statistical Society, 50, 2, 157-224 (1988) · Zbl 0684.68106
[8] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufman: Morgan Kaufman Palo Alto
[9] S. Renooij, L.C. van der Gaag, Enhancing QPNs for trade-off resolution, in: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, 1999, pp. 559-566.; S. Renooij, L.C. van der Gaag, Enhancing QPNs for trade-off resolution, in: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, 1999, pp. 559-566.
[10] S. Renooij, Qualitative approaches to quantifying probabilistic networks, Ph.D. thesis, Institute for Information and Computing Sciences, Utrecht University, The Netherlands, 2001.; S. Renooij, Qualitative approaches to quantifying probabilistic networks, Ph.D. thesis, Institute for Information and Computing Sciences, Utrecht University, The Netherlands, 2001.
[11] S. Renooij, L.C. van der Gaag, From qualitative to quantitative probabilistic networks, in: Proceedings of the Eighteenth Conference in Uncertainty in Artificial Intelligence, 2002, pp. 422-429.; S. Renooij, L.C. van der Gaag, From qualitative to quantitative probabilistic networks, in: Proceedings of the Eighteenth Conference in Uncertainty in Artificial Intelligence, 2002, pp. 422-429.
[12] S. Renooij, L.C. van der Gaag, Enhanced qualitative probabilistic networks for resolving trade-offs, Technical Report UU-CS-2006-034, Department of Information and Computing Sciences, Utrecht University, 2006.; S. Renooij, L.C. van der Gaag, Enhanced qualitative probabilistic networks for resolving trade-offs, Technical Report UU-CS-2006-034, Department of Information and Computing Sciences, Utrecht University, 2006. · Zbl 1183.68619
[13] Wellman, M., Fundamental concepts of qualitative probabilistic networks, Artificial Intelligence, 44, 3, 257-303 (1990) · Zbl 0717.68097
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.