[UAI] Tool to generate random Bayesian networks

From: Fabio Gagliardi Cozman (fgcozman@usp.br)
Date: Fri Jul 05 2002 - 11:03:09 PDT

  • Next message: iberamia@lsi.us.es: "[UAI] IBERAMIA'2002 - Workshop on Multi-Agent Systems"

    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
                    



    This archive was generated by hypermail 2b29 : Fri Jul 05 2002 - 11:03:28 PDT