Delin,
You may want to look at my UAI 2001 paper, which you can
find on my web page (http://www.cs.berkeley.edu/~eyal).
It includes references to (then) previous work on treewidth,
which is closely related to the variable ordering problem.
Briefly, when you're looking for a good variable ordering
you are trying to minimize the size of the largest clique
created when you eliminate variables. The size of the
largest clique in the best ordering that exists is the
"treewidth"+1 of the graph at hand. The problem of finding
the optimal ordering is known to be NP-hard, but there is
an algorithm that gives an order whose largest clique is
within a factor of O(log OPT) from the treewidth of the
graph, where OPT is that treewidth (this is one of the things
reported in the paper above). Unfortunately, the
constant factor in this O(...) is quite large (I think I
can bring it down to ~50 with better analysis than the
one reported in my paper, but this is still too large to
be of real use), so people use a very-good-in-practice
heuristic called "min-fill", which is quite old (I think it
is from the 70's) and is described in the above paper as well.
There are known bad cases for it (O(sqrt(n)) from the optimal),
but I didn't encounter many practical cases where it fails.
You can also download the software associated with the paper
above from my web page (a subdirectory at Stanford):
http://www-formal.stanford.edu/eyal/decomp
The above algorithm is implemented using hMETIS instead of
the real subroutine, but min-fill and others are implemented
there as well, so you can use that to compate. The input is
not very standard, but the package includes a utility that
translated BN format into this one (I should embed this
conversion into the actual executable sometime soon).
Hope that helps. If you need further help, let me know.
Eyal
----- Original Message -----
From: Delin Shen <[EMAIL PROTECTED]>
Date: Friday, July 11, 2003 3:22 pm
Subject: [UAI] asking about Bayesian Network searching order
> Hi,
>
> I'm a graduate student at MIT, and just started using Bayesian
> Network. I
> understand that the order of the variables is important to the
> performance
> of the result. I found some publications about using genetic
> algorithms
> tuning the searching orders, but could anybody point me to a good
> review or
> paper of recent research on dealing with this ordering problem?
>
> Thanks!
>
> Delin
