Dear UAIers,
I must thank Russell Almond for adding to my list of
references; I also must note that the SPI algorithm
by Li and D'Ambrosio offered an early insight into
the use of serial elimination (this is referenced in
the paper I mentioned, together with Shenoy and Shafer's
scheme):
Z. Li and B. D'Ambrosio, Efficient inference in Bayes networks
as a combinatorial optimization problem, Int. J. of Approximate
Reasoning, 11, 1994.
In SPI, like in standard variable elimination, the focus
is on inference for a single query. In fact, variable
elimination can be faster for single queries than
the junction tree approach. And Russell is correct that
doing elimination is equivalent to building a triangulated
graph (it is a result in graph theory that an elimination
ordering produces a triangulated graph; I think this is
used in Jensen's 1996 book).
Coupled with the possibility of doing a second pass and
so getting all marginal probabilities, variable elimination
becomes a quite powerful scheme.
Best,
Fabio
On Wed, 4 Apr 2001, Fabio Gagliardi Cozman wrote:
> But it is actually possible to derive a more
> general form of variable elimination, in which a second pass
> generates *all* marginal probabilities. The complexity is
> similar to usual junction tree algorithms, and the result
> is essentially the same. The bonus is that operations are much
> easier to understand, without any mention to triangulation
> and other graph-theoretic techniques. The result is similar
> to a tree propagation algorithm, but in a tree of clusters.
>
> The more general variable elimination is presented at
>
> Fabio G. Cozman, Generalizing Variable Elimination in
> Bayesian Networks, Workshop on Probabilistic Reasoning in
> Artificial Intelligence, pp. 27-32, Atibaia, Brazil, 2000.
>
> (get this paper from
> http://www.cs.cmu.edu/~javabayes/Download/jb-heading.ps.gz)
>
> This general variable elimination scheme is implemented
> in the JavaBayes system (a system for manipulation of
> Bayesian networks available at http://www.cs.cmu.edu/~javabayes).
> Because JavaBayes is distributed under the GNU license,
> the source code is available and you can read the
> implementation of the general variable elimination
> scheme.
This archive was generated by hypermail 2b29 : Thu Apr 05 2001 - 10:44:27 PDT