[en] Valuation algebras abstract a large number of formalisms for automated reasoning and enable the definition of generic inference procedures. Many of these formalisms provide some notions of solutions. Typical examples are satisfying assignments in constraint systems, models in logics or solutions to linear equation systems. Contrary to inference, there is no general algorithm to compute solutions in arbitrary valuation algebras. This paper states formal requirements for the presence of solutions and proposes a generic algorithm for solution construction based on the results of a previously executed inference scheme. We study the application of generic solution construction to semiring constraint systems, sparse linear systems and algebraic path problems and show that the proposed method generalizes various existing approaches for specific formalisms in the literature.
Disciplines :
Ingénierie, informatique & technologie: Multidisciplinaire, généralités & autres Sciences informatiques
Identifiants :
UNILU:UL-CONFERENCE-2011-191
Auteur, co-auteur :
POULY, Marc ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SnT)
Langue du document :
Anglais
Titre :
Generic Solution Construction in Valuation-Based Systems
Date de publication/diffusion :
2011
Nom de la manifestation :
24th Canadian Conference on Artificial Intelligence
Dechter, R.: Bucket elimination: a unifying framework for reasoning. Artif. Intell. 113, 41-85 (1999)
Dechter, R.: Constraint Processing. Morgan Kaufmann Publishers, San Francisco (2003)
Jensen, F., Lauritzen, S., Olesen, K.: Bayesian updating in causal probabilistic networks by local computation. Computational Statistics Quarterly 4, 269-282 (1990)
Kask, K., Dechter, R., Larrosa, J., Fabio, G.: Bucket-tree elimination for automated reasoning. Artif. Intell. 125, 91-131 (2001)
Kohlas, J.: Information Algebras: Generic Structures for Inference. Springer, Heidelberg (2003)
Kohlas, J., Wilson, N.: Semiring induced valuation algebras: Exact and approximate local computation algorithms. Artif. Intell. 172(11), 1360-1399 (2008)
Lauritzen, S., Spiegelhalter, D.: Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Stat. Soc. B 50, 157-224 (1988)
Lehmann, D.: Algebraic structures for transitive closure. Technical report, Department of Computer Science, University of Warwick (1976)
Pouly, M.: A Generic Framework for Local Computation. PhD thesis, Department of Informatics, University of Fribourg (2008)
Pouly, M.: Nenok - a software architecture for generic inference. Int. J. on Artif. Intel. Tools 19, 65-99 (2010)
Pouly, M., Kohlas, J.: Generic Inference - A unifying Theory for Automated Reasoning. Wiley & Sons, Chichester (2011)
Rose, D.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read, R. (ed.) Graph Theory and Computing. Academic Press, London (1972)
Shenoy, P.: Valuation-based systems: A framework for managing uncertainty in expert systems. In: Zadeh, L., Kacprzyk, J. (eds.) Fuzzy Logic for the Management of Uncertainty, pp. 83-104. Wiley & Sons, Chichester (1992)
Shenoy, P.: Axioms for dynamic programming. In: Gammerman, A. (ed.) Computational Learning and Probabilistic Reasoning, pp. 259-275. Wiley & Sons, Chichester (1996)
Shenoy, P., Shafer, G.: Axioms for probability and belief-function propagation. In: Shafer, G., Pearl, J. (eds.) Readings in Uncertain Reasoning, pp. 575-610. Morgan Kaufmann Publishers, San Francisco (1990)
