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.
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