Dear UAIers,
several months ago I posed the question "How to
generate random Bayesian networks?" to the list
and got several interesting answers. I was
interested in uniformly distributed random networks,
such that tests with algorithms would not be "biased"
in any way. It seems clear that it is not enough
to sample the space of all directed acyclic graphs,
but rather to look at the space of sparsely connected
graphs. Here "sparsely connected" might mean graphs with
small number of arcs, or graphs where nodes have low
degree. The problem is, it is very hard even to
characterize the space of directed acyclic graphs under
such constraints, let alone to sample uniformly from that
space.
After some thinking, it seemed that the approach used
by G. Melancon and M. Bousque-Melou to generate random
graphs was the best (thanks to R. Castelo for mentioning
that work). They use Markov chains to sample the space
of directed acyclic graphs; however they let the graphs
become disconnected and they did not consider sampling
from the class of polytrees (in fact, I'm not aware of
any current method that can generate polytrees randomly).
I have worked with a collaborator, Jaime Ide, on extending
the ideas of Melancon and Bousque-Melou to Bayesian
networks. We have produced software that can quickly
generate uniformly distributed random networks, both
multi- or singly-connected. The user can input a limitation
on node degree, so as to make the graph sparse. After a
graph is generated, conditional distributions are
generated by sampling from Dirichlet distributions
(thanks to N. Friedman for suggesting this). From our tests,
I think the graphs do look like Bayesian networks, but
I would welcome any comments.
There is a paper that explains the Markov chain method
and that describes the algorithms and the software.
The software is distributed under the GNU license and
saves networks in the XMLBIF format that is used in
the Bayesian network repository and also in some of the
Bayesian network tools in the net. Everything can be found
at the site:
http://www.pmr.poli.usp.br/ltd/Software/BNGenerator/
The paper is (there is postscript in the web site):
Jaime Shinsuke Ide, Fabio Gagliardi Cozman.
Generating random Bayesian networks, Brazilian Symposium on
Artificial Intelligence, Recife, Pernambuco, Brazil, 2002.
We are currently extending the software to accommodate other
constraints, so as to be able to uniformly generate networks
that have the properties of "practical" networks. It would
be nice to reach some common methodology to test Bayesian
network algorithms; right now many papers mention "random"
networks, but it is hard to guarantee anything about results.
I hope this tool is useful. As I said, any comments are
appreciated, let us know if you find any bugs.
Best,
Fabio Cozman
