1
$\begingroup$

As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem.

In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to find minimum number of variable that Xi independent from other variables. at least, how many variable we need?

i think, we use Markov Blanket for this problem. any solution for this problem?

Regards.

||cite|improve this question
$\endgroup$
1
$\begingroup$

In a Bayesian network, a variable is independent from all the variables given its Markov blanket (except of course the variables in the Markov blanket).

However, the Markov blanket is not the minimal set that renders two variables independent.

Also note that a variable may be independent of some variables in the Markov blanket, given another set of variables (think about the case of a spouse in the network).

By the way, I think that this problem has been solved already (if you refer to the problem of identifying the minimal set that renders two variables independent).

Edit: Check this out: http://www.cs.iastate.edu/~jtian/r254_min_separator.pdf They show how to find a minimal d-separating set in a given Bayesian network.

||cite|improve this answer
$\endgroup$
  • $\begingroup$ you means it's not related to markov blanket? $\endgroup$ – user3661613 Jun 10 '14 at 20:25
  • $\begingroup$ i think my answer is P+PQ. your answer not related to my question $\endgroup$ – user3661613 Jun 10 '14 at 20:29
  • 1
    $\begingroup$ How is it not related? Unless you are not asking for a minimal separating set, I think I exactly answer your question. If not, I would suggest you rephrase your question. $\endgroup$ – George Jun 10 '14 at 21:11
  • $\begingroup$ my answer: we have P+Q parents and child for any xi. one node (xi) will be removed from parents so children parents (P-1)Q we have (P-1)Q+P+Q=P+PQ. what's your idea? $\endgroup$ – user3661613 Jun 10 '14 at 21:17
  • 1
    $\begingroup$ P and Q are numbers? If so, not every variable can have P and Q parents/children (since it's a DAG). Assuming that this condition holds for all nodes except for roots and leafs, then the size of the Markov blanket for a non-leaf/non-root variable is at most: P + Q + Q*(P-1) = P + PQ as you wrote. I say at most, as some children may share some common parents. $\endgroup$ – George Jun 10 '14 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.