×

zbMATH — the first resource for mathematics

Credal networks. (English) Zbl 0945.68163
Summary: This paper presents a complete theory of credal networks, structures that associate convex sets of probability measures with directed acyclic graphs. Credal networks are graphical models for precise/imprecise beliefs. The main contribution of this work is a theory of credal networks that displays as much flexibility and representational power as the theory of standard Bayesian networks. Results in this paper show how to express judgements of irrelevance and independence, and how to compute inferences in credal networks. A credal network admits several extensions – several sets of probability measures comply with the constraints represented by a network. Two types of extensions are investigated. The properties of strong extensions are clarified through a new generalization of \(d\)-separation, and exact and approximate inference methods are described for strong extensions. Novel results are presented for natural extensions, and linear fractional programming methods are described for natural extensions. The paper also investigates credal networks that are defined globally through perturbations of a single network.

MSC:
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68R10 Graph theory (including graph drawing) in computer science
Software:
Hull
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, K.A.; Hooker, J.N., Bayesian logic, Decision support systems, Vol. 11, 191-210, (1994)
[2] Avriel, M., Advances in geometric programming, (1980), Plenum Press New York · Zbl 0432.00014
[3] Avriel, M.; Dembo, R.; Passy, U., Solution of generalized geometric programs, (), 203-226 · Zbl 0495.90073
[4] Bacchus, F., Representing and reasoning with probabilistic knowledge: A logical approach, (1990), MIT Press Cambridge, MA
[5] Berger, J.; Moreno, E., Bayesian robustness in bidimensional model: prior independence, J. statist. plann. inference, Vol. 40, 161-176, (1994) · Zbl 0805.62005
[6] Berger, J.O., Statistical decision theory and Bayesian analysis, (1985), Springer Berlin · Zbl 0572.62008
[7] Berger, J.O., Robust Bayesian analysis: sensitivity to the prior, J. statist. plann.inference, Vol. 25, 303-328, (1990) · Zbl 0747.62029
[8] Breese, J.S.; Fertig, K.W., Decision making with interval influence diagrams, (), 467-478
[9] Buntine, W.L., Operations for learning with graphical models, J. artificial intelligence res., Vol. 2, 159-225, (1994)
[10] Cano, A.; Cano, J.E.; Moral, S., Convex sets of probabilities propagation by simulated annealing, (), 4-8
[11] Cano, A.; Moral, S., A genetic algorithm to approximate convex sets of probabilities, (), 859-864
[12] Cano, J.; Delgado, M.; Moral, S., An axiomatic framework for propagating uncertainty in directed acyclic networks, Internat. J. approx. reason., Vol. 8, 253-280, (1993) · Zbl 0777.68071
[13] Charniak, E., Bayesian networks without tears, AI magazine, Vol. 12, 4, 50-63, (1991)
[14] Chrisman, L., Incremental conditioning of lower and upper probabilities, Internat. J. approx. reason., Vol. 13, 1, 1-25, (1995) · Zbl 0941.60002
[15] Chrisman, L., Independence with lower and upper probabilities, (), 169-177
[16] Chrisman, L., Propagation of 2-monotone lower probabilities on an undirected graph, (), 178-186
[17] Clarkson, K.L.; Mehlhorn, K.; Seidel, R., Four results on randomized incremental constructions, (), 463-474
[18] Cooper, G.F., The computational complexity of probabilistic inference using Bayesian belief networks, Artificial intelligence, Vol. 42, 393-405, (1990) · Zbl 0717.68080
[19] Couso, I.; Moral, S.; Walley, P., Examples of independence for imprecise probabilities, (), 121-130
[20] Cozman, F.G., Robustness analysis of Bayesian networks with local convex sets of distributions, (), 108-115
[21] Cozman, F.G., Irrelevance and independence in quasi-Bayesian networks, (), 89-96
[22] Cozman, F.G., Irrelevance and independence axioms in quasi-Bayesian theory, (), 128-136 · Zbl 0946.62004
[23] de Campos, L.; Moral, S., Independence concepts for convex sets of probabilities, (), 108-115
[24] ()
[25] Dechter, R., Bucket elimination: A unifying framework for probabilistic inference, (), 211-219 · Zbl 0910.68209
[26] DeRobertis, L.; Hartigan, J.A., Bayesian inference using intervals of measures, Ann. statist., Vol. 9, 2, 235-244, (1981) · Zbl 0468.62004
[27] Duffin, R.J.; Peterson, E.L., Geometric programming with signomials, J. optim. theory appl., Vol. 11, 1, 3-35, (1973) · Zbl 0238.90069
[28] Earman, J., Bayes or bust?, (1992), MIT Press Cambridge, MA
[29] Fagiuoli, E.; Zaffalon, M., 2U: an exact interval propagation algorithm for polytrees with binary variables, Artificial intelligence, Vol. 106, 1, 77-107, (1998) · Zbl 0909.68083
[30] Falk, J.; Soland, R., An algorithm for separable nonconvex programming problems, Management science, Vol. 15, 550-569, (1969) · Zbl 0172.43802
[31] Fine, T.L., Lower probability models for uncertainty and nondeterministic processes, J. statist. plann. inference, Vol. 20, 389-411, (1988) · Zbl 0677.60003
[32] Gebhardt, J.; Kruse, R., Learning possibilistic networks from data, (), 233-243
[33] Geiger, D.; Verma, T.; Pearl, J., D-separation: from theorems to algorithms, (), 139-148
[34] Giron, F.J.; Rios, S., Quasi-Bayesian behaviour: A more realistic approach to decision making?, (), 17-38 · Zbl 0459.62006
[35] Gochet, W.; Smeers, Y., A branch-and-bound method for reversed geometric programming, Oper. res., Vol. 27, 5, 983-996, (1979) · Zbl 0427.90077
[36] Good, I.J., Good thinking: the foundations of probability and its applications, (1983), University of Minnesota Press Minneapolis, MN · Zbl 0583.60001
[37] Gritzmann, P.; Klee, V., Mathematical programming and convex geometry, (), 627-674 · Zbl 0806.90098
[38] Ha, V.; Haddawy, P., Theoretical foundations for abstraction-based probabilistic planning, (), 291-298
[39] Hailperin, T., Sentential probability logic, (1996), Lehigh University Press Bethlehem, PA · Zbl 0922.03026
[40] Halpern, J.Y.; Fagin, R., Two views of belief: belief as generalized probability and belief as evidence, Artificial intelligence, Vol. 54, 275-317, (1992) · Zbl 0762.68055
[41] Herron, T.; Seidenfeld, T.; Wasserman, L., Divisive conditioning: further results on dilation, technical report 585, (1993), Department of Statistics, Carnegie Mellon University Pittsburgh, PA
[42] Ibaraki, T., Solving mathematical programming problems with fractional objective functions, (), 440-472
[43] Jaumard, B.; Hansen, P.; de Aragão, M.P., Column generation methods for probabilistic logic, ORSA J. comput., Vol. 3, 2, 135-148, (1991) · Zbl 0800.68864
[44] Jensen, F.V., An introduction to Bayesian networks, (1996), Springer New York
[45] ()
[46] Kearfott, R.B., A review of techniques in the verified solution of constrained global optimization problems, (), 23-60 · Zbl 0841.65049
[47] Kyburg, H.E., Bayesian and non-Bayesian evidential updating, Artificial intelligence, Vol. 31, 271-293, (1987) · Zbl 0622.68069
[48] Kyburg, H.E.; Pittarelli, M., Set-based Bayesianism, IEEE trans. systems man cybernet. A, Vol. 26, 3, 324-339, (1996)
[49] Laskey, K.B., Sensitivity analysis for probability assessments in Bayesian networks, IEEE trans. systems man cybernet., Vol. 25, 6, 901-909, (1995)
[50] Lavine, M., Sensitivity in Bayesian statistics, the prior and the likelihood, J. amer. statist. assoc., Vol. 86, 414, 396-399, (1991) · Zbl 0734.62005
[51] Lemmer, J.F.; Kyburg, H.E., Conditions for the existence of belief functions corresponding to intervals of belief, (), 488-493
[52] Levi, I., The enterprise of knowledge, (1980), The MIT Press Cambridge, MA
[53] Luenberger, D.G., Linear and nonlinear programming, (1989), Addison-Wesley Reading, MA · Zbl 0241.90052
[54] Lukasiewicz, T., Uncertain reasoning in concept lattices, (), 293-300
[55] Luo, C.; Yu, C.; Lobo, J.; Wang, G.; Pham, T., Computation of best bounds of probabilities from uncertain data, Computational intelligence, Vol. 12, 4, 541-566, (1996)
[56] Moral, S., A formal language for convex sets of probabilities, (), 274-281
[57] Musick, R., Minimal assumption distribution propagation in belief networks, (), 251-258
[58] Nilsson, N.J., Probabilistic logic, Artificial intelligence, Vol. 28, 71-87, (1986) · Zbl 0589.03007
[59] Papoulis, A., Probabilities, random variables and stochastic processes, (1991), McGraw-Hill New York · Zbl 0191.46704
[60] Passy, U., Global solutions of mathematical programs with intrinsically concave functions, (), 355-373 · Zbl 0455.65046
[61] Pearl, J., On probability intervals, Internat. J. approx. reason., Vol. 2, 211-216, (1988)
[62] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA
[63] Ruspini, E.H., The logical foundations of evidential reasoning, technical report SRIN408, (1987), SRI International Menlo Park, CA
[64] Russell, S.; Binder, J.; Koller, D.; Kanazawa, K., Local learning in probabilistic networks with hidden variables, (), 1146-1152
[65] Russell, S.J.; Norvig, P., Artificial intelligence: A modern approach, (1995), Prentice Hall Englewood Cliffs, NJ · Zbl 0835.68093
[66] Schaible, S.I.; Ziemba, W.T., Generalized concavity in optimization and economics, (1981), Academic Press New York
[67] Seidenfeld, T., Outline of a theory of partially ordered preferences, Philosophical topics, Vol. 21, 1, 173-188, (1993)
[68] Shafer, G., A mathematical theory of evidence, (1976), Princeton University Press Princeton, NJ · Zbl 0359.62002
[69] Shenoy, P.P.; Shafer, G., Axioms for probability and belief-function propagation, (), 169-198
[70] Shortliffe, E.H.; Buchanan, B.G., Rule-based expert systems: the MYCIN experiments of the Stanford heuristic programming project, (1985), Addison-Wesley Reading, MA
[71] Smith, C.A.B., Consistency in statistical inference and decision, J. roy. statist. soc. B, Vol. 23, 1-25, (1961) · Zbl 0124.09603
[72] Spirtes, P.; Glymour, C.; Scheines, R., Causality, prediction, and search, (1993), Springer New York · Zbl 0806.62001
[73] Suppes, P., The measurement of belief, J. roy. statist. soc. B, Vol. 2, 160-191, (1974) · Zbl 0287.60007
[74] Tessem, B., Interval probability propagation, Internat. J. approx. reason., Vol. 7, 95-120, (1992) · Zbl 0769.68113
[75] van der Gaag, L., Computing probability intervals under independency constraints, (), 457-466
[76] Walley, P., Statistical reasoning with imprecise probabilities, (1991), Chapman and Hall London · Zbl 0732.62004
[77] Walley, P., Measures of uncertainty in expert systems, Artificial intelligence, Vol. 83, 1-58, (1996)
[78] Walley, P.; Fine, T.L., Towards a frequentist theory of upper and lower probability, Ann. statist., Vol. 10, 3, 741-761, (1982) · Zbl 0488.62004
[79] Wasserman, L.A., Invariance properties of density ratio priors, Ann. statist., Vol. 20, 4, 2177-2182, (1992) · Zbl 0768.62021
[80] Wasserman, L.A., Recent methodological advances in robust Bayesian inference, (), 483-502
[81] Wasserman, L.A.; Kadane, J.B., Computing bounds on expectations, J. amer. statist. assoc., Vol. 87, 418, 516-522, (1992) · Zbl 0762.62011
[82] Wasserman, L.A.; Kadane, J.B., Bayes’ theorem for Choquet capacities, Ann. statist., Vol. 18, 3, 1328-1339, (1990) · Zbl 0736.62026
[83] Zaffalon, M., Inferenze e decisioni in condizioni di incertezza con modelli grafici orientati, ph.D. thesis, (1997), Università di Milano Milan, Italy
[84] Zaffalon, M., A credal approach to naive classification, (), 405-414
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.