Dear Kevin:
On Fri, 7 Apr 2000, Kevin Murphy wrote:
> You can use the variable elimination algorithm (pushing sums inside
> products) to compute a marginal on any *single* set of nodes in one pass
> over the network. (Choosing an optimal summation ordering is NP-hard.)
Mark Bloemeke showed how to extend the variable elimination algorithm to
compute all marginals on single variables as well as the marginal on one
single set of nodes. For details, see:
Bloemeke, M. and M. Valtorta. "A Hybrid Algorithm to Compute Marginal and
Joint Beliefs in Bayesian Networks and Its Complexity." UAI-98, pp.16-23.
Mark Bloemeke 's Ph.D. dissertation also includes an extension (using
something called "multiply headed factor trees") to the computation of
multiple joints. As far as I know, this has not yet been published
outside the dissertation. This thread tells me that it should be!
(Mark, are you listening? :-)
>
> % For details, see
> % - R. Dechter, "Bucket Elimination: A Unifying Framework for
> Probabilistic Inference", UA1 96, pp. 211-219.
> % - Z. Li and B. D'Ambrosio, "Efficient inference in Bayes networks as a
> combinatorial
> % optimization problem", Intl. J. Approximate Reasoning,
> 11(1):55-81, 1994
> % - R. McEliece and S. M. Aji, "The Generalized Distributive Law", IEEE
> Trans. Inform. Theory, to appear
>
> HTH,
> Kevin
>
>
Cheers,
Marco
Marco Valtorta, Associate Professor (on sabbatical leave in 1999/2000)
Department of Computer Science mgv@usceast.cs.sc.edu, mgv@cs.auc.dk (March)
University of South Carolina tel.: (1)(803)777-4641 fax: -3767
Columbia, SC 29208, U.S.A. http://www.cs.sc.edu/~mgv/ tlx: 805038 USC
- ---------------------------------------------------------------------------
"Probability is not about numbers. It is about the structure of reasoning."
--Glenn Shafer
- ---------------------------------------------------------------------------
------- End of Forwarded Message
This archive was generated by hypermail 2b29 : Fri Apr 07 2000 - 11:32:05 PDT