Updating beliefs with incomplete observations.

*(English)*Zbl 1086.68599Summary: Currently, there is renewed interest in the problem, raised by Shafer in 1985, of updating probabilities when observations are incomplete (or set-valued). This is a fundamental problem in general, and of particular interest for Bayesian networks. Recently, Grünwald and Halpern have shown that commonly used updating strategies fail in this case, except under very special assumptions. We propose a new method for updating probabilities with incomplete observations. Our approach is deliberately conservative: we make no assumptions about the so-called incompleteness mechanism that associates complete with incomplete observations. We model our ignorance about this mechanism by a vacuous lower prevision, a tool from the theory of imprecise probabilities, and we use only coherence arguments to turn prior into posterior (updated) probabilities. In general, this new approach to updating produces lower and upper posterior probabilities and previsions (expectations), as well as partially determinate decisions. This is a logical consequence of the existing ignorance about the incompleteness mechanism. As an example, we use the new updating method to properly address the apparent paradox in the ‘Monty Hall’ puzzle. More importantly, we apply it to the problem of classification of new evidence in probabilistic expert systems, where it leads to a new, so-called conservative updating rule. In the special case of Bayesian networks constructed using expert knowledge, we provide an exact algorithm to compare classes based on our updating rule, which has linear-time complexity for a class of networks wider than polytrees. This result is then extended to the more general framework of credal networks, where computations are often much harder than with Bayesian nets. Using an example, we show that our rule appears to provide a solid basis for reliable updating with incomplete observations, when no strong assumptions about the incompleteness mechanism are justified.

##### MSC:

68T30 | Knowledge representation |

##### Keywords:

Incomplete observations; Updating probabilities; Imprecise probabilities; Coherent lower previsions; Vacuous lower previsions; Naive updating; Conservative updating; Bayesian networks; Credal networks; Puzzles; Credal classification
PDF
BibTeX
XML
Cite

\textit{G. de Cooman} and \textit{M. Zaffalon}, Artif. Intell. 159, No. 1--2, 75--125 (2004; Zbl 1086.68599)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Charnes, A.; Cooper, W.W., Programming with linear fractional functionals, Naval research logistic quarterly, 9, 181-186, (1962) · Zbl 0127.36901 |

[2] | Cozman, F.G., Credal networks, Artificial intelligence, 120, 199-233, (2000) · Zbl 0945.68163 |

[3] | Cozman, F.G., Separation properties of sets of probabilities, (), 107-115 |

[4] | de Campos, L.M.; Huete, J.F.; Moral, S., Probability intervals: a tool for uncertain reasoning, Internat. J. uncertainty, fuzziness and knowledge-based systems, 2, 167-196, (1994) · Zbl 1232.68153 |

[5] | de Campos, L.M.; Lamata, M.T.; Moral, S., The concept of conditional fuzzy measures, Internat. J. intelligent systems, 5, 237-246, (1990) · Zbl 0694.68058 |

[6] | de Cooman, G.; Zaffalon, M., Updating with incomplete observations, (), 142-150 |

[7] | de Finetti, B., La prévision: ses lois logiques, ses sources subjectives, Ann. inst. H. Poincaré, 7, 1-68, (1937), English translation in [23] · JFM 63.1070.02 |

[8] | de Finetti, B., Teoria delle probabilità, (1970), Einaudi Torino |

[9] | de Finetti, B., Theory of probability, (1975), Wiley Chichester, English Translation of [8], two volumes |

[10] | Fagin, R.; Halpern, J.Y., A new approach to updating beliefs, (), 347-374 · Zbl 0742.68067 |

[11] | Fagiuoli, E.; Zaffalon, M., 2U: an exact interval propagation algorithm for polytrees with binary variables, Artificial intelligence, 106, 77-107, (1998) · Zbl 0909.68083 |

[12] | Ferreira da Rocha, J.C.; Cozman, F.G., Inference with separately specified sets of probabilities in credal networks, (), 430-437 |

[13] | Gill, R.; Van der Laan, M.; Robins, J., Coarsening at random: characterisations, conjectures and counter-examples, (), 255-294 · Zbl 0918.62003 |

[14] | Grünwald, P.D.; Halpern, J.Y., Updating probabilities, J. artificial intelligence res, 243-278, (2003) · Zbl 1076.68579 |

[15] | Halpern, J.Y., A logical approach to reasoning about uncertainty: a tutorial, (), 141-155 |

[16] | Halpern, J.Y.; Tuttle, M., Knowledge, probability, and adversaries, J. ACM, 40, 4, 917-962, (1993) · Zbl 0783.68120 |

[17] | Herron, T.; Seidenfeld, T.; Wasserman, L., Divisive conditioning: further results on dilation, Philos. sci, 64, 411-444, (1997) |

[18] | Jaffray, J.-Y., Bayesian updating and belief functions, IEEE trans. systems man cybernet, 22, 1144-1152, (1992) · Zbl 0769.62001 |

[19] | Khachian, L.G., A polynomial algorithm for linear programming, Soviet math. dokl, 20, 191-194, (1979), English translation of [20] · Zbl 0409.90079 |

[20] | Khachian, L.G., A polynomial algorithm for linear programming, Dokl. akad. nauk SSSR, 244, 1093-1096, (1979), In Russian · Zbl 0414.90086 |

[21] | Kolmogorov, A.N., Grundbegriffe der wahrscheinlichkeitsrechnung, (1933), Springer Berlin · Zbl 0278.60002 |

[22] | Kolmogorov, A.N., Foundations of probability, (1950), Chelsea New York, English translation of [21] · Zbl 0074.12202 |

[23] | (), Second edition (with new material) 1980 |

[24] | Levi, I., The enterprise of knowledge, (1980), MIT Press London |

[25] | Little, R.J.A.; Rubin, D.B., Statistical analysis with missing data, (1987), Wiley New York |

[26] | Manski, C., Partial identification of probability distributions, (2003), Springer Berlin · Zbl 1047.62001 |

[27] | Miranda, E.; de Cooman, G.; Couso, I., Imprecise probabilities induced by multi-valued mappings, (), 1061-1068 |

[28] | Moral, S.; Cano, A., Strong conditional independence for credal sets, Ann. math. artificial intelligence, 35, 1-4, 295-321, (2002) · Zbl 1005.60006 |

[29] | Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA |

[30] | Peot, M.A.; Shachter, R.D., Learning from what you don’t observe, (), 439-446 |

[31] | Ramoni, M.; Sebastiani, P., Robust learning with missing data, Machine learning, 45, 2, 147-170, (2001) · Zbl 1007.68154 |

[32] | Seidenfeld, T.; Wasserman, L., Dilation for sets of probabilities, Ann. statist, 21, 1139-1154, (1993) · Zbl 0796.62005 |

[33] | Shafer, G., Conditional probability, Internat. statist. rev, 53, 261-277, (1985) · Zbl 0594.62002 |

[34] | Smith, C.A.B., Consistency in statistical inference and decision, J. roy. statist. soc. ser. A, 23, 1-37, (1961) · Zbl 0124.09603 |

[35] | Strassen, V., Meßfehler und information, Z. wahr. verw. geb, 2, 273-305, (1964) · Zbl 0131.36402 |

[36] | P. Walley, Coherent lower (and upper) probabilities, Technical Report, University of Warwick, Coventry, 1981. Statistics Research Report 22 |

[37] | Walley, P., Statistical reasoning with imprecise probabilities, (1991), Chapman and Hall London · Zbl 0732.62004 |

[38] | Walley, P., Inferences from multinomial data: learning about a bag of marbles, J. roy. statist. soc. ser. B, 58, 3-57, (1996), With discussion · Zbl 0834.62004 |

[39] | Walley, P., Measures of uncertainty in expert systems, Artificial intelligence, 83, 1-58, (1996) |

[40] | Zaffalon, M., Exact credal treatment of missing data, J. statistical planning and inference, 105, 1, 105-122, (2002) · Zbl 1006.62027 |

[41] | Zaffalon, M., The naive credal classifier, J. statistical planning and inference, 105, 5-21, (2002) · Zbl 0992.62057 |

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.