Semiring induced valuation algebras: exact and approximate local computation algorithms. (English) Zbl 1183.68287

Kohlas, J.; Wilson, N.

Artif. Intell. 172, No. 11, 1360-1399 (2008).

Summary: Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and nonclassical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.

MSC:

68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
08A70	Applications of universal algebra in computer science
16Y60	Semirings

Keywords:

semirings; local computation; join tree decompositions; soft constraints; uncertainty; valuation networks; valuation algebras

References:

[1]	Aji, S. M.; McEliece, R. J., The generalized distributive law, IEEE Trans. Inform. Theory, 46, 2, 325-343 (2000) · Zbl 0998.65146
[2]	E. Amir, Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 2001, pp. 7-15; E. Amir, Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 2001, pp. 7-15
[3]	Baccelli, F.; Cohen, G.; Olsder, G. J.; Quadrat, J.-P., Synchronization and Linearity: An Algebra for Discrete Event Systems (1992), Wiley · Zbl 0824.93003
[4]	Beeri, C.; Fagin, R.; Maier, D.; Mendelzon, A.; Ullman, J.; Yannakakis, M., Properties of acyclic database schemes, (ACM Symposium on Theory of Computing (1981), ACM Press: ACM Press New York), 355-362
[5]	Bistarelli, S.; Fruewirth, T.; Marthe, M.; Rossi, F., Soft constraint propagation and solving in constraint handling rules, Comput. Intell. (2004), Special Issues on Preferences in AI and CP
[6]	S. Bistarelli, S.K.L. Fung, J.H.M. Lee, H. Leung, A local search framework for semiring-based constraint satisfaction problems, in: Proc. CP2003 Workshop on Soft Constraints (Soft-2003), 2003; S. Bistarelli, S.K.L. Fung, J.H.M. Lee, H. Leung, A local search framework for semiring-based constraint satisfaction problems, in: Proc. CP2003 Workshop on Soft Constraints (Soft-2003), 2003
[7]	S. Bistarelli, F. Gadducci, Enhancing constraints manipulation in semiring-based formalisms, in: Proc. 17th European Conference on Artificial Intelligence (ECAI 2006), 2006, pp. 63-67; S. Bistarelli, F. Gadducci, Enhancing constraints manipulation in semiring-based formalisms, in: Proc. 17th European Conference on Artificial Intelligence (ECAI 2006), 2006, pp. 63-67
[8]	Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint satisfaction and optimization optimisation, J. ACM, 44, 201-236 (1997) · Zbl 0890.68032
[9]	Bistarelli, S.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G.; Fargier, H., Semiring-based CSPs and valued CSPs: Frameworks, properties and comparison, CONSTRAINTS: An International Journal, 4, 3 (1999) · Zbl 0946.68143
[10]	Bodlaender, H. L., A tourist guide through treewidth, Acta Cybern., 11, 1-2, 1-22 (1993) · Zbl 0804.68101
[11]	Bodlaender, H. L., Treewidth: Characterizations, applications, and computations, (Fomin, F. V., WG. WG, Lecture Notes in Computer Science, vol. 4271 (2006), Springer), 1-14 · Zbl 1167.68404
[12]	Cechlárová, K.; Plávka, J., Linear independence in bottleneck algebras, Fuzzy Sets Syst., 77, 3, 337-348 (1996) · Zbl 0877.15017
[13]	L. Chang, Semiring-based unifying framework for constraint-based inference, Master’s thesis, University of British Columbia, 2005; L. Chang, Semiring-based unifying framework for constraint-based inference, Master’s thesis, University of British Columbia, 2005
[14]	L. Chang, A.K. Mackworth, Generalized constraint-based inference, Tech. Rep. TR-2005-10, Dept. of Computer Science, Univ. of British Columbia, 2005; L. Chang, A.K. Mackworth, Generalized constraint-based inference, Tech. Rep. TR-2005-10, Dept. of Computer Science, Univ. of British Columbia, 2005
[15]	Clifford, A. H.; Preston, G. B., Algebraic Theory of Semigroups. American Mathematical Society (1967), Providence: Providence Rhode Island · Zbl 0178.01203
[16]	Cooper, M.; Schiex, T., Arc consistency for soft constraints, Artif. Intell., 154, 1-2, 199-227 (2004) · Zbl 1085.68672
[17]	Croisot, R., Demi-groupes inversifs et demi-groupes réunions de demi-groupes simples, Ann. Sci. Ecole Norm. Sup., 79, 3, 361-379 (1953) · Zbl 0053.00902
[18]	De Baets, B., Idempotent uninorms, European J. Op. Res., 118, 631-642, 00 (1996) · Zbl 0933.03071
[19]	De Kleer, J.; Brown, J., Theories of causal ordering, Artif. Intell., 29, 33-61 (1986)
[20]	R. Dechter, Mini-buckets: A general scheme for generating approximations in automated reasoning, in: Proc. Fifteenth International Joint Conference of Artificial Intelligence (IJCAI97), 1997, pp. 1297-1303; R. Dechter, Mini-buckets: A general scheme for generating approximations in automated reasoning, in: Proc. Fifteenth International Joint Conference of Artificial Intelligence (IJCAI97), 1997, pp. 1297-1303
[21]	Dechter, R., Bucket elimination: A unifying framework for reasoning, Artif. Intell., 113, 1-2, 41-85 (1999) · Zbl 0939.68847
[22]	R. Dechter, K. Kask, J. Larrosa, A general scheme for multiple lower bound computation in constraint optimization, in: Proc. CP2001, 2001, pp. 346-360; R. Dechter, K. Kask, J. Larrosa, A general scheme for multiple lower bound computation in constraint optimization, in: Proc. CP2001, 2001, pp. 346-360 · Zbl 1067.68623
[23]	Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artif. Intell., 34, 1, 1-38 (1987) · Zbl 0643.68156
[24]	Dechter, R.; Rish, I., Mini-buckets: A general scheme for bounded inference, J. ACM, 50, 2, 107-153 (2003) · Zbl 1326.68335
[25]	V. Gogate, R. Dechter, A complete anytime algorithm for treewidth, in: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence UAI-04, 2004, pp. 201-208; V. Gogate, R. Dechter, A complete anytime algorithm for treewidth, in: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence UAI-04, 2004, pp. 201-208
[26]	Haenni, R., Ordered valuation algebras: A generic framework for approximating inference, Internat. J. Approx. Reason., 37, 1, 1-41 (2004) · Zbl 1093.68115
[27]	Haenni, R.; Kohlas, J.; Lehmann, N., Probabilistic argumentation systems, (Kohlas, J.; Moral, S., Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5: Algorithms for Uncertainty and Defeasible Reasoning (2000), Kluwer: Kluwer Dordrecht), 221-287 · Zbl 0987.68076
[28]	Hewitt, E.; Zuckermann, H., The l1-algebra of a commutative semigroup, Trans. Amer. Math. Soc., 83, 70-97 (1956) · Zbl 0072.12701
[29]	Jensen, F.; Lauritzen, S.; Olesen, K., Bayesian updating in causal probabilistic networks by local computations, Comp. Stat. Q., 4, 269-282 (1990) · Zbl 0715.68076
[30]	K. Kask, R. Dechter, Branch and bound with mini-bucket heuristics, in: Proc. International Joint Conference on Artificial Intelligence (IJCAI99), 1999, pp. 426-433; K. Kask, R. Dechter, Branch and bound with mini-bucket heuristics, in: Proc. International Joint Conference on Artificial Intelligence (IJCAI99), 1999, pp. 426-433
[31]	K. Kask, R. Dechter, Mini-bucket heuristics for improved search, in: Proc. UAI99, 1999, pp. 314-323; K. Kask, R. Dechter, Mini-bucket heuristics for improved search, in: Proc. UAI99, 1999, pp. 314-323
[32]	Kask, K.; Dechter, R.; Larrosa, J.; Dechter, A., Unifying cluster-tree decompositions for reasoning in graphical models, Artif. Intell., 166, 1-2, 165-193 (2005) · Zbl 1132.68680
[33]	Klement, E.; Mesiar, R.; Pap, E., Triangular Norms, Trends in Logic (2000), Kluwer Academic Publ. Dordrecht · Zbl 0972.03002
[34]	Kohlas, J., Information Algebras: Generic Structures for Inference (2003), Springer-Verlag · Zbl 1027.68060
[35]	Kohlas, J., Valuation algebras induced by semirings. Tech. Rep. 04-03, Department of Informatics, University of Fribourg (2004)
[36]	Kohlas, J.; Haenni, R.; Moral, S., Propositional information systems, J. Logic Comput., 9, 5, 651-681 (1999) · Zbl 0941.03030
[37]	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
[38]	Kolokoltsov, V.; Maslov, V., Idempotent Analysis and its Applications (1997), Kluwer Academic Publ. Dordrecht · Zbl 0941.93001
[39]	Larrosa, J.; Schiex, T., Solving weighted CSP by maintaining arc consistency, Artif. Intell., 159, 1-26 (2004) · Zbl 1086.68592
[40]	Lauritzen, S.; Jensen, F., Local computation with valuations from a commutative semigroup, Ann. Math. Artif. Intell., 21, 1, 51-70 (1997) · Zbl 0895.68045
[41]	Lauritzen, S.; Spiegelhalter, D., Local computations with probabilities on graphical structures and their application to expert systems, J. Royal Stat. Soc., 50, 2, 157-224 (1988) · Zbl 0684.68106
[42]	Maier, D., The Theory of Relational Databases (1983), Pitman: Pitman London · Zbl 0519.68082
[43]	R. Mateescu, R. Dechter, K. Kask, Tree approximation for belief updating, in: Proc. AAAI-2002, 2002, pp. 553-559; R. Mateescu, R. Dechter, K. Kask, Tree approximation for belief updating, in: Proc. AAAI-2002, 2002, pp. 553-559
[44]	Menger, K., Statistical metrics, Proc. Nat. Acad. Sci., 28, 535-537 (1942) · Zbl 0063.03886
[45]	Mengin, J.; Wilson, N., Logical deduction using the local computation framework, (Hunter, A.; Parsons, S., European Conf. ECSQARU’99 (1999), London. Lecture Notes in Artif. Intell. Springer), 386-396 · Zbl 0934.03018
[46]	J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., 1988; J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., 1988 · Zbl 0746.68089
[47]	M. Pouly, Nenok 1.1 user guide, Tech. Rep. 06-02, Department of Informatics, University of Fribourg, 2006; M. Pouly, Nenok 1.1 user guide, Tech. Rep. 06-02, Department of Informatics, University of Fribourg, 2006
[48]	M. Pouly, J. Kohlas, Minimizing communication costs of distributed local computation, Tech. rep., Department of Informatics, University of Fribourg, 2005; M. Pouly, J. Kohlas, Minimizing communication costs of distributed local computation, Tech. rep., Department of Informatics, University of Fribourg, 2005
[49]	Schiex, T., Possibilistic constraint satisfaction problems or “how to handle soft constraints?”, (Dubois, D.; Wellman, M. P.; D’Ambrosio, B.; Smets, P., Uncertainty in Artificial Intelligence: Proc. of the Eighth Conference (1992), Kaufmann: Kaufmann San Mateo, CA), 268-275
[50]	Schiex, T., Fargier, H., Verfaillie, G., Valued constraint satisfaction problems: Hard and easy problems, in: Proc. IJCAI-95, 1995, pp. 631-637; Schiex, T., Fargier, H., Verfaillie, G., Valued constraint satisfaction problems: Hard and easy problems, in: Proc. IJCAI-95, 1995, pp. 631-637
[51]	Schneuwly, C.; Pouly, M.; Kohlas, J., Local computation in covering join trees, Tech. Rep. 04-16, Department of Informatics, University of Fribourg (2004)
[52]	Schweizer, B.; Sklar, A., Statistical metric spaces, Pacific J. Math., 10, 313-334 (1960) · Zbl 0091.29801
[53]	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
[54]	Shafer, G., Probabilistic Expert Systems, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 67 (1996), SIAM: SIAM Philadelphia, PA · Zbl 0866.68108
[55]	G. Shafer, P. Shenoy, Local computation in hypertrees, Tech. Rep. 201, School of Business, University of Kansas, Lawrence, 1988; G. Shafer, P. Shenoy, Local computation in hypertrees, Tech. Rep. 201, School of Business, University of Kansas, Lawrence, 1988
[56]	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
[57]	Shenoy, P., Axioms for dynamic programming, (Gammerman, A., Computational Learning and Probabilistic Reasoning (1996), Wiley: Wiley Chichester, UK), 259-275
[58]	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
[59]	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 4. Uncertainty in Artificial Intelligence 4, Machine Intelligence and Pattern Recognition, vol. 9 (1990), Elsevier: Elsevier Amsterdam), 169-198
[60]	Spohn, W., Ordinal conditional functions: A dynamic theory of epistemic states, (Harper, W.; Skyrms, B., Causation in Decision, Belief Change, and Statistics, vol. 2 (1988), Dordrecht: Dordrecht Netherlands), 105-134
[61]	Tamura, T.; Kimura, N., On decompositions of a commutative semigroup, Kodai Math. Sem. Rep., 109-112 (1954) · Zbl 0058.01503
[62]	N. Wilson, Bounds and pre-processing for local computation of semiring valuations, in: J. Kohlas, J. Mengin, N. Wilson (Eds.), ECAI’2004, Workshop 22: Local Computation for Logics and Uncertainty, 2004, pp. 53-56; N. Wilson, Bounds and pre-processing for local computation of semiring valuations, in: J. Kohlas, J. Mengin, N. Wilson (Eds.), ECAI’2004, Workshop 22: Local Computation for Logics and Uncertainty, 2004, pp. 53-56
[63]	Yager, R.; Rybalov, A., Uninorm aggregation operators, Fuzzy Sets Syst., 80, 111-120 (1996) · Zbl 0871.04007