Markov-Equivalent DAGs in BNT

Generating Markov-Equivalent DAGs in BNT

This page describes how to generate Markov-equivalent DAGs in Matlab's Bayes Net Toolbox BNT.

First the supporting files:

You can download all four files using this ZIP-FILE.

pdag_to_all_dags.m -- This is the main function. It finds all DAGs for a partially directed DAG. The algorithm is based on Meek's algorithm [Meek, UAI 95] to find a single DAG given a PDAG (see file for a complete description of the algorithm).

complete_pattern.m -- This function implements Rules 1-4 of [Meek, UAI 95] to complete the orientations of a partially oriented graph as far as possible. This function is used by pdag_to_all_dags, but can also be used as a stand-alone.

Markov_equivalent_dags.m -- Finds all Markov equivalent DAGs for a given DAG. This builds on pdag_to_all_dags.m, but also uses function dag_to_cpdag of the Structure Learning Package (bnt-slp), so you'll need that to run the function.

pdag_unsigned_to_signed.m -- Auxiliary function to convert pdag from one notation to another.

Thanks to Daniel Eaton for extensive testing of these files and detailed bug reports.

Please see the comments at the beginning of each file for a full description of functionality, including input and output parameters.

EXAMPLES:

To generate all DAGs based on a DAG PATTERN, use function pdag_to_all_dags(pdag).

Comments:

You do NOT need the Structure Learning Package to run this function.

pdag does NOT have to be complete, since the algorithm completes the input pattern as a first step.

pdag must have the following format:

To indicate an undirected edge, use pdag(a,b) = 1 pdag(b,a) =1
To indicate a directed edge, use pdag(a,b) = -1 pdag(b,a) =0

Example:

   % Use output of PC algorithm
   dag = mk_rnd_dag(4);   % create random DAG
   % Generate pdag through PC algorithm
   pdag = learn_struct_pdag_pc('dsep', length(dag), 3, dag)
   [n_dags,dag_list] = pdag_to_all_dags(pdag);
   n_dags

To generate all Markov equivalent DAGs for a given DAG, use function Markov_equivalent_dags(dag).

You need to have the BNT Structure Learning Package in place to run this function. In newer versions of BNT that package is already included with BNT.

Example 1:

% Find all DAGs equivalent to DAG of Asia Network
BN = mk_asia_bnet();
dag = BN.dag;
[n_dags, dag_list] = Markov_equivalent_dags(dag);
n_dags         % Answer should be: 6
dag_list{1} % displays the first DAG, etc.

Example 2:

% Find all DAGs equivalent to random DAG
dag = mk_rnd_dag(4);
[n_dags, dag_list] = Markov_equivalent_dags(dag);

Topological sorting of the output:

In all cases above dag_list is a list of DAGs, but that those are generally not topologically sorted. Sorting each DAG topologically is very easy with the existing BNT functions, e.g. you can use something like this:

for i=1:length(dag_list)
   dag = dag_list{i};
   order = topological_sort(dag)
   sorted_dag = dag(order,order);
   % Now do something with it ...
end

Feedback:
Questions or comments? Found a bug?
PLEASE drop me an e-mail with any comments you may have!
Imme Ebert-Uphoff

Return to main page: www.DataOnStage.com

Page last updated: November 2011