×

Local computations in Dempster-Shafer theory of evidence. (English) Zbl 1266.68177

Summary: When applying any technique of multidimensional models to problems of practice, one always has to cope with two problems: the necessity to represent the models with a “reasonable” number of parameters and to have sufficiently efficient computational procedures at one’s disposal. When considering graphical Markov models in probability theory, both of these conditions are fulfilled; various computational procedures for decomposable models are based on the ideas of local computations, whose theoretical foundations were laid by Lauritzen and Spiegelhalter.
The presented contribution studies a possibility of transferring these ideas from probability theory into Dempster-Shafer theory of evidence. The paper recalls decomposable models, discusses connection of the model structure with the corresponding system of conditional independence relations, and shows that under special additional conditions, one can locally compute specific basic assignments which can be considered to be conditional.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 3, 479-513 (1983) · Zbl 0624.68087
[2] Ben Yaghlane, B.; Smets, Ph.; Mellouli, K., Belief function independence: I. The marginal case, Int. J. Approx. Reason., 29, 1, 47-70 (2002) · Zbl 1015.68207
[3] Ben Yaghlane, B.; Smets, Ph.; Mellouli, K., Belief function independence: II. The conditional case, Int. J. Approx. Reason., 31, 1-2, 31-75 (2002) · Zbl 1052.68126
[4] A. Cano, S. Moral, Heuristic algorithms for the triangulation of graphs, in: B. Bouchon-Meunier, R.R. Yager, L.A. Zadeh (Eds.), Advances in Intelligent Computing-IPMU ’94, Paris, France, 1995.; A. Cano, S. Moral, Heuristic algorithms for the triangulation of graphs, in: B. Bouchon-Meunier, R.R. Yager, L.A. Zadeh (Eds.), Advances in Intelligent Computing-IPMU ’94, Paris, France, 1995.
[5] Daroch, J. N.; Lauritzen, S.; Speed, T. P., Markov fields and log linear interaction models for contingency tables, Ann. Stat., 8, 522-539 (1980) · Zbl 0444.62064
[6] Dempster, A. P., Upper and lower probabilities induced by a multi-valued mapping, Ann. Math. Stat., 38, 325-339 (1967) · Zbl 0168.17501
[7] Dempster, A. P.; Kong, A., Uncertain evidence and artificial analysis, J. Stat. Plann. Infer., 20, 355-368 (1988) · Zbl 0655.62110
[8] Edwards, D. E.; Havránek, T., A fast procedure for model search in multidimensional contingency tables, Biometrika, 72, 2, 339-351 (1985) · Zbl 0576.62067
[9] Jensen, F. V., Bayesian Networks and Decision Graphs (2001), IEEE Computer Society Press: IEEE Computer Society Press New York · Zbl 0973.62005
[10] Jiroušek, R., Composition of probability measures on finite spaces, (Geiger, D.; Shenoy, P. P., Proceedings of the 13th Conference Uncertainty in Artificial Intelligence UAI’97 (1997), Morgan Kaufman Publ.: Morgan Kaufman Publ. San Francisco, California), 274-281
[11] R. Jiroušek, On a conditional irrelevance relation for belief functions based on the operator of composition, in: Ch. Beierle, G. Kern-Isberner (Eds.), Dynamics of Knowledge and Belief, Proceedings of the Workshop at the 30th Annual German Conf. on Artificial Intelligence, Fern Universität in Hagen, Osnabrück, 2007, pp. 28-41.; R. Jiroušek, On a conditional irrelevance relation for belief functions based on the operator of composition, in: Ch. Beierle, G. Kern-Isberner (Eds.), Dynamics of Knowledge and Belief, Proceedings of the Workshop at the 30th Annual German Conf. on Artificial Intelligence, Fern Universität in Hagen, Osnabrück, 2007, pp. 28-41.
[12] R. Jiroušek, Factorization and decomposable models in Dempster-Shafer theory of evidence, in: Proceedings of the Workshop on Theory of Belief Functions, Brest, 2010.; R. Jiroušek, Factorization and decomposable models in Dempster-Shafer theory of evidence, in: Proceedings of the Workshop on Theory of Belief Functions, Brest, 2010.
[13] R. Jiroušek, Is it possible to define graphical models in Dempster-Shafer theory of evidence? in: Proceedings of the 13th International Workshop on Non-Monotonic Reasoning, Toronto, 2010.; R. Jiroušek, Is it possible to define graphical models in Dempster-Shafer theory of evidence? in: Proceedings of the 13th International Workshop on Non-Monotonic Reasoning, Toronto, 2010.
[14] R. Jiroušek, An attempt to define graphical models in Dempster-Shafer theory of evidence, in: Proceedings of the 5th International Conference on Soft Methods in Probability and Statistics, 2010, pp. 361-368.; R. Jiroušek, An attempt to define graphical models in Dempster-Shafer theory of evidence, in: Proceedings of the 5th International Conference on Soft Methods in Probability and Statistics, 2010, pp. 361-368.
[15] R. Jiroušek, P.P. Shenoy, Compositional models in valuation-based systems, Working Paper No. 325, School of Business, University of Kansas, Lawrence, KS, 2011.; R. Jiroušek, P.P. Shenoy, Compositional models in valuation-based systems, Working Paper No. 325, School of Business, University of Kansas, Lawrence, KS, 2011.
[16] Jiroušek, R.; Vejnarová, J., Compositional models and conditional independence in evidence theory, Int. J. Approx. Reason., 52, 3, 316-334 (2011) · Zbl 1217.68214
[17] R. Jiroušek, J. Vejnarová, M. Daniel, Compositional models of belief functions, in: G. de Cooman, J. Vejnarová, M. Zaffalon (Eds.), Proceedings of the Fifth International Symposium on Imprecise Probability: Theories and Applications, Praha, 2007, pp. 243-252.; R. Jiroušek, J. Vejnarová, M. Daniel, Compositional models of belief functions, in: G. de Cooman, J. Vejnarová, M. Zaffalon (Eds.), Proceedings of the Fifth International Symposium on Imprecise Probability: Theories and Applications, Praha, 2007, pp. 243-252.
[18] Lauritzen, S. L., Graphical Models (1996), Oxford University Press · Zbl 0907.62001
[19] Lauritzen, S. L.; Spiegelhalter, D. J., Local computation with probabilities on graphical structures and their application to expert systems, J. Roy. Stat. Soc. Ser. B, 50, 157-224 (1988) · Zbl 0684.68106
[20] Perez, A., \( \operatorname{\&z.epsiv;} \)-Admissible simplification of the dependence structure of a set of random variables, Kybernetika, 13, 439-449 (1977) · Zbl 0382.62003
[21] Shafer, G., A Mathematical Theory of Evidence (1976), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0359.62002
[22] Shenoy, P. P., Conditional independence in valuation-based systems, Int. J. Approx. Reason., 10, 3, 203-234 (1994) · Zbl 0821.68114
[23] Shenoy, P. P.; Shafer, G., Axioms for probability and belief-function propagation, (Shachter, R. D.; Levitt, T.; Lemmer, J. F.; Kanal, L. N., Uncertainty in Artificial Intelligence, vol. 4 (1990), North-Holland)
[24] Studený, M., Formal properties of conditional independence in different calculi of AI, (Clarke, K.; Kruse, R.; Moral, S., Proceedings of European Conference on Symbolic and quantitative Approaches to Reasoning and Uncertainty ECSQARU’93 (1993), Springer-Verlag), 341-351
[25] Studený, M., On stochastic conditional independence: the problems of characterization and description, Ann. Math. Artif. Intell., 35, 323-341 (2002) · Zbl 1014.68156
[26] J. Vejnarová, On conditional independence in evidence theory, in: Proceedings of the 6th Symposium on Imprecise Probability: Theories and Applications Durham, UK, 2009, pp. 431-440.; J. Vejnarová, On conditional independence in evidence theory, in: Proceedings of the 6th Symposium on Imprecise Probability: Theories and Applications Durham, UK, 2009, pp. 431-440.
[27] Walley, P.; Fine, T. L., Towards a frequentist theory of upper and lower probability, Ann. Stat., 10, 749-761 (1982) · Zbl 0488.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.