×

Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks. (English) Zbl 1116.68080

Summary: This paper proposes two new algorithms for inference in credal networks. These algorithms enable probability intervals to be obtained for the states of a given query variable. The first algorithm is approximate and uses the hill-climbing technique in the Shenoy-Shafer architecture to propagate in join trees; the second is exact and is a modification of Rocha and Cozman’s branch-and-bound algorithm, but applied to general directed acyclic graphs.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amarger, S.; Dubois, D.; Prade, H., Constraint propagation with imprecise conditional probabilities, (Ambrosio, B. D’.; Smets, Ph.; Bonissone, P. P., Proceedings of the 7th Conference on Uncertainty in Artificial Intelligence (1991), Morgan & Kaufmann), 26-34
[2] A. Cano, S. Moral, A review of propagation algorithms for imprecise probabilities, in: Proceedings of the First International Symposium on Imprecise Probabilities and their Applications (ISIPTA’99), Ghent, 1999.; A. Cano, S. Moral, A review of propagation algorithms for imprecise probabilities, in: Proceedings of the First International Symposium on Imprecise Probabilities and their Applications (ISIPTA’99), Ghent, 1999.
[3] Cano, A.; Moral, S., Computing probability intervals with simulated annealing and probability trees, Journal of Applied Non-Classical Logics, 12, 2, 151-171 (2002) · Zbl 1060.68117
[4] Cano, A.; Moral, S., Using probabilities trees to compute marginals with imprecise probabilities, International Journal of Approximate Reasoning, 29, 1-46 (2002) · Zbl 1015.68206
[5] Cano, A.; Moral, S.; Salmerón, A., Penniless propagation in join trees, International Journal of Intelligent Systems, 15, 11, 1027-1059 (2000) · Zbl 0960.68152
[6] Cano, J. E.; Moral, S.; Verdegay-López, J. F., Propagation of convex sets of probabilities in directed acyclic networks, (Bouchon-Meunier, B.; etal., Uncertainty in Intelligent Systems (1993), Elsevier), 15-26
[7] Elvira Consortium, Elvira: an environment for creating and using probabilistic graphical models, in: J.A. Gámez, A. Salmerón (Eds.), Proceedings of the First European Workshop on Probabilistic Graphical Models, 2002, pp. 222-230.; Elvira Consortium, Elvira: an environment for creating and using probabilistic graphical models, in: J.A. Gámez, A. Salmerón (Eds.), Proceedings of the First European Workshop on Probabilistic Graphical Models, 2002, pp. 222-230.
[8] I. Couso, S. Moral, P. Walley, Examples of independence for imprecise probabilities, in: Proceedings of the First International Symposium on Imprecise Probabilities and their Applications (ISIPTA’99), 1999.; I. Couso, S. Moral, P. Walley, Examples of independence for imprecise probabilities, in: Proceedings of the First International Symposium on Imprecise Probabilities and their Applications (ISIPTA’99), 1999.
[9] Cozman, F. G., Robustness analysis of Bayesian networks with local convex sets of distributions, (Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (1997), Morgan & Kaufmann: Morgan & Kaufmann San Mateo) · Zbl 0945.68163
[10] Cozman, F. G., Credal networks, Artificial Intelligence, 120, 199-233 (2000) · Zbl 0945.68163
[11] Cozman, F. G., Graphical models for imprecise probabilities, International Journal of Approximate Reasoning, 39, 167-184 (2005) · Zbl 1099.68111
[12] Cozman, F. G., Irrelevance and independence relations in quasi-Bayesian networks, (Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-98) (1998), Morgan & Kaufman Publishers: Morgan & Kaufman Publishers San Francisco, CA), 89-96
[13] C.P. de Campos, F.G. Cozman, Inference in credal networks using multilinear programming, in: Proceedings of the Second Starting AI Researcher Symposium, 2004, pp. 50-61.; C.P. de Campos, F.G. Cozman, Inference in credal networks using multilinear programming, in: Proceedings of the Second Starting AI Researcher Symposium, 2004, pp. 50-61.
[14] C.P. de Campos, F.G. Cozman, Computing lower and upper expectations under epistemic independence, in: Proceedings of the Forth International Symposium on Imprecise Probabilities and their Applications (ISIPTA’05), Pittsburgh, PA, USA, 2005, pp. 78-87.; C.P. de Campos, F.G. Cozman, Computing lower and upper expectations under epistemic independence, in: Proceedings of the Forth International Symposium on Imprecise Probabilities and their Applications (ISIPTA’05), Pittsburgh, PA, USA, 2005, pp. 78-87.
[15] Fertig, K. W.; Breese, J. S., Interval influence diagrams, (Henrion, M.; Shacter, R. D.; Kanal, L. N.; Lemmer, J. F., Uncertainty in Artificial Intelligence, vol. 5 (1990), North-Holland: North-Holland Amsterdam), 149-161 · Zbl 0721.68061
[16] Kohlas, J., Information Algebras: Generic Structures for Inference. Information Algebras: Generic Structures for Inference, Discrete Mathematics and Theoretical Computer Science (2003), Springer-Verlag · Zbl 1027.68060
[17] Kullback, S.; Leibler, R. A., On information and sufficiency, Annals of Mathematical Statistics, 22, 76-86 (1951) · Zbl 0042.38403
[18] Lauritzen, S. L.; Spiegelhalter, D. J., Local computation with probabilities on graphical structures and their application to expert systems, Journal of the Royal Statistical Society, Ser. B, 50, 157-224 (1988) · Zbl 0684.68106
[19] Moral, S.; Cano, A., Strong conditional independence for credal sets, Annals of Mathematics and Artificial Intelligence, 35, 295-321 (2002) · Zbl 1005.60006
[20] Pearl, J., Probabilistic Reasoning with Intelligent Systems (1988), Morgan & Kaufman: Morgan & Kaufman San Mateo
[21] J.C.F. Rocha, F.G. Cozman, Inference in credal networks with branch-and-bound algorithms, in: Proceedings of the Third International Symposium on Imprecise Probabilities and their Applications (ISIPTA’03), 2003, pp. 482-495.; J.C.F. Rocha, F.G. Cozman, Inference in credal networks with branch-and-bound algorithms, in: Proceedings of the Third International Symposium on Imprecise Probabilities and their Applications (ISIPTA’03), 2003, pp. 482-495.
[22] Rocha, J. C.F.; Cozman, F. G.; de Campos, C. P., Inference in polytrees with sets of probabilities, (Meek, Christopher; Kjærulff, Uffe, Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (2003), Morgan & Kaufmann), 217-224
[23] Rocha, J. C.F.; Cozman, F. G., Inference with separately specified sets of probabilities in credal networks, (Darwiche, A.; Friedman, N., Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (2002), Morgan & Kaufmann)
[24] Shenoy, P. P., Binary join trees, (Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence (UAI-96) (1996), Portland: Portland Oregon), 492-499
[25] Shenoy, P. P.; Shafer, G., Axioms for probability and belief-function propagation, (Shachter; etal., Uncertainty in Artificial Intelligence, vol. 4 (1990), North-Holland), 169-198
[26] Tessen, B., Interval probability propagation, International Journal of Approximate Reasoning, 7, 95-120 (1992)
[27] H. Thöne, U. Güntzer, W. Kießling, Towards precision of probabilistic bounds propagation, in: Proceedings of the 8th Conference on Uncertainty in Artificial Intelligence, 1992, pp. 315-322.; H. Thöne, U. Güntzer, W. Kießling, Towards precision of probabilistic bounds propagation, in: Proceedings of the 8th Conference on Uncertainty in Artificial Intelligence, 1992, pp. 315-322.
[28] Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman and Hall: Chapman and Hall London · Zbl 0732.62004
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.