Dear UAIers,
a few days ago I posted a question on how to generate
Bayesian networks randomly, and received several
interesting answers. Here is a summary of them,
after the original mail. There are several interesting
ideas and references.
Fabio
From: Fabio Gagliardi Cozman <fgcozman@usp.br>
I would appreciate if anyone could give some pointers
on how to generate Bayesian networks randomly. That is,
how to construct directed acyclic graphs and their
associated parameters in a way that uniformly samples
the space of the DAGs? I have not found a simple explanation
on how to do it, even though many papers refer to networks
that have been generated randomly. I wonder if there is
software available for this.
Two relevant pointers:
Y. Xiang and T. Miller, A Well-Behaved Algorithm for Simulating Dependence
Structures of Bayesian Networks, International Journal of Applied
Mathematics, Vol.1, No.8, 923-932, 1999 (available at
http://snowhite.cis.uoguelph.ca/faculty_info/yxiang/).
G. Kleiter, The posterior probability of Bayes nets with stong
dependences, Soft Computing, 3, 1999, 162-173, p. 168 (random
permutations in a first step, using algorithm described in Nijenhis,
A. and Wolf, H.S. Combinatorial Algorithms, Academic Press, 1978; arcs
are switched on and off with given probability in a second step).
From: Bruce D'Ambrosio <dambrosi@cs.orst.edu>
Don't know about distributions, but two standard ways of generating
topologies are adding random arcs to an empty net and deleting random
arcs from a fully connected net, either method proceeding untill some
metric (avg # of arcs per node, for example) is reached. These two
methods generate graphs with rather different computational properties
(e.g., clique size), in my experience.
On distributions, Marek Druzdel had some interesting work a few years
back in UAI on expected distribution "peakedness" that might be
relevant.
From: Rina Dechter <dechter@ics.uci.edu>
We have a random generator that we use. It does not uniformly sample
the space of DAGs. It takes certain parameters and generate randomly
for that set of parameters. I think we can provide you with the
code. Actually we are working on a tool that allows anybody to
experiment with our algorithms and on randomly generated networks.
From: Jon Williamson <jon.williamson@kcl.ac.uk>
I've got a paper "random probability functions" which deals with
generating random Bayesian nets. It's available from my web page
below. However I don't sample the space of dags uniformly (I prefer
distributions which favour mediumly dense graphs). As far as I know
it's not easy to do this efficiently. One can do it though by
generating a random directed graph (by generating the binary values in
an adjacency matrix uniformly at random) and rejecting any cyclic
graphs. Likewise, one can generate conditional probabilities p(ai|b)
uniformly at random, by generating them uniformly at random in [0,1]
and rejecting any tuples which don't sum to 1. Neither of these
methods are ideal, and I'd be grateful if you forward any better
answers to me! http://www.kcl.ac.uk/jw
From: Kevin Murphy <murphyk@cs.berkeley.edu>
I randomly generate an NxN boolean adjacency matrix, and reject it if it
is acyclic. I'm not sure if this is equivalent to sampling uniformly
from the space of DAGs, but it seems to be.
From: Eugene Santos <eugene@mailsrv.engr.uconn.edu>
While I have never formally proven that the generation technique
I use (described below) does indeed sample the space of probability
distributions uniformly, I have been modifying it over the years as
I determine/realize problems with the generation scheme. On a side
note, I have moved away from trying to uniformly sample to trying to
mimic "features" found in real-world BNs. But then, my goal has been to
develop reasoning algorithms and "predict" how well they would work
in the real-world. However, I do see a need for the uniform sampling
especially if one is trying to find BN models to match data.
Okay, enough rambling. Here is my approach:
Assume you have n random variables.
(1) Randomly shuffle the rvs into A_1, A_2, ..., A_n
This will now be my target topological ordering on the nodes.
(2) Randomly choose a number of edges from 0 to the maximal number of
edges
that can be formed with the topological ordering above. Let this
number be e.
(3) Now, randomly select two nodes B_1 and B_2 such that B_1 is earlier
in the topological ordering than B_2. Place a directed edge from
B_1 to B_2. Do this until e different edges are introduced.
(4) For each A_i, construct the appropriate conditional table by
randomly generating values for the entries and then normalize.
I think that's everthing here.
I suspect that there might be a problem in the 4th step because of the
normalization, but I haven't fully pin-pointed it yet.
Would like to hear your comments on this especially if I've missed
something obvious here.
From: Michael Horsch <horsch@cs.usask.ca>
I've not seen anything approaching a theory about randomly generated
BNs. I have studied random undirected graphs and random binary
constraint satisfaction problems. There is at least a basic
understanding about building them. I think they are a bit simpler
than BNs; nonetheless, for many years, highly respected researchers
used random CSPs that were theoretically flawed, and based their
empirical research on them. It is also understood that random CSPs do
not really contain the kinds of structure that real-world problems
typically have. I can send you some pointers, though it is not clear
how these will help you sample BNs uniformly. Boiled down to one word
about uniform random CSPs: "Don't." I believe that the message
carries over to BNs, but that's no great insight. One would have to
know how to build uniform random BNs in order to show how bad the
resulting BNs might be.
From: Haipeng Guo <hpguo@cis.ksu.edu>
This is a very interesting problem. But I think you don't really want to
have a BBN generator which can generate networks really "randomly" because
the space of DAGs is infinite and it's impossible(and useless) to deal
with networks with extreme parameters. In real world applications we only
deal with "nomal" networks. The space of "real world" networks is just a
small subset of all networks. So instead of making a random BBN generator,
I suggest making a "real world" network generator. You can try to collect
all kinds of BBNs you can get, and sample from these real world BBN
samples in a random way. Thus you will get a random "real world" network
generator. It dosen't sample the space of the DAGs uniformly. Instead it
samples the space of "real world DAGs" uniformly.
From: DENVER H DASH <dhdst+@pitt.edu>
I think you need to distinguish between sampling the space of DAGs (for a
fixed number of nodes) from sampling the space of probability
distributions over the nodes. I don't think that sampling the former
uniformly will necessarily sample the latter uniformly.
The algorithm that I use to sample the space of DAGs for a fixed number of
nodes is as follows:
(1) Generate a random ordering over the nodes
(2) Generate a lower-triangular structure matrix of 0's and 1's.
If you can sample the ordering from a uniform distribution, I believe this
should sample the space of DAGs from a uniform distribution, although
admittedly I have never sought a proof of this.
(1) can be achieved by randomly shuffling an ordering sufficiently many
times. There is a C++ standard function called random_shuffle that
purports to do this. Again, by symmetry I believe this should sample from
a uniform distribution, but I haven't sought a proof.
From: robert castelo <roberto@cs.uu.nl>
Probably a good point to start with is generating dags randomly:
G. Melancon, I. Dutour and M. Bousquet-Melou
Random generation of dags for graph drawing.
Technical Report INS-R0005 February, 2000.
Dutch Research Center for Mathematics and Computer Science (CWI).
ISSN 1386-3681
http://www.cwi.nl/ftp/CWIreports/INS/INS-R0005.ps.Z
They are generated by constructing a Markov chain, so by
limiting the number of parents during the process, you can
probably obtain dags that resemble those used as Bayesian
Networks from real-world domains.
Once you get your dag at random, you can generate your cpt's
for each variable separately (because of global independence)
and in the way you prefer.
From: Nir Friedman <nir@cs.huji.ac.il>
Sampling a random network topology is indeed non-trivial. This really
depends on the distribution over network. The uniform distribution
over DAGs will consist mostly of very dense networks (average in
degree around n/2) which is usually not what you want. If you have a
fixed ordering in mind, then you can sample along the ordering,
selecting each family independently of the previous one. Such an
approach can then incorporated with a prior on in degree to generate
networks of specific characteristic. If you don't want to assume a
priori order you have to be careful to ensure DAGness does not screw
up your sampling distribution. Regarding parameters. You can define
Dirichlet prior and sample from it. To sample from a Dirichlet prior
over k outcome with prior \alpha_1, \ldots, \alpha_k, you need to
sample k Gamma distributions , Gamma(\alpha_1), \ldots,
\Gamma(\alpha_k) and then to normalize. The procedure to sample from a
Gamma distribution is described in a book "Stochastic Simulation" by
Ripley (p.90). The special case in which \alpha_i = 1 is very simple
to implement --- simple sample a uniform value u in [0,1] and return
-log(u). Thus, to sample from a uniform Dirichlet, you sample n
uniform values, take their -logs and then normalize.
From: Jaap Suermondt <suermondt@hpl.hp.com>
I once (in 1987) wrote some code that generates more or less (no
guarantees) random networks. At the time, I was interested in inference
on bipartite graphs (such as QMR-DT) so it has a mode where that can be
done. The problem is indeed hard; there are issues as to what you are
randomizing given the parameters you are specifying. There are also
secondary issues as to whether truly random graphs are actually
representative of the space of belief networks (which are usually
generated by a decidedly nonrandom process).
What we did is the following:
- specify how many nodes you want
- specify either a degree of connectivity or a number of arcs (from 0 to
n*(n-1) )
- specify whether you care whether the network remains connected (i.e.,
there is a path between any two nodes)
- generate a fully connected graph (this is the maximal possible DAG of
n nodes)
- randomly remove arcs until the desired connectivity is accomplished
As far as the number of values of each node and the probabilities, I did
this on a node-by-node basis, depending on what I was interested in.
I.e., specify a discrete distribution from which you want each to be
sampled -- that is not the hardest part. The random graph structure was
the hardest for me.
This seemed to work pretty well, and we used it on lots of experiments.
I am not aware of other random net generators out there; people reused
this for quite some time, back in the days when we were just getting the
first implementations of cutset conditioning, lauritzen-spiegelhalter,
and the like.
From: "KOZLOV,ALEX (HP-PaloAlto,ex1)" <alex_kozlov@hp.com>
I used a program by Jaap Suermondt. It constructs a fully connected
graph and then removes edges randomly until a required #edges/#nodes
ratio is met. I am not sure it satisfies the requirement of
"uniformly samples the space of the DAGs", but it does uniformly
sample the space of all edges given the required number of nodes. The
problem with networks generated this way was that the complexity of
network (size of the largest clique) grows dramatically beyond
#edges/#nodes ratio of 2-3. This is not realistic since many other
practical BNs have large #edges/#nodes ratio and still are
computationally manageable. Probabilities in the above program were
generated randomly. Again, this is very far from what we expect in
any practical network.
From: "[iso-8859-2] Tomas Kocka" <TKocka@seznam.cz>
I think that many people generated randomly Bayesian network
structures (i.e. DAGs) and this is fairly simple. You select at
random some ordering of the variables and then at random for each
pair of variables if they will be connected (adjacent) or not. The
ordering of variables gives you the orientation of these adges and
you can be sure that your graph is acyclic. In this way any DAG can
be generated so it is a pretty good method.
Just by the way - I do not believe that randomly generated structures
are very similar to the real world models we can see from experts or
learned from data. One point is, that you will have a very few
equivalent DAGs for your randomly generated DAGs (about 3,7) and real
world models often have much more equivalent DAGs (for example
10^20).
From: Smets Philippe <psmets@ulb.ac.be>
I had that problem once Generating a vector in n dim equi density on n
dim simplex. Generate n-1 rand var(i) on [0,1], i= 1,...n-1, put
var(n) = 1, order var from small to large, compute var(i) - var(i-1) =
x(i) with var(0) = 0. for i = 1...n x is the needed vector. I believe
the algo is OK, it is surely a proba. I am not sure it is really
equidensity. In any case it is better than generating n raandon
numbers in 0,1 and dividing them by their sum. which is not
equidensity at all.
From: Alessandra Potrich <potrich@itc.it>
Concerning the issue of randomly generating Bayes Nets, it may be of
your interest to know that an optimally efficient solution to the
problem of uniformly sampling the set of distribution functions for a
discrete, n-valued random variable is published on the Los Alamos
e-print archive (http://eprints.lanl.gov) as MATH-0011025 (3
Nov. 2000). Also directly accessible at:
http://eprints.lanl.gov/cgi-bin/w3vdkhgw?qryAAA0n_xre;math-0011025
This archive was generated by hypermail 2b29 : Wed Oct 31 2001 - 11:04:00 PST