Let me add two remarks to the series of comments about join tree
propagation, variable elimination, bucket elimination, etc.
First, an important paper has not been mentioned so far:
>Prakash P. Shenoy, "Binary Join Trees for Computing Marginals in the
>Shenoy-Shafer Architecture," International Journal of Approximate
>Reasoning, Vol. 17, Nos. 2--3, 1997, pp. 239--263.
Section 4 proposes the so-called "Fusion Algorithm" with a one-to-one
correspondance to variable elimination. Section 5 described then
clearly the relationship between fusion and join tree propagation.
Surprisingly, this work has not received much attention in terms of
related papers that refer to it, although, as much as I know, it's
the first description of variable elimination in a general setting.
Second, there is a further alternative that has not been mentioned so
far. Instead of doing inward propagation (or fusion, bucket
eliminaiton, etc. for individual marginals) and inward/outward
propagation (for all marginals of the join tree), it is also possible
to
1) do the usual inward propagation towards an empty node
2) add the query (event, hypothesis, or whatever) in a particular
way to a corresponding node in the join tree, and then do a PARTIAL
inward propagation.
Phase 1) can be considered as compilation, while in phase 2),
arbitrary queries are answered.
This method has several advantages, e.g. if the query is a logical OR
over several variables, then it still works, even if there is no node
in the tree that contains all the variables involved.
This procedure works for
- - Bayesian networks:
>R. Haenni and J. Kohlas and N. Lehmann. Computing Probabilities of
>Events in Bayesian Networks. Pages 1307--1312 of: IPMU'00,
>Proceedings of the 8th international conference, Madrid, Spain. .
>2000.
- - Dempster-Shafer belief functions:
>N. Lehmann and R. Haenni. An Alternative to Outward Propagation for
>Dempster-Shafer Belief Functions. Pages 256--267 of: A. Hunter and
>S. Parsons (eds.), European Conf. ECSQARU'99, London. Springer.
>Lecture Notes in Artif. Intell. 1999.
- - Probabilistic Argumentation Systems:
>R. Haenni and J. Kohlas and N. Lehmann. Probabilistic Argumentation
>Systems. J. Kohlas and S. Moral (eds.), Handbook of Defeasible
>Reasoning and Uncertainty Management Systems, Volume 5: Algorithms
>for Uncertainty and Defeasible Reasoning. Kluwer, Dordrecht. 2000.
Best regards,
Rolf Haenni
- --
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/ /\
\/ Dr. Rolf Haenni /\
\/ 4531L Boelter Hall /\
\/ Computer Science Department /\
\/ University of California /\
\/ Los Angeles, CA 90095 /\
\/ Office: (310) 267 7508 /\
\/ Private: (310) 267 4713 /\
\/ Email: rolf.haenni@gmx.net /\
\/ /\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
This archive was generated by hypermail 2b29 : Mon Apr 09 2001 - 14:49:46 PDT