Hi again,
Yeah, I realize now that my original answer was not correct, and I see why
your question is not trivial.
You have two reasons a dag might not be a perfect map: either the Markov
condition is violated or faithfulness is violated. The Markov condition is
guaranteed by the syntax of a Bayesian network. However, by making sure
each column in the CPT is different for each node N you guarantee that N
will be truly dependent on its parents, but you still do not guarantee that
all nodes d-connected to N will satisfy a corresponding conditional
dependence test. That is, you are only guaranteeing local faithfulness, not
global faithfulness.
I'm not sure how to insure global faithfulness without exhaustively checking
all conditional dependencies.
However, I do think the probability of violating faithfulness is very
small (of course this must depend on how you sample the parameters of the
network, but for a uniform random sampling the probability I believe is 0).
Anyway, sorry for responding without thinking it out carefully.
Denver.
----- Original Message -----
From: "Xiangdong An" <xdan@cis.uoguelph.ca>
To: "Denver Dash" <ddash@sis.pitt.edu>
Cc: <uai@cs.orst.edu>
Sent: Wednesday, September 26, 2001 5:49 PM
Subject: generate a random JPD along its p-map DAG
> Hi Denver,
>
> Thanks for your reply.
> My intention is the first of your interpretation.
>
> So by that way, we can generate a random JPD along a perfect
> map DAG D. That is, if a JPD can be generated by generating
> a set of conditional probability distributions {P(Xi|II(Xi))}
> (II(Xi) are parents of Xi in a DAG D on an ordering X1,X2,...,Xn)
> such that II(Xi) is the minimum set of predecessors satisfying
> P(Xi|II(Xi))=P(Xi|X1,...,Xi-1), then the DAG D is a perfect map
> of the JPD. I think this saying is equivalent to your statement
> in (1).
>
> My question is, we know for a JPD, there is no guarantee that
> a DAG exists to be its perfect map. I want to know what properties
> make such generated JPD to have the DAG to be its perfect map?
> i.e. What makes the JPD read off the DAG special from a randomly
> given JPD which may not have a perfect map DAG?
>
> Xiangdong
>
> On Wed, 26 Sep 2001, Denver Dash wrote:
>
> > I can think of at least two ways to interpret what you are trying to do,
> > here is the answer for all three interpretations:
> >
> > (1) I want to generate a random JPD along with its perfect map D.
> > To do this, it is sufficient to construct a random dag and randomly set
the
> > parameters so that no two columns in a given table are identical. The
dag
> > will be a perfect map to the JPD generated by the network.
> >
> > (2) Given a JPD I want to construct its perfect map D.
> > As far as I know, the only way to do this is to query the JPD for
> > independence relations along the lines of a constraint-based learning
> > algorithm, for example the PC algorithm (given in the book "Causation,
> > Prediction and Search", Spirtes, Glymour and Scheines), or Pearl and
Verma's
> > algorithm (http://citeseer.nj.nec.com/pearl91theory.html).
> >
> > Hope this helps,
> > Denver.
> > ----
> > Denver Dash http://www.sis.pitt.edu/~ddash
>
This archive was generated by hypermail 2b29 : Thu Sep 27 2001 - 05:44:05 PDT