[
Main | Projects
| People | Meeting
| Library ]
| Implementation of Uncertain Reasoning
|
Intro
In order to make belief function theory applicable to real problems,
we have developed efficient algorithms based on the Valuation- based
framework.
Valuation-based systems
Efficient computer implementations of uncertain reasoning can be
obtained by using the so-called network-based approaches like the
valuation-based system (VBS) of Shenoy and Shafer.
In VBS, knowledge is represented by a network of nodes representing
entities of the domain of discourse and their states, and links
representing relations between these entities. These relations can
express logical constraints or quantified uncertainty. For dealing
with a problem, we consider all the relevant elements and build the
corresponding nodes and links in the network. Then we associate values
called valuations with these links for representing our knowledge. In
VBS, we can represent uncertain knowledge using different uncertainty
formalisms, including probability theory, belief function theory,
possibility theory, etc..
The inference mechanism of a VBS is based on two operators called
combination and marginalization. By the combination of all the
valuations in a network, we get the joint valuation on the whole
domain of interest. Marginalization is then used to focus this joint
valuation on the domain of interest, and compute the uncertainty
valuation restricted to that domain. When there are many nodes in a
VBS, brute force computation of the joint valuation is computationally
intractable. However, it is often possible to compute the marginals on
the domain of interest using local computation, therefore strongly
reducing the computational complexity. Local computation can be used
when: (1) the problem can be decomposed, i.e., it can be described as
a combination of sub-problems; and (2) the operators of combination
and marginalization satisfy certain axioms - these axioms are
satisfied by classical uncertainty representations such as
probability, belief function, and possibility theories.
TresBel
In order for belief function theory to be applicable to real problems
within the VBS framework, we have developed efficient algorithms for
implementing local computation scheme. These algorithms are used in
TresBel, our implementation of the transferable belief model
(TBM). TresBel is implemented in a modular way, in Lisp, and is
enriched with a graphical interface. TresBel can accept both joint
and conditional belief functions. We use TresBel as an open and
practical tool to experiment different algorithms, and to verify their
efficiency and adequateness to model problems of uncertain reasoning.
Besides, we have developed two strategies for the explanations of
origin of the computed beliefs. One is based on the sensitivity
analysis, the other is based on the measure of information contents of
a belief function.
The initial VBS was adapted to joint beliefs. In order to cope with
conditional beliefs, we have also developed a network that accepts
conditional belief functions. It is more natural and much easier for
the users to provide conditional beliefs for representing the
relations between the nodes. Besides, computation is faster and
memory requirements are smaller when using conditional beliefs instead
of joint beliefs.
PULCINELLA
We have then developed a second tool based on the VBS formalism,
called PULCINELLA. PULCINELLA generalizes TresBel to cover other
uncertainty formalisms, including possibility theory, probability
theory, and classical propositional logic. PULCINELLA has been used
to comparatively test the adequacy of these formalisms in modelling
real-world problems. See the PULCINELLA Home Page
for more details.
ISDAT
VBS can be also used for representing and solving Bayesian decision
problems. Problems are represented in an extended VBS framework, and
the solution still benefits from the local computation.
Generalizing PULCINELLA, we have implemented a system, called VBSD,
for Bayesian decision analysis in VBS. The TBM provides a mental
two-level structure for representing uncertainty, one that
characterises the state of belief of the agent and where beliefs are
represented by belief functions, the other that characterises the
behavior of the agent and where a decision is to be made using the
classical expected utility theory. In our decision support system
based on the TBM, we have integrated the programs TresBel and VBSD
into ISDAT, an integrated architecture that allows decision making
under uncertainty.
[
Hong XU,
Alessandro SAFFIOTTI,
Philippe SMETS
]
Selected references
- Saffiotti A. and Umkehrer E.
- Pulcinella: A General Tool for Propagating Uncertainty
in Valuation Networks
in D'Ambrosio B. D., Smets Ph. And Bonissone P. P. eds. Proc. 7th Uncertainty
in Artificial Intelligence, pp. 323-331, San Mateo, Ca.: Morgan Kaufmann
1991.
- Xu H.
- An Efficient Tool for Reasoning with Belief Functions
in Bouchon-Meunier B.,Valverde L. and Yager R. R. eds. Uncertainty
in Intelligent Systems pp. 215-224, North-Holland, Amsterdam 1993.
- Xu H. and Kennes R.
- Steps towards an Efficient Implementation of Dempster-Shafer
Theory,
in Yager R. R., Fedrizzi M., and Kacprzyk J. eds. Advances in the Dempster-Shafer
Theory of Evidence, pp. 153-174, New York: Wiley 1994.
- Xu H. and Smets Ph.
- Reasoning in Evidential Networks with Conditional
Belief Functions International Journal of Approximate Reasoning, 1995.
- Xu H., Hsia Y-T. and Smets Ph.
- Transferable Belief Model for Decision Making in Valuation-Based
Systems, IEEE Transactions on Systems, Man andCybernetics, 1996.
[
Main | Projects
| People | Meeting
| Library ]
Last updated Jan 15, 1996 | Comments
to webmaster