×

Generic local computation. (English) Zbl 1255.68156

Summary: Many problems of artificial intelligence, or more generally, many problems of information processing, have a generic solution based on local computation on join trees or acyclic hypertrees. There are several variants of this method all based on the algebraic structure of valuation algebras. A strong requirement underlying this approach is that the elements of a problem decomposition form a join tree. Although it is always possible to construct covering join trees, if the requirement is originally not satisfied, it is not always possible or not efficient to extend the elements of the decomposition to the covering join tree. Therefore in this paper different variants of an axiomatic framework of valuation algebras are introduced which prove sufficient for local computation without the need of an extension of the factors of a decomposition. This framework covers the axiomatic system proposed in [P. P. Shenoy and G. Shafer, “Axioms for probability and belief-function propagation”, in: R. D. Shachter (ed.) et al., Uncertainty in artificial intelligence 4. Amsterdam: Elsevier. 169–198 (1990)]. A particular emphasis is laid on the important special cases of idempotent algebras and algebras with some notion of division. It is shown that all well-known architectures for local computation like the Shenoy-Shafer architecture, Lauritzen-Spiegelhalter and HUGIN architectures may be adapted to this new framework. Further a new architecture for idempotent algebras is presented. As examples, in addition to the classical instances of valuation algebras, semiring-based valuation algebras, Gaussian potentials and the relational algebra are presented.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68T30 Knowledge representation
68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shenoy, P. P.; Shafer, G., Axioms for probability and belief-function propagation, (Shachter, R. D.; Levitt, T. S.; Kanal, L. N.; Lemmer, J. F., Uncertainty in Artificial Intelligence, vol. 4. Uncertainty in Artificial Intelligence, vol. 4, Machine Intell. Pattern Recognit., vol. 9 (1990), Elsevier: Elsevier Amsterdam), 169-198
[2] Lauritzen, S. L.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application to expert systems, J. R. Stat. Soc. Ser. B Stat. Methodol., 50, 157-224 (1988) · Zbl 0684.68106
[3] Kohlas, J.; Shenoy, P., Computation in valuation algebras, (Kohlas, J.; Moral, S., Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5: Algorithms for Uncertainty and Defeasible Reasoning (2000), Kluwer: Kluwer Dordrecht), 5-40 · Zbl 1015.68196
[4] Kohlas, J., Information Algebras: Generic Structures for Inference (2003), Springer-Verlag · Zbl 1027.68060
[5] Shenoy, P., A valuation-based language for expert systems, Internat. J. Approx. Reason., 3, 383-411 (1989)
[6] Shenoy, P., Valuation-based systems for bayesian decision analysis, Oper. Res., 40, 3, 463-484 (1992) · Zbl 0850.62131
[7] G. Shafer, An axiomatic study of computation in hypertrees, Working Paper 232, School of Business, University of Kansas, 1991.; G. Shafer, An axiomatic study of computation in hypertrees, Working Paper 232, School of Business, University of Kansas, 1991.
[8] Dechter, R., Bucket elimination: A unifying framework for reasoning, Artificial Intelligence, 113, 41-85 (1999) · Zbl 0939.68847
[9] Gottlob, G.; Leone, N.; Scarcello, F., Hypertree decompositions and tractable queries, (PODSʼ99: Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (1999), ACM Press: ACM Press New York, NY, USA), 21-32 · Zbl 1052.68025
[10] Gottlob, G.; Leone, N.; Scarcello, F., A comparison of structural CSP decomposition methods, (Proceedings of the 16th International Joint Conference on Artificial Intelligence IJCAI (1999), Morgan Kaufmann), 394-399 · Zbl 0952.68044
[11] Chekuri, C.; Rajaraman, A., Conjunctive query containment revisited, (ICDTʼ97: Proceedings of the 6th International Conference on Database Theory (1997), Springer-Verlag: Springer-Verlag London, UK), 56-70 · Zbl 0944.68046
[12] Gottlob, G.; Leone, N.; Scarcello, F., The complexity of acyclic conjunctive queries, J. ACM, 48, 3, 431-498 (2001) · Zbl 1323.68250
[13] Lauritzen, S. L.; Jensen, F. V., Local computation with valuations from a commutative semigroup, Ann. Math. Artif. Intell., 21, 1, 51-69 (1997) · Zbl 0895.68045
[14] Mengin, J.; Wilson, N., Logical deduction using the local computation framework, (Hunter, A.; Parsons, S., European Conf. ECSQARUʼ99, London. European Conf. ECSQARUʼ99, London, Lecture Notes in Artificial Intelligence (1999), Springer-Verlag), 386-396 · Zbl 0934.03018
[15] Cannings, C.; Thompson, E.; Skolnick, M., Probability functions on complex pedigrees, Adv. in Appl. Probab., 10, 26-61 (1978) · Zbl 0431.92019
[16] Shenoy, P., Valuation-based systems: A framework for managing uncertainty in expert systems, (Zadeh, L.; Kacprzyk, J., Fuzzy Logic for the Management of Uncertainty (1992), John Wiley & Sons), 83-104
[17] Jensen, F.; Lauritzen, S.; Olesen, K., Bayesian updating in causal probabilistic networks by local computation, Comput. Statist. Quart., 4, 269-282 (1990) · Zbl 0715.68076
[18] Shafer, G., Probabilistic Expert Systems, CBMS-NSF Regional Conf. Ser. in Appl. Math., vol. 67 (1996), SIAM: SIAM Philadelphia, PA · Zbl 0866.68108
[19] Kohlas, J.; Monney, P., A Mathematical Theory of Hints. An Approach to the Dempster-Shafer Theory of Evidence, Lecture Notes in Econom. and Math. Systems, vol. 425 (1995), Springer-Verlag · Zbl 0833.62005
[20] J. Kohlas, Valuation algebras induced by semirings, Tech. Rep. 04-03, Department of Informatics, University of Fribourg, 2004.; J. Kohlas, Valuation algebras induced by semirings, Tech. Rep. 04-03, Department of Informatics, University of Fribourg, 2004.
[21] Davey, B.; Priestley, H., Introduction to Lattices and Order (1990), Cambridge University Press · Zbl 0701.06001
[22] Henkin, L.; Monk, J. D.; Tarski, A., Cylindric Algebras, Stud. Logic Found. Math., vols. 65, 115 (1971), North-Holland · Zbl 0214.01302
[23] Kohlas, J.; Haenni, R.; Moral, S., Propositional information systems, J. Logic Comput., 9, 5, 651-681 (1999) · Zbl 0941.03030
[24] J. Kohlas, Information in context, Tech. Rep. 02-15, Department of Informatics, University of Fribourg, 2002.; J. Kohlas, Information in context, Tech. Rep. 02-15, Department of Informatics, University of Fribourg, 2002.
[25] J.E. Cano, S. Moral, J.F. Verdegay, Propagation of convex sets of probabilities in directed acyclic networks, in: Proceedings of the 4th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMUʼ92), 1992, pp. 289-292.; J.E. Cano, S. Moral, J.F. Verdegay, Propagation of convex sets of probabilities in directed acyclic networks, in: Proceedings of the 4th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMUʼ92), 1992, pp. 289-292.
[26] Shenoy, P. P., Binary join trees for computing marginals in the Shenoy-Shafer architecture, Internat. J. Approx. Reason., 17, 239-263 (1997) · Zbl 0939.68021
[27] N. Lehmann, Argumentation system and belief functions, PhD thesis, Department of Informatics, University of Fribourg, 2001.; N. Lehmann, Argumentation system and belief functions, PhD thesis, Department of Informatics, University of Fribourg, 2001.
[28] Clifford, A. H.; Preston, G. B., Algebraic Theory of Semigroups (1967), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0178.01203
[29] Croisot, R., Demi-groupes inversifs et demi-groupes réunions de demi-groupes simples, Ann. Sci. Ec. Norm. Super., 79, 3, 361-379 (1953) · Zbl 0053.00902
[30] Tamura, T.; Kimura, N., On decompositions of a commutative semigroup, Kodai Math. Sem. Rep., 109-112 (1954) · Zbl 0058.01503
[31] Cowell, R. G.; Dawid, P.; Lauritzen, S. L.; Spiegelhalter, D. J., Probabilistic Networks and Expert Systems (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0937.68121
[32] M. Pouly, A generic architecture for local computation, Masterʼs thesis, Department of Informatics, University of Fribourg, 2004.; M. Pouly, A generic architecture for local computation, Masterʼs thesis, Department of Informatics, University of Fribourg, 2004.
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.