RPDAGs

Programs dealing with Restricted Acyclic Partially Directed Graphs (RPDAGs) [Acid de CamposAcid de Campos2003] are in bns/rpdags since they share a lot of code with BNs. RPDAGs are a compromise between BNs and their equivalence classes. While learning, one ideally will like to learn in the space of equivalence classes since they represent a set of BNs whose structure explains the data equally well. However, it is computationally more expensive to move around in the space of equivalence classes. In response, Acid2003 have proposed RPDAGs. They have the property that many BNs from a single class map to a single RPDAG. It is though also the case, that more than one RPDAGs may map to a single equivalence class. Computationally, RPDAGs are harder to construct than BNs, but easier than Markov equivalence classes.

The SLP generator of all RPDAGs can be found in rpdags/rpdag.slp while a Prolog version can be found in rpdag.pl. These are based on the additive operations presented in [Acid de CamposAcid de Campos2003, p.467,Table 2]. The number of RPDAGs according to our programs are shown in Table 2. Also in the table are shown the number of BNs, second row, and number of equivalence classes, in the last row. These are taken from [Gillispie PerlmanGillispie Perlman2001]

Table 2: Number of RPDAGs in relation to BNs and equivalence classes.

Nodes	1	2	3	4	5	6	7
BNs	1	3	25	543	29281	3781518	1138762420
RPDAGs	1	2	13	258	13521	1713008	496236097
Eq.Class	1	2	11	185	8782	1067825	312510571

Postscript files detailing all RPDAGs for three and four nodes can be found in directories rpdags/doc/three.ps.gz and rpdags/doc/four.ps.gz respectively.

The likelihood used is an extension of the likelihood used in the case of BNs. Similarly, RPDAGs are displayed with the same routines as BNs. These have been extended to display unidirectional arcs as links of black colour. To create a small Markov chain you can use query ?- run_test. defined in file run_test.pl. To visualise the models while creating the same chain use ?- run_disp. from file run_disp.pl.

RPDAGs are represented by terms of the form: rpdag(Nodes,Dag,BiD). $Nodes$ is a list of nodes to node information; a triplet containing the children the parents and the neighbours of the node. Neighbours are connected by bidirectional links. $Dag$ is the Directed Acyclic Graph representing the directed part of the RPDAG. $BiD$ is the graph containing the bidirectional links of the RPDAG. Both $Dag$ and $BiD$ are manipulated using the Prolog ugraph library.