Fabio Gagliardi Cozman wrote:
>
> The easiest inference algorithm to understand/teach is (in my
> opinion, anyway) the variable elimination algorithm, also called
> bucket elimination --- the problem with variable elimination is
> that it does not generate marginal probabilities for all variables
> in a network, just for a query variable.
[snip]
> PS: Variable elimination uses a simple idea, already mentioned
> in the peeling algorithms by Cannings, Thompson and Skolnick;
> the idea is also mentioned in the 1988
> paper by Lauritzen and Spiegelhalter. The idea resurfaced in 1996
> in two papers, one by Zhang and Poole (used "variable elimination")
> and another by Decther (used "bucket elimination"). There have
> been efforts to derive inference algorithms that use junction trees
> without the triangulation step (I know of results obtained by
> Draper and by Darwiche), but the general variable elimination
> scheme seems simpler and more direct. The papers
> containing these results are:
A key reference missing from this list is
{Bertel\`e, U. and F. Brioschi [1972]}
{\it Nonserial Dynamic Programming.\/} Academic Press.
They call the algorithm "Serial Elimination" and use it to solve utility
maximization problems. But if you use the general "Valuation" framework
of Shenoy and Shafer, this is essentially the same problem. The book is
particularly good at giving a lot of heuristics and optimization tricks
for picking elmination orderings (the NP-Hard part of the calculation
step). Augustine Kong and I were doing some research on optimal
elimination orderings which we gave up when we realized all of our
results were in this book.
I did eventually publish a summary of our findings in my book (Almond,
R.G. [1995], _Graphical Belief Modeling_, Chapman and Hall). The key
insight was Augie's, that picking an optimal elimination ordering for a
variable elimination is the same problem as computing the optimal
fill-ins for a junction tree. Thus, I can't agree more that without
understanding the variable elimination approach, you can't get an
efficient implementation of the junction tree algorithm.
> On Tue, 3 Apr 2001, Briggs, Will wrote:
> > Is there an algorithm that would handle any belief net?
> > Has anyone written it down or implemented it?
> > I had thought of using the one Russell & Norvig presents for polytrees, on
> > nets that _aren't_ polytrees. (I do realize this will give the wrong
> > answer, but hope we can tweak it to fix the problem.)
Variable elimination will work well for the same class of problems that
junction trees work well on. That is, it is possible to find networks
for which almost any elimination ordering produces huge cliques in the
filled-in graph. (The fill-ins come from connecting the neighbors of
the eliminated node at each step). This represents a huge computational
cost. There are known problems in genetics for which peeling will not
work.
The other general pupose approach is to try to set up a MCMC simulation
from the distribution represented by the graph (after entering data).
This is usually pretty simple because the Markov properties of the graph
can be exploited. This does not require any explicit (junction tree) or
implicit (variable elimination) fill-ins so the complexity is related to
the complexity of the original graph not the filled-in version.
Unfortunately, convergence in finite time is not guarenteed. There are
also known cases where this algorithm does not work well. For example,
in a pedigree (gentics family tree) it might be known that a certain
individual has a rare recessive gene, but not whether he got it from his
father or mother. Unless great care is taken the chain might not "mix"
from the father's side to the mother's side. I think that this same
problem had some large nasty loops so it was not a candidate for peeling
either.
In summary, TANSTAAFL. Variable elimination algorithms and their close
cousins the junction tree algorithms will handle arbitrary graphs, but
the computational cost might be too high. MCMC techniques will also
work for any size graph, but reaching (and assessing) convergence is a
problem too.
Hope this helps.
--Russell Almond
This archive was generated by hypermail 2b29 : Thu Apr 05 2001 - 10:42:29 PDT