ECAI04 Tutorial on Inference by Local Computation

ECAI04 Tutorial on Inference by Local Computation
(CANCELLED)

An ECAI tutorial on local computation for logics and uncertainty
On either Sunday August 22nd, Monday August 23rd or Tuesday August 24th in Valencia, Spain.
(ECAI information is at www.dsic.upv.es/ecai2004/)

A workshop on Local Computation for Logics and Uncertainty will take place the day before or the day after the tutorial.
Details at /LC/LC04

Description

Computation on acyclic hypertrees or on related graphical structures has been discovered independently as an efficient method in several different fields, including probabilistic networks, statistics, relational databases, optimization and numerical mathematics. A generic algebraic structure, called a valuation algebra, has been identified as the underlying reason for the possibility of local computation. This structure unifies these local computation methods and makes them accessible for many further formalisms for representing information and knowledge; in particular, many kinds of logics, including non-classical ones, constraints, including soft constraints, different uncertainty calculi, including possibility theory and belief functions.

Local computation has become a methodology, which should be known to designers of AI (and other) reasoning systems. This tutorial will provide a concise introduction into the underlying algebraic structure of valuation algebra, the corresponding architectures for local computation and gives some illustrative examples.

Tutorial Objectives

The tutorial will provide the attendees with the basic knowledge of valuation algebras as the underlying structure permitting local computation. It familiarizes them with the corresponding architectures for local computation. This will allow the attendees to identify instances of problems for which local computation is a potential solution and give them the basic knowledge to select an appropriate architecture for the solution to their problems.

Tutorial Content

General

Why local computation is a possible solution to hard computation problems: Illustration with examples from probability and constraint systems.
Valuation algebras, the generic framework: Variables, domains, valuations, the operations of combination and projection, the axioms.
Further instances: Relational algebra, semiring-based soft constraints, propositional logic, model-based and language-based approach.
Generic inference by the fusion method. Interpretation as message passing in a join tree.
Architectures for local computation: Shenoy-Shafer architecture. Architecture for idempotent algebras. Architectures for algebras with division.

Local Computation for Constraint Solving

The projection problem and its solution by local computation. Relationship with other approaches for constraint solving.
Constructing solution-configurations by local computation.
Soft constraints and their solution by local computation.

Local Computation in Logic

The model-based approach: Similarity model structures and valuation algebras. Application to propositional and first-order classical logics, possibilistic logic, modal and conditional logics.
The language-based approach: Conditions on the language and/or on the consequence operator for local computations.
Projection using resolution: propositional and first-order classical logics. Relationship with other automated deduction methods.

Necessary background and potential target audience

Only some basic knowledge on graphs, probabilities and logics will be necessary to follow the presentations. More advanced concepts will be introduced. The tutorial should prove interesting to anybody interested in computational aspects of knowledge engineering.

Presenters

Dr. Jürg Kohlas
Professor for Theoretical Computer Science
Department of Informatics
University of Fribourg, rue Faucigny 2, CH 1700 Fribourg, Switzerland.
juerg.kohlas@unifr.ch. Tel: +41 26 300 83 38. Fax: +41 26 300 97 26.

Dr. Jérôme Mengin
Lecturer in Computer Science
Institut de Recherche en Informatique de Toulouse
Université Paul Sabatier, 118 route de Narbonne, 31062 Toulouse Cedex 4, France.
mengin@irit.fr. Tel: +33 0561 556 451. Fax: +33 0561 556 239.

Dr. Nic Wilson
Research Scientist
Cork Constraint Computation Centre
University College Cork, Ireland.
n.wilson@4c.ucc.ie Tel: +353 21 425 5400 Fax: +353 21 4255424.

Dr Jürg Kohlas is Professor for Theoretical Computer Science at the University of Fribourg. He has been researching information algebras for ten years, and recently published a book on this topic. He teaches local computation techniques at graduate level. Nic Wilson and Jérôme Mengin have worked jointly on the application of local computation to various logics since 1997, and published a journal paper on this topic. Jérôme Mengin teaches logic to undergraduates and post-graduates at the Université Paul Sabatier in Toulouse; some aspects of local computation applied to logics are introduced in an advanced course on logic for Artificial Intelligence. Nic Wilson is a research scientist at the Cork Constraint Computation Centre. All three authors have worked for many years on computational issues and other aspects of uncertain reasoning formalisms in AI, including belief functions, non-monotonic logics, argumentation systems, reliability theory and imprecise probability.

Published work on this topic by the presenters

Kohlas, J., Haenni, R., & Moral, S.: Propositional Information Systems. J. Logic Computat. 9 (1999) 651-681.
Kohlas, J., Shenoy, P.: Computation in Valuation Algebras. In: Kohlas, J. & Moral, S. (eds.): Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 5: Algorithms for Uncertainty and Defeasible Reasoning, 5-39, Kluwer, Dordrecht 2000.
Kohlas, J.: Information Algebra. Generic Structures for Inference. Springer, London, Discrete mathematics and Theoretical Computer Science, 2003.
Wilson, N. and Mengin, J. Logical deduction using the local computation framework. In Bonacina, M.P. and Furbach, U., editors, International Workshop on First-Order Theorem Proving (FTP'97), RISC-Linz Report Series No. 97-50, pages 135-139. Johannes Kepler Universitaet, Linz (Austria), 1997.
Wilson, N. and Mengin, J. Embedding Logics in the Local Computation Framework. Journal of Applied Non-Classical Logics, Vol. 11, no. 3—4, 239—267, 2001.
For further references see: http://diuf.unifr.ch/tcs/

Some further key references

Lauritzen, S.L. & Spiegelhalter, D.J. Local computation with probabilities on graphical structures and their application to expert systems. J. of the Royal. Stat. Soc, Vol. 50, 1988, 157-224.
Shafer, G. An axiomatic study of computation in hypertrees. Working paper 232. School of Business, University of Kansas.
Shenoy, P.P., & Shafer G., Axioms for probability and belief function propagation. In: Shachter, R.D., Levitt, T.S., Lemmer, J.F., & Kanal, L.N. (eds.) Uncertainty in Artificial Intelligence 4, North Holland pp. 169-198. Also in Readings in Uncertain Reasoning, Shafer, G., and Pearl, J., (eds.) Morgan Kaufmann, San Mateo, California, 575--610 (1990).
Dechter, R., Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113, 1999, 41-85.
McIlraith, S. and Amir, E. Theorem proving with structured theories, 17th Intl' Joint Conference on Artificial Intelligence (IJCAI'01), 2001.
MacCartney, B., McIlraith, S., Amir, E. & Uribe, T. Practical Partition-Based Theorem Proving for Large Knowledge Bases. Proceedings of the Nineteenth International Conference on Artificial Intelligence (IJCAI-03), 89--96, 2003

ECAI04 Tutorial on Inference by Local Computation (CANCELLED)